[ceph.git] / ceph / src / boost / libs / multi_index / doc / tutorial / indices.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Boost.MultiIndex Documentation - Tutorial - Index types</title>
<link rel="stylesheet" href="../style.css" type="text/css">
<link rel="start" href="../index.html">
<link rel="prev" href="basics.html">
<link rel="up" href="index.html">
<link rel="next" href="key_extraction.html">
</head>

<body>
<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
"middle" width="277" height="86">Boost.MultiIndex Tutorial: Index types</h1>

<div class="prev_link"><a href="basics.html"><img src="../prev.gif" alt="basics" border="0"><br>
Basics
</a></div>
<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
Boost.MultiIndex tutorial
</a></div>
<div class="next_link"><a href="key_extraction.html"><img src="../next.gif" alt="key estraction" border="0"><br>
Key extraction
</a></div><br clear="all" style="clear: all;">

<hr>

<h2>Contents</h2>

<ul>
  <li><a href="#classification">Classification</a>
  <li><a href="#rnk_indices">Ranked indices</a>
    <ul>
      <li><a href="#rnk_spec">Specification</a></li>
      <li><a href="#rnk_ops">Rank operations</a></li>
    </ul>
  </li>
  <li><a href="#hashed_indices">Hashed indices</a>
    <ul>
      <li><a href="#hash_unique_non_unique">Unique and non-unique variants</a></li>
      <li><a href="#hash_spec">Specification</a></li>
      <li><a href="#hash_lookup">Lookup</a></li>
      <li><a href="#hash_updating">Updating</a></li>
      <li><a href="#guarantees">Guarantees on iterator validity and exception safety</a></li>
    </ul>
  </li>
  <li><a href="#rnd_indices">Random access indices</a>
    <ul>
      <li><a href="#rnd_spec">Specification</a></li>
	  <li><a href="#rnd_interface">Interface</a></li>
      <li><a href="#rnd_vs_vector">Comparison with <code>std::vector</code></a></li>
	</ul>
  </li>
  <li><a href="#rearrange">Index rearranging</a></li>
  <li><a href="#iterator_to"><code>iterator_to</code></a></li>
  <li><a href="#ordered_node_compression">Ordered indices node compression</a></li>
</ul>

<h2><a name="classification">Classification</a></h2>

<p>
Boost.MultiIndex provides six different index types, which can be classified as
shown in the table below. <a href="basics.html#ord_indices">Ordered</a> and
<a href="basics.html#seq_indices">sequenced</a> indices,
which are the most commonly used, have been explained in the basics section;
the rest of index types can be regarded as variations of the former providing
some added benefits, functionally or in the area of performance.
</p>

<p align="center">
<table cellspacing="0">
  <caption><b>Boost.MultiIndex indices.</b></caption>
<tr>
  <th align="center"colspan="2">type</th>
  <th align="center">specifier</th>
</tr>
<tr>
  <td align="center" rowspan="6">&nbsp;&nbsp;key-based&nbsp;&nbsp;</td>
  <td align="center" rowspan="4">&nbsp;&nbsp;ordered&nbsp;&nbsp;</td>
  <td align="center">&nbsp;&nbsp;<code>ordered_unique</code>&nbsp;&nbsp;</td>
</tr>
<tr class="odd_tr">
  <td align="center">&nbsp;&nbsp;<code>ordered_non_unique</code>&nbsp;&nbsp;</td>
</tr>
<tr>
  <td align="center">&nbsp;&nbsp;<code>ranked_unique</code>&nbsp;&nbsp;</td>
</tr>
<tr class="odd_tr">
  <td align="center">&nbsp;&nbsp;<code>ranked_non_unique</code>&nbsp;&nbsp;</td>
</tr>
<tr>
  <td align="center" rowspan="2">&nbsp;&nbsp;hashed&nbsp;&nbsp;</td>
  <td align="center">&nbsp;&nbsp;<code>hashed_unique</code>&nbsp;&nbsp;</td>
</tr>
<tr class="odd_tr">
  <td align="center">&nbsp;&nbsp;<code>hashed_non_unique</code>&nbsp;&nbsp;</td>
</tr>
<tr>
  <td align="center" rowspan="2" colspan="2">&nbsp;&nbsp;non key-based&nbsp;&nbsp;</td>
  <td align="center"><code>&nbsp;&nbsp;sequenced&nbsp;&nbsp;</code></td>
</tr>
<tr class="odd_tr">
  <td align="center"><code>&nbsp;&nbsp;random_access&nbsp;&nbsp;</code></td>
</tr>
</table>
</p>

<p>
Key-based indices, of which ordered indices are the usual example, provide
efficient lookup of elements based on some piece of information called the
<i>element key</i>: there is an extensive suite of
<a href="key_extraction.html">key extraction</a>
utility classes allowing for the specification of such keys. Fast lookup
imposes an internally managed order on these indices that the user is not
allowed to modify; non key-based indices, on the other hand, can be freely
rearranged at the expense of lacking lookup facilities. Sequenced indices,
modeled after the interface of <code>std::list</code>, are the customary
example of a non key-based index.
</p>

<h2><a name="rnk_indices">Ranked indices</a></h2>

<p>
Suppose we have a <code>std::multiset</code> of numbers and we want to output
the values above the 75h <a href="http://en.wikipedia.org/wiki/Percentile">percentile</a>:
</p>

<blockquote><pre>
<span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>multiset</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=identifier>int_multiset</span><span class=special>;</span>

<span class=keyword>void</span> <span class=identifier>output_above_75th_percentile</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>int_multiset</span><span class=special>&amp;</span> <span class=identifier>s</span><span class=special>)</span>
<span class=special>{</span>
  <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>
  <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>

  <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>ostream_iterator</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>,</span><span class=string>&quot;\n&quot;</span><span class=special>));</span>
<span class=special>}</span>
</pre></blockquote>

<p>
The problem with this code is that getting to the beginning of the desired subsequence
involves a linear traversal of the container. Ranked indices provide the mechanisms to do this
much faster: 
</p>

<blockquote><pre>
<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
  <span class=keyword>int</span><span class=special>,</span>
  <span class=identifier>indexed_by</span><span class=special>&lt;</span>
    <span class=identifier>ranked_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;</span>
  <span class=special>&gt;</span>
<span class=special>&gt;</span> <span class=identifier>int_multiset</span><span class=special>;</span>

<span class=keyword>void</span> <span class=identifier>output_above_75th_percentile</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>int_multiset</span><span class=special>&amp;</span> <span class=identifier>s</span><span class=special>)</span>
<span class=special>{</span>
  <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>
  <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>ostream_iterator</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>,</span><span class=string>&quot;\n&quot;</span><span class=special>));</span>
<span class=special>}</span>
</pre></blockquote>

<p>
<code>nth(n)</code> returns an iterator to the element whose <i>rank</i>, i.e. its distance
from the beginning of the index, is <code>n</code>, and does so efficiently in logarithmic time.
Conversely, <code>rank(it)</code> computes in logarithmic time the rank of the element
pointed to by <code>it</code>, or <code>size()</code> if <code>it==end()</code>.
</p>

<blockquote><pre>
<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>
<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>
</pre></blockquote>

<p>
Ranked indices provide the same interface as ordered indices plus several rank-related operations.
The cost of this extra functionality is higher memory consumption due to some internal additional
data (one word per element) and somewhat longer execution times in insertion and erasure
&#8212;in particular, erasing an element takes time proportional to <code>log(n)</code>, where
<code>n</code> is the number of elements in the index, whereas for ordered indices this time is
constant.
The <a href="../reference/rnk_indices.html">reference</a> describes these indices in complete detail.
</p>

<h3><a name="rnk_spec">Specification</a></h3>

<p>
The specification of ranked indices is done exactly as with <a href="basics.html#ord_spec">ordered indices</a>,
except that <code>ranked_unique</code> and <code>ranked_non_unique</code> are used instead.
</p>

<blockquote><pre>
<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><span class=special>&lt;[</span><i>(tag)</i><span class=special>[,</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]]&gt;</span>

<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>
  <span class=special>&lt;[</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]&gt;</span>
</pre></blockquote>

<h3><a name="rnk_ops">Rank operations</a></h3>

<p>
Besides <code>nth</code> and <code>rank</code>, ranked indices provide member functions
<ul>
  <li><code>find_rank</code>,</li>
  <li><code>lower_bound_rank</code>,</li>
  <li><code>upper_bound_rank</code>,</li>
  <li><code>equal_range_rank</code> and </li>
  <li><code>range_rank</code></li>
</ul>
that behave as their normal
<a href="basics.html#special_lookup">lookup</a> and <a href="basics.html#range">range retrieval</a>
counterparts (<code>find</code>, <code>lower_bound</code> etc.) but return ranks rather than iterators.
</p>

<blockquote><pre>
<span class=keyword>void</span> <span class=identifier>percentile</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>n</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>int_multiset</span><span class=special>&amp;</span> <span class=identifier>s</span><span class=special>)</span>
<span class=special>{</span>
  <span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>&lt;&lt;</span><span class=identifier>n</span><span class=special>&lt;&lt;</span><span class=string>&quot; lies in the &quot;</span><span class=special>&lt;&lt;</span>
    <span class=identifier>s</span><span class=special>.</span><span class=identifier>upper_bound_rank</span><span class=special>(</span><span class=identifier>n</span><span class=special>)*</span><span class=number>100.0</span><span class=special>/</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>size</span><span class=special>()&lt;&lt;</span><span class=string>&quot; percentile\n&quot;</span><span class=special>;</span>
<span class=special>}</span>
</pre></blockquote>

<p>
You might think that <code>upper_bound_rank(n)</code> is mere shorthand for
<code>rank(upper_bound(n))</code>: in reality, though, you should prefer using
<code>*_rank</code> operations directly as they run faster than the
alternative formulations.
</p>

<h2><a name="hashed_indices">Hashed indices</a></h2>

<p>
Hashed indices constitute a trade-off with respect to ordered indices: if correctly used,
they provide much faster lookup of elements, at the expense of losing sorting
information. 
Let us revisit our <code>employee_set</code> example: suppose a field for storing
the Social Security number is added, with the requisite that lookup by this
number should be as fast as possible. Instead of the usual ordered index, a
hashed index can be resorted to:
</p>

<blockquote><pre>
<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>
<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>
<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>
<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>
<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>

<span class=keyword>struct</span> <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=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
  <span class=keyword>int</span>         <span class=identifier>ssnumber</span><span class=special>;</span>

  <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>
    <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>

  <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>
<span class=special>};</span>

<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
  <span class=identifier>employee</span><span class=special>,</span>
  <span class=identifier>indexed_by</span><span class=special>&lt;</span>
    <span class=comment>// sort by employee::operator&lt;</span>
    <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>
    
    <span class=comment>// sort by less&lt;string&gt; on name</span>
    <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>
    
    <span class=comment>// hashed on ssnumber</span>
    <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>
  <span class=special>&gt;</span>
<span class=special>&gt;</span> <span class=identifier>employee_set</span>
</pre></blockquote>

<p>
Note that the hashed index does not guarantee any particular ordering of the
elements: so, for instance, we cannot efficiently query the employees whose SSN is
greater than a given number. Usually, you must consider these restrictions when
determining whether a hashed index is preferred over an ordered one.
</p>

<p>
Hashed indices replicate the interface as <code>std::unordered_set</code> and
<code>std::unordered_multiset</code>, with only minor differences where required
by the general constraints of <code>multi_index_container</code>s, and provide
additional useful capabilities like in-place updating of elements.
Check the <a href="../reference/hash_indices.html">reference</a> for a
complete specification of the interface of hashed indices,
and <a href="../examples.html#example8">example 8</a> and
<a href="../examples.html#example9">example 9</a> for practical applications.
</p>

</p>

<h3><a name="hash_unique_non_unique">Unique and non-unique variants</a></h3>

<p>
Just like ordered indices, hashed indices have unique and non-unique variants, selected
with the specifiers <code>hashed_unique</code> and <code>hashed_non_unique</code>,
respectively. In the latter case, elements with equivalent keys are kept together and can
be jointly retrieved by means of the <code>equal_range</code> member function.
</p>

<h3><a name="hash_spec">Specification</a></h3>

<p>
Hashed indices specifiers have two alternative syntaxes, depending on whether
<a href="basics.html#tagging">tags</a> are provided or not:
</p>

<blockquote><pre>
<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><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>

<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>
  <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>
</pre></blockquote>

<p>
The key extractor parameter works in exactly the same way as for
<a href="basics.html#key_extraction">ordered indices</a>; lookup, insertion,
etc., are based on the key returned by the extractor rather than the whole
element.
</p>

<p>
The hash function is the very core of the fast lookup capabilities of this type of
indices: a hasher is just a unary function object
returning an <code>std::size_t</code> value for any given
key. In general, it is impossible that every key map to a different hash value, for
the space of keys can be greater than the number of permissible hash codes: what
makes for a good hasher is that the probability of a collision (two different
keys with the same hash value) is as close to zero as possible. This is a statistical
property depending on the typical distribution of keys in a given application, so
it is not feasible to have a general-purpose hash function with excellent results
in <i>every</i> possible scenario; the default value for this parameter uses
<a href="../../../functional/hash/index.html">Boost.Hash</a>, which often provides good
enough results.
</p>

<p>
The equality predicate is used to determine whether two keys are to be treated
as the same. The default
value <code>std::equal_to&lt;KeyFromValue::result_type&gt;</code> is in most
cases exactly what is needed, so very rarely will you have to provide
your own predicate. Note that hashed indices require that two
equivalent keys have the same hash value, which
in practice greatly reduces the freedom in choosing an equality predicate.
</p>

<h3><a name="hash_lookup">Lookup</a></h3>

<p>
The lookup interface of hashed indices consists in member functions
<code>find</code>, <code>count</code> and <code>equal_range</code>.
Note that <code>lower_bound</code> and <code>upper_bound</code> are not
provided, as there is no intrinsic ordering of keys in this type of indices.
</p>

<p>
Just as with ordered indices, these member functions take keys
as their search arguments, rather than entire objects. Remember that
ordered indices lookup operations are further augmented to accept
<i>compatible keys</i>, which can roughly be regarded as "subkeys".
For hashed indices, a concept of
<a href="../reference/hash_indices.html#lookup">compatible key</a> is also
supported, though its usefulness is much more limited: basically,
a compatible key is an object which is entirely equivalent to
a native object of <code>key_type</code> value, though maybe with
a different internal representation:
</p>

<blockquote><pre>
<span class=comment>// US SSN numbering scheme</span>
<span class=keyword>struct</span> <span class=identifier>ssn</span>
<span class=special>{</span>
  <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>
    <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>
  <span class=special>{}</span>

  <span class=keyword>int</span> <span class=identifier>to_int</span><span class=special>()</span><span class=keyword>const</span>
  <span class=special>{</span>
    <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>
  <span class=special>}</span>

<span class=keyword>private</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>
<span class=special>};</span>

<span class=comment>// interoperability with SSNs in raw int form</span>

<span class=keyword>struct</span> <span class=identifier>ssn_equal</span>
<span class=special>{</span>
  <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>
  <span class=special>{</span>
    <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>
  <span class=special>}</span>

  <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>
  <span class=special>{</span>
    <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>
  <span class=special>}</span>
<span class=special>};</span>

<span class=keyword>struct</span> <span class=identifier>ssn_hash</span>
<span class=special>{</span>
  <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>
  <span class=special>{</span>
    <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>
  <span class=special>}</span>

  <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>
  <span class=special>{</span>
    <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=special>}</span>
<span class=special>};</span>

<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>

<span class=identifier>employee_set</span>         <span class=identifier>es</span><span class=special>;</span>
<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>
<span class=special>...</span>
<span class=comment>// find an employee by ssn</span>
<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>
</pre></blockquote>

<p>
In the example, we provided a hash functor <code>ssn_hash</code> and an
equality predicate <code>ssn_equal</code> allowing for interoperability
between <code>ssn</code> objects and the raw <code>int</code>s stored as
<code>SSN</code>s in <code>employee_set</code>.
</p>

<p>
By far, the most useful application of compatible keys in the context
of hashed indices lies in the fact that they allow for seamless usage of
<a href="key_extraction.html#composite_keys">composite keys</a>.
</p>

<h3><a name="hash_updating">Updating</a></h3>

<p>
Hashed indices have
<a href="../reference/hash_indices.html#replace"><code>replace</code></a>, 
<a href="../reference/hash_indices.html#modify"><code>modify</code></a> and
<a href="../reference/hash_indices.html#modify_key"><code>modify_key</code></a>
member functions, with the same functionality as in ordered indices.
</p>

<h3><a name="guarantees">Guarantees on iterator validity and exception safety</a></h3>

<p>
Due to the internal constraints imposed by the Boost.MultiIndex framework,
hashed indices provide guarantees on iterator validity and
exception safety that are actually stronger than required by the
C++ standard with respect to unordered associative containers:
<ul>
  <li>Iterator validity is preserved in any case during insertion or rehashing:
    C++ unordered associative containers can invalidate iterators when a rehash (implicit or explicit)
    is performed.</li>
  <li>Erasing an element or range of elements via iterators does not throw ever,
    as the internal hash function and equality predicate objects are not actually
    invoked.</li>
  <li><code>rehash</code> provides the strong exception safety guarantee
    unconditionally. The standard only warrants it for unordered associative containers if the internal hash function and
    equality predicate objects do not throw. The somewhat surprising consequence
    is that a standard-compliant <code>std::unordered_set</code> might erase
    elements if an exception is thrown during rehashing!</li>
</ul>
In general, these stronger guarantees play in favor of the user's convenience,
specially that which refers to iterator stability. A (hopefully minimal)
degradation in performance might result in exchange for these commodities,
though.
</p>

<h2><a name="rnd_indices">Random access indices</a></h2>

<p>
Random access indices offer the same kind of functionality as
<a href="basics.html#seq_indices">sequenced indices</a>, with the extra advantages
that their iterators are random access, and <code>operator[]</code>
and <code>at()</code> are provided for accessing
elements based on their position in the index. Let us rewrite a
container used in a previous <a href="basics.html#list_fast_lookup">example</a>,
using random access instead of sequenced indices:
</p>

<blockquote><pre>
<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>
<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>
<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>
<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>

<span class=comment>// text container with fast lookup based on a random access index</span>
<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
  <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,</span>
  <span class=identifier>indexed_by</span><span class=special>&lt;</span>
    <span class=identifier>random_access</span><span class=special>&lt;&gt;,</span>
    <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>
  <span class=special>&gt;</span>
<span class=special>&gt;</span> <span class=identifier>text_container</span><span class=special>;</span>

<span class=comment>// global text container object</span>
<span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span>
</pre></blockquote>

<p>
Random access capabilities allow us to efficiently write code
like the following:
</p>

<blockquote><pre>
<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>
<span class=special>{</span>
  <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>

  <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>
  <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>

  <span class=comment>// note random access iterators can be added offsets</span> 
  <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</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>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>
    <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>
<span class=special>}</span>

<span class=keyword>void</span> <span class=identifier>print_random_word</span><span class=special>()</span>
<span class=special>{</span>
  <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>
<span class=special>}</span>
</pre></blockquote>

<p>
This added flexibility comes at a price: insertions and deletions at positions
other than the end of the index have linear complexity, whereas these operations
are constant time for sequenced indices. This situation is reminiscent of the
differences in complexity behavior between <code>std::list</code> and
<code>std::vector</code>: in the case of random access indices, however,
insertions and deletions never incur any element copying, so the actual
performance of these operations can be acceptable, despite the theoretical
disadvantage with respect to sequenced indices.
</p>

<p>
<a href="../examples.html#example10">Example 10</a> and
<a href="../examples.html#example11">example 11</a> in the examples section put
random access indices in practice.
</p>

<h3><a name="rnd_spec">Specification</a></h3>

<p>
Random access indices are specified with the <code>random_access</code> construct,
where the <a href="basics.html#tagging">tag</a> parameter is, as usual, optional: 
</p>

<blockquote><pre>
<span class=identifier>random_access</span><span class=special>&lt;[</span><i>(tag)</i><span class=special>]&gt;</span>
</pre></blockquote>

<h3><a name="rnd_interface">Interface</a></h3>

<p>
All public functions offered by sequenced indices are also provided
by random access indices, so that the latter can act as a drop-in replacement
of the former (save with respect to their complexity bounds, as explained above).
Besides, random access
indices have <code>operator[]</code> and <code>at()</code> for positional
access to the elements, and member functions
<a href="../reference/rnd_indices.html#capacity_memfun"><code>capacity</code></a> and
<a href="../reference/rnd_indices.html#reserve"><code>reserve</code></a>
that control internal reallocation in a similar manner as the homonym
facilities in <code>std::vector</code>. Check the
<a href="../reference/rnd_indices.html">reference</a> for details.
</p>

<h3><a name="rnd_vs_vector">Comparison with <code>std::vector</code></a></h3>

<p>
It is tempting to see random access indices as an analogue of <code>std::vector</code>
for use in Boost.MultiIndex, but this metaphor can be misleading, as both constructs,
though similar in many respects, show important semantic differences. An 
advantage of random access indices is that their iterators, as well as references
to their elements, are <i>stable</i>, that is, they remain valid after any insertions
or deletions. On the other hand, random access indices have several disadvantages with
respect to <code>std::vector</code>s:
<ul>
  <li>They do not provide <i>memory contiguity</i>, a property
    of <code>std::vector</code>s by which elements are stored adjacent to one
	another in a single block of memory.
  </li>
  <li>As usual in Boost.MultiIndex, elements of random access indices are immutable
    and can only be modified through member functions
    <a href="../reference/rnd_indices.html#replace"><code>replace</code></a> and
	<a href="../reference/rnd_indices.html#modify"><code>modify</code></a>.
    This precludes the usage of many mutating
	algorithms that are nonetheless applicable to <code>std::vector</code>s.
  </li>
</ul>
The latter shortcoming can be partially remedied by means of the
<a href="#rearrange">rearranging interface</a> these indices provide.
</p>

<p>
In general, it is more instructive to regard random access indices as
a variation of sequenced indices providing random access semantics, instead
of insisting on the <code>std::vector</code> analogy.
</p>

<h2><a name="rearrange">Index rearranging</a></h2>

<p>
By design, index elements are immutable, i.e. iterators only grant
<code>const</code> access to them, and only through the provided
updating interface (<code>replace</code>, <code>modify</code> and
<code>modify_key</code>) can the elements be modified. This restriction
is set up so that the internal invariants of key-based indices are
not broken (for instance, ascending order traversal in ordered
indices), but induces important limitations in non key-based indices:
</p>

<blockquote><pre>
<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
  <span class=keyword>int</span><span class=special>,</span>
  <span class=identifier>indexed_by</span><span class=special>&lt;</span>
    <span class=identifier>random_access</span><span class=special>&lt;&gt;,</span>
    <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>
  <span class=special>&gt;</span>
<span class=special>&gt;</span> <span class=identifier>container</span><span class=special>;</span>	

<span class=identifier>container</span>    <span class=identifier>c</span><span class=special>;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>mt19937</span> <span class=identifier>rng</span><span class=special>;</span>
<span class=special>...</span>
<span class=comment>// compiler error: assignment to read-only objects</span>
<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>
</pre></blockquote>

<p>
What is unfortunate about the previous example is that the operation
performed by <code>std::shuffle</code> is potentially compatible
with <code>multi_index_container</code> invariants, as its result can be
described by a permutation of the elements in the random access index
with no actual modifications to the elements themselves. There are many
more examples of such compatible algorithms in the C++ standard library,
like for instance all sorting and partition functions.
</p>

<p>
Sequenced and random access indices provide a means to take advantage
of such external algorithms. In order to introduce this facility we need
a preliminary concept: a <i>view</i> of an index is defined as
some iterator range [<code>first</code>,<code>last</code>) over the
elements of the index such that all its elements are contained in the
range exactly once. Continuing with our example, we can apply
<code>std::random_suffle</code> on an ad hoc view obtained from the
container:
</p>

<blockquote><pre>
<span class=comment>// note that the elements of the view are not copies of the elements
// in c, but references to them</span>
<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>
<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>

<span class=comment>// this compiles OK, as reference_wrappers are swappable</span>
<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>
</pre></blockquote>

<p>
Elements of <code>v</code> are <code>reference_wrapper</code>s (from
<a href="../../../../doc/html/ref.html">Boost.Ref</a>) to the actual elements
in the multi-index container. These objects still do not allow modification
of the referenced entities, but they are swappable,
which is the only requirement <code>std::shuffle</code> imposes. Once
we have our desired rearrange stored in the view, we can transfer it to
the container with
</p>

<blockquote><pre>
<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>
</pre></blockquote>

<p>
<code>rearrange</code> accepts an input iterator signaling the beginning
of the external view (and end iterator is not needed since the length of
the view is the same as that of the index) and internally relocates the
elements of the index so that their traversal order matches the view.
Albeit with some circumventions, <code>rearrange</code> allows for the
application of a varied range of algorithms to non key-based indices.
Please note that the view concept is very general, and in no way tied
to the particular implementation example shown above. For instance, indices
of a <code>multi_index_container</code> are indeed views with respect to
its non key-based indices:
</p>

<blockquote><pre>
<span class=comment>// rearrange as index #1 (ascending order)</span>
<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>

<span class=comment>// rearrange in descending order</span>
<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>
</pre></blockquote>

<p>
The only important requirement imposed on views is that they must be
<i>free</i>, i.e. they are not affected by relocations on the base index:
thus, <code>rearrange</code> does not accept the following:
</p>

<blockquote><pre>
<span class=comment>// undefined behavior: [rbegin(),rend()) is not free with respect
// to the base index</span>
<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>
</pre></blockquote>

<p>
The view concept is defined in detail in the
<a href="../reference/indices.html#views">reference</a>.
See <a href="../examples.html#example11">example 11</a> in the examples section
for a demonstration of use of <code>rearrange</code>.
</p>

<h2><a name="iterator_to"><code>iterator_to</code></a></h2>

<p>
All indices of Boost.MultiIndex provide a member function called <code>iterator_to</code>
which returns an iterator to a given element of the container:
</p>

<blockquote><pre>
<span class=identifier>multi_index_container</span><span class=special>&lt;</span>
  <span class=keyword>int</span><span class=special>,</span>
  <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>
<span class=special>&gt;</span> <span class=identifier>c</span><span class=special>;</span>
<span class=special>...</span>
<span class=comment>// convoluted way to do c.pop_back()</span>
<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> 

<span class=comment>// The following, though similar to the previous code,
// does not work: iterator_to accepts a reference to
// the element in the container, not a copy.</span>
<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>
<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>
</pre></blockquote>

<p>
<code>iterator_to</code> provides a way to retrieve an iterator to an element
from a pointer to the element, thus making iterators and pointers interchangeable
for the purposes of element pointing (not so for traversal) in many situations.
This notwithstanding, it is not the aim of <code>iterator_to</code> to
promote the usage of pointers as substitutes for real iterators: the latter are
specifically designed for handling the elements of a container,
and not only benefit from the iterator orientation of container interfaces,
but are also capable of exposing many more programming bugs than raw pointers, both
at compile and run time. <code>iterator_to</code> is thus meant to be used
in scenarios where access via iterators is not suitable or desireable:
<ul>
  <li>Interoperability with preexisting APIs based on pointers or references.</li>
  <li>Publication of pointer-based interfaces (for instance, when
    designing a C-compatible library).
  </li>
  <li>The exposure of pointers in place of iterators can act as a <i>type
    erasure</i> barrier effectively decoupling the user of the code
    from the implementation detail of which particular container is being
    used. Similar techniques, like the famous Pimpl idiom, are used
    in large projects to reduce dependencies and build times.
  </li>
  <li>Self-referencing contexts where an element acts upon its owner
    container and no iterator to itself is available.
  </li>
</ul>
</p>

<h2><a name="ordered_node_compression">Ordered indices node compression</a></h2>

<p>
Ordered and ranked indices are implemented by means of a data structure
known as a <i>red-black tree</i>. Nodes of a red-back tree contain pointers
to the parent and the two children nodes, plus a 1-bit field referred to as
the <i>node color</i> (hence the name of the structure). Due to alignment
issues, on most architectures the color field occupies one entire word, that is,
4 bytes in 32-bit systems and 8 bytes in 64-bit environments. This waste
of space can be avoided by embedding the color bit inside one of the
node pointers, provided not all the bits of the pointer representation contain
useful information: this is precisely the case in many architectures where
such nodes are aligned to even addresses, which implies that the least
significant bit of the address must always be zero.
</p>

<p>
Boost.MultiIndex ordered and ranked indices implement this type of node compression
whenever applicable. As compared with common implementations of the STL
container <code>std::set</code>, node compression can
result in a reduction of header overload by 25% (from 16 to 12 bytes on
typical 32-bit architectures, and from 32 to 24 bytes on 64-bit systems).
The impact on performance of this optimization has been checked to be negligible
for moderately sized containers, whereas containers with many elements (hundreds
of thousands or more) perform faster with this optimization, most likely due to
L1 and L2 cache effects. 
</p>

<p>
Node compression can be disabled by globally setting the macro
<code>BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES</code>.
</p>

<hr>

<div class="prev_link"><a href="basics.html"><img src="../prev.gif" alt="basics" border="0"><br>
Basics
</a></div>
<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
Boost.MultiIndex tutorial
</a></div>
<div class="next_link"><a href="key_extraction.html"><img src="../next.gif" alt="key estraction" border="0"><br>
Key extraction
</a></div><br clear="all" style="clear: all;">

<br>

<p>Revised August 19th 2015</p>

<p>&copy; Copyright 2003-2015 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
Distributed under the Boost Software 
License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
http://www.boost.org/LICENSE_1_0.txt</a>)
</p>

</body>
</html>