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