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