Gitiles
Code Review Sign In
realtimeroboticsgroup.org / RealtimeRoboticsGroup / test / 3cbbaca6b1a4c98b648739251c948e49c6980ad9 / . / doc / tutorial / indices.html
blob: 835d533720c3b3564084568651d1a5e8578f159d [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 - Tutorial - Index types</title>
7<link rel="stylesheet" href="../style.css" type="text/css">
8<link rel="start" href="../index.html">
9<link rel="prev" href="basics.html">
10<link rel="up" href="index.html">
11<link rel="next" href="key_extraction.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 Tutorial: Index types</h1>
17
18<div class="prev_link"><a href="basics.html"><img src="../prev.gif" alt="basics" border="0"><br>
19Basics
20</a></div>
21<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
22Boost.MultiIndex tutorial
23</a></div>
24<div class="next_link"><a href="key_extraction.html"><img src="../next.gif" alt="key estraction" border="0"><br>
25Key extraction
26</a></div><br clear="all" style="clear: all;">
27
28<hr>
29
30<h2>Contents</h2>
31
32<ul>
33 <li><a href="#classification">Classification</a>
34 <li><a href="#rnk_indices">Ranked indices</a>
35 <ul>
36 <li><a href="#rnk_spec">Specification</a></li>
37 <li><a href="#rnk_ops">Rank operations</a></li>
38 </ul>
39 </li>
40 <li><a href="#hashed_indices">Hashed indices</a>
41 <ul>
42 <li><a href="#hash_unique_non_unique">Unique and non-unique variants</a></li>
43 <li><a href="#hash_spec">Specification</a></li>
44 <li><a href="#hash_lookup">Lookup</a></li>
45 <li><a href="#hash_updating">Updating</a></li>
46 <li><a href="#guarantees">Guarantees on iterator validity and exception safety</a></li>
47 </ul>
48 </li>
49 <li><a href="#rnd_indices">Random access indices</a>
50 <ul>
51 <li><a href="#rnd_spec">Specification</a></li>
52 <li><a href="#rnd_interface">Interface</a></li>
53 <li><a href="#rnd_vs_vector">Comparison with <code>std::vector</code></a></li>
54 </ul>
55 </li>
56 <li><a href="#rearrange">Index rearranging</a></li>
57 <li><a href="#iterator_to"><code>iterator_to</code></a></li>
58 <li><a href="#ordered_node_compression">Ordered indices node compression</a></li>
59</ul>
60
61<h2><a name="classification">Classification</a></h2>
62
63<p>
64Boost.MultiIndex provides six different index types, which can be classified as
65shown in the table below. <a href="basics.html#ord_indices">Ordered</a> and
66<a href="basics.html#seq_indices">sequenced</a> indices,
67which are the most commonly used, have been explained in the basics section;
68the rest of index types can be regarded as variations of the former providing
69some added benefits, functionally or in the area of performance.
70</p>
71
72<p align="center">
73<table cellspacing="0">
74 <caption><b>Boost.MultiIndex indices.</b></caption>
75<tr>
76 <th align="center"colspan="2">type</th>
77 <th align="center">specifier</th>
78</tr>
79<tr>
80 <td align="center" rowspan="6">&nbsp;&nbsp;key-based&nbsp;&nbsp;</td>
81 <td align="center" rowspan="4">&nbsp;&nbsp;ordered&nbsp;&nbsp;</td>
82 <td align="center">&nbsp;&nbsp;<code>ordered_unique</code>&nbsp;&nbsp;</td>
83</tr>
84<tr class="odd_tr">
85 <td align="center">&nbsp;&nbsp;<code>ordered_non_unique</code>&nbsp;&nbsp;</td>
86</tr>
87<tr>
88 <td align="center">&nbsp;&nbsp;<code>ranked_unique</code>&nbsp;&nbsp;</td>
89</tr>
90<tr class="odd_tr">
91 <td align="center">&nbsp;&nbsp;<code>ranked_non_unique</code>&nbsp;&nbsp;</td>
92</tr>
93<tr>
94 <td align="center" rowspan="2">&nbsp;&nbsp;hashed&nbsp;&nbsp;</td>
95 <td align="center">&nbsp;&nbsp;<code>hashed_unique</code>&nbsp;&nbsp;</td>
96</tr>
97<tr class="odd_tr">
98 <td align="center">&nbsp;&nbsp;<code>hashed_non_unique</code>&nbsp;&nbsp;</td>
99</tr>
100<tr>
101 <td align="center" rowspan="2" colspan="2">&nbsp;&nbsp;non key-based&nbsp;&nbsp;</td>
102 <td align="center"><code>&nbsp;&nbsp;sequenced&nbsp;&nbsp;</code></td>
103</tr>
104<tr class="odd_tr">
105 <td align="center"><code>&nbsp;&nbsp;random_access&nbsp;&nbsp;</code></td>
106</tr>
107</table>
108</p>
109
110<p>
111Key-based indices, of which ordered indices are the usual example, provide
112efficient lookup of elements based on some piece of information called the
113<i>element key</i>: there is an extensive suite of
114<a href="key_extraction.html">key extraction</a>
115utility classes allowing for the specification of such keys. Fast lookup
116imposes an internally managed order on these indices that the user is not
117allowed to modify; non key-based indices, on the other hand, can be freely
118rearranged at the expense of lacking lookup facilities. Sequenced indices,
119modeled after the interface of <code>std::list</code>, are the customary
120example of a non key-based index.
121</p>
122
123<h2><a name="rnk_indices">Ranked indices</a></h2>
124
125<p>
126Suppose we have a <code>std::multiset</code> of numbers and we want to output
127the values above the 75h <a href="http://en.wikipedia.org/wiki/Percentile">percentile</a>:
128</p>
129
130<blockquote><pre>
131<span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>multiset</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=identifier>int_multiset</span><span class=special>;</span>
132
133<span class=keyword>void</span> <span class=identifier>output_above_75th_percentile</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>int_multiset</span><span class=special>&amp;</span> <span class=identifier>s</span><span class=special>)</span>
134<span class=special>{</span>
135 <span class=identifier>int_multiset</span><span class=special>::</span><span class=identifier>const_iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>begin</span><span class=special>();</span>
136 <span class=identifier>std</span><span class=special>::</span><span class=identifier>advance</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>size</span><span class=special>()*</span><span class=number>3</span><span class=special>/</span><span class=number>4</span><span class=special>);</span> <span class=comment>// linear on s.size();</span>
137
138 <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>ostream_iterator</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>,</span><span class=string>&quot;\n&quot;</span><span class=special>));</span>
139<span class=special>}</span>
140</pre></blockquote>
141
142<p>
143The problem with this code is that getting to the beginning of the desired subsequence
144involves a linear traversal of the container. Ranked indices provide the mechanisms to do this
145much faster:
146</p>
147
148<blockquote><pre>
149<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
150 <span class=keyword>int</span><span class=special>,</span>
151 <span class=identifier>indexed_by</span><span class=special>&lt;</span>
152 <span class=identifier>ranked_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;</span>
153 <span class=special>&gt;</span>
154<span class=special>&gt;</span> <span class=identifier>int_multiset</span><span class=special>;</span>
155
156<span class=keyword>void</span> <span class=identifier>output_above_75th_percentile</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>int_multiset</span><span class=special>&amp;</span> <span class=identifier>s</span><span class=special>)</span>
157<span class=special>{</span>
158 <span class=identifier>int_multiset</span><span class=special>::</span><span class=identifier>const_iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>nth</span><span class=special>(</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>size</span><span class=special>()*</span><span class=number>3</span><span class=special>/</span><span class=number>4</span><span class=special>);</span> <span class=comment>// logarithmic</span>
159 <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>ostream_iterator</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>,</span><span class=string>&quot;\n&quot;</span><span class=special>));</span>
160<span class=special>}</span>
161</pre></blockquote>
162
163<p>
164<code>nth(n)</code> returns an iterator to the element whose <i>rank</i>, i.e. its distance
165from the beginning of the index, is <code>n</code>, and does so efficiently in logarithmic time.
166Conversely, <code>rank(it)</code> computes in logarithmic time the rank of the element
167pointed to by <code>it</code>, or <code>size()</code> if <code>it==end()</code>.
168</p>
169
170<blockquote><pre>
171<span class=identifier>int_multiset</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=number>10</span><span class=special>).</span><span class=identifier>first</span><span class=special>;</span>
172<span class=identifier>int_multiset</span><span class=special>::</span><span class=identifier>size_type</span> <span class=identifier>r</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>rank</span><span class=special>(</span><span class=identifier>it</span><span class=special>);</span> <span class=comment>// rank of 10;</span>
173</pre></blockquote>
174
175<p>
176Ranked indices provide the same interface as ordered indices plus several rank-related operations.
177The cost of this extra functionality is higher memory consumption due to some internal additional
178data (one word per element) and somewhat longer execution times in insertion and erasure
179&#8212;in particular, erasing an element takes time proportional to <code>log(n)</code>, where
180<code>n</code> is the number of elements in the index, whereas for ordered indices this time is
181constant.
182The <a href="../reference/rnk_indices.html">reference</a> describes these indices in complete detail.
183</p>
184
185<h3><a name="rnk_spec">Specification</a></h3>
186
187<p>
188The specification of ranked indices is done exactly as with <a href="basics.html#ord_spec">ordered indices</a>,
189except that <code>ranked_unique</code> and <code>ranked_non_unique</code> are used instead.
190</p>
191
192<blockquote><pre>
193<span class=special>(</span><span class=identifier>ranked_unique</span> <span class=special>|</span> <span class=identifier>ranked_non_unique</span><span class=special>)
194 </span><span class=special>&lt;[</span><i>(tag)</i><span class=special>[,</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]]&gt;</span>
195
196<span class=special>(</span><span class=identifier>ranked_unique</span> <span class=special>|</span> <span class=identifier>ranked_non_unique</span><span class=special>)</span>
197 <span class=special>&lt;[</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]&gt;</span>
198</pre></blockquote>
199
200<h3><a name="rnk_ops">Rank operations</a></h3>
201
202<p>
203Besides <code>nth</code> and <code>rank</code>, ranked indices provide member functions
204<ul>
205 <li><code>find_rank</code>,</li>
206 <li><code>lower_bound_rank</code>,</li>
207 <li><code>upper_bound_rank</code>,</li>
208 <li><code>equal_range_rank</code> and </li>
209 <li><code>range_rank</code></li>
210</ul>
211that behave as their normal
212<a href="basics.html#special_lookup">lookup</a> and <a href="basics.html#range">range retrieval</a>
213counterparts (<code>find</code>, <code>lower_bound</code> etc.) but return ranks rather than iterators.
214</p>
215
216<blockquote><pre>
217<span class=keyword>void</span> <span class=identifier>percentile</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>n</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>int_multiset</span><span class=special>&amp;</span> <span class=identifier>s</span><span class=special>)</span>
218<span class=special>{</span>
219 <span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>&lt;&lt;</span><span class=identifier>n</span><span class=special>&lt;&lt;</span><span class=string>&quot; lies in the &quot;</span><span class=special>&lt;&lt;</span>
220 <span class=identifier>s</span><span class=special>.</span><span class=identifier>upper_bound_rank</span><span class=special>(</span><span class=identifier>n</span><span class=special>)*</span><span class=number>100.0</span><span class=special>/</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>size</span><span class=special>()&lt;&lt;</span><span class=string>&quot; percentile\n&quot;</span><span class=special>;</span>
221<span class=special>}</span>
222</pre></blockquote>
223
224<p>
225You might think that <code>upper_bound_rank(n)</code> is mere shorthand for
226<code>rank(upper_bound(n))</code>: in reality, though, you should prefer using
227<code>*_rank</code> operations directly as they run faster than the
228alternative formulations.
229</p>
230
231<h2><a name="hashed_indices">Hashed indices</a></h2>
232
233<p>
234Hashed indices constitute a trade-off with respect to ordered indices: if correctly used,
235they provide much faster lookup of elements, at the expense of losing sorting
236information.
237Let us revisit our <code>employee_set</code> example: suppose a field for storing
238the Social Security number is added, with the requisite that lookup by this
239number should be as fast as possible. Instead of the usual ordered index, a
240hashed index can be resorted to:
241</p>
242
243<blockquote><pre>
244<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index_container</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
245<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>hashed_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
246<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>ordered_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
247<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>identity</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
248<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>member</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
249
250<span class=keyword>struct</span> <span class=identifier>employee</span>
251<span class=special>{</span>
252 <span class=keyword>int</span> <span class=identifier>id</span><span class=special>;</span>
253 <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
254 <span class=keyword>int</span> <span class=identifier>ssnumber</span><span class=special>;</span>
255
256 <span class=identifier>employee</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>id</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&amp;</span> <span class=identifier>name</span><span class=special>,</span><span class=keyword>int</span> <span class=identifier>ssnumber</span><span class=special>):</span>
257 <span class=identifier>id</span><span class=special>(</span><span class=identifier>id</span><span class=special>),</span><span class=identifier>name</span><span class=special>(</span><span class=identifier>name</span><span class=special>),</span><span class=identifier>ssnumber</span><span class=special>(</span><span class=identifier>ssnumber</span><span class=special>){}</span>
258
259 <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;(</span><span class=keyword>const</span> <span class=identifier>employee</span><span class=special>&amp;</span> <span class=identifier>e</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>id</span><span class=special>&lt;</span><span class=identifier>e</span><span class=special>.</span><span class=identifier>id</span><span class=special>;}</span>
260<span class=special>};</span>
261
262<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
263 <span class=identifier>employee</span><span class=special>,</span>
264 <span class=identifier>indexed_by</span><span class=special>&lt;</span>
265 <span class=comment>// sort by employee::operator&lt;</span>
266 <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
267
268 <span class=comment>// sort by less&lt;string&gt; on name</span>
269 <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
270
271 <span class=comment>// hashed on ssnumber</span>
272 <span class=identifier>hashed_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>ssnumber</span><span class=special>&gt;</span> <span class=special>&gt;</span>
273 <span class=special>&gt;</span>
274<span class=special>&gt;</span> <span class=identifier>employee_set</span>
275</pre></blockquote>
276
277<p>
278Note that the hashed index does not guarantee any particular ordering of the
279elements: so, for instance, we cannot efficiently query the employees whose SSN is
280greater than a given number. Usually, you must consider these restrictions when
281determining whether a hashed index is preferred over an ordered one.
282</p>
283
284<p>
285Hashed indices replicate the interface as <code>std::unordered_set</code> and
286<code>std::unordered_multiset</code>, with only minor differences where required
287by the general constraints of <code>multi_index_container</code>s, and provide
288additional useful capabilities like in-place updating of elements.
289Check the <a href="../reference/hash_indices.html">reference</a> for a
290complete specification of the interface of hashed indices,
291and <a href="../examples.html#example8">example 8</a> and
292<a href="../examples.html#example9">example 9</a> for practical applications.
293</p>
294
295</p>
296
297<h3><a name="hash_unique_non_unique">Unique and non-unique variants</a></h3>
298
299<p>
300Just like ordered indices, hashed indices have unique and non-unique variants, selected
301with the specifiers <code>hashed_unique</code> and <code>hashed_non_unique</code>,
302respectively. In the latter case, elements with equivalent keys are kept together and can
303be jointly retrieved by means of the <code>equal_range</code> member function.
304</p>
305
306<h3><a name="hash_spec">Specification</a></h3>
307
308<p>
309Hashed indices specifiers have two alternative syntaxes, depending on whether
310<a href="basics.html#tagging">tags</a> are provided or not:
311</p>
312
313<blockquote><pre>
314<span class=special>(</span><span class=identifier>hashed_unique</span> <span class=special>|</span> <span class=identifier>hashed_non_unique</span><span class=special>)
315 </span><span class=special>&lt;[</span><i>(tag)</i><span class=special>[,</span><i>(key extractor)</i><span class=special>[,</span><i>(hash function)</i><span class=special>[,</span><i>(equality predicate)</i><span class=special>]]]]&gt;</span>
316
317<span class=special>(</span><span class=identifier>hashed_unique</span> <span class=special>|</span> <span class=identifier>hashed_non_unique</span><span class=special>)</span>
318 <span class=special>&lt;[</span><i>(key extractor)</i><span class=special>[,</span><i>(hash function)</i><span class=special>[,</span><i>(equality predicate)</i><span class=special>]]]&gt;</span>
319</pre></blockquote>
320
321<p>
322The key extractor parameter works in exactly the same way as for
323<a href="basics.html#key_extraction">ordered indices</a>; lookup, insertion,
324etc., are based on the key returned by the extractor rather than the whole
325element.
326</p>
327
328<p>
329The hash function is the very core of the fast lookup capabilities of this type of
330indices: a hasher is just a unary function object
331returning an <code>std::size_t</code> value for any given
332key. In general, it is impossible that every key map to a different hash value, for
333the space of keys can be greater than the number of permissible hash codes: what
334makes for a good hasher is that the probability of a collision (two different
335keys with the same hash value) is as close to zero as possible. This is a statistical
336property depending on the typical distribution of keys in a given application, so
337it is not feasible to have a general-purpose hash function with excellent results
338in <i>every</i> possible scenario; the default value for this parameter uses
339<a href="../../../functional/hash/index.html">Boost.Hash</a>, which often provides good
340enough results.
341</p>
342
343<p>
344The equality predicate is used to determine whether two keys are to be treated
345as the same. The default
346value <code>std::equal_to&lt;KeyFromValue::result_type&gt;</code> is in most
347cases exactly what is needed, so very rarely will you have to provide
348your own predicate. Note that hashed indices require that two
349equivalent keys have the same hash value, which
350in practice greatly reduces the freedom in choosing an equality predicate.
351</p>
352
353<h3><a name="hash_lookup">Lookup</a></h3>
354
355<p>
356The lookup interface of hashed indices consists in member functions
357<code>find</code>, <code>count</code> and <code>equal_range</code>.
358Note that <code>lower_bound</code> and <code>upper_bound</code> are not
359provided, as there is no intrinsic ordering of keys in this type of indices.
360</p>
361
362<p>
363Just as with ordered indices, these member functions take keys
364as their search arguments, rather than entire objects. Remember that
365ordered indices lookup operations are further augmented to accept
366<i>compatible keys</i>, which can roughly be regarded as "subkeys".
367For hashed indices, a concept of
368<a href="../reference/hash_indices.html#lookup">compatible key</a> is also
369supported, though its usefulness is much more limited: basically,
370a compatible key is an object which is entirely equivalent to
371a native object of <code>key_type</code> value, though maybe with
372a different internal representation:
373</p>
374
375<blockquote><pre>
376<span class=comment>// US SSN numbering scheme</span>
377<span class=keyword>struct</span> <span class=identifier>ssn</span>
378<span class=special>{</span>
379 <span class=identifier>ssn</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>area_no</span><span class=special>,</span><span class=keyword>int</span> <span class=identifier>group_no</span><span class=special>,</span><span class=keyword>int</span> <span class=identifier>serial_no</span><span class=special>):</span>
380 <span class=identifier>area_no</span><span class=special>(</span><span class=identifier>area_no</span><span class=special>),</span><span class=identifier>group_no</span><span class=special>(</span><span class=identifier>group_no</span><span class=special>),</span><span class=identifier>serial_no</span><span class=special>(</span><span class=identifier>serial_no</span><span class=special>)</span>
381 <span class=special>{}</span>
382
383 <span class=keyword>int</span> <span class=identifier>to_int</span><span class=special>()</span><span class=keyword>const</span>
384 <span class=special>{</span>
385 <span class=keyword>return</span> <span class=identifier>serial_no</span><span class=special>+</span><span class=number>10000</span><span class=special>*</span><span class=identifier>group_no</span><span class=special>+</span><span class=number>1000000</span><span class=special>*</span><span class=identifier>area_no</span><span class=special>;</span>
386 <span class=special>}</span>
387
388<span class=keyword>private</span><span class=special>:</span>
389 <span class=keyword>int</span> <span class=identifier>area_no</span><span class=special>;</span>
390 <span class=keyword>int</span> <span class=identifier>group_no</span><span class=special>;</span>
391 <span class=keyword>int</span> <span class=identifier>serial_no</span><span class=special>;</span>
392<span class=special>};</span>
393
394<span class=comment>// interoperability with SSNs in raw int form</span>
395
396<span class=keyword>struct</span> <span class=identifier>ssn_equal</span>
397<span class=special>{</span>
398 <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>const</span> <span class=identifier>ssn</span><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>int</span> <span class=identifier>y</span><span class=special>)</span><span class=keyword>const</span>
399 <span class=special>{</span>
400 <span class=keyword>return</span> <span class=identifier>x</span><span class=special>.</span><span class=identifier>to_int</span><span class=special>()==</span><span class=identifier>y</span><span class=special>;</span>
401 <span class=special>}</span>
402
403 <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=identifier>ssn</span><span class=special>&amp;</span> <span class=identifier>y</span><span class=special>)</span><span class=keyword>const</span>
404 <span class=special>{</span>
405 <span class=keyword>return</span> <span class=identifier>x</span><span class=special>==</span><span class=identifier>y</span><span class=special>.</span><span class=identifier>to_int</span><span class=special>();</span>
406 <span class=special>}</span>
407<span class=special>};</span>
408
409<span class=keyword>struct</span> <span class=identifier>ssn_hash</span>
410<span class=special>{</span>
411 <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>const</span> <span class=identifier>ssn</span><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>)</span><span class=keyword>const</span>
412 <span class=special>{</span>
413 <span class=keyword>return</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>hash</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;()(</span><span class=identifier>x</span><span class=special>.</span><span class=identifier>to_int</span><span class=special>());</span>
414 <span class=special>}</span>
415
416 <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</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>
417 <span class=special>{</span>
418 <span class=keyword>return</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>hash</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;()(</span><span class=identifier>x</span><span class=special>);</span>
419 <span class=special>}</span>
420<span class=special>};</span>
421
422<span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>2</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_ssn</span><span class=special>;</span>
423
424<span class=identifier>employee_set</span> <span class=identifier>es</span><span class=special>;</span>
425<span class=identifier>employee_set_by_ssn</span><span class=special>&amp;</span> <span class=identifier>ssn_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special>&lt;</span><span class=number>2</span><span class=special>&gt;();</span>
426<span class=special>...</span>
427<span class=comment>// find an employee by ssn</span>
428<span class=identifier>employee</span> <span class=identifier>e</span><span class=special>=*(</span><span class=identifier>ssn_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=identifier>ssn</span><span class=special>(</span><span class=number>12</span><span class=special>,</span><span class=number>1005</span><span class=special>,</span><span class=number>20678</span><span class=special>),</span><span class=identifier>ssn_hash</span><span class=special>(),</span><span class=identifier>ssn_equal</span><span class=special>()));</span>
429</pre></blockquote>
430
431<p>
432In the example, we provided a hash functor <code>ssn_hash</code> and an
433equality predicate <code>ssn_equal</code> allowing for interoperability
434between <code>ssn</code> objects and the raw <code>int</code>s stored as
435<code>SSN</code>s in <code>employee_set</code>.
436</p>
437
438<p>
439By far, the most useful application of compatible keys in the context
440of hashed indices lies in the fact that they allow for seamless usage of
441<a href="key_extraction.html#composite_keys">composite keys</a>.
442</p>
443
444<h3><a name="hash_updating">Updating</a></h3>
445
446<p>
447Hashed indices have
448<a href="../reference/hash_indices.html#replace"><code>replace</code></a>,
449<a href="../reference/hash_indices.html#modify"><code>modify</code></a> and
450<a href="../reference/hash_indices.html#modify_key"><code>modify_key</code></a>
451member functions, with the same functionality as in ordered indices.
452</p>
453
454<h3><a name="guarantees">Guarantees on iterator validity and exception safety</a></h3>
455
456<p>
457Due to the internal constraints imposed by the Boost.MultiIndex framework,
458hashed indices provide guarantees on iterator validity and
459exception safety that are actually stronger than required by the
460C++ standard with respect to unordered associative containers:
461<ul>
462 <li>Iterator validity is preserved in any case during insertion or rehashing:
463 C++ unordered associative containers can invalidate iterators when a rehash (implicit or explicit)
464 is performed.</li>
465 <li>Erasing an element or range of elements via iterators does not throw ever,
466 as the internal hash function and equality predicate objects are not actually
467 invoked.</li>
468 <li><code>rehash</code> provides the strong exception safety guarantee
469 unconditionally. The standard only warrants it for unordered associative containers if the internal hash function and
470 equality predicate objects do not throw. The somewhat surprising consequence
471 is that a standard-compliant <code>std::unordered_set</code> might erase
472 elements if an exception is thrown during rehashing!</li>
473</ul>
474In general, these stronger guarantees play in favor of the user's convenience,
475specially that which refers to iterator stability. A (hopefully minimal)
476degradation in performance might result in exchange for these commodities,
477though.
478</p>
479
480<h2><a name="rnd_indices">Random access indices</a></h2>
481
482<p>
483Random access indices offer the same kind of functionality as
484<a href="basics.html#seq_indices">sequenced indices</a>, with the extra advantages
485that their iterators are random access, and <code>operator[]</code>
486and <code>at()</code> are provided for accessing
487elements based on their position in the index. Let us rewrite a
488container used in a previous <a href="basics.html#list_fast_lookup">example</a>,
489using random access instead of sequenced indices:
490</p>
491
492<blockquote><pre>
493<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index_container</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
494<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>random_access_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
495<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>ordered_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
496<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>identity</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
497
498<span class=comment>// text container with fast lookup based on a random access index</span>
499<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
500 <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,</span>
501 <span class=identifier>indexed_by</span><span class=special>&lt;</span>
502 <span class=identifier>random_access</span><span class=special>&lt;&gt;,</span>
503 <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&gt;</span> <span class=special>&gt;</span>
504 <span class=special>&gt;</span>
505<span class=special>&gt;</span> <span class=identifier>text_container</span><span class=special>;</span>
506
507<span class=comment>// global text container object</span>
508<span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span>
509</pre></blockquote>
510
511<p>
512Random access capabilities allow us to efficiently write code
513like the following:
514</p>
515
516<blockquote><pre>
517<span class=keyword>void</span> <span class=identifier>print_page</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>page_num</span><span class=special>)</span>
518<span class=special>{</span>
519 <span class=keyword>static</span> <span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>words_per_page</span><span class=special>=</span><span class=number>50</span><span class=special>;</span>
520
521 <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>pos0</span><span class=special>=</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>min</span><span class=special>(</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>size</span><span class=special>(),</span><span class=identifier>page_num</span><span class=special>*</span><span class=identifier>words_per_page</span><span class=special>);</span>
522 <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>pos1</span><span class=special>=</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>min</span><span class=special>(</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>size</span><span class=special>(),</span><span class=identifier>pos0</span><span class=special>+</span><span class=identifier>words_per_page</span><span class=special>);</span>
523
524 <span class=comment>// note random access iterators can be added offsets</span>
525 <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span>
526 <span class=identifier>tc</span><span class=special>.</span><span class=identifier>begin</span><span class=special>()+</span><span class=identifier>pos0</span><span class=special>,</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>begin</span><span class=special>()+</span><span class=identifier>pos1</span><span class=special>,</span>
527 <span class=identifier>std</span><span class=special>::</span><span class=identifier>ostream_iterator</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&gt;(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>));</span>
528<span class=special>}</span>
529
530<span class=keyword>void</span> <span class=identifier>print_random_word</span><span class=special>()</span>
531<span class=special>{</span>
532 <span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>&lt;&lt;</span><span class=identifier>tc</span><span class=special>[</span><span class=identifier>rand</span><span class=special>()%</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>size</span><span class=special>()];</span>
533<span class=special>}</span>
534</pre></blockquote>
535
536<p>
537This added flexibility comes at a price: insertions and deletions at positions
538other than the end of the index have linear complexity, whereas these operations
539are constant time for sequenced indices. This situation is reminiscent of the
540differences in complexity behavior between <code>std::list</code> and
541<code>std::vector</code>: in the case of random access indices, however,
542insertions and deletions never incur any element copying, so the actual
543performance of these operations can be acceptable, despite the theoretical
544disadvantage with respect to sequenced indices.
545</p>
546
547<p>
548<a href="../examples.html#example10">Example 10</a> and
549<a href="../examples.html#example11">example 11</a> in the examples section put
550random access indices in practice.
551</p>
552
553<h3><a name="rnd_spec">Specification</a></h3>
554
555<p>
556Random access indices are specified with the <code>random_access</code> construct,
557where the <a href="basics.html#tagging">tag</a> parameter is, as usual, optional:
558</p>
559
560<blockquote><pre>
561<span class=identifier>random_access</span><span class=special>&lt;[</span><i>(tag)</i><span class=special>]&gt;</span>
562</pre></blockquote>
563
564<h3><a name="rnd_interface">Interface</a></h3>
565
566<p>
567All public functions offered by sequenced indices are also provided
568by random access indices, so that the latter can act as a drop-in replacement
569of the former (save with respect to their complexity bounds, as explained above).
570Besides, random access
571indices have <code>operator[]</code> and <code>at()</code> for positional
572access to the elements, and member functions
573<a href="../reference/rnd_indices.html#capacity_memfun"><code>capacity</code></a> and
574<a href="../reference/rnd_indices.html#reserve"><code>reserve</code></a>
575that control internal reallocation in a similar manner as the homonym
576facilities in <code>std::vector</code>. Check the
577<a href="../reference/rnd_indices.html">reference</a> for details.
578</p>
579
580<h3><a name="rnd_vs_vector">Comparison with <code>std::vector</code></a></h3>
581
582<p>
583It is tempting to see random access indices as an analogue of <code>std::vector</code>
584for use in Boost.MultiIndex, but this metaphor can be misleading, as both constructs,
585though similar in many respects, show important semantic differences. An
586advantage of random access indices is that their iterators, as well as references
587to their elements, are <i>stable</i>, that is, they remain valid after any insertions
588or deletions. On the other hand, random access indices have several disadvantages with
589respect to <code>std::vector</code>s:
590<ul>
591 <li>They do not provide <i>memory contiguity</i>, a property
592 of <code>std::vector</code>s by which elements are stored adjacent to one
593 another in a single block of memory.
594 </li>
595 <li>As usual in Boost.MultiIndex, elements of random access indices are immutable
596 and can only be modified through member functions
597 <a href="../reference/rnd_indices.html#replace"><code>replace</code></a> and
598 <a href="../reference/rnd_indices.html#modify"><code>modify</code></a>.
599 This precludes the usage of many mutating
600 algorithms that are nonetheless applicable to <code>std::vector</code>s.
601 </li>
602</ul>
603The latter shortcoming can be partially remedied by means of the
604<a href="#rearrange">rearranging interface</a> these indices provide.
605</p>
606
607<p>
608In general, it is more instructive to regard random access indices as
609a variation of sequenced indices providing random access semantics, instead
610of insisting on the <code>std::vector</code> analogy.
611</p>
612
613<h2><a name="rearrange">Index rearranging</a></h2>
614
615<p>
616By design, index elements are immutable, i.e. iterators only grant
617<code>const</code> access to them, and only through the provided
618updating interface (<code>replace</code>, <code>modify</code> and
619<code>modify_key</code>) can the elements be modified. This restriction
620is set up so that the internal invariants of key-based indices are
621not broken (for instance, ascending order traversal in ordered
622indices), but induces important limitations in non key-based indices:
623</p>
624
625<blockquote><pre>
626<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
627 <span class=keyword>int</span><span class=special>,</span>
628 <span class=identifier>indexed_by</span><span class=special>&lt;</span>
629 <span class=identifier>random_access</span><span class=special>&lt;&gt;,</span>
630 <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;</span>
631 <span class=special>&gt;</span>
632<span class=special>&gt;</span> <span class=identifier>container</span><span class=special>;</span>
633
634<span class=identifier>container</span> <span class=identifier>c</span><span class=special>;</span>
635<span class=identifier>std</span><span class=special>::</span><span class=identifier>mt19937</span> <span class=identifier>rng</span><span class=special>;</span>
636<span class=special>...</span>
637<span class=comment>// compiler error: assignment to read-only objects</span>
638<span class=identifier>std</span><span class=special>::</span><span class=identifier>shuffle</span><span class=special>(</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>rng</span><span class=special>);</span>
639</pre></blockquote>
640
641<p>
642What is unfortunate about the previous example is that the operation
643performed by <code>std::shuffle</code> is potentially compatible
644with <code>multi_index_container</code> invariants, as its result can be
645described by a permutation of the elements in the random access index
646with no actual modifications to the elements themselves. There are many
647more examples of such compatible algorithms in the C++ standard library,
648like for instance all sorting and partition functions.
649</p>
650
651<p>
652Sequenced and random access indices provide a means to take advantage
653of such external algorithms. In order to introduce this facility we need
654a preliminary concept: a <i>view</i> of an index is defined as
655some iterator range [<code>first</code>,<code>last</code>) over the
656elements of the index such that all its elements are contained in the
657range exactly once. Continuing with our example, we can apply
658<code>std::shuffle</code> on an ad hoc view obtained from the
659container:
660</p>
661
662<blockquote><pre>
663<span class=comment>// note that the elements of the view are not copies of the elements
664// in c, but references to them</span>
665<span class=identifier>std</span><span class=special>::</span><span class=identifier>vector</span><span class=special>&lt;</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>reference_wrapper</span><span class=special>&lt;</span><span class=keyword>const</span> <span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=identifier>v</span><span class=special>;</span>
666<span class=identifier>BOOST_FOREACH</span><span class=special>(</span><span class=keyword>const</span> <span class=keyword>int</span><span class=special>&amp;</span> <span class=identifier>i</span><span class=special>,</span><span class=identifier>c</span><span class=special>)</span><span class=identifier>v</span><span class=special>.</span><span class=identifier>push_back</span><span class=special>(</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>cref</span><span class=special>(</span><span class=identifier>i</span><span class=special>));</span>
667
668<span class=comment>// this compiles OK, as reference_wrappers are swappable</span>
669<span class=identifier>std</span><span class=special>::</span><span class=identifier>shuffle</span><span class=special>(</span><span class=identifier>v</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>v</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>rng</span><span class=special>);</span>
670</pre></blockquote>
671
672<p>
673Elements of <code>v</code> are <code>reference_wrapper</code>s (from
674<a href="../../../../doc/html/ref.html">Boost.Ref</a>) to the actual elements
675in the multi-index container. These objects still do not allow modification
676of the referenced entities, but they are swappable,
677which is the only requirement <code>std::shuffle</code> imposes. Once
678we have our desired rearrange stored in the view, we can transfer it to
679the container with
680</p>
681
682<blockquote><pre>
683<span class=identifier>c</span><span class=special>.</span><span class=identifier>rearrange</span><span class=special>(</span><span class=identifier>v</span><span class=special>.</span><span class=identifier>begin</span><span class=special>());</span>
684</pre></blockquote>
685
686<p>
687<code>rearrange</code> accepts an input iterator signaling the beginning
688of the external view (and end iterator is not needed since the length of
689the view is the same as that of the index) and internally relocates the
690elements of the index so that their traversal order matches the view.
691Albeit with some circumventions, <code>rearrange</code> allows for the
692application of a varied range of algorithms to non key-based indices.
693Please note that the view concept is very general, and in no way tied
694to the particular implementation example shown above. For instance, indices
695of a <code>multi_index_container</code> are indeed views with respect to
696its non key-based indices:
697</p>
698
699<blockquote><pre>
700<span class=comment>// rearrange as index #1 (ascending order)</span>
701<span class=identifier>c</span><span class=special>.</span><span class=identifier>rearrange</span><span class=special>(</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>get</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;().</span><span class=identifier>begin</span><span class=special>());</span>
702
703<span class=comment>// rearrange in descending order</span>
704<span class=identifier>c</span><span class=special>.</span><span class=identifier>rearrange</span><span class=special>(</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>get</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;().</span><span class=identifier>rbegin</span><span class=special>());</span>
705</pre></blockquote>
706
707<p>
708The only important requirement imposed on views is that they must be
709<i>free</i>, i.e. they are not affected by relocations on the base index:
710thus, <code>rearrange</code> does not accept the following:
711</p>
712
713<blockquote><pre>
714<span class=comment>// undefined behavior: [rbegin(),rend()) is not free with respect
715// to the base index</span>
716<span class=identifier>c</span><span class=special>.</span><span class=identifier>rearrange</span><span class=special>(</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>rbegin</span><span class=special>());</span>
717</pre></blockquote>
718
719<p>
720The view concept is defined in detail in the
721<a href="../reference/indices.html#views">reference</a>.
722See <a href="../examples.html#example11">example 11</a> in the examples section
723for a demonstration of use of <code>rearrange</code>.
724</p>
725
726<h2><a name="iterator_to"><code>iterator_to</code></a></h2>
727
728<p>
729All indices of Boost.MultiIndex provide a member function called <code>iterator_to</code>
730which returns an iterator to a given element of the container:
731</p>
732
733<blockquote><pre>
734<span class=identifier>multi_index_container</span><span class=special>&lt;</span>
735 <span class=keyword>int</span><span class=special>,</span>
736 <span class=identifier>indexed_by</span><span class=special>&lt;</span><span class=identifier>sequenced</span><span class=special>&lt;&gt;</span> <span class=special>&gt;</span>
737<span class=special>&gt;</span> <span class=identifier>c</span><span class=special>;</span>
738<span class=special>...</span>
739<span class=comment>// convoluted way to do c.pop_back()</span>
740<span class=identifier>c</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>iterator_to</span><span class=special>(</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>back</span><span class=special>()));</span>
741
742<span class=comment>// The following, though similar to the previous code,
743// does not work: iterator_to accepts a reference to
744// the element in the container, not a copy.</span>
745<span class=keyword>int</span> <span class=identifier>x</span><span class=special>=</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>back</span><span class=special>();</span>
746<span class=identifier>c</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>iterator_to</span><span class=special>(</span><span class=identifier>x</span><span class=special>));</span> <span class=comment>// run-time failure ensues</span>
747</pre></blockquote>
748
749<p>
750<code>iterator_to</code> provides a way to retrieve an iterator to an element
751from a pointer to the element, thus making iterators and pointers interchangeable
752for the purposes of element pointing (not so for traversal) in many situations.
753This notwithstanding, it is not the aim of <code>iterator_to</code> to
754promote the usage of pointers as substitutes for real iterators: the latter are
755specifically designed for handling the elements of a container,
756and not only benefit from the iterator orientation of container interfaces,
757but are also capable of exposing many more programming bugs than raw pointers, both
758at compile and run time. <code>iterator_to</code> is thus meant to be used
759in scenarios where access via iterators is not suitable or desireable:
760<ul>
761 <li>Interoperability with preexisting APIs based on pointers or references.</li>
762 <li>Publication of pointer-based interfaces (for instance, when
763 designing a C-compatible library).
764 </li>
765 <li>The exposure of pointers in place of iterators can act as a <i>type
766 erasure</i> barrier effectively decoupling the user of the code
767 from the implementation detail of which particular container is being
768 used. Similar techniques, like the famous Pimpl idiom, are used
769 in large projects to reduce dependencies and build times.
770 </li>
771 <li>Self-referencing contexts where an element acts upon its owner
772 container and no iterator to itself is available.
773 </li>
774</ul>
775</p>
776
777<h2><a name="ordered_node_compression">Ordered indices node compression</a></h2>
778
779<p>
780Ordered and ranked indices are implemented by means of a data structure
781known as a <i>red-black tree</i>. Nodes of a red-back tree contain pointers
782to the parent and the two children nodes, plus a 1-bit field referred to as
783the <i>node color</i> (hence the name of the structure). Due to alignment
784issues, on most architectures the color field occupies one entire word, that is,
7854 bytes in 32-bit systems and 8 bytes in 64-bit environments. This waste
786of space can be avoided by embedding the color bit inside one of the
787node pointers, provided not all the bits of the pointer representation contain
788useful information: this is precisely the case in many architectures where
789such nodes are aligned to even addresses, which implies that the least
790significant bit of the address must always be zero.
791</p>
792
793<p>
794Boost.MultiIndex ordered and ranked indices implement this type of node compression
795whenever applicable. As compared with common implementations of the STL
796container <code>std::set</code>, node compression can
797result in a reduction of header overload by 25% (from 16 to 12 bytes on
798typical 32-bit architectures, and from 32 to 24 bytes on 64-bit systems).
799The impact on performance of this optimization has been checked to be negligible
800for moderately sized containers, whereas containers with many elements (hundreds
801of thousands or more) perform faster with this optimization, most likely due to
802L1 and L2 cache effects.
803</p>
804
805<p>
806Node compression can be disabled by globally setting the macro
807<code>BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES</code>.
808</p>
809
810<hr>
811
812<div class="prev_link"><a href="basics.html"><img src="../prev.gif" alt="basics" border="0"><br>
813Basics
814</a></div>
815<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
816Boost.MultiIndex tutorial
817</a></div>
818<div class="next_link"><a href="key_extraction.html"><img src="../next.gif" alt="key estraction" border="0"><br>
819Key extraction
820</a></div><br clear="all" style="clear: all;">
821
822<br>
823
824<p>Revised August 29th 2017</p>
825
826<p>&copy; Copyright 2003-2017 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
827Distributed under the Boost Software
828License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
829LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
830http://www.boost.org/LICENSE_1_0.txt</a>)
831</p>
832
833</body>
834</html>