| <!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 updating and modifying, which allow for the mutation of elements |
| in a controlled fashion. Immutability of elements does not significantly |
| impact the interface of ordered indices, as it is based upon that of |
| <code>std::set</code> and <code>std:multiset</code>, and these containers |
| also have non-mutable elements; but it may come as a surprise when dealing |
| with sequenced 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, save that they must model |
| <a href="http://www.sgi.com/tech/stl/Container.html"> |
| <code>Container</code></a> (without the requirement of being |
| <a href="http://www.sgi.com/tech/stl/Assignable.html"> |
| <code>Assignable</code></a>.) |
| </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="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="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 objects of a type |
| <code>Iterator</code> modelling |
| <a href="http://www.sgi.com/tech/stl/InputIterator.html"> |
| <code>Input Iterator</code></a> 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 July 21st 2009</p> |
| |
| <p>© Copyright 2003-2009 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> |