Gitiles
Code Review Sign In
realtimeroboticsgroup.org / RealtimeRoboticsGroup / test / 3cbbaca6b1a4c98b648739251c948e49c6980ad9 / . / doc / reference / indices.html
blob: a561199ce8c0277e935fa9869db389310f97b782 [file] [log] [blame]
Brian Silverman3cbbaca2018-08-04 23:38:07 -0700[diff] [blame^]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 replacement and modification which allow for the mutation of elements
109in a controlled fashion. Immutability of elements does not significantly
110impact the interfaces of ordered and hashed indices, as they are based upon
111those of associative and unordered associative containers, respectively,
112and these containers
113also have non-mutable elements; but it may come as a surprise when dealing
114with sequenced and random access indices, which are designed upon the functionality provided
115by <code>std::list</code>.
116</p>
117
118<p>
119These global operations are not directly exposed to the user, but rather
120they are wrapped as appropriate by each index (for instance, ordered indices
121provide a set-like suite of insertion member functions, whereas sequenced
122and random access indices have <code>push_back</code> and <code>push_front</code>
123operations.) Boost.MultiIndex poses no particular conditions on
124the interface of indices, although each index provided satisfy the C++ requirements for
125standard containers to the maximum extent possible within the conceptual framework
126of the library.
127</p>
128
129<h2><a name="complexity_signature">Complexity signature</a></h2>
130
131<p>
132Some member functions of an index interface are implemented by
133global primitives from the list above. Complexity of these operations
134thus depends on all indices of a given <code>multi_index_container</code>, not just
135the currently used index.
136</p>
137
138<p>
139In order to establish complexity estimates, an index is characterized
140by its <i>complexity signature</i>, consisting of the following
141associated functions on the number of elements:
142<ul>
143 <li><code>c(n)</code>: copying,
144 <li><code>i(n)</code>: insertion,
145 <li><code>h(n)</code>: hinted insertion,
146 <li><code>d(n)</code>: deletion,
147 <li><code>r(n)</code>: replacement,
148 <li><code>m(n)</code>: modifying.
149</ul>
150
151</p>
152Each function yields the complexity estimate of the contribution of the index
153to the corresponding global primitive. Let us consider
154an instantiation of <code>multi_index_container</code>
155with <code>N</code> indices labelled <code>0</code>,...,<code>N-1</code>
156whose complexity signatures are
157(<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>);
158the insertion of an element in such a container is then of complexity
159<code>O(i<sub>0</sub>(n)+···+i<sub>N-1</sub>(n))</code> where <code>n</code>
160is the number of elements. To abbreviate notation, we adopt the
161following definitions:
162<ul>
163 <li><code>C(n)=c<sub>0</sub>(n)+···+c<sub>N-1</sub>(n)</code>,</li>
164 <li><code>I(n)=i<sub>0</sub>(n)+···+i<sub>N-1</sub>(n)</code>,</li>
165 <li><code>H(n)=h<sub>0</sub>(n)+···+h<sub>N-1</sub>(n)</code>,</li>
166 <li><code>D(n)=d<sub>0</sub>(n)+···+d<sub>N-1</sub>(n)</code>,</li>
167 <li><code>R(n)=r<sub>0</sub>(n)+···+r<sub>N-1</sub>(n)</code>,</li>
168 <li><code>M(n)=m<sub>0</sub>(n)+···+m<sub>N-1</sub>(n)</code>.</li>
169</ul>
170For instance, consider a <code>multi_index_container</code> with two ordered indices,
171for which <code>i(n)=log(n)</code>, and a sequenced index with <code>i(n)=1</code>
172(constant time insertion). Insertion of an element into this <code>multi_index_container</code>
173is then of complexity
174<blockquote>
175<code>O(I(n))=O(2*log(n)+1)=O(log(n))</code>.
176</blockquote>
177</p>
178
179<h2><a name="index_specification">Index specification</a></h2>
180
181<p>
182Index specifiers are passed as instantiation arguments to
183<code>multi_index_container</code> and provide the information needed to incorporate
184the corresponding indices. Future releases of Boost.MultiIndex may allow for
185specification of user-defined indices. Meanwhile, the requirements for an index
186specifier remain implementation defined. Currently, Boost.MultiIndex provides the
187index specifiers
188<ul>
189 <li><a href="ord_indices.html#unique_non_unique"><code>ordered_unique</code> and
190 <code>ordered_non_unique</code></a> for
191 <a href="ord_indices.html">ordered indices</a>,</li>
192 <li><a href="rnk_indices.html#unique_non_unique"><code>ranked_unique</code> and
193 <code>ranked_non_unique</code></a> for
194 <a href="rnk_indices.html">ranked indices</a>,</li>
195 <li><a href="hash_indices.html#unique_non_unique"><code>hashed_unique</code> and
196 <code>hashed_non_unique</code></a> for
197 <a href="hash_indices.html">hashed indices</a>,</li>
198 <li><a href="seq_indices.html#sequenced"><code>sequenced</code></a> for
199 <a href="seq_indices.html">sequenced indices</a>,</li>
200 <li>and <a href="rnd_indices.html#random_access"><code>random_access</code></a> for
201 <a href="rnd_indices.html">random access indices</a>.</li>
202</ul>
203</p>
204
205<h2>
206<a name="indexed_by_synopsis">Header
207<a href="../../../../boost/multi_index/indexed_by.hpp">
208<code>"boost/multi_index/indexed_by.hpp"</code></a> synopsis</a></h2>
209
210<blockquote><pre>
211<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
212
213<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
214
215<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>
216<span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
217
218<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
219
220<span class=special>}</span> <span class=comment>// namespace boost</span>
221</pre></blockquote>
222
223<h3><a name="indexed_by">Class template <code>indexed_by</code></a></h3>
224
225<p>
226<code>indexed_by</code> is a model of
227<a href="../../../../libs/mpl/doc/refmanual/random-access-sequence.html">
228<code>MPL Random Access Sequence</code></a> and
229<a href="../../../../libs/mpl/doc/refmanual/extensible-sequence.html">
230<code>MPL Extensible Sequence</code></a> meant to be used to specify a
231compile-time list of indices as the <code>IndexSpecifierList</code> of
232<code>multi_index_container</code>.
233</p>
234
235<blockquote><pre>
236<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>
237<span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
238</pre></blockquote>
239
240<p>
241Each user-provided element of <code>indexed_list</code> must be an index
242specifier. At least an element must be provided. The maximum number of elements
243of an <code>indexed_by</code> sequence is implementation defined.
244</p>
245
246<h2><a name="tags">Tags</a></h2>
247
248<p>
249Tags are just conventional types used as mnemonics for indices of an
250<code>multi_index_container</code>, as for instance in member function <code>get</code>.
251Each index can have none, one or more tags associated. The way tags are assigned
252to a given index is dependent on the particular index specifier. However,
253for convenience all indices of Boost.MultiIndex support tagging through the
254class template <a href="#tag"><code>tag</code></a>.
255</p>
256
257<h2>
258<a name="tag_synopsis">Header
259<a href="../../../../boost/multi_index/tag.hpp">
260<code>"boost/multi_index/tag.hpp"</code></a> synopsis</a></h2>
261
262<blockquote><pre>
263<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
264
265<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
266
267<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>
268<span class=keyword>struct</span> <span class=identifier>tag</span><span class=special>;</span>
269
270<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
271
272<span class=special>}</span> <span class=comment>// namespace boost</span>
273</pre></blockquote>
274
275<h3><a name="tag">Class template <code>tag</code></a></h3>
276
277<p>
278<code>tag</code> is a typelist construct used to specify a compile-time
279sequence of tags to be assigned to an index in instantiation time.
280</p>
281
282<blockquote><pre>
283<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>
284<span class=keyword>struct</span> <span class=identifier>tag</span>
285<span class=special>{</span>
286 <span class=keyword>typedef</span> <b>implementation defined</b> <span class=identifier>type</span><span class=special>;</span>
287<span class=special>};</span>
288</pre></blockquote>
289
290<p>
291Elements of <code>tag</code> can be any type, though the user is expected
292to provide classes with mnemonic names. Duplicate elements are not allowed.
293The maximum number of elements of a <code>tag</code> instantiation is
294implementation defined.
295The nested
296<code>type</code> is a model of
297<a href="../../../../libs/mpl/doc/refmanual/random-access-sequence.html">
298<code>MPL Random Access Sequence</code></a> and
299<a href="../../../../libs/mpl/doc/refmanual/extensible-sequence.html">
300<code>MPL Extensible Sequence</code></a> containing the types <code>T0</code>, ... ,
301<code>Tn</code> in the same order as specified.
302</p>
303
304<h2><a name="index_catalog">Indices provided by Boost.MultiIndex</a></h2>
305
306
307<h3><a name="key_based_indices">Key-based indices</a></h3>
308
309<p>
310Indices of this type are organized around <i>keys</i> obtained from the
311elements, as described in the <a href="key_extraction.html">key extraction
312reference</a>.
313<ul>
314 <li><a href="ord_indices.html">Ordered indices</a> sort the elements
315 on the key and provide fast lookup capabilites.</li>
316 <li><a href="rnk_indices.html">Ranked indices</a> are a variation of
317 ordered indices providing extra operations based on
318 <i>rank</i>, the numerical position of an element
319 in the sequence.</li>
320 <li><a href="hash_indices.html">Hashed indices</a> offer high
321 efficiency access through hashing techniques.</li>
322</ul>
323</p>
324
325<h3><a name="other_indices">Other types</a></h3>
326
327<p>
328<ul>
329 <li><a href="seq_indices.html">Sequenced indices</a> allow to arrange
330 elements as in a bidirectional list.</li>
331 <li><a href="rnd_indices.html">Random access indices</a> provide
332 constant time positional access and free ordering of elements.</li>
333</ul>
334</p>
335
336<h2><a name="views">Index views</a></h2>
337
338<p>
339The following concept is used by the rearrange facilities of non key-based
340indices. Given an index <code>i</code> of type <code>Index</code>, a <i>view
341of <code>i</code></i> is any range [<code>first</code>,<code>last</code>)
342where <code>first</code> and <code>last</code> are input iterators such that
343<ol>
344 <li>the associated value type of <code>Iterator</code> is convertible
345 to <code>const Index::value_type&amp;</code>
346 </li>
347 <li>and each of the elements of <code>i</code> appears exactly once in
348 [<code>first</code>,<code>last</code>).
349 </li>
350</ol>
351Note that the view refers to the actual elements of <code>i</code>, not to
352copies of them. Additionally, a view is said to be <i>free</i> if its traversal
353order is not affected by changes in the traversal order of <code>i</code>.
354Examples of free views are:
355<ul>
356 <li>[<code>c.begin()</code>,<code>c.end()</code>), where <code>c</code> is
357 any container of reference wrappers (from
358 <a href="../../../../doc/html/ref.html">Boost.Ref</a>) to the elements
359 of <code>i</code> containing exactly one reference to every element.
360 </li>
361 <li>[<code>i'.begin()</code>,<code>i'.end()</code>), where <code>i'</code> is
362 any index belonging to the same <code>multi_index_container</code>
363 as <code>i</code>, except <code>i</code> itself.
364 </li>
365 <li>
366 Any range which is a permutation of the ones described above, as for
367 instance [<code>c.rbegin()</code>,<code>c.rend()</code>), or
368 ranges obtained from the former with the aid of
369 <a href="../../../../libs/iterator/doc/permutation_iterator.html">
370 <code>permutation_iterator</code></a> from Boost.Iterator.
371 </li>
372</ul>
373</p>
374
375<hr>
376
377<div class="prev_link"><a href="multi_index_container.html"><img src="../prev.gif" alt="multi_index_container reference" border="0"><br>
378<code>multi_index_container</code> reference
379</a></div>
380<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
381Boost.MultiIndex reference
382</a></div>
383<div class="next_link"><a href="ord_indices.html"><img src="../next.gif" alt="ordered indices" border="0"><br>
384Ordered indices
385</a></div><br clear="all" style="clear: all;">
386
387<br>
388
389<p>Revised April 19th 2015</p>
390
391<p>&copy; Copyright 2003-2015 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
392Distributed under the Boost Software
393License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
394LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
395http://www.boost.org/LICENSE_1_0.txt</a>)
396</p>
397
398</body>
399</html>