mirror of
https://github.com/boostorg/multi_index.git
synced 2025-05-09 23:14:04 +00:00
47b172ab68
allocator_utilities.hpp: added partial_std_allocator_wrapper::value_type
composite_key.hpp: used hash_fwd.hpp
auto_space.hpp: added support for non-standard allocators
bidir_node_iterator.hpp: moved friend-injected operators out of class
copy_map.hpp: added support for non-standard allocators
hash_index_args.hpp: removed deprecated use of <boost/functional/hash/hash.hpp>
hash_index_iterator.hpp: moved friend-injected operators our of class
hash_index_node.hpp: added support for non-standard allocators
header_holder.hpp:added support for non-standard allocators
index_base.hpp: added support for non-standard allocators, added modify_rollback, added small improvement to modify
index_loader.hpp: added support for non-standard allocators
index_matcher.hpp: added support for non-standard allocators
index_node_base.hpp: added support for non-standard allocators
iter_adaptor.hpp: added some out-of-class operators to alleviate a MSVC++ 6.0 problem
modify_key_adaptor.hpp: renamed some vars to accomudate broader usage scope
node_type.hpp: added support for non-standard allocators
ord_index_node.hpp: added support for non-standard allocators
ord_index_ops.hpp: implemented a more efficient equal_range
rnd_index_loader.hpp: added support for non-standard allocators
rnd_index_node.hpp: added support for non-standard allocators
rnd_index_ops.hpp: added support for non-standard allocators
rnd_index_ptr_array.hpp: added support for non-standard allocators
rnd_node_iterator.hpp: moved friend-injected operators out of class
seq_index_node.hpp: added support for non-standard allocators
seq_index_ops.hpp: added support for non-standard allocators
uintptr_type.hpp: added support for __int64
unbounded.hpp: fixed ODR problem
value_compare.hpp: fixed a small unefficiency
global_fun: initial commit
hashed_index.hpp: added support for non-standard allocators, added c[r]{begin|end}, [local_]iterator_to, rollback modify
identity_fwd.hpp: fixed wrong include guard name
key_extractors.hpp: added global_fun
mem_fun.hpp: removed superfluous =0's
ordered_index.hpp: added support for non-standard allocators, added c[r]{begin|end}, iterator_to, rollback modify, improved equal_range and range, added conformance to DR 233
random_access_index.hpp: added support for non-standard allocators, added c[r]{begin|end}, iterator_to, rollback modify, added conformance to 23.1.1/9
sequenced_index.hpp: added support for non-standard allocators, added c[r]{begin|end}, iterator_to, rollback modify, added conformance to 23.1.1/9, improved resize
multi_index_container.hpp: added support for non-standard allocators, improved ctor_args_list, rollback modify
acknowledgements.html: added entry for Boost 1.35
examples.html: renamed example 2, added B.IP example/composite_keys.cpp
future_work.html: removed entry on bimap
hash_indices.html: added c[r]{begin|end}, [local_]iterator_to, rollback modify
reference/index.html: added global_fun
reference/key_extraction.html: added global_fun, added technical correction
multi_index_container.html: added support for non-standard allocators
ord_indices.html: added c[r]{begin|end}, iterator_to, rollback modify
rnd_indices.html: added c[r]{begin|end}, iterator_to, rollback modify
seq_indices.html: added c[r]{begin|end}, iterator_to, rollback modify
release_notes.html: added entry for Boost 1.35
tests.html: added new serialization test file
basics.html: added rollback modify
creation.html: added support for non-standard allocators
tutorial/indices.html: added iterator_to
tutorial/key_extraction.html: added global_fun
composite_keys.cpp: fixed technicality
fun_key.cpp: was memfun_key.cpp, added global_fun
ip_allocator.cpp: initial commit
example/Jamfile.v2: renamed memfun_key, added ip_allocator
test_perf.cpp: fixed technicality
employee.hpp: used a non-standard allocator
test/Jamfile.v2: added new test file
non_std_allocator.hpp: initial commit
pair_of_ints.hpp: added decrement facilities
test_capacity.cpp: added extra check on resize
test_copy_assignment.cpp: added test for 23.1.1/9
test_iterators.cpp: added tests for c[r]{begin|end} and [local_]iterator_to, fixed technicality
test_key_extractors.cpp: added tests for global_fun
test_modifiers.cpp: added tests dor DR 233, fixed technicality
test_range.cpp: added extra checks to secure range refactoring
test_rearrange.cpp: fixed technicality
test_serialization.cpp: added new test file
test_serialization1.cpp: corrected include, used a non-standard allocator
test_serialization2.cpp: corrected include, used a non-standard allocator, split some stuff ro test_serialization3.cpp
test_serialization3.cpp: initial commit
test_serialization3.hpp: initial commit
test_serialization_template.hpp: removed some reliance on ADL
test_update.cpp: addes tests for rollback modify, fixed technicality
[SVN r39922]
240 lines
12 KiB
HTML
240 lines
12 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
|
|
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
|
|
<title>Boost.MultiIndex Documentation - Future work</title>
|
|
<link rel="stylesheet" href="style.css" type="text/css">
|
|
<link rel="start" href="index.html">
|
|
<link rel="prev" href="tests.html">
|
|
<link rel="up" href="index.html">
|
|
<link rel="next" href="release_notes.html">
|
|
</head>
|
|
|
|
<body>
|
|
<h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align=
|
|
"middle" width="277" height="86">Boost.MultiIndex Future work</h1>
|
|
|
|
<div class="prev_link"><a href="tests.html"><img src="prev.gif" alt="tests" border="0"><br>
|
|
Tests
|
|
</a></div>
|
|
<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
|
|
Index
|
|
</a></div>
|
|
<div class="next_link"><a href="release_notes.html"><img src="next.gif" alt="release notes" border="0"><br>
|
|
Release notes
|
|
</a></div><br clear="all" style="clear: all;">
|
|
|
|
<hr>
|
|
|
|
<p>
|
|
A number of new functionalities are considered for inclusion into
|
|
future releases of Boost.MultiIndex. Some of them depend on the
|
|
potential for extensibility of the library, which has been a guiding
|
|
principle driving the current internal design of <code>multi_index_container</code>.
|
|
</p>
|
|
|
|
<h2>Contents</h2>
|
|
|
|
<ul>
|
|
<li><a href="#ranked_indices">Ranked indices</a></li>
|
|
<li><a href="#notifying">Notifying indices</a></li>
|
|
<li><a href="#constraints">Constraints</a></li>
|
|
<li><a href="#user_defined_indices">User-defined indices</a></li>
|
|
<li><a href="#indexed_maps">Indexed maps</a></li>
|
|
<li><a href="#move_semantics">Move semantics</a></li>
|
|
</ul>
|
|
|
|
<h2><a name="ranked_indices">Ranked indices</a></h2>
|
|
|
|
<p>
|
|
Ordered indices are implemented using red-black trees; these trees
|
|
can be augmented with additional information to obtain a type
|
|
of data structure called
|
|
<a href="http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree"><i>order-statistics
|
|
trees</i></a>, allowing for logarithmic search of the <i>n</i>-th element. It
|
|
has been proposed that order-statistics trees be used to devise a new type of
|
|
<i>ranked indices</i> that support <code>operator[]</code> while retaining
|
|
the functionality of ordered indices.
|
|
</p>
|
|
|
|
<h2><a name="notifying">Notifying indices</a></h2>
|
|
|
|
<p>
|
|
<i>Notifying indices</i> can be implemented as decorators over
|
|
preexistent index types, with the added functionality that internal
|
|
events of the index (insertion, erasing, modifying of elements) are
|
|
signalled to an external entity --for instance, by means of the
|
|
<a href="../../../doc/html/signals.html">Boost.Signals</a>
|
|
library. This functionality can have applications for:
|
|
<ol>
|
|
<li>Logging,</li>
|
|
<li>interfacing to GUI-based applications,</li>
|
|
<li>synchronization between separate data structures.</li>
|
|
</ol>
|
|
</p>
|
|
|
|
<p>
|
|
The following is a sketch of a possible realization of notifying
|
|
indices:
|
|
</p>
|
|
|
|
<blockquote><pre>
|
|
<span class=keyword>struct</span> <span class=identifier>insert_log</span>
|
|
<span class=special>{</span>
|
|
<span class=keyword>void</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>int</span> <span class=identifier>x</span><span class=special>)</span>
|
|
<span class=special>{</span>
|
|
<span class=identifier>std</span><span class=special>::</span><span class=identifier>clog</span><span class=special><<</span><span class=string>"insert: "</span><span class=special><<</span><span class=identifier>x</span><span class=special><<</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>endl</span><span class=special>;</span>
|
|
<span class=special>}</span>
|
|
<span class=special>};</span>
|
|
|
|
<span class=keyword>int</span> <span class=identifier>main</span><span class=special>()</span>
|
|
<span class=special>{</span>
|
|
<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
|
|
<span class=keyword>int</span><span class=special>,</span>
|
|
<span class=identifier>indexed_by</span><span class=special><</span>
|
|
<span class=identifier>notifying</span><span class=special><</span><span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>></span> <span class=special>>,</span> <span class=comment>// notifying index</span>
|
|
<span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>></span>
|
|
<span class=special>></span>
|
|
<span class=special>></span> <span class=identifier>indexed_t</span><span class=special>;</span>
|
|
|
|
<span class=identifier>indexed_t</span> <span class=identifier>t</span><span class=special>;</span>
|
|
|
|
<span class=comment>// on_insert is the signal associated to insertions</span>
|
|
<span class=identifier>t</span><span class=special>.</span><span class=identifier>on_insert</span><span class=special>.</span><span class=identifier>connect</span><span class=special>(</span><span class=identifier>insert_log</span><span class=special>());</span>
|
|
|
|
<span class=identifier>t</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=number>0</span><span class=special>);</span>
|
|
<span class=identifier>t</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=number>1</span><span class=special>);</span>
|
|
|
|
<span class=keyword>return</span> <span class=number>0</span><span class=special>;</span>
|
|
<span class=special>}</span>
|
|
|
|
<span class=comment>// output:
|
|
// insert: 0
|
|
// insert: 1</span>
|
|
</pre></blockquote>
|
|
|
|
<h2><a name="constraints">Constraints</a></h2>
|
|
|
|
<p>
|
|
The notifying indices functionality described above exploits a powerful
|
|
design pattern based on <i>index adaptors</i>, decorators over preexistent
|
|
indices which add some functionality or somehow change the semantics of
|
|
the underlying index. This pattern can be used for the implementation
|
|
of <i>constraints</i>, adaptors that restrict the elements accepted by an
|
|
index according to some validation predicate. The following is a possible
|
|
realization of how constraints syntax may look like:
|
|
</p>
|
|
|
|
<blockquote><pre>
|
|
<span class=keyword>struct</span> <span class=identifier>is_even</span>
|
|
<span class=special>{</span>
|
|
<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>int</span> <span class=identifier>x</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>x</span><span class=special>%</span><span class=number>2</span><span class=special>==</span><span class=number>0</span><span class=special>;}</span>
|
|
<span class=special>};</span>
|
|
|
|
<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
|
|
<span class=keyword>int</span><span class=special>,</span>
|
|
<span class=identifier>indexed_by</span><span class=special><</span>
|
|
<span class=identifier>constrained</span><span class=special><</span><span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span><span class=identifier>is_even</span><span class=special>></span>
|
|
<span class=special>></span>
|
|
<span class=special>></span> <span class=identifier>indexed_t</span><span class=special>;</span>
|
|
</pre></blockquote>
|
|
|
|
<h2><a name="user_defined_indices">User-defined indices</a></h2>
|
|
|
|
<p>
|
|
The mechanisms by which Boost.MultiIndex orchestrates the
|
|
operations of the indices held by a <code>multi_index_container</code> are
|
|
simple enough to make them worth documenting so that the (bold)
|
|
user can write implementations for her own indices.
|
|
</p>
|
|
|
|
<h2><a name="indexed_maps">Indexed maps</a></h2>
|
|
|
|
<p>
|
|
<code>multi_index_container</code> is rich enough to provide the basis
|
|
for implementation of <i>indexed maps</i>, i.e. maps which
|
|
can be looked upon several different keys. The motivation for having
|
|
such a container is mainly aesthetic convenience, since it
|
|
would not provide any additional feature to similar constructs
|
|
based directly on <code>multi_index_container</code>.
|
|
</p>
|
|
|
|
<p>
|
|
The main challenge in writing an indexed map lies in the design of a
|
|
reasonable interface that resembles that of <code>std::map</code> as
|
|
much as possible. There seem to be fundamental difficulties in extending
|
|
the syntax of a <code>std::map</code> to multiple keys. For one example,
|
|
consider the situation:
|
|
</p>
|
|
|
|
<blockquote><pre>
|
|
<span class=identifier>indexed_map</span><span class=special><</span><span class=keyword>int</span><span class=special>,</span><span class=identifier>string</span><span class=special>,</span><span class=keyword>double</span><span class=special>></span> <span class=identifier>m</span><span class=special>;</span>
|
|
<span class=comment>// keys are int and string, double is the mapped to value</span>
|
|
|
|
<span class=special>...</span>
|
|
|
|
<span class=identifier>cout</span><span class=special><<</span><span class=identifier>m</span><span class=special>[</span><span class=number>0</span><span class=special>]<<</span><span class=identifier>endl</span><span class=special>;</span> <span class=comment>// OK</span>
|
|
<span class=identifier>cout</span><span class=special><<</span><span class=identifier>m</span><span class=special>[</span><span class=string>"zero"</span><span class=special>]<<</span><span class=identifier>endl</span><span class=special>;</span> <span class=comment>// OK</span>
|
|
<span class=identifier>m</span><span class=special>[</span><span class=number>1</span><span class=special>]=</span><span class=number>1.0</span><span class=special>;</span> <span class=comment>// !!</span>
|
|
</pre></blockquote>
|
|
|
|
<p>
|
|
In the last sentence of the example, the user has no way of
|
|
providing the <code>string</code> key mapping to the same value
|
|
as <code>m[1]</code>. This and similar problems have to be devoted
|
|
a careful study when designing the interface of a potential
|
|
indexed map.
|
|
</p>
|
|
|
|
<h2><a name="move_semantics">Move semantics</a></h2>
|
|
|
|
<p>
|
|
Andrei Alexandrescu introduced a technique for simulating move
|
|
constructors called Mojo (see his article in C/C++ User Journal
|
|
<a href="http://www.cuj.com/documents/s=8246/cujcexp2102alexandr/">
|
|
"Generic<Programming>: Move Constructors"</a>.) Move semantics
|
|
alleviates the computational load involved in the creation and copying
|
|
of temporary objects, specially for heavy classes as
|
|
<code>multi_index_container</code>s are. David Abrahams and Gary Powell provide
|
|
an alternative implementation of move semantics in their paper
|
|
<a href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2004/n1610.html">
|
|
"Clarification of Initialization of Class Objects by rvalues"</a> for
|
|
the C++ Evolution Working Group.
|
|
</p>
|
|
|
|
<p>
|
|
Adding move semantics to <code>multi_index_container</code> is particularly
|
|
beneficial when the container is used as an internal building block in other
|
|
libraries (vg. relational database frameworks), enabling the efficient
|
|
development of functions returning <code>multi_index_container</code>s. Without support
|
|
for move semantics, this scheme is impractical and less elegant syntaxes
|
|
should be resorted to.
|
|
</p>
|
|
|
|
<hr>
|
|
|
|
<div class="prev_link"><a href="tests.html"><img src="prev.gif" alt="tests" border="0"><br>
|
|
Tests
|
|
</a></div>
|
|
<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
|
|
Index
|
|
</a></div>
|
|
<div class="next_link"><a href="release_notes.html"><img src="next.gif" alt="release notes" border="0"><br>
|
|
Release notes
|
|
</a></div><br clear="all" style="clear: all;">
|
|
|
|
<br>
|
|
|
|
<p>Revised July 5th 2007</p>
|
|
|
|
<p>© Copyright 2003-2007 Joaquín M López Muñoz.
|
|
Distributed under the Boost Software
|
|
License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">
|
|
LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
|
|
http://www.boost.org/LICENSE_1_0.txt</a>)
|
|
</p>
|
|
|
|
</body>
|
|
</html>
|