Squashed 'third_party/boostorg/multi_index/' content from commit d95a949
Change-Id: Ie67c2d797c11dc122c7f11e767e81691bf2191a4
git-subtree-dir: third_party/boostorg/multi_index
git-subtree-split: d95a94942b918140e565feb99ed36ea97c30084e
diff --git a/doc/tutorial/basics.html b/doc/tutorial/basics.html
new file mode 100644
index 0000000..684d70e
--- /dev/null
+++ b/doc/tutorial/basics.html
@@ -0,0 +1,1265 @@
+<!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 - Basics</title>
+<link rel="stylesheet" href="../style.css" type="text/css">
+<link rel="start" href="../index.html">
+<link rel="prev" href="index.html">
+<link rel="up" href="index.html">
+<link rel="next" href="indices.html">
+</head>
+
+<body>
+<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
+"middle" width="277" height="86">Boost.MultiIndex Tutorial: Basics</h1>
+
+<div class="prev_link"><a href="index.html"><img src="../prev.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
+Boost.MultiIndex tutorial
+</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="indices.html"><img src="../next.gif" alt="index types" border="0"><br>
+Index types
+</a></div><br clear="all" style="clear: all;">
+
+<hr>
+
+<h2>Contents</h2>
+
+<ul>
+ <li><a href="#intro">Introduction</a>
+ <ul>
+ <li><a href="#multiple_sort">Multiple sorts on a single set</a></li>
+ <li><a href="#list_fast_lookup">A bidirectional list with fast lookup</a></li>
+ </ul>
+ </li>
+ <li><a href="#index_spec">Index specification</a></li>
+ <li><a href="#tagging">Tagging</a></li>
+ <li><a href="#iterator_access">Iterator access</a></li>
+ <li><a href="#index_types">Index types</a>
+ <ul>
+ <li><a href="#ord_indices">Ordered indices</a>
+ <ul>
+ <li><a href="#unique_non_unique">Unique and non-unique variants</a></li>
+ <li><a href="#ord_spec">Specification</a></li>
+ <li><a href="#key_extraction">Key extraction</a></li>
+ <li><a href="#comparison_predicates">Comparison predicates</a></li>
+ <li><a href="#special_lookup">Special lookup operations</a></li>
+ <li><a href="#range">Retrieval of ranges</a></li>
+ <li><a href="#ord_updating">Updating</a></li>
+ </ul>
+ </li>
+ <li><a href="#seq_indices">Sequenced indices</a>
+ <ul>
+ <li><a href="#seq_spec">Specification</a></li>
+ <li><a href="#list_ops">List operations</a></li>
+ <li><a href="#seq_updating">Updating</a></li>
+ </ul>
+ </li>
+ </ul>
+ </li>
+ <li><a href="#projection">Projection of iterators</a></li>
+ <li><a href="#complexity">Complexity and exception safety</a></li>
+</ul>
+
+<h2><a name="intro">Introduction</a></h2>
+
+<p>
+We introduce the main concepts of Boost.MultiIndex through the study of
+two typical use cases.
+</p>
+
+<h3><a name="multiple_sort">Multiple sorts on a single set</a></h3>
+
+<p>
+STL sets and multisets are varying-length containers where elements are efficiently
+sorted according to a given comparison predicate. These container classes fall short
+of functionality when the programmer wishes to efficiently sort and look up the elements
+following a different sorting criterion. Consider for instance:
+</p>
+
+<blockquote><pre>
+<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=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=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=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>
+<span class=special>};</span>
+</pre></blockquote>
+
+<p>The fact that IDs are unique to each employee is reflected by the way
+<code>operator<</code> is defined, so a natural data structure for storing of
+<code>employee</code>s is just a <code>std::set<employee></code>. Now,
+if one wishes to print out a listing of all employees in alphabetical order, available
+solutions may have disadvantages either in terms of storage space, complexity or ease
+of maintenance:
+<ul>
+<li>Copy the employee set into a vector or similar and sort this by a comparison
+functor dependent upon <code>employee::name</code>.
+<li>Keep a secondary data structure of pointers to the elements of the set, appropriately
+sorted by name.
+</ul>
+Of these, probably the second solution will be the one adopted by most programmers
+concerned about efficiency, but it imposes the annoying burden of keeping the two
+structures in sync. If the code is additionally required to be exception-safe, this
+construct easily becomes unmaintainable.
+</p>
+
+<p>
+Boost.MultiIndex features <a href="#ord_indices"><i>ordered indices</i></a>, which
+sort the elements according to a particular key, and are designed to help programmers
+in need of sequences of elements for which <i>more than one</i> sorting criteria are
+relevant. We do so by defining a <code>multi_index_container</code>
+instantiation composed of several ordered indices: each index, viewed in isolation,
+behaves much as an ordered <code>std::set</code> (or <code>std::multiset</code>), whilst
+the overall integrity of the entire data structure is preserved. Our example problem
+thus can be solved with Boost.MultiIndex as follows:
+</p>
+
+<blockquote><pre>
+<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>
+<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>
+<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>
+<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>
+
+<span class=comment>// define a multiply indexed set with indices by id and name</span>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=comment>// sort by employee::operator<</span>
+ <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>
+
+ <span class=comment>// sort by less<string> on name</span>
+ <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>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+
+<span class=keyword>void</span> <span class=identifier>print_out_by_name</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>employee_set</span><span class=special>&</span> <span class=identifier>es</span><span class=special>)</span>
+<span class=special>{</span>
+ <span class=comment>// get a view to index #1 (name)</span>
+ <span class=keyword>const</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>name_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>1</span><span class=special>>();</span>
+ <span class=comment>// use name_index as a regular std::set</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span>
+ <span class=identifier>name_index</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>name_index</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=identifier>employee</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=special>}</span>
+</pre></blockquote>
+
+<p>
+Instead of a single comparison predicate type, as it happens for STL associative
+containers, <code>multi_index_container</code> is passed a
+<a href="../reference/multi_index_container.html#multi_index_container">list</a> of index
+specifications (<code>indexed_by</code>), each one inducing the corresponding index.
+Indices are accessed via
+<a href="../reference/multi_index_container.html#index_retrieval"><code>get</code></a><code><N>()</code>
+where <i>N</i> ranges between 0 and the number of comparison
+predicates minus one. The functionality of index #0 can be accessed directly from a
+<code>multi_index_container</code> object without using <code>get<0>()</code>: for instance,
+<code>es.begin()</code> is equivalent to <code>es.get<0>().begin()</code>.
+</p>
+
+<p>
+Note that <code>get</code> returns a <i>reference</i> to the index, and not
+an index object. Indices cannot be constructed as separate objects from the
+container they belong to, so the following
+</p>
+
+<blockquote><pre>
+<span class=comment>// Wrong: we forgot the & after employee_set::nth_index<1>::type</span>
+<span class=keyword>const</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>name_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>1</span><span class=special>>();</span>
+</pre></blockquote>
+
+<p>
+does not compile, since it is trying to construct the index object
+<code>name_index</code>. This is a common source of errors in user code.
+</p>
+
+<h3><a name="list_fast_lookup">A bidirectional list with fast lookup</a></h3>
+
+<p>
+This study case allows us to introduce so-called
+<a href="#seq_indices"><i>sequenced indices</i></a>, and how they
+interact with ordered indices to construct powerful containers. Suppose
+we have a text parsed into words and stored in a list like this:
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>list</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>text_container</span><span class=special>;</span>
+
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>text</span><span class=special>=</span>
+ <span class=string>"Alice was beginning to get very tired of sitting by her sister on the "</span>
+ <span class=string>"bank, and of having nothing to do: once or twice she had peeped into the "</span>
+ <span class=string>"book her sister was reading, but it had no pictures or conversations in "</span>
+ <span class=string>"it, 'and what is the use of a book,' thought Alice 'without pictures or "</span>
+ <span class=string>"conversation?'"</span><span class=special>;</span>
+
+<span class=comment>// feed the text into the list</span>
+<span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span>
+<span class=identifier>boost</span><span class=special>::</span><span class=identifier>tokenizer</span><span class=special><</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special><</span><span class=keyword>char</span><span class=special>></span> <span class=special>></span> <span class=identifier>tok</span>
+ <span class=special>(</span><span class=identifier>text</span><span class=special>,</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special><</span><span class=keyword>char</span><span class=special>>(</span><span class=string>" \t\n.,;:!?'\"-"</span><span class=special>));</span>
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>tok</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>tok</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>back_inserter</span><span class=special>(</span><span class=identifier>tc</span><span class=special>));</span>
+</pre></blockquote>
+
+<p>
+If we want to count the occurrences of a given word into the text we will resort
+to <code>std::count</code>:
+</p>
+
+<blockquote><pre>
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>occurrences</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>word</span><span class=special>)</span>
+<span class=special>{</span>
+ <span class=keyword>return</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>count</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>tc</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>word</span><span class=special>);</span>
+<span class=special>}</span>
+</pre></blockquote>
+
+<p>
+But this implementation of <code>occurrences</code> performs in linear time, which
+could be unacceptable for large quantities of text. Similarly, other operations like
+deletion of selected words are just too costly to carry out on a
+<code>std::list</code>:
+</p>
+
+<blockquote><pre>
+<span class=keyword>void</span> <span class=identifier>delete_word</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>word</span><span class=special>)</span>
+<span class=special>{</span>
+ <span class=identifier>tc</span><span class=special>.</span><span class=identifier>remove</span><span class=special>(</span><span class=identifier>word</span><span class=special>);</span> <span class=comment>// scans the entire list looking for word</span>
+<span class=special>}</span>
+</pre></blockquote>
+
+<p>
+When performance is a concern, we will need an additional data structure that indexes
+the elements in <code>tc</code>, presumably in alphabetical order. Boost.MultiIndex
+does precisely this through the combination of sequenced and ordered indices:
+</p>
+
+<blockquote><pre>
+<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>
+<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>sequenced_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span>
+<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>
+<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>
+
+<span class=comment>// define a multi_index_container with a list-like index and an ordered index</span>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</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>indexed_by</span><span class=special><</span>
+ <span class=identifier>sequenced</span><span class=special><>,</span> <span class=comment>// list-like index</span>
+ <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> <span class=comment>// words by alphabetical order</span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>text_container</span><span class=special>;</span>
+
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>text</span><span class=special>=...</span>
+
+<span class=comment>// feed the text into the list</span>
+<span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span>
+<span class=identifier>boost</span><span class=special>::</span><span class=identifier>tokenizer</span><span class=special><</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special><</span><span class=keyword>char</span><span class=special>></span> <span class=special>></span> <span class=identifier>tok</span>
+ <span class=special>(</span><span class=identifier>text</span><span class=special>,</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special><</span><span class=keyword>char</span><span class=special>>(</span><span class=string>" \t\n.,;:!?'\"-"</span><span class=special>));</span>
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>tok</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>tok</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>back_inserter</span><span class=special>(</span><span class=identifier>tc</span><span class=special>));</span>
+</pre></blockquote>
+
+<p>
+So far, the substitution of <code>multi_index_container</code> for <code>std::list</code>
+does not show any advantage. The code for inserting the text into the container
+does not change as sequenced indices provide an interface similar to that of
+<code>std::list</code> (no explicit access to this index through
+<code>get<0>()</code> is needed as <code>multi_index_container</code> inherits the
+functionality of index #0.) But the specification of an additional ordered index
+allows us to implement <code>occurrences</code> and <code>delete_word</code>
+in a much more efficient manner:
+</p>
+
+<blockquote><pre>
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>occurrences</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>word</span><span class=special>)</span>
+<span class=special>{</span>
+ <span class=comment>// get a view to index #1</span>
+ <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>sorted_index</span><span class=special>=</span><span class=identifier>tc</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=comment>// use sorted_index as a regular std::set</span>
+ <span class=keyword>return</span> <span class=identifier>sorted_index</span><span class=special>.</span><span class=identifier>count</span><span class=special>(</span><span class=identifier>word</span><span class=special>);</span>
+<span class=special>}</span>
+
+<span class=keyword>void</span> <span class=identifier>delete_word</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>word</span><span class=special>)</span>
+<span class=special>{</span>
+ <span class=comment>// get a view to index #1</span>
+ <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>sorted_index</span><span class=special>=</span><span class=identifier>tc</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=comment>// use sorted_index as a regular std::set</span>
+ <span class=identifier>sorted_index</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(</span><span class=identifier>word</span><span class=special>);</span>
+<span class=special>}</span>
+</pre></blockquote>
+
+<p>
+Now, <code>occurrences</code> and <code>delete_word</code> have logarithmic
+complexity. The programmer can use index #0 for accessing the text as with
+<code>std::list</code>, and use index #1 when logarithmic lookup is needed.
+</p>
+
+<h2>
+<a name="index_spec">Index specification</a>
+</h2>
+
+<p>
+The indices of a <code>multi_index_container</code> instantiation are specified by
+means of the <a href="../reference/indices.html#indexed_by">
+<code>indexed_by</code></a> construct. For instance, the instantiation
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <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>
+ <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>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+is comprised of a <a href="#unique_non_unique">unique ordered index</a> and a
+<a href="#unique_non_unique">non-unique ordered index</a>, while in
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</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>indexed_by</span><span class=special><</span>
+ <span class=identifier>sequenced</span><span class=special><>,</span>
+ <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>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>text_container</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+we specifiy two indices, the first of <a href="#seq_indices">sequenced type</a>,
+the second a non-unique <a href="#ord_indices">ordered index</a>. In general, we
+can specify an arbitrary number of indices: each of the arguments of
+<code>indexed_by</code> is called an
+<a href="../reference/indices.html#index_specification"><i>index specifier</i></a>.
+Depending on the type of index being specified, the corresponding specifier
+will need additional information: for instance, the specifiers <code>ordered_unique</code>
+and <code>ordered_non_unique</code> are provided with a
+<a href="#key_extraction">key extractor</a> and an optional
+<a href="#comparison_predicates">comparison predicate</a> which jointly indicate
+how the sorting of elements will be performed.
+</p>
+
+<p>
+A <code>multi_index_container</code> instantiation can be declared without supplying
+the <code>indexed_by</code> part: in this case, default index values are taken
+so that the resulting type is equivalent to a regular <code>std::set</code>.
+Concretely, the instantiation
+</p>
+
+<blockquote><pre>
+<span class=identifier>multi_index_container</span><span class=special><</span><i>(element)</i><span class=special>></span>
+</pre></blockquote>
+
+<p>
+is equivalent to
+</p>
+
+<blockquote><pre>
+<span class=identifier>multi_index_container</span><span class=special><</span>
+ <i>(element)</i><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><(</span><span class=identifier>element</span><span class=special>)></span> <span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span>
+</pre></blockquote>
+
+<h2><a name="tagging">Tagging</a></h2>
+
+<p>
+In order to retrieve (a reference to) an index of a given <code>multi_index_container</code>,
+the programmer must provide its order number, which is cumbersome and not very
+self-descriptive. Optionally, indices can be assigned <i>tags</i> (C++ types) that
+act as more convenient mnemonics. If provided, tags must be passed as the
+first parameter of the corresponding index specifier. The following is a revised version of
+<code>employee_set</code> with inclusion of tags:
+</p>
+
+<blockquote><pre>
+<span class=comment>// tags</span>
+<span class=keyword>struct</span> <span class=identifier>name</span><span class=special>{};</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <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>
+ <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>tag</span><span class=special><</span><span class=identifier>name</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>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+Tags have to be passed inside the <a href="../reference/indices.html#tag"><code>tag</code></a>
+construct. Any type can be used as a tag for an index, although in general one will choose
+names that are descriptive of the index they are associated with. The tagging mechanism allows
+us to write expressions like</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
+<span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</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=identifier>name</span><span class=special>>().</span><span class=identifier>begin</span><span class=special>();</span>
+</pre></blockquote>
+
+<p>
+If no tag is provided for an index (as is the case for index #0 of the previous
+example), access to that index can only be performed by number. Note the existence
+of two different <code>typedef</code>s <code>nth_index</code> and
+<code>index</code> for referring to an index by number and by tag, respectively;
+for instance,
+<ul>
+ <li><code>employee_set::nth_index<1>::type</code> is the type of
+ index #1,</li>
+ <li><code>employee_set::index<name>::type</code> is the type of the index
+ tagged with <code>name</code> (the same index #1 in this case.)</li>
+</ul>
+<code>get()</code>, on the other hand, is overloaded to serve both styles of access:
+</p>
+
+<blockquote><pre>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>name_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=identifier>name</span><span class=special>>();</span>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>name_index2</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>1</span><span class=special>>();</span> <span class=comment>// same index</span>
+</pre></blockquote>
+
+<p>
+Additionally, the <code>tag</code> class template accepts several tags for one
+index, that we can use interchangeably: for instance, the specification of index #1
+in the previous example can be rewritten to hold two different tags
+<code>name</code> and <code>by_name</code>:
+</p>
+
+<blockquote><pre>
+<span class=comment>// tags</span>
+<span class=keyword>struct</span> <span class=identifier>name</span><span class=special>{};</span>
+<span class=keyword>struct</span> <span class=identifier>by_name</span><span class=special>{};</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=special>...</span>
+ <span class=identifier>ordered_non_unique</span><span class=special><</span>
+ <span class=identifier>tag</span><span class=special><</span><span class=identifier>name</span><span class=special>,</span><span class=identifier>by_name</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>
+ <span class=special>...</span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<h2><a name="iterator_access">Iterator access</a></h2>
+
+<p>
+Each index of a <code>multi_index_container</code> uses its own
+iterator types, which are different from those of another indices. As is
+the rule with STL containers, these iterators are defined as nested
+types of the index:
+</p>
+
+<blockquote><pre>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</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>1</span><span class=special>>().</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Judy Smith"</span><span class=special>);</span>
+</pre></blockquote>
+
+<p>
+This kind of expressions can be rendered more readable by
+means of user-defined <code>typedef</code>s:
+</p>
+
+<blockquote><pre>
+<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>1</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
+<span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</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>1</span><span class=special>>().</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Judy Smith"</span><span class=special>);</span>
+</pre></blockquote>
+
+<p>
+The iterators provided by every index are <i>constant</i>, that is, the elements they point to
+cannot be mutated directly. This follows the interface of <code>std::set</code> for ordered
+indices but might come as a surprise for other types such as sequenced indices, which are modeled after
+<code>std::list</code>, where this limitation does not happen. This seemingly odd behavior
+is imposed by the way <code>multi_index_container</code>s work; if elements were
+allowed to be mutated indiscriminately, we could introduce inconsistencies
+in the ordered indices of the <code>multi_index_container</code> without the container
+being notified about it. Element modification is properly done by means of
+<a href="#ord_updating">update operations</a> on any index.
+</p>
+
+<h2>
+<a name="index_types">Index types</a>
+</h2>
+
+<p>
+Currently, Boost.MultiIndex provides the following index types:
+<ul>
+ <li>Ordered indices sort the elements like <code>std::set</code>s do and
+ provide a similar interface. There are <i>unique</i> and <i>non-unique</i>
+ variants: the former do not allow for duplicates, while the latter permit
+ them (like <code>std::multiset</code>.)</li>
+ <li>Ranked indices are a variation of ordered indices providing extra capabilities
+ for querying and accessing elements based on their <i>rank</i> (the numerical position
+ they occupy in the index).
+ </li>
+ <li>Sequenced indices are modeled after the semantics and interface of
+ <code>std::list</code>: they arrange the elements as if in a bidirectional
+ list.</li>
+ <li>Hashed indices provide fast access to the elements through hashing
+ techniques, in a similar way as non-standard <code>hash_set</code>s provided
+ by some vendors. Recently, <i>unordered associative containers</i> have been
+ proposed as part of an extension of the C++ standard library known
+ in the standardization commitee as TR1. Hashed indices closely model this
+ proposal.</li>
+ <li>Random access indices provide an interface similar to that of
+ sequenced indices, and additionally feature random access iterators
+ and positional access to the elements.</li>
+</ul>
+The examples in the <a href="#intro">introduction</a> exercise ordered and sequenced
+indices, which are the most commonly used; the other kinds of indices are presented
+in the <a href="indices.html">index types</a> section of the tutorial.
+</p>
+
+<h3>
+<a name="ord_indices">Ordered indices</a>
+</h3>
+
+<p>
+Ordered indices sort the elements in a <code>multi_index_container</code> according
+to a specified key and an associated comparison predicate. These indices can
+be viewed as analogues of the standard container <code>std::set</code>, and in fact
+they do replicate its interface, albeit with some minor differences dictated
+by the general constraints of Boost.MultiIndex.
+</p>
+
+<h4>
+<a name="unique_non_unique">Unique and non-unique variants</a>
+</h4>
+
+<p>
+Ordered indices are classified into <i>unique</i>, which prohibit two
+elements to have the same key value, and <i>non-unique</i> indices,
+which allow for duplicates. Consider again the definition
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <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>
+ <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>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+In this instantiation of <code>multi_index_container</code>, the first index is to be
+treated as unique (since IDs are exclusive to each employee) and thus is declared using
+<code>ordered_unique</code>, whereas the second index is non-unique (as the possibility exists
+that say two John Smiths are hired in the same company), which is specified by the use
+of <code>ordered_non_unique</code>.
+</p>
+
+<p>
+The classification of ordered indices in unique and non-unique has an impact on which
+elements are allowed to be inserted into a given <code>multi_index_container</code>; briefly put,
+unique ordered indices mimic the behavior of <code>std::set</code>s while non-unique
+ordered indices are similar to <code>std::multiset</code>s. For instance, an
+<code>employee_set</code> can hold the objects <code>employee(0,"George Brown")</code>
+and <code>employee(1,"George Brown")</code>, but will not accept the insertion of an
+<code>employee</code> object whose ID coincides with that of some previously inserted
+employee.
+</p>
+
+<p>
+More than one unique index can be specified. For instance, if we augment
+<code>employee</code> to include an additional member for the Social Security number,
+which is reasonably treated as unique, the following captures this design:
+</p>
+
+<blockquote><pre>
+<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>&</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><(</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>
+<span class=special>};</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=comment>// sort by employee::operator<</span>
+ <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>
+
+ <span class=comment>// sort by less<string> on name</span>
+ <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>
+
+ <span class=comment>// sort by less<int> on ssnumber</span>
+ <span class=identifier>ordered_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>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<h4>
+<a name="ord_spec">Specification</a>
+</h4>
+
+<p>
+Ordered index specifiers in <code>indexed_by</code> must conform to one of the
+following syntaxes:
+</p>
+
+<blockquote><pre>
+<span class=special>(</span><span class=identifier>ordered_unique</span> <span class=special>|</span> <span class=identifier>ordered_non_unique</span><span class=special>)
+ </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>
+
+<span class=special>(</span><span class=identifier>ordered_unique</span> <span class=special>|</span> <span class=identifier>ordered_non_unique</span><span class=special>)</span>
+ <span class=special><[</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]></span>
+</pre></blockquote>
+
+<p>
+The first optional argument is used if <a href="#tagging">tags</a> are associated
+with the index. We now proceed to briefly discuss the remaining arguments
+of an ordered index specifier.
+</p>
+
+<h4>
+<a name="key_extraction">Key extraction</a>
+</h4>
+
+<p>
+The first template parameter (or the second, if tags are supplied)
+in the specification of an ordered index provides a <i>key extraction</i> predicate.
+This predicate takes a whole element (in our example, a reference to an
+<code>employee</code> object) and returns the piece of information by which
+the sorting is performed. In most cases, one of the following two situations arises:
+<ul>
+<li>The whole element serves as the key, as is the case of the first index
+in <code>employee_set</code>. The predefined
+<a href="key_extraction.html#identity"><code>identity</code></a> predicate
+can be used here as a key extractor; <code>identity</code> returns as the key the
+same object passed as argument.</li>
+<li>The comparison is performed on a particular data member of the element; this
+closely follows the specification of indices on a column of a table in relational
+databases. Boost.MultiIndex provides
+<a href="key_extraction.html#member"><code>member</code></a>, which returns
+as the key a member of the element specified by a given pointer.</li>
+</ul>
+As an example, consider again the definition of <code>employee_set</code>. The
+definition of the first index:
+</p>
+
+<blockquote><pre>
+<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>
+</pre></blockquote>
+
+<p>
+specifies by means of <code>identity</code> that <code>element</code>
+objects themselves serve as key for this index. On the other hand, in the second
+index:
+</p>
+
+<blockquote><pre>
+<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>
+</pre></blockquote>
+
+<p>
+we use <code>member</code> to extract the <code>name</code> part of the
+<code>employee</code> object. The key type of this index is then
+<code>std::string</code>.
+</p>
+
+<p>
+Apart from <code>identity</code> and <code>member</code>, Boost.MultiIndex provides
+several other predefined key extractors and powerful ways to combine them.
+Key extractors can also be defined by the user.
+Consult the <a href="key_extraction.html">key extraction section</a> of
+the tutorial for a more detailed exposition of this topic.
+</p>
+
+<h4><a name="comparison_predicates">Comparison predicates</a></h4>
+
+<p>
+The last part of the specification of an ordered index is the associated
+<i>comparison predicate</i>, which must order the keys in a less-than fashion.
+These comparison predicates are not different from those used by STL containers like
+<code>std::set</code>. By default (i.e. if no comparison predicate is provided),
+an index with keys of type <code>key_type</code> sorts the elements by
+<code>std::less<key_type></code>. Should other comparison criteria be needed,
+they can be specified as an additional parameter in the index declaration:
+</p>
+
+<blockquote><pre>
+<span class=comment>// define a multiply indexed set with indices by id and by name
+// in reverse alphabetical order</span>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <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> <span class=comment>// as usual</span>
+ <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=identifier>std</span><span class=special>::</span><span class=identifier>greater</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=comment>// default would be std::less<std::string></span>
+ <span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<h4><a name="special_lookup">Special lookup operations</a></h4>
+
+<p>
+A given ordered index allows for lookup based on its key type, rather than the
+whole element. For instance, to find Veronica Cruz in an
+<code>employee_set</code> one would write:
+</p>
+
+<blockquote><pre>
+<span class=identifier>employee_set</span> <span class=identifier>es</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>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
+<span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</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=identifier>name</span><span class=special>>().</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Veronica Cruz"</span><span class=special>);</span>
+</pre></blockquote>
+
+<p>As a plus, Boost.MultiIndex provides lookup operations accepting search keys
+different from the <code>key_type</code> of the index, which is a specially useful
+facility when <code>key_type</code> objects are expensive to create. Ordered STL containers
+fail to provide this functionality, which often leads to inelegant workarounds: consider for
+instance the problem of determining the employees whose IDs fall in the range [0,100]. Given
+that the key of <code>employee_set</code> index #0
+is <code>employee</code> itself, on a first approach one would write the following:
+</p>
+
+<blockquote><pre>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>p0</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=identifier>employee</span><span class=special>(</span><span class=number>0</span><span class=special>,</span><span class=string>""</span><span class=special>));</span>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>p1</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>upper_bound</span><span class=special>(</span><span class=identifier>employee</span><span class=special>(</span><span class=number>100</span><span class=special>,</span><span class=string>""</span><span class=special>));</span>
+</pre></blockquote>
+
+<p>
+Note however that <code>std::less<employee></code> actually only depends
+on the IDs of the employees, so it would be more convenient to avoid
+the creation of entire <code>employee</code> objects just for the sake of
+their IDs. Boost.MultiIndex allows for this: define an appropriate
+comparison predicate
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>comp_id</span>
+<span class=special>{</span>
+ <span class=comment>// compare an ID and an employee</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>employee</span><span class=special>&</span> <span class=identifier>e2</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>e2</span><span class=special>.</span><span class=identifier>id</span><span class=special>;}</span>
+
+ <span class=comment>// compare an employee and an ID</span>
+ <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>e1</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>e1</span><span class=special>.</span><span class=identifier>id</span><span class=special><</span><span class=identifier>x</span><span class=special>;}</span>
+<span class=special>};</span>
+</pre></blockquote>
+
+<p>and now write the search as</p>
+
+<blockquote><pre>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>p0</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=number>0</span><span class=special>,</span><span class=identifier>comp_id</span><span class=special>());</span>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>p1</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>upper_bound</span><span class=special>(</span><span class=number>100</span><span class=special>,</span><span class=identifier>comp_id</span><span class=special>());</span>
+</pre></blockquote>
+
+<p>
+Here we are not only passing IDs instead of <code>employee</code> objects:
+an alternative comparison predicate is passed as well. In general, lookup operations
+of ordered indices are overloaded to accept
+<a href="../reference/ord_indices.html#set_operations"><i>compatible sorting
+criteria</i></a>. The somewhat cumbersone definition of compatibility in this context
+is given in the reference, but roughly speaking we say that a comparison predicate
+<code>C1</code> is compatible with <code>C2</code> if any sequence sorted by
+<code>C2</code> is also sorted with respect to <code>C1</code>.
+The following shows a more interesting use of compatible predicates:
+</p>
+
+<blockquote><pre>
+<span class=comment>// sorting by name's initial</span>
+<span class=keyword>struct</span> <span class=identifier>comp_initial</span>
+<span class=special>{</span>
+ <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>char</span> <span class=identifier>ch</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>s</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span>
+ <span class=keyword>if</span><span class=special>(</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>empty</span><span class=special>())</span><span class=keyword>return</span> <span class=keyword>false</span><span class=special>;</span>
+ <span class=keyword>return</span> <span class=identifier>ch</span><span class=special><</span><span class=identifier>s</span><span class=special>[</span><span class=number>0</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>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&</span> <span class=identifier>s</span><span class=special>,</span><span class=keyword>char</span> <span class=identifier>ch</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span>
+ <span class=keyword>if</span><span class=special>(</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>empty</span><span class=special>())</span><span class=keyword>return</span> <span class=keyword>true</span><span class=special>;</span>
+ <span class=keyword>return</span> <span class=identifier>s</span><span class=special>[</span><span class=number>0</span><span class=special>]<</span><span class=identifier>ch</span><span class=special>;</span>
+ <span class=special>}</span>
+<span class=special>};</span>
+
+<span class=comment>// obtain first employee whose name begins with 'J' (ordered by name)</span>
+<span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
+<span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_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=identifier>name</span><span class=special>>();</span>
+<span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>const_iterator</span> <span class=identifier>it</span><span class=special>=</span>
+ <span class=identifier>name_index</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=literal>'J'</span><span class=special>,</span><span class=identifier>comp_initial</span><span class=special>());</span>
+</pre></blockquote>
+
+<h4><a name="range">Retrieval of ranges</a></h4>
+
+<p>
+Range searching, i.e. the lookup of all elements in a given interval, is a very
+frequent operation for which standard <code>lower_bound</code> and
+<code>upper_bound</code> can be resorted to, though in a cumbersome manner.
+For instance, the following code retrieves the elements of an
+<code>multi_index_container<double></code> in the interval [100,200]:
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=keyword>double</span><span class=special>></span> <span class=identifier>double_set</span><span class=special>;</span>
+<span class=comment>// note: default template parameters resolve to
+// multi_index_container<double,indexed_by<unique<identity<double> > > >.</span>
+
+<span class=identifier>double_set</span> <span class=identifier>s</span><span class=special>;</span>
+<span class=special>...</span>
+<span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it0</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=number>100.0</span><span class=special>);</span>
+<span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>upper_bound</span><span class=special>(</span><span class=number>200.0</span><span class=special>);</span>
+<span class=comment>// range [it0,it1) contains the elements in [100,200]</span>
+</pre></blockquote>
+
+<p>
+Subtle changes to the code are required when strict inequalities are considered.
+To retrieve the elements <i>greater</i> than 100 and <i>less</i> than 200, the
+code has to be rewritten as
+</p>
+
+<blockquote><pre>
+<span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it0</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>upper_bound</span><span class=special>(</span><span class=number>100.0</span><span class=special>);</span>
+<span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=number>200.0</span><span class=special>);</span>
+<span class=comment>// range [it0,it1) contains the elements in (100,200)</span>
+</pre></blockquote>
+
+<p>
+To add to this complexity, the careful programmer has to take into account
+that the lower and upper bounds of the interval searched be compatible: for
+instance, if the lower bound is 200 and the upper bound is 100, the iterators
+<code>it0</code> and <code>it1</code> produced by the code above will be in reverse
+order, with possibly catastrophic results if a traversal from <code>it0</code>
+to <code>it1</code> is tried. All these details make range searching a tedious
+and error prone task.
+</p>
+
+<p>
+The <a href="../reference/ord_indices.html#range_operations"><code>range</code></a>
+member function, often in combination with
+<a href="../../../../libs/lambda/index.html">Boost.Lambda</a> expressions, can
+greatly help alleviate this situation:
+</p>
+
+<blockquote><pre>
+<span class=keyword>using</span> <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>lambda</span><span class=special>;</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=keyword>double</span><span class=special>></span> <span class=identifier>double_set</span><span class=special>;</span>
+<span class=identifier>double_set</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>pair</span><span class=special><</span><span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>></span> <span class=identifier>p</span><span class=special>=</span>
+ <span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=number>100.0</span><span class=special><=</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>_1</span><span class=special><=</span><span class=number>200</span><span class=special>);</span> <span class=comment>// 100<= x <=200</span>
+<span class=special>...</span>
+<span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=number>100.0</span><span class=special><</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>_1</span><span class=special><</span><span class=number>200</span><span class=special>);</span> <span class=comment>// 100< x < 200</span>
+<span class=special>...</span>
+<span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=number>100.0</span><span class=special><=</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>_1</span><span class=special><</span><span class=number>200</span><span class=special>);</span> <span class=comment>// 100<= x < 200</span>
+</pre></blockquote>
+
+<p>
+<code>range</code> simply accepts predicates specifying the lower and upper bounds
+of the interval searched. Please consult the reference for a detailed explanation
+of the permissible predicates passed to <code>range</code>.</p>
+
+<p>
+One or both bounds can be omitted with the special <code>unbounded</code> marker:
+</p>
+
+<blockquote><pre>
+<span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=number>100.0</span><span class=special><=</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>unbounded</span><span class=special>);</span> <span class=comment>// 100 <= x</span>
+<span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=identifier>unbounded</span><span class=special>,</span><span class=identifier>_1</span><span class=special><</span><span class=number>200.0</span><span class=special>);</span> <span class=comment>// x < 200</span>
+<span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=identifier>unbounded</span><span class=special>,</span><span class=identifier>unbounded</span><span class=special>);</span> <span class=comment>// equiv. to std::make_pair(s.begin(),s.end())</span>
+</pre></blockquote>
+
+<h4><a name="ord_updating">Updating</a></h4>
+
+<p>
+The <a href="../reference/ord_indices.html#replace"><code>replace</code></a> member function
+performs in-place replacement of a given element as the following example shows:
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>index</span><span class=special><</span><span class=identifier>employee_set</span><span class=special>,</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
+<span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_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=identifier>name</span><span class=special>>();</span>
+
+<span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Anna Jones"</span><span class=special>);</span>
+<span class=identifier>employee</span> <span class=identifier>anna</span><span class=special>=*</span><span class=identifier>it</span><span class=special>;</span>
+<span class=identifier>anna</span><span class=special>.</span><span class=identifier>name</span><span class=special>=</span><span class=string>"Anna Smith"</span><span class=special>;</span> <span class=comment>// she just got married to Calvin Smith</span>
+<span class=identifier>name_index</span><span class=special>.</span><span class=identifier>replace</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>anna</span><span class=special>);</span> <span class=comment>// update her record</span>
+</pre></blockquote>
+
+<p>
+<code>replace</code> performs this substitution in such a manner that:
+<ul>
+<li>The complexity is constant time if the changed element retains its original
+order with respect to all indices; it is logarithmic otherwise.
+<li>Iterator and reference validity are preserved.
+<li>The operation is strongly exception-safe, i.e. the <code>multi_index_container</code>
+remains unchanged if some exception (originated by the system or the user's data
+types) is thrown.
+</ul>
+<code>replace</code> is a powerful operation not provided by standard STL
+containers, and one that is specially handy when strong exception-safety is
+required.
+</p>
+
+<p>
+The observant reader might have noticed that the convenience of <code>replace</code>
+comes at a cost: namely the whole element has to be copied <i>twice</i> to do
+the updating (when retrieving it and inside <code>replace</code>). If elements
+are expensive to copy, this may be quite a computational cost for the modification
+of just a tiny part of the object. To cope with this situation, Boost.MultiIndex
+provides an alternative updating mechanism called
+<a href="../reference/ord_indices.html#modify"><code>modify</code></a>:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>change_name</span>
+<span class=special>{</span>
+ <span class=identifier>change_name</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>new_name</span><span class=special>):</span><span class=identifier>new_name</span><span class=special>(</span><span class=identifier>new_name</span><span class=special>){}</span>
+
+ <span class=keyword>void</span> <span class=keyword>operator</span><span class=special>()(</span><span class=identifier>employee</span><span class=special>&</span> <span class=identifier>e</span><span class=special>)</span>
+ <span class=special>{</span>
+ <span class=identifier>e</span><span class=special>.</span><span class=identifier>name</span><span class=special>=</span><span class=identifier>new_name</span><span class=special>;</span>
+ <span class=special>}</span>
+
+<span class=keyword>private</span><span class=special>:</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>new_name</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>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
+<span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_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=identifier>name</span><span class=special>>();</span>
+
+<span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Anna Jones"</span><span class=special>);</span>
+<span class=identifier>name_index</span><span class=special>.</span><span class=identifier>modify</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>change_name</span><span class=special>(</span><span class=string>"Anna Smith"</span><span class=special>));</span>
+</pre></blockquote>
+
+<p><code>modify</code> accepts a functor (or pointer to function) that is
+passed a reference to the element to be changed, thus eliminating the need
+for spurious copies. Like <code>replace</code>, <code>modify</code> does preserve
+the internal orderings of all the indices of the <code>multi_index_container</code>.
+However, the semantics of <code>modify</code> is not entirely equivalent to
+<code>replace</code>. Consider what happens if a collision occurs as a result
+of modifying the element, i.e. the modified element clashes with another with
+respect to some unique ordered index. In the case of <code>replace</code>, the
+original value is kept and the method returns without altering the container, but
+<code>modify</code> cannot afford such an approach, since the modifying functor
+leaves no trace of the previous value of the element. Integrity constraints
+thus lead to the following policy: when a collision happens in the
+process of calling <code>modify</code>, the element is erased and the method returns
+<code>false</code>. There is a further version of <code>modify</code> which
+accepts a <i>rollback</i> functor to undo the changes in case of collision:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>change_id</span>
+<span class=special>{</span>
+ <span class=identifier>change_id</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>new_id</span><span class=special>):</span><span class=identifier>new_id</span><span class=special>(</span><span class=identifier>new_id</span><span class=special>){}</span>
+
+ <span class=keyword>void</span> <span class=keyword>operator</span><span class=special>()(</span><span class=identifier>employee</span><span class=special>&</span> <span class=identifier>e</span><span class=special>)</span>
+ <span class=special>{</span>
+ <span class=identifier>e</span><span class=special>.</span><span class=identifier>id</span><span class=special>=</span><span class=identifier>new_id</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>new_id</span><span class=special>;</span>
+<span class=special>};</span>
+<span class=special>...</span>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=...</span>
+
+<span class=keyword>int</span> <span class=identifier>old_id</span><span class=special>=</span><span class=identifier>it</span><span class=special>-></span><span class=identifier>id</span><span class=special>;</span> <span class=comment>// keep the original id
+
+// try to modify the id, restore it in case of collisions</span>
+<span class=identifier>es</span><span class=special>.</span><span class=identifier>modify</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>change_id</span><span class=special>(</span><span class=number>321</span><span class=special>),</span><span class=identifier>change_id</span><span class=special>(</span><span class=identifier>old_id</span><span class=special>));</span>
+</pre></blockquote>
+
+<p>In the example, <code>change_id(old_id)</code> is invoked to restore the original
+conditions when the modification results in collisions with some other element.
+The differences in behavior between <code>replace</code>, <code>modify</code> and
+<code>modify</code> with rollback have to be considered by the programmer on a
+case-by-case basis to determine the best updating mechanism.
+</p>
+
+<p align="center">
+<table cellspacing="0">
+ <caption><b>Behavior of the different updating mechanisms.</b></caption>
+<tr>
+ <th align="center">updating function</th>
+ <th>If there is a collision...</th>
+</tr>
+<tr>
+ <td align="center"><code>replace(it,x)</code></td>
+ <td>replacement does not take place.</td>
+</tr>
+<tr class="odd_tr">
+ <td align="center"><code>modify(it,mod)</code></td>
+ <td>the element is erased.</td>
+</tr>
+<tr>
+ <td align="center"><code>modify(it,mod,back)</code></td>
+ <td><code>back</code> is used to restore the original conditions.
+ (If <code>back</code> throws, the element is erased.)
+ </td>
+</tr>
+</table>
+</p>
+
+
+<p>
+Key-based versions of <code>modify</code>, named
+<a href="../reference/ord_indices.html#modify_key"><code>modify_key</code></a>, are
+provided as well. In this case, the modifying functors are passed a reference to
+the <code>key_type</code> part of the element instead of the whole object.
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>change_str</span>
+<span class=special>{</span>
+ <span class=identifier>change_str</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>new_str</span><span class=special>):</span><span class=identifier>new_str</span><span class=special>(</span><span class=identifier>new_str</span><span class=special>){}</span>
+
+ <span class=comment>// note this is passed a string, not an employee</span>
+ <span class=keyword>void</span> <span class=keyword>operator</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>str</span><span class=special>)</span>
+ <span class=special>{</span>
+ <span class=identifier>str</span><span class=special>=</span><span class=identifier>new_str</span><span class=special>;</span>
+ <span class=special>}</span>
+
+<span class=keyword>private</span><span class=special>:</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>new_str</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>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
+<span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_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=identifier>name</span><span class=special>>();</span>
+
+<span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Anna Jones"</span><span class=special>);</span>
+<span class=identifier>name_index</span><span class=special>.</span><span class=identifier>modify_key</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>change_str</span><span class=special>(</span><span class=string>"Anna Smith"</span><span class=special>));</span>
+</pre></blockquote>
+
+<p>
+Like <code>modify</code>, there are versions of <code>modify_key</code> with and
+without rollback. <code>modify</code> and
+<code>modify_key</code> are particularly well suited to use in conjunction to
+<a href="../../../../libs/lambda/index.html">Boost.Lambda</a>
+for defining the modifying functors:
+</p>
+
+<blockquote><pre>
+<span class=keyword>using</span> <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>lambda</span><span class=special>;</span>
+
+<span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
+<span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_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=identifier>name</span><span class=special>>();</span>
+
+<span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Anna Jones"</span><span class=special>);</span>
+<span class=identifier>name_index</span><span class=special>.</span><span class=identifier>modify_key</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>_1</span><span class=special>=</span><span class=string>"Anna Smith"</span><span class=special>);</span>
+</pre></blockquote>
+
+<p>
+<code>modify_key</code> requires that the key extractor be of
+a special type called
+<a href="key_extraction.html#read_write_key_extractors">read/write</a>:
+this is usually, but not always, the case.
+</p>
+
+<h3>
+<a name="seq_indices">Sequenced indices</a>
+</h3>
+
+<p>
+Unlike ordered indices, sequenced indices do not impose a fixed order on the
+elements: instead, these can be arranged in any position on the sequence, in the
+same way as <code>std::list</code> permits. The interface of sequenced indices
+is thus designed upon that of <code>std::list</code>; nearly every operation
+provided in the standard container is replicated here, occasionally with changes
+in the syntax and/or semantics to cope with the constraints imposed by
+Boost.MultiIndex. An important difference, commented <a href="#iterator_access">above</a>,
+is the fact that the values pointed to by sequenced index iterators are treated
+as <i>constant</i>:
+</p>
+
+<blockquote><pre>
+<span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span><span class=identifier>sequenced</span><span class=special><></span> <span class=special>></span>
+<span class=special>></span> <span class=identifier>s</span><span class=special>;</span> <span class=comment>// list-like container</span>
+
+<span class=identifier>s</span><span class=special>.</span><span class=identifier>push_front</span><span class=special>(</span><span class=number>0</span><span class=special>);</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=number>1</span><span class=special>;</span> <span class=comment>// ERROR: the element cannot be changed</span>
+</pre></blockquote>
+
+<p>
+As with any other type of index, element modification
+can nevertheless be done by means of
+<a href="#seq_updating">update operations</a>.
+</p>
+
+<p>
+Consider a <code>multi_index_container</code> with two or more indices, one of them
+of sequenced type. If an element is inserted through another index,
+then it will be automatically appended to the end of the sequenced index.
+An example will help to clarify this:
+</p>
+
+<blockquote><pre>
+<span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>sequenced</span><span class=special><>,</span> <span class=comment>// sequenced type</span>
+ <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> <span class=comment>// another index</span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>s</span><span class=special>;</span>
+
+<span class=identifier>s</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>insert</span><span class=special>(</span><span class=number>1</span><span class=special>);</span> <span class=comment>// insert 1 through index #1</span>
+<span class=identifier>s</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>insert</span><span class=special>(</span><span class=number>0</span><span class=special>);</span> <span class=comment>// insert 0 through index #1
+
+// list elements through sequenced index #0</span>
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</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>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=comment>// result: 1 0</span>
+</pre></blockquote>
+
+<p>
+Thus the behavior of sequenced indices when insertions are not made through
+them is to preserve insertion order.
+</p>
+
+<h4><a name="seq_spec">Specification</a></h4>
+
+<p>
+Sequenced indices are specified with the <code>sequenced</code> construct:
+</p>
+
+<blockquote><pre>
+<span class=identifier>sequenced</span><span class=special><[</span><i>(tag)</i><span class=special>]></span>
+</pre></blockquote>
+
+<p>
+The <a href="#tagging">tag</a> parameter is optional.
+</p>
+
+<h4><a name="list_ops">List operations</a></h4>
+
+<p>
+As mentioned before, sequenced indices mimic the interface of
+<code>std::list</code>, and most of the original operations therein are
+provided as well. The semantics and complexity of these operations, however,
+do not always coincide with those of the standard container. Differences
+result mainly from the fact that insertions into a sequenced index are not
+guaranteed to succeed, due to the possible banning by other indices
+of the <code>multi_index_container</code>. Consult the
+<a href="../reference/seq_indices.html">reference</a> for further details.
+</p>
+
+<h4><a name="seq_updating">Updating</a></h4>
+
+<p>
+Like ordered indices, sequenced indices provide
+<a href="../reference/seq_indices.html#replace"><code>replace</code></a> and
+<a href="../reference/seq_indices.html#modify"><code>modify</code></a>
+operations, with identical functionality. There is however no analogous
+<code>modify_key</code>, since sequenced indices are not key-based.
+</p>
+
+<h2><a name="projection">Projection of iterators</a></h2>
+
+<p>
+Given indices <code>i1</code> and <code>i2</code> on the same <code>multi_index_container</code>,
+<a href="../reference/multi_index_container.html#projection"><code>project</code></a> can be used to
+retrieve an <code>i2</code>-iterator from an <code>i1</code>-iterator, both of them
+pointing to the same element of the container. This functionality allows the programmer to
+move between different indices of the same <code>multi_index_container</code> when performing
+elaborate operations:
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
+<span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_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=identifier>name</span><span class=special>>();</span>
+
+<span class=comment>// list employees by ID starting from Robert Brown's ID</span>
+
+<span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Robert Brown"</span><span class=special>);</span>
+
+<span class=comment>// obtain an iterator of index #0 from it1</span>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>project</span><span class=special><</span><span class=number>0</span><span class=special>>(</span><span class=identifier>it1</span><span class=special>);</span>
+
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>it2</span><span class=special>,</span><span class=identifier>es</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=identifier>employee</span><span class=special>>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>));</span>
+</pre></blockquote>
+
+<p>
+A slightly more interesting example:
+</p>
+
+<blockquote><pre>
+<span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span>
+
+<span class=comment>// get a view to index #1 (ordered index on the words)</span>
+<span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>sorted_index</span><span class=special>=</span><span class=identifier>tc</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=comment>// prepend "older" to all occurrences of "sister"</span>
+
+<span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span>
+ <span class=identifier>sorted_index</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=string>"sister"</span><span class=special>);</span>
+
+<span class=keyword>while</span><span class=special>(</span><span class=identifier>it1</span><span class=special>!=</span><span class=identifier>sorted_index</span><span class=special>.</span><span class=identifier>end</span><span class=special>()&&*</span><span class=identifier>it1</span><span class=special>==</span><span class=string>"sister"</span><span class=special>){</span>
+ <span class=comment>// convert to an iterator to the sequenced index</span>
+ <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>project</span><span class=special><</span><span class=number>0</span><span class=special>>(</span><span class=identifier>it1</span><span class=special>);</span>
+
+ <span class=identifier>tc</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=identifier>it2</span><span class=special>,</span><span class=string>"older"</span><span class=special>);</span>
+ <span class=special>++</span><span class=identifier>it1</span><span class=special>;</span>
+<span class=special>}</span>
+</pre></blockquote>
+
+<p>
+When provided, <code>project</code> can also be used with
+<a href="#tagging">tags</a>.
+</p>
+
+<h2><a name="complexity">Complexity and exception safety</a></h2>
+
+<p>
+<code>multi_index_container</code> provides the same complexity and exception safety
+guarantees as the equivalent STL containers do. Iterator and reference validity
+is preserved in the face of insertions, even for replace and modify operations.
+</p>
+
+<p>
+Appropriate instantiations of <code>multi_index_container</code> can in fact simulate
+<code>std::set</code>, <code>std::multiset</code> and (with more limitations)
+<code>std::list</code>, as shown in the
+<a href="techniques.html#emulate_std_containers">techniques</a>
+section. These simulations are as nearly as efficient as the original STL
+containers; consult the <a href="../reference/index.html">reference</a> for further
+information on complexity guarantees and the
+<a href="../performance.html">performance section</a> for practical measurements of
+efficiency.
+</p>
+
+<hr>
+
+<div class="prev_link"><a href="index.html"><img src="../prev.gif" alt="tutorial" border="0"><br>
+Boost.MultiIndex Tutorial
+</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="indices.html"><img src="../next.gif" alt="index types" border="0"><br>
+Index types
+</a></div><br clear="all" style="clear: all;">
+
+<br>
+
+<p>Revised November 24th 2015</p>
+
+<p>© Copyright 2003-2015 Joaquín M López Muñ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>
diff --git a/doc/tutorial/creation.html b/doc/tutorial/creation.html
new file mode 100644
index 0000000..0a02138
--- /dev/null
+++ b/doc/tutorial/creation.html
@@ -0,0 +1,353 @@
+<!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 - Container creation</title>
+<link rel="stylesheet" href="../style.css" type="text/css">
+<link rel="start" href="../index.html">
+<link rel="prev" href="key_extraction.html">
+<link rel="up" href="index.html">
+<link rel="next" href="debug.html">
+</head>
+
+<body>
+<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
+"middle" width="277" height="86">Boost.MultiIndex Tutorial: Container creation</h1>
+
+<div class="prev_link"><a href="key_extraction.html"><img src="../prev.gif" alt="key extraction" border="0"><br>
+Key extraction
+</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="debug.html"><img src="../next.gif" alt="debugging support" border="0"><br>
+Debugging support
+</a></div><br clear="all" style="clear: all;">
+
+<hr>
+
+<h2>Contents</h2>
+
+<ul>
+ <li><a href="#value_semantics">Value semantics</a></li>
+ <li><a href="#ctor_args_list">Use of <code>ctor_args_list</code></a></li>
+ <li><a href="#special_allocator">Special allocator support</a></li>
+ <li><a href="#serialization">Serialization</a></li>
+</ul>
+
+<h2><a name="value_semantics">Value semantics</a></h2>
+
+<p>
+<code>multi_index_container</code>s have the usual value semantics associated
+to copy construction and assignment, i.e. copies of the elements from the source
+container are created and inserted into the destination container.
+More interestingly, copying also recreates the original order in which
+elements are arranged for <i>every index</i> of the container.
+This implies that equality of all indices is preserved under copying
+or assignment, for those index types where equality is defined. This behavior
+can be regarded as a natural extension to the general rule on copy semantics
+stating that if <code>y</code> is a copy of <code>x</code>, then
+<code>y==x</code>.
+</p>
+
+<h2><a name="ctor_args_list">Use of <code>ctor_args_list</code></a></h2>
+
+<p>
+Although in most cases <code>multi_index_container</code>s will be default constructed
+(or copied from a preexisting <code>multi_index_container</code>), sometimes it is
+necessary to specify particular values for the internal objects used (key extractors,
+comparison predicates, allocator), for instance if some of these objects do not have
+a default constructor. The same situation can arise with standard STL containers,
+which allow for the optional specification of such objects:
+</p>
+
+<blockquote><pre>
+<span class=comment>// example of non-default constructed std::set</span>
+<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>IntegralType</span><span class=special>></span>
+<span class=keyword>struct</span> <span class=identifier>modulo_less</span>
+<span class=special>{</span>
+ <span class=identifier>modulo_less</span><span class=special>(</span><span class=identifier>IntegralType</span> <span class=identifier>m</span><span class=special>):</span><span class=identifier>modulo</span><span class=special>(</span><span class=identifier>m</span><span class=special>){}</span>
+
+ <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>()(</span><span class=identifier>IntegralType</span> <span class=identifier>x</span><span class=special>,</span><span class=identifier>IntegralType</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=special>(</span><span class=identifier>x</span><span class=special>%</span><span class=identifier>modulo</span><span class=special>)<(</span><span class=identifier>y</span><span class=special>%</span><span class=identifier>modulo</span><span class=special>);</span>
+ <span class=special>}</span>
+
+<span class=keyword>private</span><span class=special>:</span>
+ <span class=identifier>IntegralType</span> <span class=identifier>modulo</span><span class=special>;</span>
+<span class=special>};</span>
+
+<span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>set</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>,</span><span class=identifier>modulo_less</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>></span> <span class=special>></span> <span class=identifier>modulo_set</span><span class=special>;</span>
+
+<span class=identifier>modulo_set</span> <span class=identifier>m</span><span class=special>(</span><span class=identifier>modulo_less</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>>(</span><span class=number>10</span><span class=special>));</span>
+</pre></blockquote>
+
+<p>
+<code>multi_index_container</code> does also provide this functionality, though in a
+considerably more complex fashion, due to the fact that the constructor
+of a <code>multi_index_container</code> has to accept values for all the internal
+objects of its indices. The full form of <code>multi_index_container</code> constructor
+is
+</p>
+
+<blockquote><pre>
+<span class=keyword>explicit</span> <span class=identifier>multi_index_container</span><span class=special>(</span>
+ <span class=keyword>const</span> <span class=identifier>ctor_args_list</span><span class=special>&</span> <span class=identifier>args_list</span><span class=special>=</span><span class=identifier>ctor_args_list</span><span class=special>(),</span>
+ <span class=keyword>const</span> <span class=identifier>allocator_type</span><span class=special>&</span> <span class=identifier>al</span><span class=special>=</span><span class=identifier>allocator_type</span><span class=special>());</span>
+</pre></blockquote>
+
+<p>
+The specification of the allocator object poses no particular problems;
+as for the <code>ctor_args_list</code>, this object is designed so as to hold
+the necessary construction values for every index in the <code>multi_index_container</code>.
+From the point of view of the user, <code>ctor_args_list</code> is equivalent
+to the type
+</p>
+
+<blockquote><pre>
+<span class=identifier>boost</span><span class=special>::</span><span class=identifier>tuple</span><span class=special><</span><span class=identifier>C<sub>0</sub></span><span class=special>,...,</span><span class=identifier>C<sub>I-1</sub></span><span class=special>></span>
+</pre></blockquote>
+
+<p>
+where <code>I</code> is the number of indices, and <code>C<sub>i</sub></code> is
+</p>
+
+<blockquote><pre>
+<span class=identifier>nth_index</span><span class=special><</span><span class=identifier>i</span><span class=special>>::</span><span class=identifier>type</span><span class=special>::</span><span class=identifier>ctor_args</span>
+</pre></blockquote>
+
+<p>
+that is, the nested type <code>ctor_args</code> of the <code>i</code>-th index. Each
+<code>ctor_args</code> type is in turn a tuple holding values for constructor
+arguments of the associated index: so, ordered indices demand a key extractor object
+and a comparison predicate, hashed indices take an initial number of buckets,
+a key extractor, a hash function and an equality predicate; while sequenced
+and random access indices do not need any construction argument. For instance,
+given the definition
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>hashed_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>></span> <span class=special>>,</span>
+ <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>>,</span> <span class=identifier>modulo_less</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>></span> <span class=special>>,</span>
+ <span class=identifier>sequenced</span><span class=special><>,</span>
+ <span class=identifier>random_access</span><span class=special><></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>modulo_indexed_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+the corresponding <code>ctor_args_list</code> type is equivalent to
+</p>
+
+<blockquote><pre>
+<span class=identifier>boost</span><span class=special>::</span><span class=identifier>tuple</span><span class=special><</span>
+ <span class=comment>// ctr_args of index #0</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tuple</span><span class=special><</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span><span class=special>,</span> <span class=comment>// initial number of buckets; 0 if unspecified</span>
+ <span class=identifier>identity</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>>,</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>hash</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>>,</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>equal_to</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>></span> <span class=special>>,</span>
+
+ <span class=comment>// ctr_args of index #1</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tuple</span><span class=special><</span>
+ <span class=identifier>identity</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>>,</span>
+ <span class=identifier>modulo_less</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>></span> <span class=special>>,</span>
+
+ <span class=comment>// sequenced indices do not have any construction argument</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tuple</span><span class=special><>,</span>
+
+ <span class=comment>// neither do random access indices</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tuple</span><span class=special><></span>
+<span class=special>></span>
+</pre></blockquote>
+
+<p>
+Such a <code>modulo_indexed_set</code> cannot be default constructed, because
+<code>modulo_less</code> does not provide a default constructor. The following shows
+how the construction can be done:
+</p>
+
+<blockquote><pre>
+<span class=identifier>modulo_indexed_set</span><span class=special>::</span><span class=identifier>ctor_args_list</span> <span class=identifier>args_list</span><span class=special>=</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span>
+ <span class=comment>// ctor_args for index #0 is default constructible</span>
+ <span class=identifier>modulo_indexed_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>0</span><span class=special>>::</span><span class=identifier>type</span><span class=special>::</span><span class=identifier>ctor_args</span><span class=special>(),</span>
+
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>>(),</span><span class=identifier>modulo_less</span><span class=special><</span><span class=keyword>unsigned</span> <span class=keyword>int</span><span class=special>>(</span><span class=number>10</span><span class=special>)),</span>
+
+ <span class=comment>// these are also default constructible (actually, empty tuples)</span>
+ <span class=identifier>modulo_indexed_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=special>::</span><span class=identifier>ctor_args</span><span class=special>(),</span>
+ <span class=identifier>modulo_indexed_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>3</span><span class=special>>::</span><span class=identifier>type</span><span class=special>::</span><span class=identifier>ctor_args</span><span class=special>()</span>
+ <span class=special>);</span>
+
+<span class=identifier>modulo_indexed_set</span> <span class=identifier>m</span><span class=special>(</span><span class=identifier>args_list</span><span class=special>);</span>
+</pre></blockquote>
+
+<p>
+A program is provided in the <a href="../examples.html#example3">examples section</a> that
+puts in practise these concepts.
+</p>
+
+<h2><a name="special_allocator">Special allocator support</a></h2>
+
+<p>
+Boost.MultiIndex allows for a slightly more general class of allocators
+than strictly required by the C++ standard, as explained in detail in the
+<a href="../reference/multi_index_container.html#instantiation_types">reference</a>.
+An important type of non-standard allocators supported are those provided by the
+<a href="../../../interprocess/index.html">Boost Interprocess Library</a>;
+this opens up the possibility of placing <code>multi_index_container</code>s
+in shared memory.
+</p>
+
+<blockquote><pre>
+<span class=preprocessor>#include</span> <span class=special><</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>interprocess</span><span class=special>/</span><span class=identifier>allocators</span><span class=special>/</span><span class=identifier>allocator</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span>
+<span class=preprocessor>#include</span> <span class=special><</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>interprocess</span><span class=special>/</span><span class=identifier>managed_shared_memory</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span>
+
+<span class=keyword>namespace</span> <span class=identifier>bip</span><span class=special>=</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>interprocess</span><span class=special>;</span>
+
+<span class=comment>// a shared memory compatible allocator of ints</span>
+<span class=keyword>typedef</span> <span class=identifier>bip</span><span class=special>::</span><span class=identifier>allocator</span><span class=special><</span>
+ <span class=keyword>int</span><span class=special>,</span><span class=identifier>bip</span><span class=special>::</span><span class=identifier>managed_shared_memory</span><span class=special>::</span><span class=identifier>segment_manager</span>
+<span class=special>></span> <span class=identifier>shared_int_allocator</span><span class=special>;</span>
+
+<span class=comment>// define a shared memory compatible multi_index_container
+// using shared_int_allocator</span>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>sequenced</span><span class=special><>,</span>
+ <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>
+ <span class=special>>,</span>
+ <span class=identifier>shared_int_allocator</span>
+<span class=special>></span> <span class=identifier>unique_int_list</span><span class=special>;</span>
+
+<span class=special>...</span>
+
+<span class=comment>// create a managed memory segment</span>
+<span class=identifier>bip</span><span class=special>::</span><span class=identifier>managed_shared_memory</span> <span class=identifier>seg</span><span class=special>(</span>
+ <span class=identifier>bip</span><span class=special>::</span><span class=identifier>create_only</span><span class=special>,</span><span class=string>"SharedMemoryID"</span><span class=special>,</span><span class=number>65536</span><span class=special>);</span>
+
+<span class=comment>// construct a unique_int_list into the segment</span>
+<span class=identifier>unique_int_list</span><span class=special>*</span> <span class=identifier>puil</span><span class=special>=</span><span class=identifier>seg</span><span class=special>.</span><span class=identifier>construct</span><span class=special><</span><span class=identifier>unique_int_list</span><span class=special>></span>
+ <span class=special>(</span><span class=string>"UniqueIntListID"</span><span class=special>)</span> <span class=comment>// object identifier within the segment
+ // Construction args: first a ctor arg list, then a
+ // shared memory allocator obtained from the segment object.</span>
+ <span class=special>(</span><span class=identifier>unique_int_list</span><span class=special>::</span><span class=identifier>ctor_args_list</span><span class=special>(),</span>
+ <span class=identifier>unique_int_list</span><span class=special>::</span><span class=identifier>allocator_type</span><span class=special>(</span><span class=identifier>seg</span><span class=special>.</span><span class=identifier>get_segment_manager</span><span class=special>()));</span>
+ </pre></blockquote>
+
+<p>
+The examples section includes a <a href="../examples.html#example12">program</a>
+that further explores this capability.
+</p>
+
+<h2><a name="serialization">Serialization</a></h2>
+
+<p>
+<code>multi_index_container</code>s can be archived and retrieved by means of the
+<a href="../../../serialization/index.html">Boost Serialization Library</a>. Both regular
+and XML archives are supported. The usage is straightforward and does not
+differ from that of any other serializable type. For instance:
+</p>
+
+<blockquote><pre>
+<span class=preprocessor>#include</span> <span class=special><</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>archive</span><span class=special>/</span><span class=identifier>text_oarchive</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span>
+<span class=preprocessor>#include</span> <span class=special><</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>archive</span><span class=special>/</span><span class=identifier>text_iarchive</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span>
+<span class=preprocessor>#include</span> <span class=special><</span><span class=identifier>fstream</span><span class=special>></span>
+
+<span class=special>...</span>
+
+<span class=keyword>void</span> <span class=identifier>save</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>employee_set</span><span class=special>&</span> <span class=identifier>es</span><span class=special>)</span>
+<span class=special>{</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>ofstream</span> <span class=identifier>ofs</span><span class=special>(</span><span class=string>"data"</span><span class=special>);</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>archive</span><span class=special>::</span><span class=identifier>text_oarchive</span> <span class=identifier>oa</span><span class=special>(</span><span class=identifier>ofs</span><span class=special>);</span>
+ <span class=identifier>oa</span><span class=special><<</span><span class=identifier>es</span><span class=special>;</span>
+<span class=special>}</span>
+
+<span class=keyword>void</span> <span class=identifier>load</span><span class=special>(</span><span class=identifier>employee_set</span><span class=special>&</span> <span class=identifier>es</span><span class=special>)</span>
+<span class=special>{</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>ifstream</span> <span class=identifier>ifs</span><span class=special>(</span><span class=string>"data"</span><span class=special>);</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>archive</span><span class=special>::</span><span class=identifier>text_iarchive</span> <span class=identifier>ia</span><span class=special>(</span><span class=identifier>ifs</span><span class=special>);</span>
+ <span class=identifier>ia</span><span class=special>>></span><span class=identifier>es</span><span class=special>;</span>
+<span class=special>}</span>
+
+<span class=special>...</span>
+
+<span class=identifier>employee_set</span> <span class=identifier>es</span><span class=special>;</span>
+<span class=special>...</span> <span class=comment>// fill it with data</span>
+<span class=identifier>save</span><span class=special>(</span><span class=identifier>es</span><span class=special>);</span>
+
+<span class=special>...</span>
+
+<span class=identifier>employee_set</span> <span class=identifier>restored_es</span><span class=special>;</span>
+<span class=identifier>load</span><span class=special>(</span><span class=identifier>restored_es</span><span class=special>);</span>
+</pre></blockquote>
+
+<p>
+Serialization capabilities are automatically provided by just linking with
+the appropriate Boost.Serialization library module: it is not necessary
+to explicitly include any header from Boost.Serialization,
+apart from those declaring the type of archive used in the process. If not used,
+however, serialization support can be disabled by globally defining the macro
+<code>BOOST_MULTI_INDEX_DISABLE_SERIALIZATION</code>. Disabling serialization
+for Boost.MultiIndex can yield a small improvement in build times, and may
+be necessary in those defective compilers that fail to correctly process
+Boost.Serialization headers.
+</p>
+
+<p>
+In accordance with Boost.MultiIndex
+<a href="#value_semantics">value semantics</a>, retrieving an
+archived <code>multi_index_container</code> restores not only
+the elements, but also the order they were arranged into for
+every index of the container. There is an exception to this rule,
+though: for <a href="indices.html#hashed_indices">hashed
+indices</a>, no guarantee is made about the order in which elements will
+be iterated in the restored container; in general, it is unwise to rely on
+the ordering of elements of a hashed index, since it can change in arbitrary
+ways during insertion or rehashing --this is precisely the reason why
+hashed indices and TR1 unordered associative containers do not define
+an equality operator.
+</p>
+
+<p>
+Iterators to indices of a <code>multi_index_container</code> can also be
+serialized. Serialization of iterators must be done only after serializing
+their corresponding container.
+</p>
+
+<p>
+<a href="../examples.html#example9">Example 9</a> in the examples section shows
+the serialization capabilities of Boost.MultiIndex.
+</p>
+
+<hr>
+
+<div class="prev_link"><a href="key_extraction.html"><img src="../prev.gif" alt="key extraction" border="0"><br>
+Key extraction
+</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="debug.html"><img src="../next.gif" alt="debugging support" border="0"><br>
+Debugging support
+</a></div><br clear="all" style="clear: all;">
+
+<br>
+
+<p>Revised July 17th 2007</p>
+
+<p>© Copyright 2003-2007 Joaquín M López Muñ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>
diff --git a/doc/tutorial/debug.html b/doc/tutorial/debug.html
new file mode 100644
index 0000000..3853e84
--- /dev/null
+++ b/doc/tutorial/debug.html
@@ -0,0 +1,252 @@
+<!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 -Debugging support</title>
+<link rel="stylesheet" href="../style.css" type="text/css">
+<link rel="start" href="../index.html">
+<link rel="prev" href="creation.html">
+<link rel="up" href="index.html">
+<link rel="next" href="techniques.html">
+</head>
+
+<body>
+<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
+"middle" width="277" height="86">Boost.MultiIndex Tutorial: Debugging support</h1>
+
+<div class="prev_link"><a href="creation.html"><img src="../prev.gif" alt="container creation" border="0"><br>
+Container creation
+</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="techniques.html"><img src="../next.gif" alt="techniques" border="0"><br>
+Techniques
+</a></div><br clear="all" style="clear: all;">
+
+<hr>
+
+<h2>Contents</h2>
+
+<ul>
+ <li><a href="#debugging_support">Debugging support</a></li>
+ <li><a href="#safe_mode">Safe mode</a>
+ <ul>
+ <li><a href="#serialization_and_safe_mode">Serialization and safe mode</a></li>
+ </ul>
+ </li>
+ <li><a href="#invariant_check">Invariant-checking mode</a></li>
+</ul>
+
+<h2><a name="debugging_support">Debugging support</a></h2>
+
+<p>
+The concept of <i>Design by Contract</i>, originally developed as part
+of Bertrand Meyer's <a href="http://www.eiffel.com">Eiffel</a> language,
+revolves around the formulation of a <i>contract</i> between the user
+of a library and the implementor, by which the first is required to
+respect some <i>preconditions</i> on the values passed when invoking
+methods of the library, and the implementor guarantees in return
+that certain constraints on the results are met (<i>postconditions</i>),
+as well as the honoring of specified internal consistency rules, called
+<i>invariants</i>. Eiffel natively supports the three parts of the
+contract just described by means of constructs <code>require</code>,
+<code>ensure</code> and <code>invariant</code>, respectively.
+</p>
+
+<p>
+C++ does not enjoy direct support for Design by Contract techniques: these
+are customarily implemented as assertion code, often turned off in
+release mode for performance reasons. Following this approach,
+Boost.MultiIndex provides two distinct debugging modes:
+<ul>
+ <li><i>Safe mode</i> checks preconditions on the invocations to the
+ facilities of the library,</li>
+ <li><i>invariant-checking mode</i> performs post-execution checks aimed
+ at ensuring that the internal consistency of the library is preserved.</li>
+</ul>
+These two modes are independent of each other and can be set on or off
+individually. It is important to note that errors detected by safe mode are
+due in principle to faulty code in the user's program, while
+invariant-checking mode detects potential <i>internal</i> bugs in the
+implementation of Boost.MultiIndex.
+</p>
+
+<h2><a name="safe_mode">Safe mode</a></h2>
+
+<p>
+The idea of adding precondition checking facilities to STL as a debugging aid
+was first introduced by Cay S. Horstmann in his
+<a href="http://www.horstmann.com/safestl.html">Safe STL</a> library and later
+adopted by <a href="http://www.stlport.com/doc/debug_mode.html">STLport Debug
+Mode</a>. Similarly, Boost.MultiIndex features the so-called <i>safe mode</i>
+in which all sorts of preconditions are checked when dealing with iterators
+and functions of the library.
+</p>
+
+<p>
+Boost.MultiIndex safe mode is set by globally defining the macro
+<code>BOOST_MULTI_INDEX_ENABLE_SAFE_MODE</code>. Error conditions
+are checked via the macro <code>BOOST_MULTI_INDEX_SAFE_MODE_ASSERT</code>, which
+by default resolves to a call to <a href="../../../../libs/assert">
+<code>BOOST_ASSERT</code></a>.
+</p>
+
+<p>
+If the user decides to define her own version of
+<code>BOOST_MULTI_INDEX_SAFE_MODE_ASSERT</code>, it has to take the form
+</p>
+
+<blockquote><pre>
+<span class=identifier>BOOST_MULTI_INDEX_SAFE_MODE_ASSERT</span><span class=special>(</span><span class=identifier>expr</span><span class=special>,</span><span class=identifier>error_code</span><span class=special>)</span>
+</pre></blockquote>
+
+<p>
+where <code>expr</code> is the condition checked and <code>error_code</code>
+is one value of the <code>safe_mode::error_code</code> enumeration:
+</p>
+
+<blockquote><pre>
+<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
+
+<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
+
+<span class=keyword>namespace</span> <span class=identifier>safe_mode</span><span class=special>{</span>
+
+<span class=keyword>enum</span> <span class=identifier>error_code</span>
+<span class=special>{</span>
+ <span class=identifier>invalid_iterator</span><span class=special>,</span> <span class=comment>// vg. default cted or pointing to erased element</span>
+ <span class=identifier>not_dereferenceable_iterator</span><span class=special>,</span> <span class=comment>// iterator is not dereferenceable</span>
+ <span class=identifier>not_incrementable_iterator</span><span class=special>,</span> <span class=comment>// iterator points to end of sequence</span>
+ <span class=identifier>not_decrementable_iterator</span><span class=special>,</span> <span class=comment>// iterator points to beginning of sequence</span>
+ <span class=identifier>not_owner</span><span class=special>,</span> <span class=comment>// iterator does not belong to the container</span>
+ <span class=identifier>not_same_owner</span><span class=special>,</span> <span class=comment>// iterators belong to different containers</span>
+ <span class=identifier>invalid_range</span><span class=special>,</span> <span class=comment>// last not reachable from first</span>
+ <span class=identifier>inside_range</span><span class=special>,</span> <span class=comment>// iterator lies within a range (and it mustn't)</span>
+ <span class=identifier>out_of_bounds</span><span class=special>,</span> <span class=comment>// move attempted beyond container limits</span>
+ <span class=identifier>same_container</span> <span class=comment>// containers ought to be different</span>
+<span class=special>};</span>
+
+<span class=special>}</span> <span class=comment>// namespace multi_index::safe_mode</span>
+
+<span class=special>}</span> <span class=comment>// namespace multi_index</span>
+
+<span class=special>}</span> <span class=comment>// namespace boost</span>
+</pre></blockquote>
+
+<p>
+For instance, the following replacement of
+<code>BOOST_MULTI_INDEX_SAFE_MODE_ASSERT</code> throws an exception instead of
+asserting:
+</p>
+
+<blockquote><pre>
+<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>safe_mode_errors</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span>
+
+<span class=keyword>struct</span> <span class=identifier>safe_mode_exception</span>
+<span class=special>{</span>
+ <span class=identifier>safe_mode_exception</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>safe_mode</span><span class=special>::</span><span class=identifier>error_code</span> <span class=identifier>error_code</span><span class=special>):</span>
+ <span class=identifier>error_code</span><span class=special>(</span><span class=identifier>error_code</span><span class=special>)</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>safe_mode</span><span class=special>::</span><span class=identifier>error_code</span> <span class=identifier>error_code</span><span class=special>;</span>
+<span class=special>};</span>
+
+<span class=preprocessor>#define</span> <span class=identifier>BOOST_MULTI_INDEX_SAFE_MODE_ASSERT</span><span class=special>(</span><span class=identifier>expr</span><span class=special>,</span><span class=identifier>error_code</span><span class=special>)</span> <span class=special>\</span>
+<span class=keyword>if</span><span class=special>(!(</span><span class=identifier>expr</span><span class=special>)){</span><span class=keyword>throw</span> <span class=identifier>safe_mode_exception</span><span class=special>(</span><span class=identifier>error_code</span><span class=special>);}</span>
+
+<span class=comment>// This has to go before the inclusion of any header from Boost.MultiIndex,
+// except possibly safe_error_codes.hpp.</span>
+</pre></blockquote>
+
+<p>
+Other possibilites, like outputting to a log or firing some kind of alert, are
+also implementable.
+</p>
+
+<p>
+<b>Warning:</b> Safe mode adds a very important overhead to the program
+both in terms of space and time used, so in general it should not be set for
+<code>NDEBUG</code> builds. Also, this mode is intended solely as a debugging aid,
+and programs must not rely on it as part of their normal execution flow: in
+particular, no guarantee is made that all possible precondition errors are diagnosed,
+or that the checks remain stable across different versions of the library.
+</p>
+
+<h3><a name="serialization_and_safe_mode">Serialization and safe mode</a></h3>
+
+<p>
+Iterators restored from an archive are not subject to safe mode checks. This is
+so because it is not possible to automatically know the associated
+<code>multi_index_container</code> of an iterator from the serialization
+information alone. However, if desired, a restored iterator can be converted to a
+checked value by using the following workaround:
+</p>
+
+<blockquote><pre>
+<span class=identifier>employee_set</span> <span class=identifier>es</span><span class=special>;</span>
+<span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>;</span>
+
+<span class=comment>// restore es and it from an archive ar</span>
+<span class=identifier>ar</span><span class=special>>></span><span class=identifier>es</span><span class=special>;</span>
+<span class=identifier>ar</span><span class=special>>></span><span class=identifier>it</span><span class=special>;</span> <span class=comment>// it won't benefit from safe mode checks
+
+// Turn it into a checked value by providing Boost.MultiIndex
+// with info about the associated container.
+// This statement has virtually zero cost if safe mode is turned off.</span>
+<span class=identifier>it</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>project</span><span class=special><</span><span class=number>1</span><span class=special>>(</span><span class=identifier>it</span><span class=special>);</span>
+</pre></blockquote>
+
+<h2><a name="invariant_check">Invariant-checking mode</a></h2>
+
+<p>
+The so called <i>invariant-checking mode</i> of Boost.MultiIndex can be
+set by globally defining the macro
+<code>BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING</code>.
+When this mode is in effect, all public functions of Boost.MultiIndex
+will perform post-execution tests aimed at ensuring that the basic
+internal invariants of the data structures managed are preserved.
+</p>
+
+<p>
+If an invariant test fails, Boost.MultiIndex will indicate the failure
+by means of the unary macro <code>BOOST_MULTI_INDEX_INVARIANT_ASSERT</code>.
+Unless the user provides a definition for this macro, it defaults to
+<a href="../../../../libs/assert">
+<code>BOOST_ASSERT</code></a>. Any assertion of this kind should
+be regarded in principle as a bug in the library. Please report such
+problems, along with as much contextual information as possible, to the
+maintainer of the library.
+</p>
+
+<p>
+It is recommended that users of Boost.MultiIndex always set the
+invariant-checking mode in debug builds.
+</p>
+
+<hr>
+
+<div class="prev_link"><a href="creation.html"><img src="../prev.gif" alt="container creation" border="0"><br>
+Container creation
+</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="techniques.html"><img src="../next.gif" alt="techniques" border="0"><br>
+Techniques
+</a></div><br clear="all" style="clear: all;">
+
+<br>
+
+<p>Revised July 07th 2017</p>
+
+<p>© Copyright 2003-2017 Joaquín M López Muñ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>
diff --git a/doc/tutorial/index.html b/doc/tutorial/index.html
new file mode 100644
index 0000000..b70ea35
--- /dev/null
+++ b/doc/tutorial/index.html
@@ -0,0 +1,139 @@
+<!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</title>
+<link rel="stylesheet" href="../style.css" type="text/css">
+<link rel="start" href="../index.html">
+<link rel="prev" href="../index.html">
+<link rel="up" href="../index.html">
+<link rel="next" href="basics.html">
+</head>
+
+<body>
+<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
+"middle" width="277" height="86">Boost.MultiIndex Tutorial</h1>
+
+<div class="prev_link"><a href="../index.html"><img src="../prev.gif" alt="index" border="0"><br>
+Index
+</a></div>
+<div class="up_link"><a href="../index.html"><img src="../up.gif" alt="index" border="0"><br>
+Index
+</a></div>
+<div class="next_link"><a href="basics.html"><img src="../next.gif" alt="basics" border="0"><br>
+Basics
+</a></div><br clear="all" style="clear: all;">
+
+<hr>
+
+<h2>Contents</h2>
+
+<ul>
+ <li><a href="#rationale">Rationale</a></li>
+ <li><a href="#namespace">Namespace</a></li>
+ <li><a href="basics.html">Basics</a></li>
+ <li><a href="indices.html">Index types</a></li>
+ <li><a href="key_extraction.html">Key extraction</a></li>
+ <li><a href="creation.html">Container creation</a></li>
+ <li><a href="debug.html">Debugging support</a></li>
+ <li><a href="techniques.html">Techniques</a></li>
+</ul>
+
+<h2><a name="rationale">Rationale</a></h2>
+
+<p>
+STL containers are designed around the concept that each container controls its
+own collection of elements, giving access to them in a manner specified by the
+container's type: so, an <code>std::set</code> maintains the elements ordered
+by a specified sorting criterion, <code>std::list</code> allows for free
+positioning of elements along a linear sequence, and so on.
+</p>
+
+<p>
+Sometimes, the necessity arises of having different access interfaces
+to the same underlying collection: for instance, some data might need to be
+sorted according to more than one comparison predicate, or a bidirectional list
+might benefit from a supplemental logarithmic lookup interface. In these
+situations, programmers typically resort to manual compositions of different
+containers, a solution that generally involves a fair amount of code
+devoted to preserve the synchronization of the different parts of
+the composition. Boost.MultiIndex allows for the specification of
+<code>multi_index_container</code>s comprised of one or more <i>indices</i> with
+different interfaces to the same collection of elements. The resulting constructs
+are conceptually cleaner than manual compositions, and often perform much better.
+An important design decision has been taken that the indices of a given
+<code>multi_index_container</code> instantiation be specified at compile time: this
+gives ample room for static type checking and code optimization.
+</p>
+
+<p>
+Boost.MultiIndex takes inspiration from basic concepts of indexing arising in the
+theory of relational databases, though it is not intended to provide a full-fledged
+relational database framework. <code>multi_index_container</code> integrates seamlessly
+into the STL container/algorithm design, and features some extra capabilities regarding
+lookup operations and element updating which are useful extensions even for
+single-indexed containers.
+</p>
+
+<p align="center">
+<img src="multi_index_cont_example.png"
+alt="diagram of a multi_index_container with three indices"
+width="600" height="304"><br>
+<b>Fig. 1: Diagram of a <code>multi_index_container</code> with three indices.</b>
+</p>
+
+<p>
+The figure above depicts a <code>multi_index_container</code> composed of three indices:
+the first two present a set-like interface to the elements sorted by
+shape and id, respectively, while the latter index provides the functionality
+of a bidirectional list in the spirit of <code>std::list</code>. These
+indices act as "views" to the internal collection of elements, but they do not only
+provide read access to the set: insertion/deletion methods are also implemented much
+as those of <code>std::set</code>s or <code>std::list</code>s. Insertion of an
+element through one given index will only succeed if the uniqueness constraints of all
+indices are met.
+</p>
+
+<h2>
+<a name="namespace">Namespace</a>
+</h2>
+
+<p>
+All the public types of Boost.MultiIndex reside in namespace <code>::boost::multi_index</code>.
+Additionaly, the main class template <code>multi_index_container</code> and global functions
+<code>get</code> and <code>project</code> are lifted to namespace <code>::boost</code>
+by means of <code>using</code> declarations. For brevity of exposition, the fragments
+of code in the documentation are written as if the following declarations were in effect:
+</p>
+
+<blockquote><pre>
+<span class=keyword>using</span> <span class=keyword>namespace</span> <span class=special>::</span><span class=identifier>boost</span><span class=special>;</span>
+<span class=keyword>using</span> <span class=keyword>namespace</span> <span class=special>::</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>multi_index</span><span class=special>;</span>
+</pre></blockquote>
+
+<hr>
+
+<div class="prev_link"><a href="../index.html"><img src="../prev.gif" alt="index" border="0"><br>
+Index
+</a></div>
+<div class="up_link"><a href="../index.html"><img src="../up.gif" alt="index" border="0"><br>
+Index
+</a></div>
+<div class="next_link"><a href="basics.html"><img src="../next.gif" alt="basics" border="0"><br>
+Basics
+</a></div><br clear="all" style="clear: all;">
+
+<br>
+
+<p>Revised February 21st 2006</p>
+
+<p>© Copyright 2003-2006 Joaquín M López Muñ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>
diff --git a/doc/tutorial/indices.html b/doc/tutorial/indices.html
new file mode 100644
index 0000000..835d533
--- /dev/null
+++ b/doc/tutorial/indices.html
@@ -0,0 +1,834 @@
+<!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"> key-based </td>
+ <td align="center" rowspan="4"> ordered </td>
+ <td align="center"> <code>ordered_unique</code> </td>
+</tr>
+<tr class="odd_tr">
+ <td align="center"> <code>ordered_non_unique</code> </td>
+</tr>
+<tr>
+ <td align="center"> <code>ranked_unique</code> </td>
+</tr>
+<tr class="odd_tr">
+ <td align="center"> <code>ranked_non_unique</code> </td>
+</tr>
+<tr>
+ <td align="center" rowspan="2"> hashed </td>
+ <td align="center"> <code>hashed_unique</code> </td>
+</tr>
+<tr class="odd_tr">
+ <td align="center"> <code>hashed_non_unique</code> </td>
+</tr>
+<tr>
+ <td align="center" rowspan="2" colspan="2"> non key-based </td>
+ <td align="center"><code> sequenced </code></td>
+</tr>
+<tr class="odd_tr">
+ <td align="center"><code> random_access </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><</span><span class=keyword>int</span><span class=special>></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>&</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><</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>
+<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><</span>
+ <span class=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <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>
+ <span class=special>></span>
+<span class=special>></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>&</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><</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>
+<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
+—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><[</span><i>(tag)</i><span class=special>[,</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]]></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><[</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]></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>&</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><<</span><span class=identifier>n</span><span class=special><<</span><span class=string>" lies in the "</span><span class=special><<</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>()<<</span><span class=string>" percentile\n"</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><</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>
+<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>
+<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>
+<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>
+<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>
+
+<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>&</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><(</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>
+<span class=special>};</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=comment>// sort by employee::operator<</span>
+ <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>
+
+ <span class=comment>// sort by less<string> on name</span>
+ <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>
+
+ <span class=comment>// hashed on ssnumber</span>
+ <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>
+ <span class=special>></span>
+<span class=special>></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><[</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>
+
+<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><[</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>
+</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<KeyFromValue::result_type></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>&</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>&</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>&</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><</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>
+ <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><</span><span class=keyword>int</span><span class=special>>()(</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><</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>
+
+<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>&</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>
+<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><</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>
+<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>
+<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>
+<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>
+
+<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><</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><</span>
+ <span class=identifier>random_access</span><span class=special><>,</span>
+ <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>
+ <span class=special>></span>
+<span class=special>></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><</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>
+<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><<</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><[</span><i>(tag)</i><span class=special>]></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><</span>
+ <span class=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>random_access</span><span class=special><>,</span>
+ <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>
+ <span class=special>></span>
+<span class=special>></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::shuffle</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><</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>
+<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>
+
+<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><</span><span class=number>1</span><span class=special>>().</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><</span><span class=number>1</span><span class=special>>().</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><</span>
+ <span class=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span><span class=identifier>sequenced</span><span class=special><></span> <span class=special>></span>
+<span class=special>></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 29th 2017</p>
+
+<p>© Copyright 2003-2017 Joaquín M López Muñ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>
diff --git a/doc/tutorial/key_extraction.html b/doc/tutorial/key_extraction.html
new file mode 100644
index 0000000..8f455a6
--- /dev/null
+++ b/doc/tutorial/key_extraction.html
@@ -0,0 +1,968 @@
+<!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 - Key extraction</title>
+<link rel="stylesheet" href="../style.css" type="text/css">
+<link rel="start" href="../index.html">
+<link rel="prev" href="indices.html">
+<link rel="up" href="index.html">
+<link rel="next" href="creation.html">
+</head>
+
+<body>
+<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
+"middle" width="277" height="86">Boost.MultiIndex Tutorial: Key extraction</h1>
+
+<div class="prev_link"><a href="indices.html"><img src="../prev.gif" alt="index types" border="0"><br>
+Index types
+</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="creation.html"><img src="../next.gif" alt="container creation" border="0"><br>
+Container creation
+</a></div><br clear="all" style="clear: all;">
+
+<hr>
+
+<h2>Contents</h2>
+
+<ul>
+ <li><a href="#intro">Introduction</a>
+ <ul>
+ <li><a href="#read_write_key_extractors">Read/write key extractors</a></li>
+ </ul>
+ </li>
+ <li><a href="#predefined_key_extractors">Predefined key extractors</a>
+ <ul>
+ <li><a href="#identity"><code>identity</code></a></li>
+ <li><a href="#member"><code>member</code></a></li>
+ <li><a href="#const_mem_fun"><code>const_mem_fun</code>
+ and <code>mem_fun</code></a></li>
+ <li><a href="#global_fun"><code>global_fun</code></a></li>
+ </ul>
+ </li>
+ <li><a href="#user_defined_key_extractors">User-defined key extractors</a></li>
+ <li><a href="#composite_keys">Composite keys</a>
+ <ul>
+ <li><a href="#composite_keys_hash">Composite keys and hashed indices</a></li>
+ </ul>
+ </li>
+ <li><a href="#advanced_key_extractors">Advanced features of Boost.MultiIndex key
+ extractors</a></li>
+</ul>
+
+<h2><a name="intro">Introduction</a></h2>
+
+<p>
+STL associative containers have a notion of key, albeit in a somewhat incipient
+form. So, the keys of such containers are identified by a nested type
+<code>key_type</code>; for <code>std::set</code>s and <code>std::multiset</code>s,
+<code>key_type</code> coincides with <code>value_type</code>, i.e. the key is the
+element itself. <code>std::map</code> and <code>std::multimap</code> manage
+elements of type <code>std::pair<const Key,T></code>, where the first
+member is the key. In either case, the process of obtaining the key from a
+given element is implicitly fixed and cannot be customized by the user.
+</p>
+
+<p>
+Fixed key extraction mechanisms like those performed by STL associative
+containers do not scale well in the context of Boost.MultiIndex, where
+several indices share their <code>value_type</code> definition but
+might feature completely different lookup semantics. For this reason,
+Boost.MultiIndex formalizes the concept of a
+<a href="../reference/key_extraction.html#key_extractors"><code>Key
+Extractor</code></a> in order to make it explicit and controllable
+in the definition of key-based indices.
+</p>
+
+<p>
+Intuitively speaking, a key extractor is a function object that accepts
+a reference to an element and returns its associated key. The formal
+concept also imposes some reasonable constraints about the stability
+of the process, in the sense that extractors are assumed to
+return the same key when passed the same element: this is in consonance
+with the informal understanding that keys are actually some "part"
+of the element and do not depend on external data.
+</p>
+
+<h3><a name="read_write_key_extractors">Read/write key extractors</a></h3>
+
+<p>
+A key extractor is called <i>read/write</i> if it returns a non-constant reference
+to the key when passed a non-constant element, and it is called <i>read-only</i>
+otherwise. Boost.MultiIndex requires that the key extractor be read/write
+when using the <code>modify_key</code> member function of ordered and hashed
+indices. In all other situations, read-only extractors suffice.
+The section on <a href="#advanced_key_extractors">advanced features
+of Boost.MultiIndex key extractors</a> details which of the predefined
+key extractors are read/write.
+</p>
+
+<h2><a name="predefined_key_extractors">Predefined key extractors</a></h2>
+
+<h3><a name="identity"><code>identity</code></a></h3>
+
+<p>
+The <a href="../reference/key_extraction.html#identity"><code>identity</code></a>
+key extractor returns the entire base object as the associated key:
+</p>
+
+<blockquote><pre>
+<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>
+<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>
+<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>
+
+<span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <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=comment>// the key is the entire element</span>
+ <span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>cont</span><span class=special>;</span>
+</pre></blockquote>
+
+<h3><a name="member"><code>member</code></a></h3>
+
+<p>
+<a href="../reference/key_extraction.html#member"><code>member</code></a>
+key extractors return a reference to a specified
+data field of the base object. For instance, in the following version of our
+familiar employee container:
+</p>
+
+<blockquote><pre>
+<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>
+<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>
+<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>
+<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>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <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>
+ <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>
+ <span class=identifier>ordered_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>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+the second and third indices use <code>member</code> extractors on
+<code>employee::name</code> and <code>employee::ssnumber</code>, respectively.
+The specification of an instantiation of <code>member</code> is simple
+yet a little contrived:
+</p>
+
+<blockquote><pre>
+<span class=identifier>member</span><span class=special><</span><span class=identifier><i>(base type)</i></span><span class=special>,</span><span class=identifier><i>(key type)</i></span><span class=special>,</span><span class=identifier><i>(pointer to member)</i></span><span class=special>></span>
+</pre></blockquote>
+
+<p>
+It might seem that the first and second parameters are superfluous,
+since the type of the base object and of the associated data field are
+already implicit in the pointer to member argument: unfortunately, it is
+not possible to extract this information with current C++ mechanisms,
+which makes the syntax of <code>member</code> a little too verbose.
+</p>
+
+<h3><a name="const_mem_fun"><code>const_mem_fun</code> and <code>mem_fun</code></a></h3>
+
+<p>
+Sometimes, the key of an index is not a concrete data member of the element,
+but rather it is a value returned by a particular member function.
+This resembles the notion of <i>calculated indices</i> supported by some
+relational databases. Boost.MultiIndex supports this
+kind of key extraction through
+<a href="../reference/key_extraction.html#const_mem_fun"><code>const_mem_fun</code></a>.
+Consider the following container where sorting on the third index
+is based upon the length of the name field:
+</p>
+
+<blockquote><pre>
+<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>
+<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>
+<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>
+<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>
+<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>mem_fun</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></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=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=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=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>
+
+ <span class=comment>// returns the length of the name field</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>name_length</span><span class=special>()</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>name</span><span class=special>.</span><span class=identifier>size</span><span class=special>();}</span>
+<span class=special>};</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=comment>// sort by employee::operator<</span>
+ <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>
+
+ <span class=comment>// sort by less<string> on name</span>
+ <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>
+
+ <span class=comment>// sort by less<int> on name_length()</span>
+ <span class=identifier>ordered_non_unique</span><span class=special><</span>
+ <span class=identifier>const_mem_fun</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>size_t</span><span class=special>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name_length</span><span class=special>></span>
+ <span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+<code>const_mem_fun</code> usage syntax is similar to that of
+<a href="#member"><code>member</code></a>:
+</p>
+
+<blockquote><pre>
+<span class=identifier>const_mem_fun</span><span class=special><</span><span class=identifier><i>(base type)</i></span><span class=special>,</span><span class=identifier><i>(key type)</i></span><span class=special>,</span><span class=identifier><i>(pointer to member function)</i></span><span class=special>></span>
+</pre></blockquote>
+
+<p>
+The member function referred to must be <code>const</code>, take no arguments and return
+a value of the specified key type.
+Almost always you will want to use a <code>const</code> member function,
+since elements in a <code>multi_index_container</code> are treated as constant, much
+as elements of an <code>std::set</code>. However, a
+<a href="../reference/key_extraction.html#mem_fun"><code>mem_fun</code></a>
+counterpart is provided for use with non-constant member functions, whose
+applicability is discussed on the paragraph on
+<a href="#advanced_key_extractors">advanced features
+of Boost.MultiIndex key extractors</a>.
+</p>
+
+<p><a href="../examples.html#example2">Example 2</a> in the examples section
+provides a complete program showing how to use <code>const_mem_fun</code>.
+<p>
+
+<h3><a name="global_fun"><code>global_fun</code></a></h3>
+
+<p>
+Whereas <code>const_mem_fun</code> and <code>mem_fun</code> are based on a
+given member function of the base type from where the key is extracted,
+<a href="../reference/key_extraction.html#global_fun"><code>global_fun</code></a>
+takes a global function (or static member function) accepting the base
+type as its parameter and returning the key:
+</p>
+
+<blockquote><pre>
+<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>
+<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>
+<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>global_fun</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span>
+
+<span class=keyword>struct</span> <span class=identifier>rectangle</span>
+<span class=special>{</span>
+ <span class=keyword>int</span> <span class=identifier>x0</span><span class=special>,</span><span class=identifier>y0</span><span class=special>;</span>
+ <span class=keyword>int</span> <span class=identifier>x1</span><span class=special>,</span><span class=identifier>y1</span><span class=special>;</span>
+<span class=special>};</span>
+
+<span class=keyword>unsigned</span> <span class=keyword>long</span> <span class=identifier>area</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>rectangle</span><span class=special>&</span> <span class=identifier>r</span><span class=special>)</span>
+<span class=special>{</span>
+ <span class=keyword>return</span> <span class=special>(</span><span class=keyword>unsigned</span> <span class=keyword>long</span><span class=special>)(</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>x1</span><span class=special>-</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>x0</span><span class=special>)*(</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>x1</span><span class=special>-</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>x0</span><span class=special>)+</span>
+ <span class=special>(</span><span class=keyword>unsigned</span> <span class=keyword>long</span><span class=special>)(</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>y1</span><span class=special>-</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>y0</span><span class=special>)*(</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>y1</span><span class=special>-</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>y0</span><span class=special>);</span>
+<span class=special>}</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>rectangle</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=comment>// sort by increasing area</span>
+ <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>global_fun</span><span class=special><</span><span class=keyword>const</span> <span class=identifier>rectangle</span><span class=special>&,</span><span class=keyword>unsigned</span> <span class=keyword>long</span><span class=special>,&</span><span class=identifier>area</span><span class=special>></span> <span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>rectangle_container</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+The specification of <code>global_fun</code> obeys the following syntax:
+</p>
+
+<blockquote><pre>
+<span class=identifier>global_fun</span><span class=special><</span><span class=identifier><i>(argument type)</i></span><span class=special>,</span><span class=identifier><i>(key type)</i></span><span class=special>,</span><span class=identifier><i>(pointer to function)</i></span><span class=special>></span>
+</pre></blockquote>
+
+<p>
+where the argument type and key type must match <i>exactly</i> those in the
+signature of the function used; for instance, in the example above the argument
+type is <code>const rectangle&</code>, without omitting the "<code>const</code>"
+and "<code>&</code>" parts. So, although most of the time the base type will be
+accepted by constant reference, <code>global_fun</code> is also prepared to take
+functions accepting their argument by value or by non-constant reference: this
+latter case cannot generally be used directly in the specification of
+<code>multi_index_container</code>s as their elements are treated as constant,
+but the section on <a href="#advanced_key_extractors">advanced features
+of Boost.MultiIndex key extractors</a> describes valid use cases of
+key extraction based on such functions with a non-constant reference argument.
+</p>
+
+<p><a href="../examples.html#example2">Example 2</a> in the examples section
+uses <code>gobal_fun</code>.
+<p>
+
+<h2><a name="user_defined_key_extractors">User-defined key extractors</a></h2>
+
+<p>
+Although the <a href="#predefined_key_extractors">predefined key extractors</a>
+provided by Boost.MultiIndex are intended to serve most cases,
+the user can also provide her own key extractors in more exotic situations,
+as long as these conform to the
+<a href="../reference/key_extraction.html#key_extractors"><code>Key
+Extractor</code></a> concept.
+</p>
+
+<blockquote><pre>
+<span class=comment>// some record class</span>
+<span class=keyword>struct</span> <span class=identifier>record</span>
+<span class=special>{</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>gregorian</span><span class=special>::</span><span class=identifier>date</span> <span class=identifier>d</span><span class=special>;</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>str</span><span class=special>;</span>
+<span class=special>};</span>
+
+<span class=comment>// extracts a record's year</span>
+<span class=keyword>struct</span> <span class=identifier>record_year</span>
+<span class=special>{</span>
+ <span class=comment>// result_type typedef required by Key Extractor concept</span>
+ <span class=keyword>typedef</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>gregorian</span><span class=special>::</span><span class=identifier>greg_year</span> <span class=identifier>result_type</span><span class=special>;</span>
+
+ <span class=identifier>result_type</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>const</span> <span class=identifier>record</span><span class=special>&</span> <span class=identifier>r</span><span class=special>)</span><span class=keyword>const</span> <span class=comment>// operator() must be const</span>
+ <span class=special>{</span>
+ <span class=keyword>return</span> <span class=identifier>r</span><span class=special>.</span><span class=identifier>d</span><span class=special>.</span><span class=identifier>year</span><span class=special>();</span>
+ <span class=special>}</span>
+<span class=special>};</span>
+
+<span class=comment>// example of use of the previous key extractor</span>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>record</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>record_year</span><span class=special>></span> <span class=comment>// sorted by record's year</span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>record_log</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+<a href="../examples.html#example6">Example 6</a> in the examples section
+applies some user-defined key extractors in a complex scenario where
+keys are accessed via pointers.
+</p>
+
+<h2><a name="composite_keys">Composite keys</a></h2>
+
+<p>
+In relational databases, composite keys depend on two or more fields of a given table.
+The analogous concept in Boost.MultiIndex is modeled by means of
+<a href="../reference/key_extraction.html#composite_key">
+<code>composite_key</code></a>, as shown in the example:
+</p>
+
+<blockquote><pre>
+<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>
+<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>
+<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>
+<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>composite_key</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span>
+
+<span class=keyword>struct</span> <span class=identifier>phonebook_entry</span>
+<span class=special>{</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>family_name</span><span class=special>;</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>given_name</span><span class=special>;</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>phone_number</span><span class=special>;</span>
+
+ <span class=identifier>phonebook_entry</span><span class=special>(</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>family_name</span><span class=special>,</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>given_name</span><span class=special>,</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>phone_number</span><span class=special>):</span>
+ <span class=identifier>family_name</span><span class=special>(</span><span class=identifier>family_name</span><span class=special>),</span><span class=identifier>given_name</span><span class=special>(</span><span class=identifier>given_name</span><span class=special>),</span><span class=identifier>phone_number</span><span class=special>(</span><span class=identifier>phone_number</span><span class=special>)</span>
+ <span class=special>{}</span>
+<span class=special>};</span>
+
+<span class=comment>// define a multi_index_container with a composite key on
+// (family_name,given_name)</span>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>phonebook_entry</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=comment>//non-unique as some subscribers might have more than one number</span>
+ <span class=identifier>ordered_non_unique</span><span class=special><</span>
+ <span class=identifier>composite_key</span><span class=special><</span>
+ <span class=identifier>phonebook_entry</span><span class=special>,</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>phonebook_entry</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>phonebook_entry</span><span class=special>::</span><span class=identifier>family_name</span><span class=special>>,</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>phonebook_entry</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>phonebook_entry</span><span class=special>::</span><span class=identifier>given_name</span><span class=special>></span>
+ <span class=special>></span>
+ <span class=special>>,</span>
+ <span class=identifier>ordered_unique</span><span class=special><</span> <span class=comment>// unique as numbers belong to only one subscriber</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>phonebook_entry</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>phonebook_entry</span><span class=special>::</span><span class=identifier>phone_number</span><span class=special>></span>
+ <span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>phonebook</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+<code>composite_key</code> accepts two or more key extractors on the same
+value (here, <code>phonebook_entry</code>). Lookup operations on a composite
+key are accomplished by passing tuples with the values searched:
+</p>
+
+<blockquote><pre>
+<span class=identifier>phonebook</span> <span class=identifier>pb</span><span class=special>;</span>
+<span class=special>...</span>
+<span class=comment>// search for Dorothea White's number</span>
+<span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>pb</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=string>"White"</span><span class=special>,</span><span class=string>"Dorothea"</span><span class=special>));</span>
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>number</span><span class=special>=</span><span class=identifier>it</span><span class=special>-></span><span class=identifier>phone_number</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+Composite keys are sorted by lexicographical order, i.e. sorting is performed
+by the first key, then the second key if the first one is equal, etc. This
+order allows for partial searches where only the first keys are specified:
+</p>
+
+<blockquote><pre>
+<span class=identifier>phonebook</span> <span class=identifier>pb</span><span class=special>;</span>
+<span class=special>...</span>
+<span class=comment>// look for all Whites</span>
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special><</span><span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>></span> <span class=identifier>p</span><span class=special>=</span>
+ <span class=identifier>pb</span><span class=special>.</span><span class=identifier>equal_range</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=string>"White"</span><span class=special>));</span>
+</pre></blockquote>
+
+<p>
+As a notational convenience, when only the first key is specified it is possible
+to pass the argument directly without including it into a tuple:
+</p>
+
+<blockquote><pre>
+<span class=identifier>phonebook</span> <span class=identifier>pb</span><span class=special>;</span>
+<span class=special>...</span>
+<span class=comment>// look for all Whites</span>
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special><</span><span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>></span> <span class=identifier>p</span><span class=special>=</span><span class=identifier>pb</span><span class=special>.</span><span class=identifier>equal_range</span><span class=special>(</span><span class=string>"White"</span><span class=special>);</span>
+</pre></blockquote>
+
+<p>
+On the other hand, partial searches without specifying the first keys are not
+allowed.
+</p>
+
+<p>
+By default, the corresponding <code>std::less</code> predicate is used
+for each subkey of a composite key. Alternate comparison predicates can
+be specified with <a href="../reference/key_extraction.html#composite_key_compare">
+<code>composite_key_compare</code></a>:
+</p>
+
+<blockquote><pre>
+<span class=comment>// phonebook with given names in reverse order</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>phonebook_entry</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>ordered_non_unique</span><span class=special><</span>
+ <span class=identifier>composite_key</span><span class=special><</span>
+ <span class=identifier>phonebook_entry</span><span class=special>,</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>phonebook_entry</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>phonebook_entry</span><span class=special>::</span><span class=identifier>family_name</span><span class=special>>,</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>phonebook_entry</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>phonebook_entry</span><span class=special>::</span><span class=identifier>given_name</span><span class=special>></span>
+ <span class=special>>,</span>
+ <span class=identifier>composite_key_compare</span><span class=special><</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>less</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=comment>// family names sorted as by default</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</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=comment>// given names reversed</span>
+ <span class=special>></span>
+ <span class=special>>,</span>
+ <span class=identifier>ordered_unique</span><span class=special><</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>phonebook_entry</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>phonebook_entry</span><span class=special>::</span><span class=identifier>phone_number</span><span class=special>></span>
+ <span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>phonebook</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+See <a href="../examples.html#example7">example 7</a> in the examples section
+for an application of <code>composite_key</code>.
+</p>
+
+<h3><a name="composite_keys_hash">Composite keys and hashed indices</a></h3>
+
+<p>
+Composite keys can also be used with hashed indices in a straightforward manner:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>street_entry</span>
+<span class=special>{</span>
+ <span class=comment>// quadrant coordinates</span>
+ <span class=keyword>int</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=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
+
+ <span class=identifier>street_entry</span><span class=special>(</span><span class=keyword>int</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=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=identifier>x</span><span class=special>(</span><span class=identifier>x</span><span class=special>),</span><span class=identifier>y</span><span class=special>(</span><span class=identifier>y</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=special>};</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>street_entry</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>hashed_non_unique</span><span class=special><</span> <span class=comment>// indexed by quadrant coordinates</span>
+ <span class=identifier>composite_key</span><span class=special><</span>
+ <span class=identifier>street_entry</span><span class=special>,</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>x</span><span class=special>>,</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>y</span><span class=special>></span>
+ <span class=special>></span>
+ <span class=special>>,</span>
+ <span class=identifier>hashed_non_unique</span><span class=special><</span> <span class=comment>// indexed by street name</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</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>street_entry</span><span class=special>::</span><span class=identifier>name</span><span class=special>></span>
+ <span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>street_locator</span><span class=special>;</span>
+
+<span class=identifier>street_locator</span> <span class=identifier>sl</span><span class=special>;</span>
+<span class=special>...</span>
+<span class=keyword>void</span> <span class=identifier>streets_in_quadrant</span><span class=special>(</span><span class=keyword>int</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=special>{</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special><</span><span class=identifier>street_locator</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>street_locator</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>></span> <span class=identifier>p</span><span class=special>=</span>
+ <span class=identifier>sl</span><span class=special>.</span><span class=identifier>equal_range</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=identifier>x</span><span class=special>,</span><span class=identifier>y</span><span class=special>));</span>
+
+ <span class=keyword>while</span><span class=special>(</span><span class=identifier>p</span><span class=special>.</span><span class=identifier>first</span><span class=special>!=</span><span class=identifier>p</span><span class=special>.</span><span class=identifier>second</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=identifier>p</span><span class=special>.</span><span class=identifier>first</span><span class=special>-></span><span class=identifier>name</span><span class=special><<</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>endl</span><span class=special>;</span>
+ <span class=special>++</span><span class=identifier>p</span><span class=special>.</span><span class=identifier>first</span><span class=special>;</span>
+ <span class=special>}</span>
+<span class=special>}</span>
+</pre></blockquote>
+
+<p>
+Note that hashing is automatically taken care of: <code>boost::hash</code> is
+specialized to hash a composite key as a function of the <code>boost::hash</code>
+values of its elements. Should we need to specify different hash functions for the
+elements of a composite key, we can explicitly do so by using the
+<a href="../reference/key_extraction.html#composite_key_hash"><code>composite_key_hash</code></a>
+utility:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>tuned_int_hash</span>
+<span class=special>{</span>
+ <span class=keyword>int</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=comment>// specially tuned hash for this application</span>
+ <span class=special>}</span>
+<span class=special>};</span>
+
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>street_entry</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>hashed_non_unique</span><span class=special><</span> <span class=comment>// indexed by quadrant coordinates</span>
+ <span class=identifier>composite_key</span><span class=special><</span>
+ <span class=identifier>street_entry</span><span class=special>,</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>x</span><span class=special>>,</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>y</span><span class=special>></span>
+ <span class=special>>,</span>
+ <span class=identifier>composite_key_hash</span><span class=special><</span>
+ <span class=identifier>tuned_int_hash</span><span class=special>,</span>
+ <span class=identifier>tuned_int_hash</span>
+ <span class=special>></span>
+ <span class=special>>,</span>
+ <span class=identifier>hashed_non_unique</span><span class=special><</span> <span class=comment>// indexed by street name</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</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>street_entry</span><span class=special>::</span><span class=identifier>name</span><span class=special>></span>
+ <span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>street_locator</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+Also, equality of composite keys can be tuned with
+<a href="../reference/key_extraction.html#composite_key_equal_to"><code>composite_key_equal_to</code></a>,
+though in most cases the default equality predicate (relying on
+the <code>std::equal_to</code> instantiations for the element types)
+will be the right choice.
+</p>
+
+<p>
+Unlike with ordered indices, we cannot perform partial searches specifying
+only the first elements of a composite key:
+</p>
+
+<blockquote><pre>
+<span class=comment>// try to locate streets in quadrants with x==0
+// compile-time error: hashed indices do not allow such operations</span>
+<span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special><</span><span class=identifier>street_locator</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>street_locator</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>></span> <span class=identifier>p</span><span class=special>=</span>
+ <span class=identifier>sl</span><span class=special>.</span><span class=identifier>equal_range</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=number>0</span><span class=special>));</span>
+</pre></blockquote>
+
+<p>
+The reason for this limitation is quite logical: as the hash value of a composite
+key depends on all of its elements, it is impossible to calculate it from
+partial information.
+</p>
+
+<h2><a name="advanced_key_extractors">Advanced features of Boost.MultiIndex key
+extractors</a></h2>
+
+<p>
+The <a href="../reference/key_extraction.html#key_extractors"><code>Key Extractor</code></a>
+concept allows the same object to extract keys from several different types,
+possibly through suitably defined overloads of <code>operator()</code>:
+</p>
+
+<blockquote><pre>
+<span class=comment>// example of a name extractor from employee and employee *</span>
+<span class=keyword>struct</span> <span class=identifier>name_extractor</span>
+<span class=special>{</span>
+ <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>result_type</span><span class=special>;</span>
+
+ <span class=keyword>const</span> <span class=identifier>result_type</span><span class=special>&</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>e</span><span class=special>.</span><span class=identifier>name</span><span class=special>;}</span>
+ <span class=identifier>result_type</span><span class=special>&</span> <span class=keyword>operator</span><span class=special>()(</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>e</span><span class=special>-></span><span class=identifier>name</span><span class=special>;}</span>
+<span class=special>};</span>
+
+<span class=comment>// name_extractor can handle elements of type employee...</span>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>name_extractor</span><span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+
+<span class=comment>// ...as well as elements of type employee *</span>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span><span class=special>*,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>name_extractor</span><span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_ptr_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+This possibility is fully exploited by predefined key extractors provided
+by Boost.MultiIndex, making it simpler to define <code>multi_index_container</code>s
+where elements are pointers or references to the actual objects. The following
+specifies a <code>multi_index_container</code> of pointers to employees sorted by their
+names.
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
+ <span class=identifier>employee</span> <span class=special>*,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <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> <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+Note that this is specified in exactly the same manner as a <code>multi_index_container</code>
+of actual <code>employee</code> objects: <code>member</code> takes care of the
+extra dereferencing needed to gain access to <code>employee::name</code>. A similar
+functionality is provided for interoperability with reference wrappers from
+<a href="../../../../doc/html/ref.html">Boost.Ref</a>:
+</p>
+
+<blockquote><pre>
+<span class=keyword>typedef</span> <span class=identifier>multi_index_container</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=identifier>employee</span><span class=special>>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <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> <span class=special>></span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+In fact, support for pointers is further extended to accept what we call
+<i>chained pointers</i>. Such a chained pointer is defined by induction as a raw or
+smart pointer or iterator to the actual element, to a reference wrapper of the
+element or <i>to another chained pointer</i>; that is, chained pointers are arbitrary
+compositions of pointer-like types ultimately dereferencing
+to the element from where the key is to be extracted. Examples of chained
+pointers to <code>employee</code> are:
+<ul>
+ <li><code>employee *</code>,</li>
+ <li><code>const employee *</code>,</li>
+ <li><code>std::unique_ptr<employee></code>,</li>
+ <li><code>std::list<boost::reference_wrapper<employee> >::iterator</code>,</li>
+ <li><code>employee **</code>,</li>
+ <li><code>boost::shared_ptr<const employee *></code>.</li>
+</ul>
+In general, chained pointers with dereferencing distance greater than 1 are not
+likely to be used in a normal program, but they can arise in frameworks
+which construct "views" as <code>multi_index_container</code>s from preexisting
+<code>multi_index_container</code>s.
+</p>
+
+<p>
+In order to present a short summary of the different usages of Boost.MultiIndex
+key extractors in the presence of reference wrappers and pointers, consider the
+following final type:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>T</span>
+<span class=special>{</span>
+ <span class=keyword>int</span> <span class=identifier>i</span><span class=special>;</span>
+ <span class=keyword>const</span> <span class=keyword>int</span> <span class=identifier>j</span><span class=special>;</span>
+ <span class=keyword>int</span> <span class=identifier>f</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=keyword>int</span> <span class=identifier>g</span><span class=special>();</span>
+ <span class=keyword>static</span> <span class=keyword>int</span> <span class=identifier>gf</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>T</span><span class=special>&);</span>
+ <span class=keyword>static</span> <span class=keyword>int</span> <span class=identifier>gg</span><span class=special>(</span><span class=identifier>T</span><span class=special>&);</span>
+<span class=special>};</span>
+</pre></blockquote>
+
+<p>
+The table below lists the appropriate key extractors to be used for
+different pointer and reference wrapper types based on <code>T</code>, for
+each of its members.
+</p>
+
+<p align="center">
+<table cellspacing="0">
+ <caption><b>Use cases for Boost.MultiIndex key extractors.</b></caption>
+<tr>
+ <th>element type</th>
+ <th> key </th>
+ <th>key extractor</th>
+ <th>applicable to<br><code>const</code> elements?</th>
+ <th>read/write?</th>
+</tr>
+<tr>
+ <td align="center" rowspan="6"><code>T</code></td>
+ <td><code>i</code></td>
+ <td><code>member<T,int,&T::i></code></td>
+ <td align="center">yes</td>
+ <td align="center">yes</td>
+</tr>
+<tr>
+ <td><code>j</code></td>
+ <td><code>member<T,const int,&T::j></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>f()</code></td>
+ <td><code>const_mem_fun<T,int,&T::f></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>g()</code></td>
+ <td><code>mem_fun<T,int,&T::g></code></td>
+ <td align="center">no</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>gf()</code></td>
+ <td><code>global_fun<const T&,int,&T::gf></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>gg()</code></td>
+ <td><code>global_fun<T&,int,&T::gg></code></td>
+ <td align="center">no</td>
+ <td align="center">no</td>
+</tr>
+
+<tr class="odd_tr">
+ <td align="center" rowspan="6"><code>reference_wrapper<T></code></td>
+ <td><code>i</code></td>
+ <td><code>member<T,int,&T::i></code></td>
+ <td align="center">yes</td>
+ <td align="center">yes</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>j</code></td>
+ <td><code>member<T,const int,&T::j></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>f()</code></td>
+ <td><code>const_mem_fun<T,int,&T::f></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>g()</code></td>
+ <td><code>mem_fun<T,int,&T::g></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>gf()</code></td>
+ <td><code>global_fun<const T&,int,&T::gf></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>gg()</code></td>
+ <td><code>global_fun<T&,int,&T::gg></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+
+<tr>
+ <td align="center" rowspan="6"><code>reference_wrapper<const T></code></td>
+ <td><code>i</code></td>
+ <td><code>member<T,const int,&T::i></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>j</code></td>
+ <td><code>member<T,const int,&T::j></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>f()</code></td>
+ <td><code>const_mem_fun<T,int,&T::f></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>g()</code></td>
+ <td colspan="3"> </td>
+</tr>
+<tr>
+ <td><code>gf()</code></td>
+ <td><code>global_fun<const T&,int,&T::gf></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>gg()</code></td>
+ <td colspan="3"> </td>
+</tr>
+
+<tr class="odd_tr">
+ <td align="center" rowspan="6">chained pointer to <code>T</code><br>
+ or to <code>reference_wrapper<T></code></td>
+ <td><code>i</code></td>
+ <td><code>member<T,int,&T::i></code></td>
+ <td align="center">yes</td>
+ <td align="center">yes</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>j</code></td>
+ <td><code>member<T,const int,&T::j></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>f()</code></td>
+ <td><code>const_mem_fun<T,int,&T::f></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>g()</code></td>
+ <td><code>mem_fun<T,int,&T::g></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>gf()</code></td>
+ <td><code>global_fun<const T&,int,&T::gf></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr class="odd_tr">
+ <td><code>gg()</code></td>
+ <td><code>global_fun<T&,int,&T::gg></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+
+<tr>
+ <td align="center" rowspan="6">chained pointer to <code>const T</code><br>
+ or to <code>reference_wrapper<const T></code></td>
+ <td><code>i</code></td>
+ <td><code>member<T,const int,&T::i></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>j</code></td>
+ <td><code>member<T,const int,&T::j></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>f()</code></td>
+ <td><code>const_mem_fun<T,int,&T::f></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>g()</code></td>
+ <td colspan="3"> </td>
+</tr>
+<tr>
+ <td><code>gf()</code></td>
+ <td><code>global_fun<const T&,int,&T::gf></code></td>
+ <td align="center">yes</td>
+ <td align="center">no</td>
+</tr>
+<tr>
+ <td><code>gg()</code></td>
+ <td colspan="3"> </td>
+</tr>
+
+</table>
+</p>
+
+<p>
+The column "applicable to <code>const</code> elements?" states whether the
+corresponding key extractor can be used when passed constant elements (this
+relates to the elements specified in the first column, not the referenced
+<code>T</code> objects). The only negative cases are for <code>T::g</code> and
+<code>T:gg</code> when the elements are raw <code>T</code> objects, which make sense
+as we are dealing with a non-constant member function (<code>T::g</code>)
+and a function taking <code>T</code> by
+non-constant reference: this also implies that <code>multi_index_container</code>s
+of elements of <code>T</code> cannot be sorted by <code>T::g</code> or <code>T::gg</code>, because
+elements contained within a <code>multi_index_container</code> are treated as constant.
+</p>
+
+<p>
+The column "read/write?" shows which combinations yield
+<a href="#read_write_key_extractors">read/write key extractors</a>.
+</p>
+
+<p>
+Some care has to be taken to preserve <code>const</code>-correctness in the
+specification of <code>member</code> key extractors: in some sense, the <code>const</code>
+qualifier is carried along to the member part, even if that particular
+member is not defined as <code>const</code>. For instance, if the elements
+are of type <code>const T *</code>, sorting by <code>T::i</code> is <i>not</i>
+specified as <code>member<const T,int,&T::i></code>, but rather as
+<code>member<T,const int,&T::i></code>.
+</p>
+
+<p>
+For practical demonstrations of use of these key extractors, refer to
+<a href="../examples.html#example2">example 2</a> and
+<a href="../examples.html#example6">example 6</a> in the examples section.
+</p>
+
+<hr>
+
+<div class="prev_link"><a href="indices.html"><img src="../prev.gif" alt="index types" border="0"><br>
+Index types
+</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="creation.html"><img src="../next.gif" alt="container creation" border="0"><br>
+Container creation
+</a></div><br clear="all" style="clear: all;">
+
+<br>
+
+<p>Revised March 25th 2015</p>
+
+<p>© Copyright 2003-2015 Joaquín M López Muñ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>