123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399 |
- <!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 - Index reference</title>
- <link rel="stylesheet" href="../style.css" type="text/css">
- <link rel="start" href="../index.html">
- <link rel="prev" href="multi_index_container.html">
- <link rel="up" href="index.html">
- <link rel="next" href="ord_indices.html">
- </head>
- <body>
- <h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
- "middle" width="277" height="86">Boost.MultiIndex Index reference</h1>
- <div class="prev_link"><a href="multi_index_container.html"><img src="../prev.gif" alt="multi_index_container reference" border="0"><br>
- <code>multi_index_container</code> reference
- </a></div>
- <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
- Boost.MultiIndex reference
- </a></div>
- <div class="next_link"><a href="ord_indices.html"><img src="../next.gif" alt="ordered indices" border="0"><br>
- Ordered indices
- </a></div><br clear="all" style="clear: all;">
- <hr>
- <h2>Contents</h2>
- <ul>
- <li><a href="#index_concepts">Index concepts</a></li>
- <li><a href="#complexity_signature">Complexity signature</a></li>
- <li><a href="#index_specification">Index specification</a></li>
- <li><a href="#indexed_by_synopsis">Header
- <code>"boost/multi_index/indexed_by.hpp"</code> synopsis</a>
- <ul>
- <li><a href="#indexed_by">Class template <code>indexed_by</code></a></li>
- </ul>
- </li>
- <li><a href="#tags">Tags</a></li>
- <li><a href="#tag_synopsis">Header
- <code>"boost/multi_index/tag.hpp"</code> synopsis</a>
- <ul>
- <li><a href="#tag">Class template <code>tag</code></a></li>
- </ul>
- </li>
- <li><a href="#index_catalog">Indices provided by Boost.MultiIndex</a>
- <ul>
- <li><a href="#key_based_indices">Key-based indices</a></li>
- <li><a href="#other_indices">Other types</a></li>
- </ul>
- </li>
- <li><a href="#views">Index views</a></li>
- </ul>
- <h2><a name="index_concepts">Index concepts</a></h2>
- <p>
- <code>multi_index_container</code> instantiations comprise one or more indices
- specified at compile time. Each index allows read/write access to the elements
- contained in a definite manner. For instance,
- <a href="ord_indices.html">ordered indices</a>
- provide a set-like interface to the elements, whereas
- <a href="seq_indices.html">sequenced indices</a> mimic the functionality
- of <code>std::list</code>.
- </p>
- <p>
- Indices are not isolated objects, and so cannot be constructed on their
- own. Rather they are embedded into a <code>multi_index_container</code> as specified by
- means of an <a href="#index_specification">index specifier</a>. The name of
- the index class implementation proper is never directly exposed to the user, who
- has only access to the associated index specifier.
- </p>
- <p>
- Insertion and erasing of elements are always performed through the
- appropriate interface of some index of the <code>multi_index_container</code>;
- these operations, however, do have an impact on all other indices as
- well: for instance, insertion through a given index may fail because
- there exists another index which bans the operation in order to preserve
- its invariant (like uniqueness of elements.) This circumstance, rather
- than being an obstacle, yields much of the power of Boost.MultiIndex:
- equivalent constructions based on manual composition of standard
- containers would have to add a fair amount of code in order to
- globally preserve the invariants of each container while guaranteeing
- that all of them are synchronized. The global operations performed
- in a joint manner among the various indices can be reduced to
- six primitives:
- <ul>
- <li>Copying,</li>
- <li>insertion of an element,</li>
- <li>hinted insertion, where a preexisting element is suggested in
- order to improve the efficiency of the operation,</li>
- <li>deletion of an element,</li>
- <li>replacement of the value of an element,
- which may trigger the rearrangement of this element in one or
- more indices, or the banning of the replacement,</li>
- <li>modification of an element, and its subsequent
- rearrangement/banning by the various indices.
- </ul>
- The last two primitives deserve some further explanation: in order to
- guarantee the invariants associated to each index (e.g. some definite
- ordering,) elements of a <code>multi_index_container</code> are not mutable.
- To overcome this restriction, indices expose member functions
- for replacement and modification which allow for the mutation of elements
- in a controlled fashion. Immutability of elements does not significantly
- impact the interfaces of ordered and hashed indices, as they are based upon
- those of associative and unordered associative containers, respectively,
- and these containers
- also have non-mutable elements; but it may come as a surprise when dealing
- with sequenced and random access indices, which are designed upon the functionality provided
- by <code>std::list</code>.
- </p>
- <p>
- These global operations are not directly exposed to the user, but rather
- they are wrapped as appropriate by each index (for instance, ordered indices
- provide a set-like suite of insertion member functions, whereas sequenced
- and random access indices have <code>push_back</code> and <code>push_front</code>
- operations.) Boost.MultiIndex poses no particular conditions on
- the interface of indices, although each index provided satisfy the C++ requirements for
- standard containers to the maximum extent possible within the conceptual framework
- of the library.
- </p>
- <h2><a name="complexity_signature">Complexity signature</a></h2>
- <p>
- Some member functions of an index interface are implemented by
- global primitives from the list above. Complexity of these operations
- thus depends on all indices of a given <code>multi_index_container</code>, not just
- the currently used index.
- </p>
- <p>
- In order to establish complexity estimates, an index is characterized
- by its <i>complexity signature</i>, consisting of the following
- associated functions on the number of elements:
- <ul>
- <li><code>c(n)</code>: copying,
- <li><code>i(n)</code>: insertion,
- <li><code>h(n)</code>: hinted insertion,
- <li><code>d(n)</code>: deletion,
- <li><code>r(n)</code>: replacement,
- <li><code>m(n)</code>: modifying.
- </ul>
- </p>
- Each function yields the complexity estimate of the contribution of the index
- to the corresponding global primitive. Let us consider
- an instantiation of <code>multi_index_container</code>
- with <code>N</code> indices labelled <code>0</code>,...,<code>N-1</code>
- whose complexity signatures are
- (<code>c<sub>i</sub></code>,<code>i<sub>i</sub></code>,<code>h<sub>i</sub></code>,<code>d<sub>i</sub></code>,<code>r<sub>i</sub></code>,<code>m<sub>i</sub></code>);
- the insertion of an element in such a container is then of complexity
- <code>O(i<sub>0</sub>(n)+···+i<sub>N-1</sub>(n))</code> where <code>n</code>
- is the number of elements. To abbreviate notation, we adopt the
- following definitions:
- <ul>
- <li><code>C(n)=c<sub>0</sub>(n)+···+c<sub>N-1</sub>(n)</code>,</li>
- <li><code>I(n)=i<sub>0</sub>(n)+···+i<sub>N-1</sub>(n)</code>,</li>
- <li><code>H(n)=h<sub>0</sub>(n)+···+h<sub>N-1</sub>(n)</code>,</li>
- <li><code>D(n)=d<sub>0</sub>(n)+···+d<sub>N-1</sub>(n)</code>,</li>
- <li><code>R(n)=r<sub>0</sub>(n)+···+r<sub>N-1</sub>(n)</code>,</li>
- <li><code>M(n)=m<sub>0</sub>(n)+···+m<sub>N-1</sub>(n)</code>.</li>
- </ul>
- For instance, consider a <code>multi_index_container</code> with two ordered indices,
- for which <code>i(n)=log(n)</code>, and a sequenced index with <code>i(n)=1</code>
- (constant time insertion). Insertion of an element into this <code>multi_index_container</code>
- is then of complexity
- <blockquote>
- <code>O(I(n))=O(2*log(n)+1)=O(log(n))</code>.
- </blockquote>
- </p>
- <h2><a name="index_specification">Index specification</a></h2>
- <p>
- Index specifiers are passed as instantiation arguments to
- <code>multi_index_container</code> and provide the information needed to incorporate
- the corresponding indices. Future releases of Boost.MultiIndex may allow for
- specification of user-defined indices. Meanwhile, the requirements for an index
- specifier remain implementation defined. Currently, Boost.MultiIndex provides the
- index specifiers
- <ul>
- <li><a href="ord_indices.html#unique_non_unique"><code>ordered_unique</code> and
- <code>ordered_non_unique</code></a> for
- <a href="ord_indices.html">ordered indices</a>,</li>
- <li><a href="rnk_indices.html#unique_non_unique"><code>ranked_unique</code> and
- <code>ranked_non_unique</code></a> for
- <a href="rnk_indices.html">ranked indices</a>,</li>
- <li><a href="hash_indices.html#unique_non_unique"><code>hashed_unique</code> and
- <code>hashed_non_unique</code></a> for
- <a href="hash_indices.html">hashed indices</a>,</li>
- <li><a href="seq_indices.html#sequenced"><code>sequenced</code></a> for
- <a href="seq_indices.html">sequenced indices</a>,</li>
- <li>and <a href="rnd_indices.html#random_access"><code>random_access</code></a> for
- <a href="rnd_indices.html">random access indices</a>.</li>
- </ul>
- </p>
- <h2>
- <a name="indexed_by_synopsis">Header
- <a href="../../../../boost/multi_index/indexed_by.hpp">
- <code>"boost/multi_index/indexed_by.hpp"</code></a> synopsis</a></h2>
- <blockquote><pre>
- <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
- <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
- <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>T0</span><span class=special>,...,</span><span class=keyword>typename</span> <span class=identifier>Tn</span><span class=special>></span>
- <span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
- <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
- <span class=special>}</span> <span class=comment>// namespace boost</span>
- </pre></blockquote>
- <h3><a name="indexed_by">Class template <code>indexed_by</code></a></h3>
- <p>
- <code>indexed_by</code> is a model of
- <a href="../../../../libs/mpl/doc/refmanual/random-access-sequence.html">
- <code>MPL Random Access Sequence</code></a> and
- <a href="../../../../libs/mpl/doc/refmanual/extensible-sequence.html">
- <code>MPL Extensible Sequence</code></a> meant to be used to specify a
- compile-time list of indices as the <code>IndexSpecifierList</code> of
- <code>multi_index_container</code>.
- </p>
- <blockquote><pre>
- <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>T0</span><span class=special>,...,</span><span class=keyword>typename</span> <span class=identifier>Tn</span><span class=special>></span>
- <span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- Each user-provided element of <code>indexed_list</code> must be an index
- specifier. At least an element must be provided. The maximum number of elements
- of an <code>indexed_by</code> sequence is implementation defined.
- </p>
- <h2><a name="tags">Tags</a></h2>
- <p>
- Tags are just conventional types used as mnemonics for indices of an
- <code>multi_index_container</code>, as for instance in member function <code>get</code>.
- Each index can have none, one or more tags associated. The way tags are assigned
- to a given index is dependent on the particular index specifier. However,
- for convenience all indices of Boost.MultiIndex support tagging through the
- class template <a href="#tag"><code>tag</code></a>.
- </p>
- <h2>
- <a name="tag_synopsis">Header
- <a href="../../../../boost/multi_index/tag.hpp">
- <code>"boost/multi_index/tag.hpp"</code></a> synopsis</a></h2>
- <blockquote><pre>
- <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
- <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
- <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>T0</span><span class=special>,...,</span><span class=keyword>typename</span> <span class=identifier>Tn</span><span class=special>></span>
- <span class=keyword>struct</span> <span class=identifier>tag</span><span class=special>;</span>
- <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
- <span class=special>}</span> <span class=comment>// namespace boost</span>
- </pre></blockquote>
- <h3><a name="tag">Class template <code>tag</code></a></h3>
- <p>
- <code>tag</code> is a typelist construct used to specify a compile-time
- sequence of tags to be assigned to an index in instantiation time.
- </p>
- <blockquote><pre>
- <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>T0</span><span class=special>,...,</span><span class=keyword>typename</span> <span class=identifier>Tn</span><span class=special>></span>
- <span class=keyword>struct</span> <span class=identifier>tag</span>
- <span class=special>{</span>
- <span class=keyword>typedef</span> <b>implementation defined</b> <span class=identifier>type</span><span class=special>;</span>
- <span class=special>};</span>
- </pre></blockquote>
- <p>
- Elements of <code>tag</code> can be any type, though the user is expected
- to provide classes with mnemonic names. Duplicate elements are not allowed.
- The maximum number of elements of a <code>tag</code> instantiation is
- implementation defined.
- The nested
- <code>type</code> is a model of
- <a href="../../../../libs/mpl/doc/refmanual/random-access-sequence.html">
- <code>MPL Random Access Sequence</code></a> and
- <a href="../../../../libs/mpl/doc/refmanual/extensible-sequence.html">
- <code>MPL Extensible Sequence</code></a> containing the types <code>T0</code>, ... ,
- <code>Tn</code> in the same order as specified.
- </p>
- <h2><a name="index_catalog">Indices provided by Boost.MultiIndex</a></h2>
- <h3><a name="key_based_indices">Key-based indices</a></h3>
- <p>
- Indices of this type are organized around <i>keys</i> obtained from the
- elements, as described in the <a href="key_extraction.html">key extraction
- reference</a>.
- <ul>
- <li><a href="ord_indices.html">Ordered indices</a> sort the elements
- on the key and provide fast lookup capabilites.</li>
- <li><a href="rnk_indices.html">Ranked indices</a> are a variation of
- ordered indices providing extra operations based on
- <i>rank</i>, the numerical position of an element
- in the sequence.</li>
- <li><a href="hash_indices.html">Hashed indices</a> offer high
- efficiency access through hashing techniques.</li>
- </ul>
- </p>
- <h3><a name="other_indices">Other types</a></h3>
- <p>
- <ul>
- <li><a href="seq_indices.html">Sequenced indices</a> allow to arrange
- elements as in a bidirectional list.</li>
- <li><a href="rnd_indices.html">Random access indices</a> provide
- constant time positional access and free ordering of elements.</li>
- </ul>
- </p>
- <h2><a name="views">Index views</a></h2>
- <p>
- The following concept is used by the rearrange facilities of non key-based
- indices. Given an index <code>i</code> of type <code>Index</code>, a <i>view
- of <code>i</code></i> is any range [<code>first</code>,<code>last</code>)
- where <code>first</code> and <code>last</code> are input iterators such that
- <ol>
- <li>the associated value type of <code>Iterator</code> is convertible
- to <code>const Index::value_type&</code>
- </li>
- <li>and each of the elements of <code>i</code> appears exactly once in
- [<code>first</code>,<code>last</code>).
- </li>
- </ol>
- Note that the view refers to the actual elements of <code>i</code>, not to
- copies of them. Additionally, a view is said to be <i>free</i> if its traversal
- order is not affected by changes in the traversal order of <code>i</code>.
- Examples of free views are:
- <ul>
- <li>[<code>c.begin()</code>,<code>c.end()</code>), where <code>c</code> is
- any container of reference wrappers (from
- <a href="../../../../doc/html/ref.html">Boost.Ref</a>) to the elements
- of <code>i</code> containing exactly one reference to every element.
- </li>
- <li>[<code>i'.begin()</code>,<code>i'.end()</code>), where <code>i'</code> is
- any index belonging to the same <code>multi_index_container</code>
- as <code>i</code>, except <code>i</code> itself.
- </li>
- <li>
- Any range which is a permutation of the ones described above, as for
- instance [<code>c.rbegin()</code>,<code>c.rend()</code>), or
- ranges obtained from the former with the aid of
- <a href="../../../../libs/iterator/doc/permutation_iterator.html">
- <code>permutation_iterator</code></a> from Boost.Iterator.
- </li>
- </ul>
- </p>
- <hr>
- <div class="prev_link"><a href="multi_index_container.html"><img src="../prev.gif" alt="multi_index_container reference" border="0"><br>
- <code>multi_index_container</code> reference
- </a></div>
- <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
- Boost.MultiIndex reference
- </a></div>
- <div class="next_link"><a href="ord_indices.html"><img src="../next.gif" alt="ordered indices" border="0"><br>
- Ordered indices
- </a></div><br clear="all" style="clear: all;">
- <br>
- <p>Revised April 19th 2015</p>
- <p>© Copyright 2003-2015 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>
|