ceph/src/boost/libs/multi_index/doc/tutorial/indices.html

   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>
  19 Basics
  20 </a></div>
  21 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
  22 Boost.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>
  25 Key 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>
  64 Boost.MultiIndex provides six different index types, which can be classified as
  65 shown in the table below. <a href="basics.html#ord_indices">Ordered</a> and
  66 <a href="basics.html#seq_indices">sequenced</a> indices,
  67 which are the most commonly used, have been explained in the basics section;
  68 the rest of index types can be regarded as variations of the former providing
  69 some 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>
 111 Key-based indices, of which ordered indices are the usual example, provide
 112 efficient 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>
 115 utility classes allowing for the specification of such keys. Fast lookup
 116 imposes an internally managed order on these indices that the user is not
 117 allowed to modify; non key-based indices, on the other hand, can be freely
 118 rearranged at the expense of lacking lookup facilities. Sequenced indices,
 119 modeled after the interface of <code>std::list</code>, are the customary
 120 example of a non key-based index.
 121 </p>
 122
 123 <h2><a name="rnk_indices">Ranked indices</a></h2>
 124
 125 <p>
 126 Suppose we have a <code>std::multiset</code> of numbers and we want to output
 127 the 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>
 143 The problem with this code is that getting to the beginning of the desired subsequence
 144 involves a linear traversal of the container. Ranked indices provide the mechanisms to do this
 145 much 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
 165 from the beginning of the index, is <code>n</code>, and does so efficiently in logarithmic time.
 166 Conversely, <code>rank(it)</code> computes in logarithmic time the rank of the element
 167 pointed 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>
 176 Ranked indices provide the same interface as ordered indices plus several rank-related operations.
 177 The cost of this extra functionality is higher memory consumption due to some internal additional
 178 data (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
 181 constant.
 182 The <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>
 188 The specification of ranked indices is done exactly as with <a href="basics.html#ord_spec">ordered indices</a>,
 189 except 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>
 203 Besides <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>
 211 that behave as their normal
 212 <a href="basics.html#special_lookup">lookup</a> and <a href="basics.html#range">range retrieval</a>
 213 counterparts (<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>
 225 You 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
 228 alternative formulations.
 229 </p>
 230
 231 <h2><a name="hashed_indices">Hashed indices</a></h2>
 232
 233 <p>
 234 Hashed indices constitute a trade-off with respect to ordered indices: if correctly used,
 235 they provide much faster lookup of elements, at the expense of losing sorting
 236 information.
 237 Let us revisit our <code>employee_set</code> example: suppose a field for storing
 238 the Social Security number is added, with the requisite that lookup by this
 239 number should be as fast as possible. Instead of the usual ordered index, a
 240 hashed 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>
 278 Note that the hashed index does not guarantee any particular ordering of the
 279 elements: so, for instance, we cannot efficiently query the employees whose SSN is
 280 greater than a given number. Usually, you must consider these restrictions when
 281 determining whether a hashed index is preferred over an ordered one.
 282 </p>
 283
 284 <p>
 285 Hashed indices replicate the interface as <code>std::unordered_set</code> and
 286 <code>std::unordered_multiset</code>, with only minor differences where required
 287 by the general constraints of <code>multi_index_container</code>s, and provide
 288 additional useful capabilities like in-place updating of elements.
 289 Check the <a href="../reference/hash_indices.html">reference</a> for a
 290 complete specification of the interface of hashed indices,
 291 and <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>
 300 Just like ordered indices, hashed indices have unique and non-unique variants, selected
 301 with the specifiers <code>hashed_unique</code> and <code>hashed_non_unique</code>,
 302 respectively. In the latter case, elements with equivalent keys are kept together and can
 303 be 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>
 309 Hashed 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>
 322 The key extractor parameter works in exactly the same way as for
 323 <a href="basics.html#key_extraction">ordered indices</a>; lookup, insertion,
 324 etc., are based on the key returned by the extractor rather than the whole
 325 element.
 326 </p>
 327
 328 <p>
 329 The hash function is the very core of the fast lookup capabilities of this type of
 330 indices: a hasher is just a unary function object
 331 returning an <code>std::size_t</code> value for any given
 332 key. In general, it is impossible that every key map to a different hash value, for
 333 the space of keys can be greater than the number of permissible hash codes: what
 334 makes for a good hasher is that the probability of a collision (two different
 335 keys with the same hash value) is as close to zero as possible. This is a statistical
 336 property depending on the typical distribution of keys in a given application, so
 337 it is not feasible to have a general-purpose hash function with excellent results
 338 in <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
 340 enough results.
 341 </p>
 342
 343 <p>
 344 The equality predicate is used to determine whether two keys are to be treated
 345 as the same. The default
 346 value <code>std::equal_to&lt;KeyFromValue::result_type&gt;</code> is in most
 347 cases exactly what is needed, so very rarely will you have to provide
 348 your own predicate. Note that hashed indices require that two
 349 equivalent keys have the same hash value, which
 350 in 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>
 356 The lookup interface of hashed indices consists in member functions
 357 <code>find</code>, <code>count</code> and <code>equal_range</code>.
 358 Note that <code>lower_bound</code> and <code>upper_bound</code> are not
 359 provided, as there is no intrinsic ordering of keys in this type of indices.
 360 </p>
 361
 362 <p>
 363 Just as with ordered indices, these member functions take keys
 364 as their search arguments, rather than entire objects. Remember that
 365 ordered indices lookup operations are further augmented to accept
 366 <i>compatible keys</i>, which can roughly be regarded as "subkeys".
 367 For hashed indices, a concept of
 368 <a href="../reference/hash_indices.html#lookup">compatible key</a> is also
 369 supported, though its usefulness is much more limited: basically,
 370 a compatible key is an object which is entirely equivalent to
 371 a native object of <code>key_type</code> value, though maybe with
 372 a 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>
 432 In the example, we provided a hash functor <code>ssn_hash</code> and an
 433 equality predicate <code>ssn_equal</code> allowing for interoperability
 434 between <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>
 439 By far, the most useful application of compatible keys in the context
 440 of 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>
 447 Hashed 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>
 451 member 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>
 457 Due to the internal constraints imposed by the Boost.MultiIndex framework,
 458 hashed indices provide guarantees on iterator validity and
 459 exception safety that are actually stronger than required by the
 460 C++ 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>
 474 In general, these stronger guarantees play in favor of the user's convenience,
 475 specially that which refers to iterator stability. A (hopefully minimal)
 476 degradation in performance might result in exchange for these commodities,
 477 though.
 478 </p>
 479
 480 <h2><a name="rnd_indices">Random access indices</a></h2>
 481
 482 <p>
 483 Random access indices offer the same kind of functionality as
 484 <a href="basics.html#seq_indices">sequenced indices</a>, with the extra advantages
 485 that their iterators are random access, and <code>operator[]</code>
 486 and <code>at()</code> are provided for accessing
 487 elements based on their position in the index. Let us rewrite a
 488 container used in a previous <a href="basics.html#list_fast_lookup">example</a>,
 489 using 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>
 512 Random access capabilities allow us to efficiently write code
 513 like 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>
 537 This added flexibility comes at a price: insertions and deletions at positions
 538 other than the end of the index have linear complexity, whereas these operations
 539 are constant time for sequenced indices. This situation is reminiscent of the
 540 differences in complexity behavior between <code>std::list</code> and
 541 <code>std::vector</code>: in the case of random access indices, however,
 542 insertions and deletions never incur any element copying, so the actual
 543 performance of these operations can be acceptable, despite the theoretical
 544 disadvantage 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
 550 random access indices in practice.
 551 </p>
 552
 553 <h3><a name="rnd_spec">Specification</a></h3>
 554
 555 <p>
 556 Random access indices are specified with the <code>random_access</code> construct,
 557 where 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>
 567 All public functions offered by sequenced indices are also provided
 568 by random access indices, so that the latter can act as a drop-in replacement
 569 of the former (save with respect to their complexity bounds, as explained above).
 570 Besides, random access
 571 indices have <code>operator[]</code> and <code>at()</code> for positional
 572 access 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>
 575 that control internal reallocation in a similar manner as the homonym
 576 facilities 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>
 583 It is tempting to see random access indices as an analogue of <code>std::vector</code>
 584 for use in Boost.MultiIndex, but this metaphor can be misleading, as both constructs,
 585 though similar in many respects, show important semantic differences. An
 586 advantage of random access indices is that their iterators, as well as references
 587 to their elements, are <i>stable</i>, that is, they remain valid after any insertions
 588 or deletions. On the other hand, random access indices have several disadvantages with
 589 respect 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>
 603 The 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>
 608 In general, it is more instructive to regard random access indices as
 609 a variation of sequenced indices providing random access semantics, instead
 610 of insisting on the <code>std::vector</code> analogy.
 611 </p>
 612
 613 <h2><a name="rearrange">Index rearranging</a></h2>
 614
 615 <p>
 616 By design, index elements are immutable, i.e. iterators only grant
 617 <code>const</code> access to them, and only through the provided
 618 updating interface (<code>replace</code>, <code>modify</code> and
 619 <code>modify_key</code>) can the elements be modified. This restriction
 620 is set up so that the internal invariants of key-based indices are
 621 not broken (for instance, ascending order traversal in ordered
 622 indices), 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>
 642 What is unfortunate about the previous example is that the operation
 643 performed by <code>std::shuffle</code> is potentially compatible
 644 with <code>multi_index_container</code> invariants, as its result can be
 645 described by a permutation of the elements in the random access index
 646 with no actual modifications to the elements themselves. There are many
 647 more examples of such compatible algorithms in the C++ standard library,
 648 like for instance all sorting and partition functions.
 649 </p>
 650
 651 <p>
 652 Sequenced and random access indices provide a means to take advantage
 653 of such external algorithms. In order to introduce this facility we need
 654 a preliminary concept: a <i>view</i> of an index is defined as
 655 some iterator range [<code>first</code>,<code>last</code>) over the
 656 elements of the index such that all its elements are contained in the
 657 range exactly once. Continuing with our example, we can apply
 658 <code>std::random_suffle</code> on an ad hoc view obtained from the
 659 container:
 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>
 673 Elements 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
 675 in the multi-index container. These objects still do not allow modification
 676 of the referenced entities, but they are swappable,
 677 which is the only requirement <code>std::shuffle</code> imposes. Once
 678 we have our desired rearrange stored in the view, we can transfer it to
 679 the 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
 688 of the external view (and end iterator is not needed since the length of
 689 the view is the same as that of the index) and internally relocates the
 690 elements of the index so that their traversal order matches the view.
 691 Albeit with some circumventions, <code>rearrange</code> allows for the
 692 application of a varied range of algorithms to non key-based indices.
 693 Please note that the view concept is very general, and in no way tied
 694 to the particular implementation example shown above. For instance, indices
 695 of a <code>multi_index_container</code> are indeed views with respect to
 696 its 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>
 708 The 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:
 710 thus, <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>
 720 The view concept is defined in detail in the
 721 <a href="../reference/indices.html#views">reference</a>.
 722 See <a href="../examples.html#example11">example 11</a> in the examples section
 723 for 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>
 729 All indices of Boost.MultiIndex provide a member function called <code>iterator_to</code>
 730 which 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
 751 from a pointer to the element, thus making iterators and pointers interchangeable
 752 for the purposes of element pointing (not so for traversal) in many situations.
 753 This notwithstanding, it is not the aim of <code>iterator_to</code> to
 754 promote the usage of pointers as substitutes for real iterators: the latter are
 755 specifically designed for handling the elements of a container,
 756 and not only benefit from the iterator orientation of container interfaces,
 757 but are also capable of exposing many more programming bugs than raw pointers, both
 758 at compile and run time. <code>iterator_to</code> is thus meant to be used
 759 in 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>
 780 Ordered and ranked indices are implemented by means of a data structure
 781 known as a <i>red-black tree</i>. Nodes of a red-back tree contain pointers
 782 to the parent and the two children nodes, plus a 1-bit field referred to as
 783 the <i>node color</i> (hence the name of the structure). Due to alignment
 784 issues, on most architectures the color field occupies one entire word, that is,
 785 4 bytes in 32-bit systems and 8 bytes in 64-bit environments. This waste
 786 of space can be avoided by embedding the color bit inside one of the
 787 node pointers, provided not all the bits of the pointer representation contain
 788 useful information: this is precisely the case in many architectures where
 789 such nodes are aligned to even addresses, which implies that the least
 790 significant bit of the address must always be zero.
 791 </p>
 792
 793 <p>
 794 Boost.MultiIndex ordered and ranked indices implement this type of node compression
 795 whenever applicable. As compared with common implementations of the STL
 796 container <code>std::set</code>, node compression can
 797 result in a reduction of header overload by 25% (from 16 to 12 bytes on
 798 typical 32-bit architectures, and from 32 to 24 bytes on 64-bit systems).
 799 The impact on performance of this optimization has been checked to be negligible
 800 for moderately sized containers, whereas containers with many elements (hundreds
 801 of thousands or more) perform faster with this optimization, most likely due to
 802 L1 and L2 cache effects.
 803 </p>
 804
 805 <p>
 806 Node 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>
 813 Basics
 814 </a></div>
 815 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
 816 Boost.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>
 819 Key extraction
 820 </a></div><br clear="all" style="clear: all;">
 821
 822 <br>
 823
 824 <p>Revised August 19th 2015</p>
 825
 826 <p>&copy; Copyright 2003-2015 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
 827 Distributed under the Boost Software
 828 License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
 829 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
 830 http://www.boost.org/LICENSE_1_0.txt</a>)
 831 </p>
 832
 833 </body>
 834 </html>