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/.gitattributes b/.gitattributes
new file mode 100644
index 0000000..3e84d7c
--- /dev/null
+++ b/.gitattributes
@@ -0,0 +1,96 @@
+* text=auto !eol svneol=native#text/plain
+*.gitattributes text svneol=native#text/plain
+
+# Scriptish formats
+*.bat text svneol=native#text/plain
+*.bsh text svneol=native#text/x-beanshell
+*.cgi text svneol=native#text/plain
+*.cmd text svneol=native#text/plain
+*.js text svneol=native#text/javascript
+*.php text svneol=native#text/x-php
+*.pl text svneol=native#text/x-perl
+*.pm text svneol=native#text/x-perl
+*.py text svneol=native#text/x-python
+*.sh eol=lf svneol=LF#text/x-sh
+configure eol=lf svneol=LF#text/x-sh
+
+# Image formats
+*.bmp binary svneol=unset#image/bmp
+*.gif binary svneol=unset#image/gif
+*.ico binary svneol=unset#image/ico
+*.jpeg binary svneol=unset#image/jpeg
+*.jpg binary svneol=unset#image/jpeg
+*.png binary svneol=unset#image/png
+*.tif binary svneol=unset#image/tiff
+*.tiff binary svneol=unset#image/tiff
+*.svg text svneol=native#image/svg%2Bxml
+
+# Data formats
+*.pdf binary svneol=unset#application/pdf
+*.avi binary svneol=unset#video/avi
+*.doc binary svneol=unset#application/msword
+*.dsp text svneol=crlf#text/plain
+*.dsw text svneol=crlf#text/plain
+*.eps binary svneol=unset#application/postscript
+*.gz binary svneol=unset#application/gzip
+*.mov binary svneol=unset#video/quicktime
+*.mp3 binary svneol=unset#audio/mpeg
+*.ppt binary svneol=unset#application/vnd.ms-powerpoint
+*.ps binary svneol=unset#application/postscript
+*.psd binary svneol=unset#application/photoshop
+*.rdf binary svneol=unset#text/rdf
+*.rss text svneol=unset#text/xml
+*.rtf binary svneol=unset#text/rtf
+*.sln text svneol=native#text/plain
+*.swf binary svneol=unset#application/x-shockwave-flash
+*.tgz binary svneol=unset#application/gzip
+*.vcproj text svneol=native#text/xml
+*.vcxproj text svneol=native#text/xml
+*.vsprops text svneol=native#text/xml
+*.wav binary svneol=unset#audio/wav
+*.xls binary svneol=unset#application/vnd.ms-excel
+*.zip binary svneol=unset#application/zip
+
+# Text formats
+.htaccess text svneol=native#text/plain
+*.bbk text svneol=native#text/xml
+*.cmake text svneol=native#text/plain
+*.css text svneol=native#text/css
+*.dtd text svneol=native#text/xml
+*.htm text svneol=native#text/html
+*.html text svneol=native#text/html
+*.ini text svneol=native#text/plain
+*.log text svneol=native#text/plain
+*.mak text svneol=native#text/plain
+*.qbk text svneol=native#text/plain
+*.rst text svneol=native#text/plain
+*.sql text svneol=native#text/x-sql
+*.txt text svneol=native#text/plain
+*.xhtml text svneol=native#text/xhtml%2Bxml
+*.xml text svneol=native#text/xml
+*.xsd text svneol=native#text/xml
+*.xsl text svneol=native#text/xml
+*.xslt text svneol=native#text/xml
+*.xul text svneol=native#text/xul
+*.yml text svneol=native#text/plain
+boost-no-inspect text svneol=native#text/plain
+CHANGES text svneol=native#text/plain
+COPYING text svneol=native#text/plain
+INSTALL text svneol=native#text/plain
+Jamfile text svneol=native#text/plain
+Jamroot text svneol=native#text/plain
+Jamfile.v2 text svneol=native#text/plain
+Jamrules text svneol=native#text/plain
+Makefile* text svneol=native#text/plain
+README text svneol=native#text/plain
+TODO text svneol=native#text/plain
+
+# Code formats
+*.c text svneol=native#text/plain
+*.cpp text svneol=native#text/plain
+*.h text svneol=native#text/plain
+*.hpp text svneol=native#text/plain
+*.ipp text svneol=native#text/plain
+*.tpp text svneol=native#text/plain
+*.jam text svneol=native#text/plain
+*.java text svneol=native#text/plain
diff --git a/doc/acknowledgements.html b/doc/acknowledgements.html
new file mode 100644
index 0000000..74f014a
--- /dev/null
+++ b/doc/acknowledgements.html
@@ -0,0 +1,205 @@
+<!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 - Acknowledgements</title>
+<link rel="stylesheet" href="style.css" type="text/css">
+<link rel="start" href="index.html">
+<link rel="prev" href="release_notes.html">
+<link rel="up" href="index.html">
+</head>
+
+<body>
+<h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align=
+"middle" width="277" height="86">Boost.MultiIndex Acknowledgements</h1>
+
+<div class="prev_link"><a href="release_notes.html"><img src="prev.gif" alt="release notes" border="0"><br>
+Release notes
+</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">
+</div><br clear="all" style="clear: all;">
+
+<hr>
+
+<p>
+Fernando Cacciola, Darren Cook, Beman Dawes, Jeremy Maitin-Shepard and Daryle
+Walker from the Boost mailing list provided useful suggestions for improvement
+on the first alpha releases of the library. Gang Wang discovered several
+bugs in the code. Thomas Wenisch brought out the idea of "sequence sets"
+from which sequenced indices were designed. Giovanni Bajo, Chris Little and
+Maxim Yegorushkin tested the library on several platforms. Daniel Wallin
+contributed fixes for MSVC++ 7.0. Ron Liechty and the support staff at
+Metrowerks provided assistance during the porting of the library to CW 8.3.
+Porting to VisualAge 6.0 counted on Toon Knapen's help. Markus Schöpflin
+aided with Compaq C++ 6.5 and GCC for Tru64 UNIX. Rosa Bernárdez proofread the
+last versions of the tutorial.
+</p>
+
+<p>
+Pavel Voženílek has been immensely helpful in thoroughly reviewing
+every single bit of the library, and he also suggested several extra
+functionalities, most notably range querying, safe mode, polymorphic key
+extractors and MPL support. Thank you!
+</p>
+
+<p>
+The Boost acceptance review took place between March 20th and 30th 2004.
+Pavel Voženílek was the review manager. Thanks to all the people
+who participated and specially to those who submitted reviews:
+Fredrik Blomqvist, Tom Brinkman, Paul A Bristow, Darren Cook, Jeff Garland,
+David B. Held, Brian McNamara, Gary Powell, Rob Stewart, Arkadiy Vertleyb,
+Jörg Walter. Other Boost members also contributed ideas, particularly
+in connection with the library's naming scheme: Pavol Droba,
+Dave Gomboc, Jeremy Maitin-Shepard, Thorsten Ottosen, Matthew Vogt,
+Daryle Walker. My apologies if I inadvertently left somebody out of this
+list.
+</p>
+
+<p>
+Boost.MultiIndex could not have been written without Aleksey Gurtovoy
+et al. superb <a href="../../../libs/mpl/doc/index.html">Boost MPL
+Library</a>. Also, Aleksey's techniques for dealing with ETI-related
+problems in MSVC++ 6.0 helped solve some internal issues of the library.
+</p>
+
+<p>
+The internal implementation of red-black trees is based on that of SGI STL
+<a href="http://www.sgi.com/tech/stl/stl_tree.h">stl_tree.h</a> file:
+</p>
+
+<blockquote>
+Copyright (c) 1996,1997
+Silicon Graphics Computer Systems, Inc.
+<br>
+Permission to use, copy, modify, distribute and sell this software
+and its documentation for any purpose is hereby granted without fee,
+provided that the above copyright notice appear in all copies and
+that both that copyright notice and this permission notice appear
+in supporting documentation. Silicon Graphics makes no
+representations about the suitability of this software for any
+purpose. It is provided "as is" without express or implied warranty.
+<br>
+<br>
+Copyright (c) 1994
+Hewlett-Packard Company
+<br>
+Permission to use, copy, modify, distribute and sell this software
+and its documentation for any purpose is hereby granted without fee,
+provided that the above copyright notice appear in all copies and
+that both that copyright notice and this permission notice appear
+in supporting documentation. Hewlett-Packard Company makes no
+representations about the suitability of this software for any
+purpose. It is provided "as is" without express or implied warranty.
+</blockquote>
+
+<p>
+<span style="float:right;margin-left:10px"><img src="lopez.jpg" width="160" height="120"></span>
+I would like to dedicate this piece of work to Rosa Bernárdez, my very first
+C++ teacher, for her unconditional support in many endeavors of which programming is
+by no means the most important. In memory of my cat López (2001-2003): he
+lived too fast, died too young.
+<br style="clear:all;">
+</p>
+
+<h2><a name="boost_1_33">Boost 1.33 release</a></h2>
+
+<p>
+Many thanks again to Pavel Voženílek, who has carefully reviewed
+the new material and suggested many improvements. The design of hashed indices
+has benefited from discussions with several Boost members, most notably
+Howard Hinnant and Daniel James. Daniel has also contributed
+<a href="../../functional/hash/index.html">Boost.Hash</a>
+to the community: hashed indices depend on this library as
+their default hash function provider. Robert Ramey's
+<a href="../../serialization/index.html">Boost Serialization Library</a>
+provides the very solid framework upon which Boost.MultiIndex serialization
+capabilities are built. Toon Knapen helped adjust the library for VisualAge 6.0.
+Markus Schöpflin provided a Jamfile tweak for GCC under Tru64 UNIX.
+</p>
+
+<h2><a name="boost_1_34">Boost 1.34 release</a></h2>
+
+<p>
+<span style="float:left;margin-right:10px"><img src="hector.jpg" width="150" height="198"></span>
+Thanks go to Pavel Voženílek for his useful comments and suggestions
+during the development of this release, and to Rosa Bernárdez for reviewing
+the new material in the documentation.
+Alo Sarv suggested a notational improvement in the specification of
+partial searches with composite keys.
+Maxim Yegorushkin proposed a valuable
+<a href="tutorial/indices.html#ordered_node_compression">spatial optimization</a>
+for ordered indices and provided figures of its impact on performance
+for containers with large numbers of elements.
+Caleb Epstein performed the tests under MSVC++ 8.0 described in the
+performance section. The following people have reported bugs and problems with
+previous versions and prereleases of the library: Alexei Alexandrov,
+Matías Capeletto, John Eddy, Martin Eigel, Guillaume Lazzara,
+Felipe Magno de Almeida, Julien Pervillé, Hubert Schmid, Toby Smith.
+</p>
+
+<p>
+New member in the family! Thanks to Héctor for his patience during
+long development sessions and his occasional contributions to the source
+codebase.
+<br style="clear:all;">
+</p>
+
+<h2><a name="boost_1_35">Boost 1.35 release</a></h2>
+
+<p>
+<a href="tutorial/key_extraction.html#global_fun"><code>global_fun</code></a>
+was included after a proposal by Markus Werle. Bruno Martínez Aguerre
+suggested the inclusion of
+<a href="tutorial/indices.html#iterator_to"><code>iterator_to</code></a>. The
+rollback versions of <code>modify</code> and <code>modify_key</code> arose
+from discussions with Matías Capeletto. Steven Watanabe spotted an
+include guard bug present from the first release of the library.
+</p>
+
+<h2><a name="boost_1_36">Boost 1.36 release</a></h2>
+
+<p>
+Thanks to Amit Jain for reporting a problem with allocator management.
+Michael Fawcett proposed the addition of an allocator constructor to
+<code>multi_index_container</code>.
+A report from Zachary Zhou has led to
+<a href="release_notes.html#stable_update">enhancing the behavior of
+hashed indices update functions</a> so that they meet some intuitive expectations.
+Grzegorz Jakacki spotted some internal dead code.
+</p>
+
+<h2><a name="boost_1_56">Boost 1.56 release</a></h2>
+
+<p>
+Stephen Kelly has contributed the removal of workaround code for old compilers
+no longer supported.
+</p>
+
+<hr>
+
+<div class="prev_link"><a href="release_notes.html"><img src="prev.gif" alt="release notes" border="0"><br>
+Release notes
+</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">
+</div><br clear="all" style="clear: all;">
+
+<br>
+
+<p>Revised October 9th 2013</p>
+
+<p>© Copyright 2003-2013 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/compiler_specifics.html b/doc/compiler_specifics.html
new file mode 100644
index 0000000..5d531cf
--- /dev/null
+++ b/doc/compiler_specifics.html
@@ -0,0 +1,390 @@
+<!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 - Compiler specifics</title>
+<link rel="stylesheet" href="style.css" type="text/css">
+<link rel="start" href="index.html">
+<link rel="prev" href="reference/key_extraction.html">
+<link rel="up" href="index.html">
+<link rel="next" href="performance.html">
+</head>
+
+<body>
+<h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align=
+"middle" width="277" height="86">Boost.MultiIndex Compiler specifics</h1>
+
+<div class="prev_link"><a href="reference/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="index" border="0"><br>
+Index
+</a></div>
+<div class="next_link"><a href="performance.html"><img src="next.gif" alt="performance" border="0"><br>
+Performance
+</a></div><br clear="all" style="clear: all;">
+
+<hr>
+
+<p>
+Boost.MultiIndex utilizes some C++11 capabilities but is also equipped
+to work reasonably well in decent C++03-compliant environments.
+We list some of the possible limitations along with suitable workarounds when available.
+</p>
+
+<h2>Contents</h2>
+
+<ul>
+ <li><a href="#move">Move semantics</a></li>
+ <li><a href="#emplace">Emplace functions</a></li>
+ <li><a href="#initializer_list">Initializer lists</a></li>
+ <li><a href="#tuple">Tuples</a></li>
+ <li><a href="#symbol_reduction">Reduction of symbol name lengths</a>
+ <ul>
+ <li><a href="#argument_limitation">Limitation of maximum number of arguments</a></li>
+ <li><a href="#type_hiding">Type hiding</a></li>
+ </ul>
+ </li>
+ <li><a href="#legacy">Legacy compilers</a></li>
+</ul>
+
+<h2><a name="move">Move semantics</a></h2>
+
+<p>
+Boost.MultiIndex uses <a href="../../../doc/html/move.html">Boost.Move</a>
+to support compilers without rvalue references. In such scenarios, taking
+advantage of <code>multi_index_container<Value></code> capabilities for
+increased efficiency in insertion and handling of moveable-only elements will
+require that <code>Value</code> be suitably instrumented.
+</p>
+
+<h2><a name="emplace">Emplace functions</a></h2>
+
+<p>
+In compilers without variadic template support, Boost.MultiIndex emplace
+functions emulate this missing functionality by accepting up to
+<code>BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS</code>
+construction arguments that are internally forwarded with
+<a href="../../../doc/html/move.html">Boost.Move</a>:
+only constant lvalue references and rvalues are permitted as construction arguments
+in such case.
+</p>
+
+<p>
+<code>BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS</code>, which by default is 5, can
+be globally defined by the user to a different value.
+</p>
+
+<h2><a name="initializer_list">Initializer lists</a></h2>
+
+<p>
+No transparent emulation of this functionality can be provided in the absence of
+<code>std::initializer_list</code>: consider
+<a href="../../../libs/assign/index.html">Boost.Assign</a> as a
+possible replacement.
+</p>
+
+<h2><a name="tuple">Tuples</a></h2>
+
+<p>
+Everywhere where <code>std::tuple</code>s are used in the library interface,
+<code>boost::tuple</code>s can be resorted to in their place. The converse, however,
+is not true.
+</p>
+
+<h2><a name="symbol_reduction">Reduction of symbol name lengths</a></h2>
+
+<p>
+The types generated on the instantiations of <code>multi_index_container</code>s
+typically produce very long symbol names, sometimes beyond the internal limits
+of some compilers. There are several techniques to shorten generated symbol
+names: these techniques have also the beneficial side effect that resulting error
+messages are more readable.
+</p>
+
+<h3><a name="argument_limitation">Limitation of maximum number of arguments</a></h3>
+
+<p>
+The class templates <a href="reference/indices.html#indexed_by"><code>indexed_by</code></a>,
+<a href="reference/indices.html#tag"><code>tag</code></a> and
+<a href="reference/key_extraction.html#composite_key"><code>composite_key</code></a>
+accept a variable number of arguments whose maximum number is limited by
+internal macros. Even non-used arguments contribute to the final types,
+so manually adjusting the corresponding macros can result in a modest reduction
+of symbol names.
+</p>
+
+<p align="center">
+<table cellspacing="0">
+ <caption><b>Limiting maximum number of arguments of some class templates
+ of Boost.MultiIndex.</b></caption>
+<tr>
+ <th>class template</th>
+ <th>limiting macro</th>
+ <th>default value</th>
+</tr>
+<tr>
+ <td align="center"> <code>indexed_by</code> </td>
+ <td align="center"> <code>BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE</code> </td>
+ <td align="center">20</td>
+</tr>
+<tr class="odd_tr">
+ <td align="center"> <code>tag</code> </td>
+ <td align="center"> <code>BOOST_MULTI_INDEX_LIMIT_TAG_SIZE</code> </td>
+ <td align="center">20</td>
+</tr>
+<tr>
+ <td align="center"> <code>composite_key</code> </td>
+ <td align="center"> <code>BOOST_MULTI_INDEX_LIMIT_COMPOSITE_KEY_SIZE</code> </td>
+ <td align="center">10</td>
+</tr>
+</table>
+</p>
+
+<h3><a name="type_hiding">Type hiding</a></h3>
+
+<p>
+Consider a typical instantiation of <code>multi_index_container</code>:
+</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=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>
+Then, for instance, the type <code>employee_set::nth_index<0>::type</code>
+resolves to the following in GCC:
+</p>
+
+<blockquote><pre>
+<span class=identifier>boost</span><span class=special>::</span><span class=identifier>multi_index</span><span class=special>::</span><span class=identifier>detail</span><span class=special>::</span><span class=identifier>ordered_index</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>employee</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>employee</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>detail</span><span class=special>::</span><span class=identifier>nth_layer</span><span class=special><</span>
+ <span class=number>1</span><span class=special>,</span> <span class=identifier>employee</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>indexed_by</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_unique</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>employee</span><span class=special>>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</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_non_unique</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>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=special>&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>>,</span>
+ <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</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_unique</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>employee</span><span class=special>,</span> <span class=keyword>int</span><span class=special>,</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=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span>
+ <span class=special>>,</span>
+ <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span>
+ <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span>
+ <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span><span class=special>,</span> <span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</span>
+ <span class=special>>,</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>allocator</span><span class=special><</span><span class=identifier>employee</span><span class=special>></span>
+ <span class=special>>,</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>mpl</span><span class=special>::</span><span class=identifier>vector0</span><span class=special><</span><span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</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>detail</span><span class=special>::</span><span class=identifier>ordered_unique_tag</span>
+<span class=special>></span>
+</pre></blockquote>
+
+<p>
+It can be seen that a significant portion of the type name is contributed by
+the <code>indexed_by<...></code> part, which is nothing but an expanded
+version of the index specifier list provided in the definition of
+<code>employee_set</code>. We can prevent this very long name from appearing
+in the final type by encapsulating it into another, shorter-named construct:
+</p>
+
+<blockquote><pre>
+<span class=comment>// reducing symbol names through type hiding
+// type hide the index specifier list within employee_set_indices</span>
+
+<span class=keyword>struct</span> <span class=identifier>employee_set_indices</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=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>employee_set_indices</span>
+<span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
+</pre></blockquote>
+
+<p>
+<code>employee_set_indices</code> works as a conventional <code>typedef</code>
+in all respects, save for a detail: its name does not explicitly
+include the information contained in the <code>indexed_by</code> instantiation.
+Applying this technique, <code>employee_set::nth_index<0>::type</code>
+now becomes:
+</p>
+
+<blockquote><pre>
+<span class=identifier>boost</span><span class=special>::</span><span class=identifier>multi_index</span><span class=special>::</span><span class=identifier>detail</span><span class=special>::</span><span class=identifier>ordered_index</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>employee</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>employee</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>detail</span><span class=special>::</span><span class=identifier>nth_layer</span><span class=special><</span>
+ <span class=number>1</span><span class=special>,</span> <span class=identifier>employee</span><span class=special>,</span>
+ <span class=identifier>employee_set_indices</span><span class=special>,</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>allocator</span><span class=special><</span><span class=identifier>employee</span><span class=special>></span>
+ <span class=special>>,</span>
+ <span class=identifier>boost</span><span class=special>::</span><span class=identifier>mpl</span><span class=special>::</span><span class=identifier>vector0</span><span class=special><</span><span class=identifier>mpl_</span><span class=special>::</span><span class=identifier>na</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>detail</span><span class=special>::</span><span class=identifier>ordered_unique_tag</span>
+<span class=special>></span>
+</pre></blockquote>
+
+<p>
+which is considerably shorter than the original, and also more
+easily parsed by a human reader. Type hiding would not work if, instead of
+making <code>employee_set_indices</code> a derived <code>struct</code> of
+<code>indexed_by<...></code>, we had defined it as a <code>typedef</code>:
+<code>typedef</code>s are syntactic aliases and usually get expanded
+by the compiler before doing any further type handling.
+</p>
+
+<p>
+Type hiding techniques can also be applied to <code>composite_key</code> intantiations,
+which often contribute a great deal to symbol name lengths.
+</p>
+
+<h2><a name="legacy">Legacy compilers</a></h2>
+
+<p>
+Boost.MultiIndex support for legacy compilers is not actively kept, so if you happen
+to work with an old environment you might need to use a former version of the library.
+A table is provided of some legacy compilers along with the latest version of
+Boost.MultiIndex known to work for them (frequently with limitations as explained
+in the corresponding compiler specifics section.) If you successfully try one of those
+with newer versions of Boost.MultiIndex than stated here, please report back so that
+the information can be updated.
+</p>
+
+<p align="center">
+<table cellspacing="0" cellpadding="5">
+ <caption><b>Support for legacy compilers.</b></caption>
+<tr>
+ <th>Compiler</th>
+ <th>Latest known<br>compatible version</th>
+ <th>Date</th>
+</tr>
+<tr>
+ <td>Borland C++ Builder 6.4 through 2006, CodeGear C++Builder 2010</td>
+ <td>Never worked with Boost.MultiIndex</td>
+ <td></td>
+</tr>
+<tr class="odd_tr">
+ <td>Comeau C/C++ 4.3.10.1 for Windows (VC++ 9.0 backend)</td>
+ <td><a href="http://www.boost.org/doc/libs/1_38_0/libs/multi_index/doc/compiler_specifics.html#comeau_43101_win_vc7_71">Boost 1.38</a></td>
+ <td>February 2009</td>
+</tr>
+<tr>
+ <td>Compaq C++ 6.5-042 through 7.1-006 for Tru64 UNIX</td>
+ <td><a href="http://www.boost.org/doc/libs/1_38_0/libs/multi_index/doc/compiler_specifics.html#compaq_65">Boost 1.38</a></td>
+ <td>February 2009</td>
+</tr>
+<tr class="odd_tr">
+ <td>GCC 3.2 through 3.4</td>
+ <td><a href="http://www.boost.org/doc/libs/1_41_0/libs/multi_index/doc/compiler_specifics.html#gcc_32">Boost 1.41</a></td>
+ <td>November 2009</td>
+</tr>
+<tr>
+ <td>HP aC++ A.06.12 through A.06.17 for HP-UX IA64</td>
+ <td><a href="http://www.boost.org/doc/libs/1_38_0/libs/multi_index/doc/compiler_specifics.html#acc_612_ia64">Boost 1.38</a></td>
+ <td>February 2009</td>
+</tr>
+<tr class="odd_tr">
+ <td>HP aC++ A.03.80 through A.03.85 for HP-UX PA-RISC</td>
+ <td><a href="http://www.boost.org/doc/libs/1_38_0/libs/multi_index/doc/compiler_specifics.html#acc_380_pa_risc">Boost 1.38</a></td>
+ <td>February 2009</td>
+</tr>
+<tr>
+ <td>IBM VisualAge C++ V6.0 for AIX</td>
+ <td><a href="http://www.boost.org/doc/libs/1_33_1/libs/multi_index/doc/compiler_specifics.html#va_60">Boost 1.33.1</a></td>
+ <td>December 2006</td>
+</tr>
+<tr class="odd_tr">
+ <td>IBM XL C/C++ V9.0 through V10.1 for AIX</td>
+ <td><a href="http://www.boost.org/doc/libs/1_41_0/libs/multi_index/doc/compiler_specifics.html#xl_90">Boost 1.41</a></td>
+ <td>November 2009</td>
+</tr>
+<tr>
+ <td>Intel C++ Compiler for Linux 8.1 through 11.1</td>
+ <td><a href="http://www.boost.org/doc/libs/1_41_0/libs/multi_index/doc/compiler_specifics.html#intel_81_lin">Boost 1.41</a></td>
+ <td>November 2009</td>
+</tr>
+<tr class="odd_tr">
+ <td>Intel C++ Compiler for Mac OS 9.1 through 11.0</td>
+ <td><a href="http://www.boost.org/doc/libs/1_41_0/libs/multi_index/doc/compiler_specifics.html#intel_91_mac">Boost 1.41</a></td>
+ <td>November 2009</td>
+</tr>
+<tr>
+ <td>Intel C++ Compiler for Windows 32-bit 8.0 through 11.1</td>
+ <td><a href="http://www.boost.org/doc/libs/1_41_0/libs/multi_index/doc/compiler_specifics.html#intel_80_win">Boost 1.41</a></td>
+ <td>November 2009</td>
+</tr>
+<tr class="odd_tr">
+ <td>Intel C++ Compiler for Windows 64-bit 10.0 through 11.11</td>
+ <td><a href="http://www.boost.org/doc/libs/1_41_0/libs/multi_index/doc/compiler_specifics.html#intel_100_win64">Boost 1.41</a></td>
+ <td>November 2009</td>
+</tr>
+<tr>
+ <td>Metrowerks CodeWarrior 8.3</td>
+ <td><a href="http://www.boost.org/doc/libs/1_36_0/libs/multi_index/doc/compiler_specifics.html#cw_83">Boost 1.36</a></td>
+ <td>August 2008</td>
+</tr>
+<tr class="odd_tr">
+ <td>Metrowerks CodeWarrior 9 through 9.5</td>
+ <td><a href="http://www.boost.org/doc/libs/1_34_1/libs/multi_index/doc/compiler_specifics.html#cw_9x">Boost 1.34.1</a></td>
+ <td>July 2007</td>
+</tr>
+<tr>
+ <td>Microsoft Visual C++ 6.0 Service Pack 5</td>
+ <td><a href="http://www.boost.org/doc/libs/1_36_0/libs/multi_index/doc/compiler_specifics.html#msvc_60">Boost 1.36</a></td>
+ <td>August 2008</td>
+</tr>
+<tr class="odd_tr">
+ <td>Microsoft Visual C++ 7.0</td>
+ <td><a href="http://www.boost.org/doc/libs/1_35_0/libs/multi_index/doc/compiler_specifics.html#msvc_70">Boost 1.35</a></td>
+ <td>March 2008</td>
+</tr>
+<tr>
+ <td>Sun Studio 10 through 12 Update 1 for Solaris</td>
+ <td><a href="http://www.boost.org/doc/libs/1_41_0/libs/multi_index/doc/compiler_specifics.html#sun_10">Boost 1.41</a></td>
+ <td>November 2009</td>
+</tr>
+</table>
+</p>
+
+<hr>
+
+<div class="prev_link"><a href="reference/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="index" border="0"><br>
+Index
+</a></div>
+<div class="next_link"><a href="performance.html"><img src="next.gif" alt="performance" border="0"><br>
+Performance
+</a></div><br clear="all" style="clear: all;">
+
+<br>
+
+<p>Revised August 20th 2014</p>
+
+<p>© Copyright 2003-2014 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/examples.html b/doc/examples.html
new file mode 100644
index 0000000..39d58f6
--- /dev/null
+++ b/doc/examples.html
@@ -0,0 +1,463 @@
+<!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 - Examples</title>
+<link rel="stylesheet" href="style.css" type="text/css">
+<link rel="start" href="index.html">
+<link rel="prev" href="performance.html">
+<link rel="up" href="index.html">
+<link rel="next" href="tests.html">
+</head>
+
+<body>
+<h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align=
+"middle" width="277" height="86">Boost.MultiIndex Examples</h1>
+
+<div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
+Performance
+</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="tests.html"><img src="next.gif" alt="tests" border="0"><br>
+Tests
+</a></div><br clear="all" style="clear: all;">
+
+<hr>
+
+<h2>Contents</h2>
+
+<ul>
+ <li><a href="#example1">Example 1: basic usage</a></li>
+ <li><a href="#example2">Example 2: using functions as keys</a></li>
+ <li><a href="#example3">Example 3: constructing <code>multi_index_container</code>s
+ with <code>ctor_args_list</code></a></li>
+ <li><a href="#example4">Example 4: bidirectional map</a></li>
+ <li><a href="#example5">Example 5: sequenced indices</a></li>
+ <li><a href="#example6">Example 6: complex searches and foreign keys</a></li>
+ <li><a href="#example7">Example 7: composite keys</a></li>
+ <li><a href="#example8">Example 8: hashed indices</a></li>
+ <li><a href="#example9">Example 9: serialization and MRU lists</a></li>
+ <li><a href="#example10">Example 10: random access indices</a></li>
+ <li><a href="#example11">Example 11: index rearrangement</a></li>
+ <li><a href="#example12">Example 12: using Boost.Interprocess allocators</a></li>
+</ul>
+
+<h2><a name="example1">Example 1: basic usage</a></h2>
+
+<p>
+See <a href="../example/basic.cpp">source code</a>.
+</p>
+
+<p>
+Basic program showing the multi-indexing capabilities of Boost.MultiIndex
+with an admittedly boring set of <code>employee</code> records.
+</p>
+
+<h2><a name="example2">Example 2: using functions as keys</a></h2>
+
+<p>
+See <a href="../example/fun_key.cpp">source code</a>.
+</p>
+
+<p>
+Usually keys assigned to an index are based on a member variable of the
+element, but key extractors can be defined which take their value from
+a member function or a global function. This has some similarity with the concept of
+<i>calculated keys</i> supported by some relational database engines.
+The example shows how to use the predefined <code>const_mem_fun</code>
+and <code>global_fun</code> key extractors to deal with this situation.
+</p>
+
+<p>
+Keys based on functions usually will not be actual references,
+but rather the temporary values resulting from the invocation of the
+member function used. This implies that <code>modify_key</code> cannot be
+applied to this type of extractors, which is a perfectly logical
+constraint anyway.
+</p>
+
+<h2><a name="example3">Example 3: constructing <code>multi_index_container</code>s
+with <code>ctor_args_list</code></a></h2>
+
+<p>
+See <a href="../example/non_default_ctor.cpp">source code</a>.
+</p>
+
+<p>
+We show a practical example of usage of <code>multi_index_container::ctor_arg_list</code>,
+whose definition and purpose are explained in the
+<a href="tutorial/creation.html#ctor_args_list">tutorial</a>. The
+program groups a sorted collection of numbers based on identification through
+modulo arithmetics, by which <code>x</code> and <code>y</code> are equivalent
+if <code>(x%n)==(y%n)</code>, for some fixed <code>n</code>.
+</p>
+
+<h2><a name="example4">Example 4: bidirectional map</a></h2>
+
+<p>
+See <a href="../example/bimap.cpp">source code</a>.
+</p>
+
+<p>
+This example shows how to construct a bidirectional map with
+<code>multi_index_container</code>. By a <i>bidirectional map</i> we mean
+a container of <code>(const FromType,const ToType)</code> pairs
+such that no two elements exists with the same first
+<i>or</i> second component (<code>std::map</code> only
+guarantees uniqueness of the first component). Fast lookup is provided
+for both keys. The program features a tiny Spanish-English
+dictionary with online query of words in both languages.
+</p>
+
+<p>
+This bidirectional map can be considered as a primitive precursor
+to the full-fledged container provided by
+<a href="../../bimap/index.html">Boost.Bimap</a>.
+</p>
+
+<h2><a name="example5">Example 5: sequenced indices</a></h2>
+
+<p>
+See <a href="../example/sequenced.cpp">source code</a>.
+</p>
+
+<p>
+The combination of a sequenced index with an index of type <code>ordered_non_unique</code>
+yields a <code>list</code>-like structure with fast lookup capabilities. The
+example performs some operations on a given text, like word counting and
+selective deletion of some words.
+</p>
+
+<h2><a name="example6">Example 6: complex searches and foreign keys</a></h2>
+
+<p>
+See <a href="../example/complex_structs.cpp">source code</a>.
+</p>
+
+<p>
+This program illustrates some advanced techniques that can be applied
+for complex data structures using <code>multi_index_container</code>.
+Consider a <code>car_model</code> class for storing information
+about automobiles. On a first approach, <code>car_model</code> can
+be defined as:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>car_model</span>
+<span class=special>{</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>model</span><span class=special>;</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>manufacturer</span><span class=special>;</span>
+ <span class=keyword>int</span> <span class=identifier>price</span><span class=special>;</span>
+<span class=special>};</span>
+</pre></blockquote>
+
+<p>
+This definition has a design flaw that any reader acquainted with
+relational databases can easily spot: The <code>manufacturer</code>
+member is duplicated among all cars having the same manufacturer.
+This is a waste of space and poses difficulties when, for instance,
+the name of a manufacturer has to be changed. Following the usual
+principles in relational database design, the appropriate design
+involves having the manufactures stored in a separate
+<code>multi_index_container</code> and store pointers to these in
+<code>car_model</code>:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>car_manufacturer</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=special>};</span>
+
+<span class=keyword>struct</span> <span class=identifier>car_model</span>
+<span class=special>{</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>model</span><span class=special>;</span>
+ <span class=identifier>car_manufacturer</span><span class=special>*</span> <span class=identifier>manufacturer</span><span class=special>;</span>
+ <span class=keyword>int</span> <span class=identifier>price</span><span class=special>;</span>
+<span class=special>};</span>
+</pre></blockquote>
+
+<p>
+Although predefined Boost.MultiIndex key extractors can handle many
+situations involving pointers (see
+<a href="tutorial/key_extraction.html#advanced_key_extractors">advanced features
+of Boost.MultiIndex key extractors</a> in the tutorial), this case
+is complex enough that a suitable key extractor has to be defined. The following
+utility cascades two key extractors:
+</p>
+
+<blockquote><pre>
+<span class=keyword>template</span><span class=special><</span><span class=keyword>class</span> <span class=identifier>KeyExtractor1</span><span class=special>,</span><span class=keyword>class</span> <span class=identifier>KeyExtractor2</span><span class=special>></span>
+<span class=keyword>struct</span> <span class=identifier>key_from_key</span>
+<span class=special>{</span>
+<span class=keyword>public</span><span class=special>:</span>
+ <span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>KeyExtractor1</span><span class=special>::</span><span class=identifier>result_type</span> <span class=identifier>result_type</span><span class=special>;</span>
+
+ <span class=identifier>key_from_key</span><span class=special>(</span>
+ <span class=keyword>const</span> <span class=identifier>KeyExtractor1</span><span class=special>&</span> <span class=identifier>key1_</span><span class=special>=</span><span class=identifier>KeyExtractor1</span><span class=special>(),</span>
+ <span class=keyword>const</span> <span class=identifier>KeyExtractor2</span><span class=special>&</span> <span class=identifier>key2_</span><span class=special>=</span><span class=identifier>KeyExtractor2</span><span class=special>()):</span>
+ <span class=identifier>key1</span><span class=special>(</span><span class=identifier>key1_</span><span class=special>),</span><span class=identifier>key2</span><span class=special>(</span><span class=identifier>key2_</span><span class=special>)</span>
+ <span class=special>{}</span>
+
+ <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Arg</span><span class=special>></span>
+ <span class=identifier>result_type</span> <span class=keyword>operator</span><span class=special>()(</span><span class=identifier>Arg</span><span class=special>&</span> <span class=identifier>arg</span><span class=special>)</span><span class=keyword>const</span>
+ <span class=special>{</span>
+ <span class=keyword>return</span> <span class=identifier>key1</span><span class=special>(</span><span class=identifier>key2</span><span class=special>(</span><span class=identifier>arg</span><span class=special>));</span>
+ <span class=special>}</span>
+
+<span class=keyword>private</span><span class=special>:</span>
+ <span class=identifier>KeyExtractor1</span> <span class=identifier>key1</span><span class=special>;</span>
+ <span class=identifier>KeyExtractor2</span> <span class=identifier>key2</span><span class=special>;</span>
+<span class=special>};</span>
+</pre></blockquote>
+
+<p>
+so that access from a <code>car_model</code> to the <code>name</code> field
+of its associated <code>car_manufacturer</code> can be accomplished with
+</p>
+
+<blockquote><pre>
+<span class=identifier>key_from_key</span><span class=special><</span>
+ <span class=identifier>member</span><span class=special><</span><span class=identifier>car_manufacturer</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>car_manufacturer</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>car_model</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>car_manufacturer</span> <span class=special>*,</span><span class=identifier>car_model</span><span class=special>::</span><span class=identifier>manufacturer</span><span class=special>></span>
+<span class=special>></span>
+</pre></blockquote>
+
+<p>
+The program asks the user for a car manufacturer and a range of prices
+and returns the car models satisfying these requirements. This is a complex
+search that cannot be performed on a single operation. Broadly sketched,
+one procedure for executing the selection is:
+<ol>
+ <li>Select the elements with the given manufacturer by means
+ of <code>equal_range</code>,
+ <li>feed these elements into a <code>multi_index_container</code> sorted
+ by price,
+ <li>select by price using <code>lower_bound</code> and
+ <code>upper_bound</code>;
+</ol>
+or alternatively:
+<ol>
+ <li>Select the elements within the price range with
+ <code>lower_bound</code> and <code>upper_bound</code>,
+ <li>feed these elements into a <code>multi_index_container</code> sorted
+ by manufacturer,
+ <li>locate the elements with given manufacturer using
+ <code>equal_range</code>.
+</ol>
+An interesting technique developed in the example lies in
+the construction of the intermediate <code>multi_index_container</code>.
+In order to avoid object copying, appropriate <i>view</i> types
+are defined with <code>multi_index_container</code>s having as elements
+pointers to <code>car_model</code>s instead of actual objects.
+These views have to be supplemented with appropriate
+dereferencing key extractors.
+</p>
+
+<h2><a name="example7">Example 7: composite keys</a></h2>
+
+<p>
+See <a href="../example/composite_keys.cpp">source code</a>.
+</p>
+
+<p>
+Boost.MultiIndex <a href="tutorial/key_extraction.html#composite_keys">
+<code>composite_key</code></a> construct provides a flexible tool for
+creating indices with non-trivial sorting criteria.
+The program features a rudimentary simulation of a file system
+along with an interactive Unix-like shell. A file entry is represented by
+the following structure:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>file_entry</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>unsigned</span> <span class=identifier>size</span><span class=special>;</span>
+ <span class=keyword>bool</span> <span class=identifier>is_dir</span><span class=special>;</span> <span class=comment>// true if the entry is a directory</span>
+ <span class=keyword>const</span> <span class=identifier>file_entry</span><span class=special>*</span> <span class=identifier>dir</span><span class=special>;</span> <span class=comment>// directory this entry belongs in</span>
+<span class=special>};</span>
+</pre></blockquote>
+
+<p>
+Entries are kept in a <code>multi_index_container</code> maintaining two indices
+with composite keys:
+<ul>
+ <li>A primary index ordered by directory and name,</li>
+ <li>a secondary index ordered by directory and size.</li>
+</ul>
+The reason that the order is made firstly by the directory in which
+the files are located obeys to the local nature of the shell commands,
+like for instance <code>ls</code>. The shell simulation only has three
+commands:
+<ul>
+ <li><code>cd [.|..|<i><directory></i>]</code></li>
+ <li><code>ls [-s]</code> (<code>-s</code> orders the output by size)</li>
+ <li><code>mkdir <i><directory></i></code></li>
+</ul>
+The program exits when the user presses the Enter key at the command prompt.
+</p>
+
+<p>
+The reader is challenged to add more functionality to the program; for
+instance:
+<ul>
+ <li>Implement additional commands, like <code>cp</code>.</li>
+ <li>Add handling of absolute paths.</li>
+ <li>Use <a href="tutorial/creation.html#serialization">serialization</a>
+ to store and retrieve the filesystem state between program runs.</li>
+</ul>
+</p>
+
+<h2><a name="example8">Example 8: hashed indices</a></h2>
+
+<p>
+See <a href="../example/hashed.cpp">source code</a>.
+</p>
+
+<p>
+Hashed indices can be used as an alternative to ordered indices when
+fast lookup is needed and sorting information is of no interest. The
+example features a word counter where duplicate entries are checked
+by means of a hashed index. Confront the word counting algorithm with
+that of <a href="#example5">example 5</a>.
+</p>
+
+<h2><a name="example9">Example 9: serialization and MRU lists</a></h2>
+
+<p>
+See <a href="../example/serialization.cpp">source code</a>.
+</p>
+
+<p>
+A typical application of serialization capabilities allows a program to
+restore the user context between executions. The example program asks
+the user for words and keeps a record of the ten most recently entered
+ones, in the current or in previous sessions. The serialized data structure,
+sometimes called an <i>MRU (most recently used) list</i>, has some interest
+on its own: an MRU list behaves as a regular FIFO queue, with the exception
+that, when inserting a preexistent entry, this does not appear twice, but
+instead the entry is moved to the front of the list. You can observe this
+behavior in many programs featuring a "Recent files" menu command. This
+data structure is implemented with <code>multi_index_container</code> by
+combining a sequenced index and an index of type <code>hashed_unique</code>.
+</p>
+
+<h2><a name="example10">Example 10: random access indices</a></h2>
+
+<p>
+See <a href="../example/random_access.cpp">source code</a>.
+</p>
+
+<p>
+The example resumes the text container introduced in
+<a href="#example5">example 5</a> and shows how substituting a random
+access index for a sequenced index allows for extra capabilities like
+efficient access by position and calculation of the offset of a given
+element into the container.
+</p>
+
+<h2><a name="example11">Example 11: index rearrangement</a></h2>
+
+<p>
+See <a href="../example/rearrange.cpp">source code</a>.
+</p>
+
+<p>
+There is a relatively common piece of urban lore claiming that
+a deck of cards must be shuffled seven times in a row to be perfectly
+mixed. The statement derives from the works of mathematician Persi
+Diaconis on <i>riffle shuffling</i>: this shuffling
+technique involves splitting the deck in two packets roughly the same
+size and then dropping the cards from both packets so that they become
+interleaved. It has been shown that when repeating this procedure
+seven times the statistical distribution of cards is reasonably
+close to that associated with a truly random permutation. A measure
+of "randomness" can be estimated by counting <i>rising sequences</i>:
+consider a permutation of the sequence 1,2, ... , <i>n</i>, a rising sequence
+is a maximal chain of consecutive elements <i>m</i>, <i>m+1</i>, ... , <i>m+r</i>
+such that they are arranged in ascending order. For instance, the permutation
+125364789 is composed of the two rising sequences 1234 and 56789,
+as becomes obvious by displaying the sequence like this,
+<span style="vertical-align:sub">1</span><span style="vertical-align:sub">2</span><span style="vertical-align:super">5</span><span style="vertical-align:sub">3</span><span style="vertical-align:super">6</span><span style="vertical-align:sub">4</span><span style="vertical-align:super">7</span><span style="vertical-align:super">8</span><span style="vertical-align:super">9</span>.
+The average number of rising sequences in a random permutation of
+<i>n</i> elements is (<i>n</i>+1)/2: by contrast, after a single riffle
+shuffle of an initially sorted deck of cards, there cannot be more than
+two rising sequences. The average number of rising sequences approximates
+to (<i>n</i>+1)/2 as the number of consecutive riffle shuffles increases,
+with seven shuffles yielding a close result for a 52-card poker deck.
+Brad Mann's paper
+<a href="http://www.dartmouth.edu/~chance/teaching_aids/books_articles/Mann.pdf">"How
+many times should you shuffle a deck of cards?"</a> provides a
+rigorous yet very accessible treatment of this subject.
+
+</p>
+
+<p>
+The example program estimates the average number of rising sequences
+in a 52-card deck after repeated riffle shuffling as well as applying
+a completely random permutation. The deck is modeled by the following
+container:
+<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>random_access</span><span class=special><>,</span>
+ <span class=identifier>random_access</span><span class=special><></span>
+ <span class=special>></span>
+<span class=special>></span>
+</pre></blockquote>
+where the first index stores the current arrangement of the deck, while
+the second index is used to remember the start position. This representation
+allows for an efficient implementation of a rising sequences counting
+algorithm in linear time.
+<a href="reference/rnd_indices.html#rearrange"><code>rearrange</code></a>
+is used to apply to the deck a shuffle performed externally on an
+auxiliary data structure.
+</p>
+
+<h2><a name="example12">Example 12: using Boost.Interprocess allocators</a></h2>
+
+<p>
+See <a href="../example/ip_allocator.cpp">source code</a>.
+</p>
+
+<p>
+Boost.MultiIndex supports special allocators such as those provided by
+<a href="../../interprocess/index.html">Boost.Interprocess</a>,
+which allows for <code>multi_index_container</code>s to be placed in shared
+memory. The example features a front-end to a small book database
+implemented by means of a <code>multi_index_container</code> stored
+in a Boost.Interprocess memory mapped file. The reader can verify that several
+instances of the program correctly work simultaneously and immediately see
+the changes to the database performed by any other instance.
+</p>
+
+<hr>
+
+<div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
+Performance
+</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="tests.html"><img src="next.gif" alt="tests" border="0"><br>
+Tests
+</a></div><br clear="all" style="clear: all;">
+
+<br>
+
+<p>Revised May 26th 2009</p>
+
+<p>© Copyright 2003-2009 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/future_work.html b/doc/future_work.html
new file mode 100644
index 0000000..b38e1d3
--- /dev/null
+++ b/doc/future_work.html
@@ -0,0 +1,199 @@
+<!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 - Future work</title>
+<link rel="stylesheet" href="style.css" type="text/css">
+<link rel="start" href="index.html">
+<link rel="prev" href="tests.html">
+<link rel="up" href="index.html">
+<link rel="next" href="release_notes.html">
+</head>
+
+<body>
+<h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align=
+"middle" width="277" height="86">Boost.MultiIndex Future work</h1>
+
+<div class="prev_link"><a href="tests.html"><img src="prev.gif" alt="tests" border="0"><br>
+Tests
+</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="release_notes.html"><img src="next.gif" alt="release notes" border="0"><br>
+Release notes
+</a></div><br clear="all" style="clear: all;">
+
+<hr>
+
+<p>
+A number of new functionalities are considered for inclusion into
+future releases of Boost.MultiIndex. Some of them depend on the
+potential for extensibility of the library, which has been a guiding
+principle driving the current internal design of <code>multi_index_container</code>.
+</p>
+
+<h2>Contents</h2>
+
+<ul>
+ <li><a href="#notifying">Notifying indices</a></li>
+ <li><a href="#constraints">Constraints</a></li>
+ <li><a href="#user_defined_indices">User-defined indices</a></li>
+ <li><a href="#indexed_maps">Indexed maps</a></li>
+</ul>
+
+<h2><a name="notifying">Notifying indices</a></h2>
+
+<p>
+<i>Notifying indices</i> can be implemented as decorators over
+preexistent index types, with the added functionality that internal
+events of the index (insertion, erasing, modifying of elements) are
+signalled to an external entity --for instance, by means of the
+<a href="../../../doc/html/signals.html">Boost.Signals</a>
+library. This functionality can have applications for:
+<ol>
+ <li>Logging,</li>
+ <li>interfacing to GUI-based applications,</li>
+ <li>synchronization between separate data structures.</li>
+</ol>
+</p>
+
+<p>
+The following is a sketch of a possible realization of notifying
+indices:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>insert_log</span>
+<span class=special>{</span>
+ <span class=keyword>void</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=special>{</span>
+ <span class=identifier>std</span><span class=special>::</span><span class=identifier>clog</span><span class=special><<</span><span class=string>"insert: "</span><span class=special><<</span><span class=identifier>x</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=special>};</span>
+
+<span class=keyword>int</span> <span class=identifier>main</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=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>notifying</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=comment>// notifying index</span>
+ <span class=identifier>ordered_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>indexed_t</span><span class=special>;</span>
+
+ <span class=identifier>indexed_t</span> <span class=identifier>t</span><span class=special>;</span>
+
+ <span class=comment>// on_insert is the signal associated to insertions</span>
+ <span class=identifier>t</span><span class=special>.</span><span class=identifier>on_insert</span><span class=special>.</span><span class=identifier>connect</span><span class=special>(</span><span class=identifier>insert_log</span><span class=special>());</span>
+
+ <span class=identifier>t</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=identifier>t</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=keyword>return</span> <span class=number>0</span><span class=special>;</span>
+<span class=special>}</span>
+
+<span class=comment>// output:
+// insert: 0
+// insert: 1</span>
+</pre></blockquote>
+
+<h2><a name="constraints">Constraints</a></h2>
+
+<p>
+The notifying indices functionality described above exploits a powerful
+design pattern based on <i>index adaptors</i>, decorators over preexistent
+indices which add some functionality or somehow change the semantics of
+the underlying index. This pattern can be used for the implementation
+of <i>constraints</i>, adaptors that restrict the elements accepted by an
+index according to some validation predicate. The following is a possible
+realization of how constraints syntax may look like:
+</p>
+
+<blockquote><pre>
+<span class=keyword>struct</span> <span class=identifier>is_even</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=special>{</span><span class=keyword>return</span> <span class=identifier>x</span><span class=special>%</span><span class=number>2</span><span class=special>==</span><span class=number>0</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=keyword>int</span><span class=special>,</span>
+ <span class=identifier>indexed_by</span><span class=special><</span>
+ <span class=identifier>constrained</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=identifier>is_even</span><span class=special>></span>
+ <span class=special>></span>
+<span class=special>></span> <span class=identifier>indexed_t</span><span class=special>;</span>
+</pre></blockquote>
+
+<h2><a name="user_defined_indices">User-defined indices</a></h2>
+
+<p>
+The mechanisms by which Boost.MultiIndex orchestrates the
+operations of the indices held by a <code>multi_index_container</code> are
+simple enough to make them worth documenting so that the (bold)
+user can write implementations for her own indices.
+</p>
+
+<h2><a name="indexed_maps">Indexed maps</a></h2>
+
+<p>
+<code>multi_index_container</code> is rich enough to provide the basis
+for implementation of <i>indexed maps</i>, i.e. maps which
+can be looked upon several different keys. The motivation for having
+such a container is mainly aesthetic convenience, since it
+would not provide any additional feature to similar constructs
+based directly on <code>multi_index_container</code>.
+</p>
+
+<p>
+The main challenge in writing an indexed map lies in the design of a
+reasonable interface that resembles that of <code>std::map</code> as
+much as possible. There seem to be fundamental difficulties in extending
+the syntax of a <code>std::map</code> to multiple keys. For one example,
+consider the situation:
+</p>
+
+<blockquote><pre>
+<span class=identifier>indexed_map</span><span class=special><</span><span class=keyword>int</span><span class=special>,</span><span class=identifier>string</span><span class=special>,</span><span class=keyword>double</span><span class=special>></span> <span class=identifier>m</span><span class=special>;</span>
+<span class=comment>// keys are int and string, double is the mapped to value</span>
+
+<span class=special>...</span>
+
+<span class=identifier>cout</span><span class=special><<</span><span class=identifier>m</span><span class=special>[</span><span class=number>0</span><span class=special>]<<</span><span class=identifier>endl</span><span class=special>;</span> <span class=comment>// OK</span>
+<span class=identifier>cout</span><span class=special><<</span><span class=identifier>m</span><span class=special>[</span><span class=string>"zero"</span><span class=special>]<<</span><span class=identifier>endl</span><span class=special>;</span> <span class=comment>// OK</span>
+<span class=identifier>m</span><span class=special>[</span><span class=number>1</span><span class=special>]=</span><span class=number>1.0</span><span class=special>;</span> <span class=comment>// !!</span>
+</pre></blockquote>
+
+<p>
+In the last sentence of the example, the user has no way of
+providing the <code>string</code> key mapping to the same value
+as <code>m[1]</code>. This and similar problems have to be devoted
+a careful study when designing the interface of a potential
+indexed map.
+</p>
+
+<hr>
+
+<div class="prev_link"><a href="tests.html"><img src="prev.gif" alt="tests" border="0"><br>
+Tests
+</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="release_notes.html"><img src="next.gif" alt="release notes" border="0"><br>
+Release notes
+</a></div><br clear="all" style="clear: all;">
+
+<br>
+
+<p>Revised April 19th 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>