Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/multi_index/doc/reference/indices.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 16.6 KB
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
2
3<html>
4<head>
5<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
6<title>Boost.MultiIndex Documentation - Index reference</title>
7<link rel="stylesheet" href="../style.css" type="text/css">
8<link rel="start" href="../index.html">
9<link rel="prev" href="multi_index_container.html">
10<link rel="up" href="index.html">
11<link rel="next" href="ord_indices.html">
12</head>
13
14<body>
15<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
16"middle" width="277" height="86">Boost.MultiIndex Index reference</h1>
17
18<div class="prev_link"><a href="multi_index_container.html"><img src="../prev.gif" alt="multi_index_container reference" border="0"><br>
19<code>multi_index_container</code> reference
20</a></div>
21<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
22Boost.MultiIndex reference
23</a></div>
24<div class="next_link"><a href="ord_indices.html"><img src="../next.gif" alt="ordered indices" border="0"><br>
25Ordered indices
26</a></div><br clear="all" style="clear: all;">
27
28<hr>
29
30<h2>Contents</h2>
31
32<ul>
33  <li><a href="#index_concepts">Index concepts</a></li>
34  <li><a href="#complexity_signature">Complexity signature</a></li>
35  <li><a href="#index_specification">Index specification</a></li>
36  <li><a href="#indexed_by_synopsis">Header
37    <code>"boost/multi_index/indexed_by.hpp"</code> synopsis</a>
38    <ul>
39      <li><a href="#indexed_by">Class template <code>indexed_by</code></a></li>
40    </ul>
41  </li>
42  <li><a href="#tags">Tags</a></li>
43  <li><a href="#tag_synopsis">Header
44    <code>"boost/multi_index/tag.hpp"</code> synopsis</a>
45    <ul>
46      <li><a href="#tag">Class template <code>tag</code></a></li>
47    </ul>
48  </li>
49  <li><a href="#index_catalog">Indices provided by Boost.MultiIndex</a>
50    <ul>
51      <li><a href="#key_based_indices">Key-based indices</a></li>
52      <li><a href="#other_indices">Other types</a></li>
53    </ul>
54  </li>
55  <li><a href="#views">Index views</a></li>
56</ul>
57
58<h2><a name="index_concepts">Index concepts</a></h2>
59
60<p>
61<code>multi_index_container</code> instantiations comprise one or more indices
62specified at compile time. Each index allows read/write access to the elements
63contained in a definite manner. For instance,
64<a href="ord_indices.html">ordered indices</a>
65provide a set-like interface to the elements, whereas
66<a href="seq_indices.html">sequenced indices</a> mimic the functionality
67of <code>std::list</code>.
68</p>
69
70<p>
71Indices are not isolated objects, and so cannot be constructed on their
72own. Rather they are embedded into a <code>multi_index_container</code> as specified by
73means of an <a href="#index_specification">index specifier</a>. The name of
74the index class implementation proper is never directly exposed to the user, who
75has only access to the associated index specifier.
76</p>
77
78<p>
79Insertion and erasing of elements are always performed through the
80appropriate interface of some index of the <code>multi_index_container</code>;
81these operations, however, do have an impact on all other indices as
82well: for instance, insertion through a given index may fail because
83there exists another index which bans the operation in order to preserve
84its invariant (like uniqueness of elements.) This circumstance, rather
85than being an obstacle, yields much of the power of Boost.MultiIndex:
86equivalent constructions based on manual composition of standard
87containers would have to add a fair amount of code in order to
88globally preserve the invariants of each container while guaranteeing
89that all of them are synchronized. The global operations performed
90in a joint manner among the various indices can be reduced to
91six primitives:
92<ul>
93  <li>Copying,</li>
94  <li>insertion of an element,</li>
95  <li>hinted insertion, where a preexisting element is suggested in
96    order to improve the efficiency of the operation,</li>
97  <li>deletion of an element,</li>
98  <li>replacement of the value of an element,
99    which may trigger the rearrangement of this element in one or
100    more indices, or the banning of the replacement,</li>
101  <li>modification of an element, and its subsequent
102    rearrangement/banning by the various indices.
103</ul>
104The last two primitives deserve some further explanation: in order to
105guarantee the invariants associated to each index (e.g. some definite
106ordering,) elements of a <code>multi_index_container</code> are not mutable.
107To overcome this restriction, indices expose member functions
108for updating and modifying, which allow for the mutation of elements
109in a controlled fashion. Immutability of elements does not significantly
110impact the interface of ordered indices, as it is based upon  that of
111<code>std::set</code> and <code>std:multiset</code>, and these containers
112also have non-mutable elements; but it may come as a surprise when dealing
113with sequenced indices, which are designed upon the functionality provided
114by <code>std::list</code>.
115</p>
116
117<p>
118These global operations are not directly exposed to the user, but rather
119they are wrapped as appropriate by each index (for instance, ordered indices
120provide a set-like suite of insertion member functions, whereas sequenced
121and random access indices have <code>push_back</code> and <code>push_front</code>
122operations.) Boost.MultiIndex poses no particular conditions on
123the interface of indices, save that they must model
124<a href="http://www.sgi.com/tech/stl/Container.html">
125<code>Container</code></a> (without the requirement of being
126<a href="http://www.sgi.com/tech/stl/Assignable.html">
127<code>Assignable</code></a>.)
128</p>
129
130<h2><a name="complexity_signature">Complexity signature</a></h2>
131
132<p>
133Some member functions of an index interface are implemented by
134global primitives from the list above. Complexity of these operations
135thus depends on all indices of a given <code>multi_index_container</code>, not just
136the currently used index.
137</p>
138
139<p>
140In order to establish complexity estimates, an index is characterized
141by its <i>complexity signature</i>, consisting of the following
142associated functions on the number of elements:
143<ul>
144  <li><code>c(n)</code>: copying,
145  <li><code>i(n)</code>: insertion,
146  <li><code>h(n)</code>: hinted insertion,
147  <li><code>d(n)</code>: deletion,
148  <li><code>r(n)</code>: replacement,
149  <li><code>m(n)</code>: modifying.
150</ul>
151
152</p>
153Each function yields the complexity estimate of the contribution of the index
154to the corresponding global primitive. Let us consider
155an instantiation of <code>multi_index_container</code>
156with <code>N</code> indices labelled <code>0</code>,...,<code>N-1</code>
157whose complexity signatures are
158(<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>);
159the insertion of an element in such a container is then of complexity
160<code>O(i<sub>0</sub>(n)+···+i<sub>N-1</sub>(n))</code> where <code>n</code>
161is the number of elements. To abbreviate notation, we adopt the
162following definitions:
163<ul>
164  <li><code>C(n)=c<sub>0</sub>(n)+···+c<sub>N-1</sub>(n)</code>,</li>
165  <li><code>I(n)=i<sub>0</sub>(n)+···+i<sub>N-1</sub>(n)</code>,</li>
166  <li><code>H(n)=h<sub>0</sub>(n)+···+h<sub>N-1</sub>(n)</code>,</li>
167  <li><code>D(n)=d<sub>0</sub>(n)+···+d<sub>N-1</sub>(n)</code>,</li>
168  <li><code>R(n)=r<sub>0</sub>(n)+···+r<sub>N-1</sub>(n)</code>,</li>
169  <li><code>M(n)=m<sub>0</sub>(n)+···+m<sub>N-1</sub>(n)</code>.</li>
170</ul>
171For instance, consider a <code>multi_index_container</code> with two ordered indices,
172for which <code>i(n)=log(n)</code>, and a sequenced index with <code>i(n)=1</code>
173(constant time insertion). Insertion of an element into this <code>multi_index_container</code>
174is then of complexity
175<blockquote>
176<code>O(I(n))=O(2*log(n)+1)=O(log(n))</code>.
177</blockquote>
178</p>
179
180<h2><a name="index_specification">Index specification</a></h2>
181
182<p>
183Index specifiers are passed as instantiation arguments to
184<code>multi_index_container</code> and provide the information needed to incorporate
185the corresponding indices. Future releases of Boost.MultiIndex may allow for
186specification of user-defined indices. Meanwhile, the requirements for an index
187specifier remain implementation defined. Currently, Boost.MultiIndex provides the
188index specifiers
189<ul>
190  <li><a href="ord_indices.html#unique_non_unique"><code>ordered_unique</code> and
191    <code>ordered_non_unique</code></a> for
192    <a href="ord_indices.html">ordered indices</a>,</li>
193  <li><a href="hash_indices.html#unique_non_unique"><code>hashed_unique</code> and
194    <code>hashed_non_unique</code></a> for
195    <a href="hash_indices.html">hashed indices</a>,</li>
196  <li><a href="seq_indices.html#sequenced"><code>sequenced</code></a> for
197    <a href="seq_indices.html">sequenced indices</a></li>
198  <li>and <a href="rnd_indices.html#random_access"><code>random_access</code></a> for
199    <a href="rnd_indices.html">random access indices</a>.</li>
200</ul>
201</p>
202
203<h2>
204<a name="indexed_by_synopsis">Header
205<a href="../../../../boost/multi_index/indexed_by.hpp">
206<code>"boost/multi_index/indexed_by.hpp"</code></a> synopsis</a></h2>
207
208<blockquote><pre>
209<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
210
211<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
212
213<span class=keyword>template</span><span class=special>&lt;</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>&gt;</span>
214<span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
215
216<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span> 
217
218<span class=special>}</span> <span class=comment>// namespace boost</span>
219</pre></blockquote>
220
221<h3><a name="indexed_by">Class template <code>indexed_by</code></a></h3>
222
223<p>
224<code>indexed_by</code> is a model of
225<a href="../../../../libs/mpl/doc/refmanual/random-access-sequence.html">
226<code>MPL Random Access Sequence</code></a> and
227<a href="../../../../libs/mpl/doc/refmanual/extensible-sequence.html">
228<code>MPL Extensible Sequence</code></a> meant to be used to specify a
229compile-time list of indices as the <code>IndexSpecifierList</code> of
230<code>multi_index_container</code>.
231</p>
232
233<blockquote><pre>
234<span class=keyword>template</span><span class=special>&lt;</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>&gt;</span>
235<span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
236</pre></blockquote>
237
238<p>
239Each user-provided element of <code>indexed_list</code> must be an index
240specifier. At least an element must be provided. The maximum number of elements
241of an <code>indexed_by</code> sequence is implementation defined.
242</p>
243
244<h2><a name="tags">Tags</a></h2>
245
246<p>
247Tags are just conventional types used as mnemonics for indices of an
248<code>multi_index_container</code>, as for instance in member function <code>get</code>.
249Each index can have none, one or more tags associated. The way tags are assigned
250to a given index is dependent on the particular index specifier. However,
251for convenience all indices of Boost.MultiIndex support tagging through the
252class template <a href="#tag"><code>tag</code></a>.
253</p>
254
255<h2>
256<a name="tag_synopsis">Header
257<a href="../../../../boost/multi_index/tag.hpp">
258<code>"boost/multi_index/tag.hpp"</code></a> synopsis</a></h2>
259
260<blockquote><pre>
261<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
262
263<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
264
265<span class=keyword>template</span><span class=special>&lt;</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>&gt;</span>
266<span class=keyword>struct</span> <span class=identifier>tag</span><span class=special>;</span>
267
268<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span> 
269
270<span class=special>}</span> <span class=comment>// namespace boost</span>
271</pre></blockquote>
272
273<h3><a name="tag">Class template <code>tag</code></a></h3>
274
275<p>
276<code>tag</code> is a typelist construct used to specify a compile-time
277sequence of tags to be assigned to an index in instantiation time.
278</p>
279
280<blockquote><pre>
281<span class=keyword>template</span><span class=special>&lt;</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>&gt;</span>
282<span class=keyword>struct</span> <span class=identifier>tag</span><span class=special>;</span>
283</pre></blockquote>
284
285<p>
286Elements of <code>tag</code> can be any type, though the user is expected
287to provide classes with mnemonic names. Duplicate elements are not allowed.
288The maximum number of elements of a <code>tag</code> instantiation is
289implementation defined.
290</p>
291
292<h2><a name="index_catalog">Indices provided by Boost.MultiIndex</a></h2>
293
294
295<h3><a name="key_based_indices">Key-based indices</a></h3>
296
297<p>
298Indices of this type are organized around <i>keys</i> obtained from the
299elements, as described in the <a href="key_extraction.html">key extraction
300reference</a>.
301<ul>
302  <li><a href="ord_indices.html">Ordered indices</a> sort the elements
303    on the key and provide fast lookup capabilites.</li>
304  <li><a href="hash_indices.html">Hashed indices</a> offer high
305    efficiency access through hashing techniques.</li>
306</ul>
307</p>
308
309<h3><a name="other_indices">Other types</a></h3>
310
311<p>
312<ul>
313  <li><a href="seq_indices.html">Sequenced indices</a> allow to arrange
314    elements as in a bidirectional list.</li>
315  <li><a href="rnd_indices.html">Random access indices</a> provide
316    constant time positional access and free ordering of elements.</li>
317</ul>
318</p>
319
320<h2><a name="views">Index views</a></h2>
321
322<p>
323The following concept is used by the rearrange facilities of non key-based
324indices. Given an index <code>i</code> of type <code>Index</code>, a <i>view
325of <code>i</code></i> is any range [<code>first</code>,<code>last</code>)
326where <code>first</code> and <code>last</code> are objects of a type
327<code>Iterator</code> modelling
328<a href="http://www.sgi.com/tech/stl/InputIterator.html">
329<code>Input Iterator</code></a> such that
330<ol>
331  <li>the associated value type of <code>Iterator</code> is convertible
332    to <code>const Index::value_type&amp;</code>
333  </li>
334  <li>and each of the elements of <code>i</code> appears exactly once in
335    [<code>first</code>,<code>last</code>).
336  </li>
337</ol>
338Note that the view refers to the actual elements of <code>i</code>, not to
339copies of them. Additionally, a view is said to be <i>free</i> if its traversal
340order is not affected by changes in the traversal order of <code>i</code>.
341Examples of free views are:
342<ul>
343  <li>[<code>c.begin()</code>,<code>c.end()</code>), where <code>c</code> is
344    any container of reference wrappers (from
345    <a href="../../../../doc/html/ref.html">Boost.Ref</a>) to the elements
346    of <code>i</code> containing exactly one reference to every element.
347  </li>
348  <li>[<code>i'.begin()</code>,<code>i'.end()</code>), where <code>i'</code> is
349    any index belonging to the same <code>multi_index_container</code>
350    as <code>i</code>, except <code>i</code> itself.
351  </li>
352  <li>
353    Any range which is a permutation of the ones described above, as for
354    instance [<code>c.rbegin()</code>,<code>c.rend()</code>), or
355    ranges obtained from the former with the aid of
356    <a href="../../../../libs/iterator/doc/permutation_iterator.html">
357    <code>permutation_iterator</code></a> from Boost.Iterator.
358  </li>
359</ul>
360</p>
361
362<hr>
363
364<div class="prev_link"><a href="multi_index_container.html"><img src="../prev.gif" alt="multi_index_container reference" border="0"><br>
365<code>multi_index_container</code> reference
366</a></div>
367<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
368Boost.MultiIndex reference
369</a></div>
370<div class="next_link"><a href="ord_indices.html"><img src="../next.gif" alt="ordered indices" border="0"><br>
371Ordered indices
372</a></div><br clear="all" style="clear: all;">
373
374<br>
375
376<p>Revised February 6th 2006</p>
377
378<p>&copy; Copyright 2003-2006 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
379Distributed under the Boost Software
380License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
381LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
382http://www.boost.org/LICENSE_1_0.txt</a>)
383</p>
384
385</body>
386</html>
Note: See TracBrowser for help on using the repository browser.