ceph/src/boost/libs/multi_index/doc/tutorial/basics.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
   2
   3 <html>
   4 <head>
   5 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   6 <title>Boost.MultiIndex Documentation - Tutorial - Basics</title>
   7 <link rel="stylesheet" href="../style.css" type="text/css">
   8 <link rel="start" href="../index.html">
   9 <link rel="prev" href="index.html">
  10 <link rel="up" href="index.html">
  11 <link rel="next" href="indices.html">
  12 </head>
  13
  14 <body>
  15 <h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
  16 "middle" width="277" height="86">Boost.MultiIndex Tutorial: Basics</h1>
  17
  18 <div class="prev_link"><a href="index.html"><img src="../prev.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
  19 Boost.MultiIndex tutorial
  20 </a></div>
  21 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
  22 Boost.MultiIndex tutorial
  23 </a></div>
  24 <div class="next_link"><a href="indices.html"><img src="../next.gif" alt="index types" border="0"><br>
  25 Index types
  26 </a></div><br clear="all" style="clear: all;">
  27
  28 <hr>
  29
  30 <h2>Contents</h2>
  31
  32 <ul>
  33   <li><a href="#intro">Introduction</a>
  34     <ul>
  35       <li><a href="#multiple_sort">Multiple sorts on a single set</a></li>
  36       <li><a href="#list_fast_lookup">A bidirectional list with fast lookup</a></li>
  37     </ul>
  38   </li>
  39   <li><a href="#index_spec">Index specification</a></li>
  40   <li><a href="#tagging">Tagging</a></li>
  41   <li><a href="#iterator_access">Iterator access</a></li>
  42   <li><a href="#index_types">Index types</a>
  43     <ul>
  44       <li><a href="#ord_indices">Ordered indices</a>
  45         <ul>
  46           <li><a href="#unique_non_unique">Unique and non-unique variants</a></li>
  47           <li><a href="#ord_spec">Specification</a></li>
  48           <li><a href="#key_extraction">Key extraction</a></li>
  49           <li><a href="#comparison_predicates">Comparison predicates</a></li>
  50           <li><a href="#special_lookup">Special lookup operations</a></li>
  51           <li><a href="#range">Retrieval of ranges</a></li>
  52           <li><a href="#ord_updating">Updating</a></li>
  53         </ul>
  54       </li>
  55       <li><a href="#seq_indices">Sequenced indices</a>
  56         <ul>
  57           <li><a href="#seq_spec">Specification</a></li>
  58           <li><a href="#list_ops">List operations</a></li>
  59           <li><a href="#seq_updating">Updating</a></li>
  60         </ul>
  61       </li>
  62     </ul>
  63   </li>
  64   <li><a href="#projection">Projection of iterators</a></li>
  65   <li><a href="#complexity">Complexity and exception safety</a></li>
  66 </ul>
  67
  68 <h2><a name="intro">Introduction</a></h2>
  69
  70 <p>
  71 We introduce the main concepts of Boost.MultiIndex through the study of
  72 two typical use cases.
  73 </p>
  74
  75 <h3><a name="multiple_sort">Multiple sorts on a single set</a></h3>
  76
  77 <p>
  78 STL sets and multisets are varying-length containers where elements are efficiently
  79 sorted according to a given comparison predicate. These container classes fall short
  80 of functionality when the programmer wishes to efficiently sort and look up the elements
  81 following a different sorting criterion. Consider for instance:
  82 </p>
  83
  84 <blockquote><pre>
  85 <span class=keyword>struct</span> <span class=identifier>employee</span>
  86 <span class=special>{</span>
  87   <span class=keyword>int</span>         <span class=identifier>id</span><span class=special>;</span>
  88   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
  89
  90   <span class=identifier>employee</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>id</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&amp;</span> <span class=identifier>name</span><span class=special>):</span><span class=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>
  91
  92   <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;(</span><span class=keyword>const</span> <span class=identifier>employee</span><span class=special>&amp;</span> <span class=identifier>e</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>id</span><span class=special>&lt;</span><span class=identifier>e</span><span class=special>.</span><span class=identifier>id</span><span class=special>;}</span>
  93 <span class=special>};</span>
  94 </pre></blockquote>
  95
  96 <p>The fact that IDs are unique to each employee is reflected by the way
  97 <code>operator&lt;</code> is defined, so a natural data structure for storing of
  98 <code>employee</code>s is just a <code>std::set&lt;employee></code>. Now,
  99 if one wishes to print out a listing of all employees in alphabetical order, available
 100 solutions may have disadvantages either in terms of storage space, complexity or ease
 101 of maintenance:
 102 <ul>
 103 <li>Copy the employee set into a vector or similar and sort this by a comparison
 104 functor dependent upon <code>employee::name</code>.
 105 <li>Keep a secondary data structure of pointers to the elements of the set, appropriately
 106 sorted by name.
 107 </ul>
 108 Of these, probably the second solution will be the one adopted by most programmers
 109 concerned about efficiency, but it imposes the annoying burden of keeping the two
 110 structures in sync. If the code is additionally required to be exception-safe, this
 111 construct easily becomes unmaintainable.
 112 </p>
 113
 114 <p>
 115 Boost.MultiIndex features <a href="#ord_indices"><i>ordered indices</i></a>, which
 116 sort the elements according to a particular key, and are designed to help programmers
 117 in need of sequences of elements for which <i>more than one</i> sorting criteria are
 118 relevant. We do so by defining a <code>multi_index_container</code>
 119 instantiation composed of several ordered indices: each index, viewed in isolation,
 120 behaves much as an ordered <code>std::set</code> (or <code>std::multiset</code>), whilst
 121 the overall integrity of the entire data structure is preserved. Our example problem
 122 thus can be solved with Boost.MultiIndex as follows:
 123 </p>
 124
 125 <blockquote><pre>
 126 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index_container</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 127 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>ordered_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 128 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>identity</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 129 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>member</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 130
 131 <span class=comment>// define a multiply indexed set with indices by id and name</span>
 132 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 133   <span class=identifier>employee</span><span class=special>,</span>
 134   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 135     <span class=comment>// sort by employee::operator&lt;</span>
 136     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 137
 138     <span class=comment>// sort by less&lt;string&gt; on name</span>
 139     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 140   <span class=special>&gt;</span>
 141 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 142
 143 <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>&amp;</span> <span class=identifier>es</span><span class=special>)</span>
 144 <span class=special>{</span>
 145   <span class=comment>// get a view to index #1 (name)</span>
 146   <span class=keyword>const</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;::</span><span class=identifier>type</span><span class=special>&amp;</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>&lt;</span><span class=number>1</span><span class=special>&gt;();</span>
 147   <span class=comment>// use name_index as a regular std::set</span>
 148   <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span>
 149     <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>
 150     <span class=identifier>std</span><span class=special>::</span><span class=identifier>ostream_iterator</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>));</span>
 151 <span class=special>}</span>
 152 </pre></blockquote>
 153
 154 <p>
 155 Instead of a single comparison predicate type, as it happens for STL associative
 156 containers, <code>multi_index_container</code> is passed a
 157 <a href="../reference/multi_index_container.html#multi_index_container">list</a> of index
 158 specifications (<code>indexed_by</code>), each one inducing the corresponding index.
 159 Indices are accessed via
 160 <a href="../reference/multi_index_container.html#index_retrieval"><code>get</code></a><code>&lt;N>()</code>
 161 where <i>N</i> ranges between 0 and the number of comparison
 162 predicates minus one. The functionality of index #0 can be accessed directly from a
 163 <code>multi_index_container</code> object without using <code>get&lt;0>()</code>: for instance,
 164 <code>es.begin()</code> is equivalent to <code>es.get&lt;0>().begin()</code>.
 165 </p>
 166
 167 <p>
 168 Note that <code>get</code> returns a <i>reference</i> to the index, and not
 169 an index object. Indices cannot be constructed as separate objects from the
 170 container they belong to, so the following
 171 </p>
 172
 173 <blockquote><pre>
 174 <span class=comment>// Wrong: we forgot the &amp; after employee_set::nth_index&lt;1&gt;::type</span>
 175 <span class=keyword>const</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;::</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>&lt;</span><span class=number>1</span><span class=special>&gt;();</span>
 176 </pre></blockquote>
 177
 178 <p>
 179 does not compile, since it is trying to construct the index object
 180 <code>name_index</code>. This is a common source of errors in user code.
 181 </p>
 182
 183 <h3><a name="list_fast_lookup">A bidirectional list with fast lookup</a></h3>
 184
 185 <p>
 186 This study case allows us to introduce so-called
 187 <a href="#seq_indices"><i>sequenced indices</i></a>, and how they
 188 interact with ordered indices to construct powerful containers. Suppose
 189 we have a text parsed into words and stored in a list like this:
 190 </p>
 191
 192 <blockquote><pre>
 193 <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>list</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&gt;</span> <span class=identifier>text_container</span><span class=special>;</span>
 194
 195 <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>text</span><span class=special>=</span>
 196   <span class=string>&quot;Alice was beginning to get very tired of sitting by her sister on the &quot;</span>
 197   <span class=string>&quot;bank, and of having nothing to do: once or twice she had peeped into the &quot;</span>
 198   <span class=string>&quot;book her sister was reading, but it had no pictures or conversations in &quot;</span>
 199   <span class=string>&quot;it, 'and what is the use of a book,' thought Alice 'without pictures or &quot;</span>
 200   <span class=string>&quot;conversation?'&quot;</span><span class=special>;</span>
 201
 202 <span class=comment>// feed the text into the list</span>
 203 <span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span>
 204 <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tokenizer</span><span class=special>&lt;</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special>&lt;</span><span class=keyword>char</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=identifier>tok</span>
 205   <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>&lt;</span><span class=keyword>char</span><span class=special>&gt;(</span><span class=string>&quot; \t\n.,;:!?'\&quot;-&quot;</span><span class=special>));</span>
 206 <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>
 207 </pre></blockquote>
 208
 209 <p>
 210 If we want to count the occurrences of a given word into the text we will resort
 211 to <code>std::count</code>:
 212 </p>
 213
 214 <blockquote><pre>
 215 <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>&amp;</span> <span class=identifier>word</span><span class=special>)</span>
 216 <span class=special>{</span>
 217   <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>
 218 <span class=special>}</span>
 219 </pre></blockquote>
 220
 221 <p>
 222 But this implementation of <code>occurrences</code> performs in linear time, which
 223 could be unacceptable for large quantities of text. Similarly, other operations like
 224 deletion of selected words are just too costly to carry out on a
 225 <code>std::list</code>:
 226 </p>
 227
 228 <blockquote><pre>
 229 <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>&amp;</span> <span class=identifier>word</span><span class=special>)</span>
 230 <span class=special>{</span>
 231   <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>
 232 <span class=special>}</span>
 233 </pre></blockquote>
 234
 235 <p>
 236 When performance is a concern, we will need an additional data structure that indexes
 237 the elements in <code>tc</code>, presumably in alphabetical order. Boost.MultiIndex
 238 does precisely this through the combination of sequenced and ordered indices:
 239 </p>
 240
 241 <blockquote><pre>
 242 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index_container</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 243 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>sequenced_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 244 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>ordered_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 245 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>identity</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 246
 247 <span class=comment>// define a multi_index_container with a list-like index and an ordered index</span>
 248 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 249   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,</span>
 250   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 251     <span class=identifier>sequenced</span><span class=special>&lt;&gt;,</span> <span class=comment>// list-like index</span>
 252     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=comment>// words by alphabetical order</span>
 253   <span class=special>&gt;</span>
 254 <span class=special>&gt;</span> <span class=identifier>text_container</span><span class=special>;</span>
 255
 256 <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>text</span><span class=special>=...</span>
 257
 258 <span class=comment>// feed the text into the list</span>
 259 <span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span>
 260 <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tokenizer</span><span class=special>&lt;</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special>&lt;</span><span class=keyword>char</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=identifier>tok</span>
 261   <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>&lt;</span><span class=keyword>char</span><span class=special>&gt;(</span><span class=string>&quot; \t\n.,;:!?'\&quot;-&quot;</span><span class=special>));</span>
 262 <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>
 263 </pre></blockquote>
 264
 265 <p>
 266 So far, the substitution of <code>multi_index_container</code> for <code>std::list</code>
 267 does not show any advantage. The code for inserting the text into the container
 268 does not change as sequenced indices provide an interface similar to that of
 269 <code>std::list</code> (no explicit access to this index through
 270 <code>get&lt;0>()</code> is needed as <code>multi_index_container</code> inherits the
 271 functionality of index #0.) But the specification of an additional ordered index
 272 allows us to implement <code>occurrences</code> and <code>delete_word</code>
 273 in a much more efficient manner:
 274 </p>
 275
 276 <blockquote><pre>
 277 <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>&amp;</span> <span class=identifier>word</span><span class=special>)</span>
 278 <span class=special>{</span>
 279   <span class=comment>// get a view to index #1</span>
 280   <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;::</span><span class=identifier>type</span><span class=special>&amp;</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>&lt;</span><span class=number>1</span><span class=special>&gt;();</span>
 281
 282   <span class=comment>// use sorted_index as a regular std::set</span>
 283   <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>
 284 <span class=special>}</span>
 285
 286 <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>&amp;</span> <span class=identifier>word</span><span class=special>)</span>
 287 <span class=special>{</span>
 288   <span class=comment>// get a view to index #1</span>
 289   <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;::</span><span class=identifier>type</span><span class=special>&amp;</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>&lt;</span><span class=number>1</span><span class=special>&gt;();</span>
 290
 291   <span class=comment>// use sorted_index as a regular std::set</span>
 292   <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>
 293 <span class=special>}</span>
 294 </pre></blockquote>
 295
 296 <p>
 297 Now, <code>occurrences</code> and <code>delete_word</code> have logarithmic
 298 complexity. The programmer can use index #0 for accessing the text as with
 299 <code>std::list</code>, and use index #1 when logarithmic lookup is needed.
 300 </p>
 301
 302 <h2>
 303 <a name="index_spec">Index specification</a>
 304 </h2>
 305
 306 <p>
 307 The indices of a <code>multi_index_container</code> instantiation are specified by
 308 means of the <a href="../reference/indices.html#indexed_by">
 309 <code>indexed_by</code></a> construct. For instance, the instantiation
 310 </p>
 311
 312 <blockquote><pre>
 313 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 314   <span class=identifier>employee</span><span class=special>,</span>
 315   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 316     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 317     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 318   <span class=special>&gt;</span>
 319 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 320 </pre></blockquote>
 321
 322 <p>
 323 is comprised of a <a href="#unique_non_unique">unique ordered index</a> and a
 324 <a href="#unique_non_unique">non-unique ordered index</a>, while in
 325 </p>
 326
 327 <blockquote><pre>
 328 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 329   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,</span>
 330   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 331     <span class=identifier>sequenced</span><span class=special>&lt;&gt;,</span>
 332     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 333   <span class=special>&gt;</span>
 334 <span class=special>&gt;</span> <span class=identifier>text_container</span><span class=special>;</span>
 335 </pre></blockquote>
 336
 337 <p>
 338 we specifiy two indices, the first of <a href="#seq_indices">sequenced type</a>,
 339 the second a non-unique <a href="#ord_indices">ordered index</a>. In general, we
 340 can specify an arbitrary number of indices: each of the arguments of
 341 <code>indexed_by</code> is called an
 342 <a href="../reference/indices.html#index_specification"><i>index specifier</i></a>.
 343 Depending on the type of index being specified, the corresponding specifier
 344 will need additional information: for instance, the specifiers <code>ordered_unique</code>
 345 and <code>ordered_non_unique</code> are provided with a
 346 <a href="#key_extraction">key extractor</a> and an optional
 347 <a href="#comparison_predicates">comparison predicate</a> which jointly indicate
 348 how the sorting of elements will be performed.
 349 </p>
 350
 351 <p>
 352 A <code>multi_index_container</code> instantiation can be declared without supplying
 353 the <code>indexed_by</code> part: in this case, default index values are taken
 354 so that the resulting type is equivalent to a regular <code>std::set</code>.
 355 Concretely, the instantiation
 356 </p>
 357
 358 <blockquote><pre>
 359 <span class=identifier>multi_index_container</span><span class=special>&lt;</span><i>(element)</i><span class=special>&gt;</span>
 360 </pre></blockquote>
 361
 362 <p>
 363 is equivalent to
 364 </p>
 365
 366 <blockquote><pre>
 367 <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 368   <i>(element)</i><span class=special>,</span>
 369   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 370     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;(</span><span class=identifier>element</span><span class=special>)&gt;</span> <span class=special>&gt;</span>
 371   <span class=special>&gt;</span>
 372 <span class=special>&gt;</span>
 373 </pre></blockquote>
 374
 375 <h2><a name="tagging">Tagging</a></h2>
 376
 377 <p>
 378 In order to retrieve (a reference to) an index of a given <code>multi_index_container</code>,
 379 the programmer must provide its order number, which is cumbersome and not very
 380 self-descriptive. Optionally, indices can be assigned <i>tags</i> (C++ types) that
 381 act as more convenient mnemonics. If provided, tags must be passed as the
 382 first parameter of the corresponding index specifier. The following is a revised version of
 383 <code>employee_set</code> with inclusion of tags:
 384 </p>
 385
 386 <blockquote><pre>
 387 <span class=comment>// tags</span>
 388 <span class=keyword>struct</span> <span class=identifier>name</span><span class=special>{};</span>
 389
 390 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 391   <span class=identifier>employee</span><span class=special>,</span>
 392   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 393     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 394     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>tag</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>&gt;,</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 395   <span class=special>&gt;</span>
 396 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 397 </pre></blockquote>
 398
 399 <p>
 400 Tags have to be passed inside the <a href="../reference/indices.html#tag"><code>tag</code></a>
 401 construct. Any type can be used as a tag for an index, although in general one will choose
 402 names that are descriptive of the index they are associated with. The tagging mechanism allows
 403 us to write expressions like</p>
 404
 405 <blockquote><pre>
 406 <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
 407 <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>&lt;</span><span class=identifier>name</span><span class=special>&gt;().</span><span class=identifier>begin</span><span class=special>();</span>
 408 </pre></blockquote>
 409
 410 <p>
 411 If no tag is provided for an index (as is the case for index #0 of the previous
 412 example), access to that index can only be performed by number. Note the existence
 413 of two different <code>typedef</code>s <code>nth_index</code> and
 414 <code>index</code> for referring to an index by number and by tag, respectively;
 415 for instance,
 416 <ul>
 417   <li><code>employee_set::nth_index&lt;1>::type</code> is the type of
 418     index #1,</li>
 419   <li><code>employee_set::index&lt;name>::type</code> is the type of the index
 420     tagged with <code>name</code> (the same index #1 in this case.)</li>
 421 </ul>
 422 <code>get()</code>, on the other hand, is overloaded to serve both styles of access:
 423 </p>
 424
 425 <blockquote><pre>
 426 <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>&gt;::</span><span class=identifier>type</span><span class=special>&amp;</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>&lt;</span><span class=identifier>name</span><span class=special>&gt;();</span>
 427 <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;::</span><span class=identifier>type</span><span class=special>&amp;</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>&lt;</span><span class=number>1</span><span class=special>&gt;();</span> <span class=comment>// same index</span>
 428 </pre></blockquote>
 429
 430 <p>
 431 Additionally, the <code>tag</code> class template accepts several tags for one
 432 index, that we can use interchangeably: for instance, the specification of index #1
 433 in the previous example can be rewritten to hold two different tags
 434 <code>name</code> and <code>by_name</code>:
 435 </p>
 436
 437 <blockquote><pre>
 438 <span class=comment>// tags</span>
 439 <span class=keyword>struct</span> <span class=identifier>name</span><span class=special>{};</span>
 440 <span class=keyword>struct</span> <span class=identifier>by_name</span><span class=special>{};</span>
 441
 442 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 443   <span class=special>...</span>
 444     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span>
 445       <span class=identifier>tag</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>,</span><span class=identifier>by_name</span><span class=special>&gt;,</span>
 446       <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span>
 447     <span class=special>&gt;</span>
 448   <span class=special>...</span>
 449 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 450 </pre></blockquote>
 451
 452 <h2><a name="iterator_access">Iterator access</a></h2>
 453
 454 <p>
 455 Each index of a <code>multi_index_container</code> uses its own
 456 iterator types, which are different from those of another indices. As is
 457 the rule with STL containers, these iterators are defined as nested
 458 types of the index:
 459 </p>
 460
 461 <blockquote><pre>
 462 <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;::</span><span class=identifier>type</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span>
 463   <span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;().</span><span class=identifier>find</span><span class=special>(</span><span class=string>&quot;Judy Smith&quot;</span><span class=special>);</span>
 464 </pre></blockquote>
 465
 466 <p>
 467 This kind of expressions can be rendered more readable by
 468 means of user-defined <code>typedef</code>s:
 469 </p>
 470
 471 <blockquote><pre>
 472 <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
 473 <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>
 474   <span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;().</span><span class=identifier>find</span><span class=special>(</span><span class=string>&quot;Judy Smith&quot;</span><span class=special>);</span>
 475 </pre></blockquote>
 476
 477 <p>
 478 The iterators provided by every index are <i>constant</i>, that is, the elements they point to
 479 cannot be mutated directly. This  follows the interface of <code>std::set</code> for ordered
 480 indices but might come as a surprise for other types such as sequenced indices, which are modeled after
 481 <code>std::list</code>, where this limitation does not happen. This seemingly odd behavior
 482 is imposed by the way <code>multi_index_container</code>s work; if elements were
 483 allowed to be mutated indiscriminately, we could introduce inconsistencies
 484 in the ordered indices of the <code>multi_index_container</code> without the container
 485 being notified about it. Element modification is properly done by means of
 486 <a href="#ord_updating">update operations</a> on any index.
 487 </p>
 488
 489 <h2>
 490 <a name="index_types">Index types</a>
 491 </h2>
 492
 493 <p>
 494 Currently, Boost.MultiIndex provides the following index types:
 495 <ul>
 496   <li>Ordered indices sort the elements like <code>std::set</code>s do and
 497     provide a similar interface. There are <i>unique</i> and <i>non-unique</i>
 498     variants: the former do not allow for duplicates, while the latter permit
 499     them (like <code>std::multiset</code>.)</li>
 500   <li>Ranked indices are a variation of ordered indices providing extra capabilities
 501     for querying and accessing elements based on their <i>rank</i> (the numerical position
 502     they occupy in the index).
 503   </li>
 504   <li>Sequenced indices are modeled after the semantics and interface of
 505     <code>std::list</code>: they arrange the elements as if in a bidirectional
 506     list.</li>
 507   <li>Hashed indices provide fast access to the elements through hashing
 508     techniques, in a similar way as non-standard <code>hash_set</code>s provided
 509     by some vendors. Recently, <i>unordered associative containers</i> have been
 510     proposed as part of an extension of the C++ standard library known
 511     in the standardization commitee as TR1. Hashed indices closely model this
 512     proposal.</li>
 513   <li>Random access indices provide an interface similar to that of
 514     sequenced indices, and additionally feature random access iterators
 515     and positional access to the elements.</li>
 516 </ul>
 517 The examples in the <a href="#intro">introduction</a> exercise ordered and sequenced
 518 indices, which are the most commonly used; the other kinds of indices are presented
 519 in the <a href="indices.html">index types</a> section of the tutorial.
 520 </p>
 521
 522 <h3>
 523 <a name="ord_indices">Ordered indices</a>
 524 </h3>
 525
 526 <p>
 527 Ordered indices sort the elements in a <code>multi_index_container</code> according
 528 to a specified key and an associated comparison predicate. These indices can
 529 be viewed as analogues of the standard container <code>std::set</code>, and in fact
 530 they do replicate its interface, albeit with some minor differences dictated
 531 by the general constraints of Boost.MultiIndex.
 532 </p>
 533
 534 <h4>
 535 <a name="unique_non_unique">Unique and non-unique variants</a>
 536 </h4>
 537
 538 <p>
 539 Ordered indices are classified into <i>unique</i>, which prohibit two
 540 elements to have the same key value, and <i>non-unique</i> indices,
 541 which allow for duplicates. Consider again the definition
 542 </p>
 543
 544 <blockquote><pre>
 545 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 546   <span class=identifier>employee</span><span class=special>,</span>
 547   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 548     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 549     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 550   <span class=special>&gt;</span>
 551 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 552 </pre></blockquote>
 553
 554 <p>
 555 In this instantiation of <code>multi_index_container</code>, the first index is to be
 556 treated as unique (since IDs are exclusive to each employee) and thus is declared using
 557 <code>ordered_unique</code>, whereas the second index is non-unique (as the possibility exists
 558 that say two John Smiths are hired in the same company), which is specified by the use
 559 of <code>ordered_non_unique</code>.
 560 </p>
 561
 562 <p>
 563 The classification of ordered indices in unique and non-unique has an impact on which
 564 elements are allowed to be inserted into a given <code>multi_index_container</code>; briefly put,
 565 unique ordered indices mimic the behavior of <code>std::set</code>s while non-unique
 566 ordered indices are similar to <code>std::multiset</code>s. For instance, an
 567 <code>employee_set</code> can hold the objects <code>employee(0,"George Brown")</code>
 568 and <code>employee(1,"George Brown")</code>, but will not accept the insertion of an
 569 <code>employee</code> object whose ID coincides with that of some previously inserted
 570 employee.
 571 </p>
 572
 573 <p>
 574 More than one unique index can be specified. For instance, if we augment
 575 <code>employee</code> to include an additional member for the Social Security number,
 576 which is reasonably treated as unique, the following captures this design:
 577 </p>
 578
 579 <blockquote><pre>
 580 <span class=keyword>struct</span> <span class=identifier>employee</span>
 581 <span class=special>{</span>
 582   <span class=keyword>int</span>         <span class=identifier>id</span><span class=special>;</span>
 583   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
 584   <span class=keyword>int</span>         <span class=identifier>ssnumber</span><span class=special>;</span>
 585
 586   <span class=identifier>employee</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>id</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&amp;</span> <span class=identifier>name</span><span class=special>,</span><span class=keyword>int</span> <span class=identifier>ssnumber</span><span class=special>):</span>
 587     <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>
 588
 589   <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;(</span><span class=keyword>const</span> <span class=identifier>employee</span><span class=special>&amp;</span> <span class=identifier>e</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>id</span><span class=special>&lt;</span><span class=identifier>e</span><span class=special>.</span><span class=identifier>id</span><span class=special>;}</span>
 590 <span class=special>};</span>
 591
 592 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 593   <span class=identifier>employee</span><span class=special>,</span>
 594   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 595     <span class=comment>// sort by employee::operator&lt;</span>
 596     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 597
 598     <span class=comment>// sort by less&lt;string&gt; on name</span>
 599     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 600
 601     <span class=comment>// sort by less&lt;int&gt; on ssnumber</span>
 602     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>ssnumber</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 603   <span class=special>&gt;</span>
 604 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 605 </pre></blockquote>
 606
 607 <h4>
 608 <a name="ord_spec">Specification</a>
 609 </h4>
 610
 611 <p>
 612 Ordered index specifiers in <code>indexed_by</code> must conform to one of the
 613 following syntaxes:
 614 </p>
 615
 616 <blockquote><pre>
 617 <span class=special>(</span><span class=identifier>ordered_unique</span> <span class=special>|</span> <span class=identifier>ordered_non_unique</span><span class=special>)
 618   </span><span class=special>&lt;[</span><i>(tag)</i><span class=special>[,</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]]&gt;</span>
 619
 620 <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>
 621   <span class=special>&lt;[</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]&gt;</span>
 622 </pre></blockquote>
 623
 624 <p>
 625 The first optional argument is used if <a href="#tagging">tags</a> are associated
 626 with the index. We now proceed to briefly discuss the remaining arguments
 627 of an ordered index specifier.
 628 </p>
 629
 630 <h4>
 631 <a name="key_extraction">Key extraction</a>
 632 </h4>
 633
 634 <p>
 635 The first template parameter (or the second, if tags are supplied)
 636 in the specification of an ordered index provides a <i>key extraction</i> predicate.
 637 This predicate takes a whole element (in our example, a reference to an
 638 <code>employee</code> object) and returns the piece of information by which
 639 the sorting is performed. In most cases, one of the following two situations arises:
 640 <ul>
 641 <li>The whole element serves as the key, as is the case of the first index
 642 in <code>employee_set</code>. The predefined
 643 <a href="key_extraction.html#identity"><code>identity</code></a> predicate
 644 can be used here as a key extractor; <code>identity</code> returns as the key the
 645 same object passed as argument.</li>
 646 <li>The comparison is performed on a particular data member of the element; this
 647 closely follows the specification of indices on a column of a table in relational
 648 databases. Boost.MultiIndex provides
 649 <a href="key_extraction.html#member"><code>member</code></a>, which returns
 650 as the key a member of the element specified by a given pointer.</li>
 651 </ul>
 652 As an example, consider again the definition of <code>employee_set</code>. The
 653 definition of the first index:
 654 </p>
 655
 656 <blockquote><pre>
 657 <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 658 </pre></blockquote>
 659
 660 <p>
 661 specifies by means of <code>identity</code> that <code>element</code>
 662 objects themselves serve as key for this index. On the other hand, in the second
 663 index:
 664 </p>
 665
 666 <blockquote><pre>
 667 <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 668 </pre></blockquote>
 669
 670 <p>
 671 we use <code>member</code> to extract the <code>name</code> part of the
 672 <code>employee</code> object. The key type of this index is then
 673 <code>std::string</code>.
 674 </p>
 675
 676 <p>
 677 Apart from <code>identity</code> and <code>member</code>, Boost.MultiIndex provides
 678 several other predefined key extractors and powerful ways to combine them.
 679 Key extractors can also be defined by the user.
 680 Consult the <a href="key_extraction.html">key extraction section</a> of
 681 the tutorial for a more detailed exposition of this topic.
 682 </p>
 683
 684 <h4><a name="comparison_predicates">Comparison predicates</a></h4>
 685
 686 <p>
 687 The last part of the specification of an ordered index is the associated
 688 <i>comparison predicate</i>, which must order the keys in a less-than fashion.
 689 These comparison predicates are not different from those used by STL containers like
 690 <code>std::set</code>. By default (i.e. if no comparison predicate is provided),
 691 an index with keys of type <code>key_type</code> sorts the elements by
 692 <code>std::less&lt;key_type></code>. Should other comparison criteria be needed,
 693 they can be specified as an additional parameter in the index declaration:
 694 </p>
 695
 696 <blockquote><pre>
 697 <span class=comment>// define a multiply indexed set with indices by id and by name
 698 // in reverse alphabetical order</span>
 699 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 700   <span class=identifier>employee</span><span class=special>,</span>
 701   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 702     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;,</span> <span class=comment>// as usual</span>
 703     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span>
 704       <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;,</span>
 705       <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&gt;</span>  <span class=comment>// default would be std::less&lt;std::string&gt;</span>
 706     <span class=special>&gt;</span>
 707   <span class=special>&gt;</span>
 708 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 709 </pre></blockquote>
 710
 711 <h4><a name="special_lookup">Special lookup operations</a></h4>
 712
 713 <p>
 714 A given ordered index allows for lookup based on its key type, rather than the
 715 whole element. For instance, to find Veronica Cruz in an
 716 <code>employee_set</code> one would write:
 717 </p>
 718
 719 <blockquote><pre>
 720 <span class=identifier>employee_set</span> <span class=identifier>es</span><span class=special>;</span>
 721 <span class=special>...</span>
 722 <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
 723 <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>&lt;</span><span class=identifier>name</span><span class=special>&gt;().</span><span class=identifier>find</span><span class=special>(</span><span class=string>&quot;Veronica Cruz&quot;</span><span class=special>);</span>
 724 </pre></blockquote>
 725
 726 <p>As a plus, Boost.MultiIndex provides lookup operations accepting search keys
 727 different from the <code>key_type</code> of the index, which is a specially useful
 728 facility when <code>key_type</code> objects  are expensive to create. Ordered STL containers
 729 fail to provide this functionality, which often leads to inelegant workarounds: consider for
 730 instance the problem of determining the employees whose IDs fall in the range [0,100]. Given
 731 that the key of <code>employee_set</code> index #0
 732 is <code>employee</code> itself, on a first approach one would write the following:
 733 </p>
 734
 735 <blockquote><pre>
 736 <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>&quot;&quot;</span><span class=special>));</span>
 737 <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>&quot;&quot;</span><span class=special>));</span>
 738 </pre></blockquote>
 739
 740 <p>
 741 Note however that <code>std::less&lt;employee></code> actually only depends
 742 on the IDs of the employees, so it would be more convenient to avoid
 743 the creation of entire <code>employee</code> objects just for the sake of
 744 their IDs. Boost.MultiIndex allows for this: define an appropriate
 745 comparison predicate
 746 </p>
 747
 748 <blockquote><pre>
 749 <span class=keyword>struct</span> <span class=identifier>comp_id</span>
 750 <span class=special>{</span>
 751   <span class=comment>// compare an ID and an employee</span>
 752   <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>&amp;</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>&lt;</span><span class=identifier>e2</span><span class=special>.</span><span class=identifier>id</span><span class=special>;}</span>
 753
 754   <span class=comment>// compare an employee and an ID</span>
 755   <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>&amp;</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>&lt;</span><span class=identifier>x</span><span class=special>;}</span>
 756 <span class=special>};</span>
 757 </pre></blockquote>
 758
 759 <p>and now write the search as</p>
 760
 761 <blockquote><pre>
 762 <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>
 763 <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>
 764 </pre></blockquote>
 765
 766 <p>
 767 Here we are not only passing IDs instead of <code>employee</code> objects:
 768 an alternative comparison predicate is passed as well. In general, lookup operations
 769 of ordered indices are overloaded to accept
 770 <a href="../reference/ord_indices.html#set_operations"><i>compatible sorting
 771 criteria</i></a>. The somewhat cumbersone definition of compatibility in this context
 772 is given in the reference, but roughly speaking we say that a comparison predicate
 773 <code>C1</code> is compatible with <code>C2</code> if any sequence sorted by
 774 <code>C2</code> is also sorted with respect to <code>C1</code>.
 775 The following shows a more interesting use of compatible predicates:
 776 </p>
 777
 778 <blockquote><pre>
 779 <span class=comment>// sorting by name's initial</span>
 780 <span class=keyword>struct</span> <span class=identifier>comp_initial</span>
 781 <span class=special>{</span>
 782   <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>&amp;</span> <span class=identifier>s</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span>
 783     <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>
 784     <span class=keyword>return</span> <span class=identifier>ch</span><span class=special>&lt;</span><span class=identifier>s</span><span class=special>[</span><span class=number>0</span><span class=special>];</span>
 785   <span class=special>}</span>
 786
 787   <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>&amp;</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>
 788     <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>
 789     <span class=keyword>return</span> <span class=identifier>s</span><span class=special>[</span><span class=number>0</span><span class=special>]&lt;</span><span class=identifier>ch</span><span class=special>;</span>
 790   <span class=special>}</span>
 791 <span class=special>};</span>
 792
 793 <span class=comment>// obtain first employee whose name begins with 'J' (ordered by name)</span>
 794 <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
 795 <span class=identifier>employee_set_by_name</span><span class=special>&amp;</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>&lt;</span><span class=identifier>name</span><span class=special>&gt;();</span>
 796 <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>
 797   <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>
 798 </pre></blockquote>
 799
 800 <h4><a name="range">Retrieval of ranges</a></h4>
 801
 802 <p>
 803 Range searching, i.e. the lookup of all elements in a given interval, is a very
 804 frequent operation for which standard <code>lower_bound</code> and
 805 <code>upper_bound</code> can be resorted to, though in a cumbersome manner.
 806 For instance, the following code retrieves the elements of an
 807 <code>multi_index_container&lt;double></code> in the interval [100,200]:
 808 </p>
 809
 810 <blockquote><pre>
 811 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span><span class=keyword>double</span><span class=special>&gt;</span> <span class=identifier>double_set</span><span class=special>;</span>
 812 <span class=comment>// note: default template parameters resolve to
 813 // multi_index_container&lt;double,indexed_by&lt;unique&lt;identity&lt;double&gt; &gt; &gt; &gt;.</span>
 814
 815 <span class=identifier>double_set</span> <span class=identifier>s</span><span class=special>;</span>
 816 <span class=special>...</span>
 817 <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>
 818 <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>
 819 <span class=comment>// range [it0,it1) contains the elements in [100,200]</span>
 820 </pre></blockquote>
 821
 822 <p>
 823 Subtle changes to the code are required when strict inequalities are considered.
 824 To retrieve the elements <i>greater</i> than 100 and <i>less</i> than 200, the
 825 code has to be rewritten as
 826 </p>
 827
 828 <blockquote><pre>
 829 <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>
 830 <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>
 831 <span class=comment>// range [it0,it1) contains the elements in (100,200)</span>
 832 </pre></blockquote>
 833
 834 <p>
 835 To add to this complexity, the careful programmer has to take into account
 836 that the lower and upper bounds of the interval searched be compatible: for
 837 instance, if the lower bound is 200 and the upper bound is 100, the iterators
 838 <code>it0</code> and <code>it1</code> produced by the code above will be in reverse
 839 order, with possibly catastrophic results if a traversal from <code>it0</code>
 840 to <code>it1</code> is tried. All these details make range searching a tedious
 841 and error prone task.
 842 </p>
 843
 844 <p>
 845 The <a href="../reference/ord_indices.html#range_operations"><code>range</code></a>
 846 member function, often in combination with
 847 <a href="../../../../libs/lambda/index.html">Boost.Lambda</a> expressions, can
 848 greatly help alleviate this situation:
 849 </p>
 850
 851 <blockquote><pre>
 852 <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>
 853
 854 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span><span class=keyword>double</span><span class=special>&gt;</span> <span class=identifier>double_set</span><span class=special>;</span>
 855 <span class=identifier>double_set</span> <span class=identifier>s</span><span class=special>;</span>
 856 <span class=special>...</span>
 857 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</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>&gt;</span> <span class=identifier>p</span><span class=special>=</span>
 858   <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>&lt;=</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>_1</span><span class=special>&lt;=</span><span class=number>200</span><span class=special>);</span> <span class=comment>// 100&lt;= x &lt;=200</span>
 859 <span class=special>...</span>
 860 <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>&lt;</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>_1</span><span class=special>&lt;</span><span class=number>200</span><span class=special>);</span>   <span class=comment>// 100&lt;  x &lt; 200</span>
 861 <span class=special>...</span>
 862 <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>&lt;=</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>_1</span><span class=special>&lt;</span><span class=number>200</span><span class=special>);</span>  <span class=comment>// 100&lt;= x &lt; 200</span>
 863 </pre></blockquote>
 864
 865 <p>
 866 <code>range</code> simply accepts predicates specifying the lower and upper bounds
 867 of the interval searched. Please consult the reference for a detailed explanation
 868 of the permissible predicates passed to <code>range</code>.</p>
 869
 870 <p>
 871 One or both bounds can be omitted with the special <code>unbounded</code> marker:
 872 </p>
 873
 874 <blockquote><pre>
 875 <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>&lt;=</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>unbounded</span><span class=special>);</span> <span class=comment>// 100 &lt;= x</span>
 876 <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>&lt;</span><span class=number>200.0</span><span class=special>);</span>  <span class=comment>//   x &lt;  200</span>
 877 <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>
 878 </pre></blockquote>
 879
 880 <h4><a name="ord_updating">Updating</a></h4>
 881
 882 <p>
 883 The <a href="../reference/ord_indices.html#replace"><code>replace</code></a> member function
 884 performs in-place replacement of a given element as the following example shows:
 885 </p>
 886
 887 <blockquote><pre>
 888 <span class=keyword>typedef</span> <span class=identifier>index</span><span class=special>&lt;</span><span class=identifier>employee_set</span><span class=special>,</span><span class=identifier>name</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
 889 <span class=identifier>employee_set_by_name</span><span class=special>&amp;</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>&lt;</span><span class=identifier>name</span><span class=special>&gt;();</span>
 890
 891 <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>&quot;Anna Jones&quot;</span><span class=special>);</span>
 892 <span class=identifier>employee</span> <span class=identifier>anna</span><span class=special>=*</span><span class=identifier>it</span><span class=special>;</span>
 893 <span class=identifier>anna</span><span class=special>.</span><span class=identifier>name</span><span class=special>=</span><span class=string>&quot;Anna Smith&quot;</span><span class=special>;</span>      <span class=comment>// she just got married to Calvin Smith</span>
 894 <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>
 895 </pre></blockquote>
 896
 897 <p>
 898 <code>replace</code> performs this substitution in such a manner that:
 899 <ul>
 900 <li>The complexity is constant time if the changed element retains its original
 901 order with respect to all indices; it is logarithmic otherwise.
 902 <li>Iterator and reference validity are preserved.
 903 <li>The operation is strongly exception-safe, i.e. the <code>multi_index_container</code>
 904 remains unchanged if some exception (originated by the system or the user's data
 905 types) is thrown.
 906 </ul>
 907 <code>replace</code> is a powerful operation not provided by standard STL
 908 containers, and one that is specially handy when strong exception-safety is
 909 required.
 910 </p>
 911
 912 <p>
 913 The observant reader might have noticed that the convenience of <code>replace</code>
 914 comes at a cost: namely the whole element has to be copied <i>twice</i> to do
 915 the updating (when retrieving it and inside <code>replace</code>). If elements
 916 are expensive to copy, this may be quite a computational cost for the modification
 917 of just a tiny part of the object. To cope with this situation, Boost.MultiIndex
 918 provides an alternative updating mechanism called
 919 <a href="../reference/ord_indices.html#modify"><code>modify</code></a>:
 920 </p>
 921
 922 <blockquote><pre>
 923 <span class=keyword>struct</span> <span class=identifier>change_name</span>
 924 <span class=special>{</span>
 925   <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>&amp;</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>
 926
 927   <span class=keyword>void</span> <span class=keyword>operator</span><span class=special>()(</span><span class=identifier>employee</span><span class=special>&amp;</span> <span class=identifier>e</span><span class=special>)</span>
 928   <span class=special>{</span>
 929     <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>
 930   <span class=special>}</span>
 931
 932 <span class=keyword>private</span><span class=special>:</span>
 933   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>new_name</span><span class=special>;</span>
 934 <span class=special>};</span>
 935 <span class=special>...</span>
 936 <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
 937 <span class=identifier>employee_set_by_name</span><span class=special>&amp;</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>&lt;</span><span class=identifier>name</span><span class=special>&gt;();</span>
 938
 939 <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>&quot;Anna Jones&quot;</span><span class=special>);</span>
 940 <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>&quot;Anna Smith&quot;</span><span class=special>));</span>
 941 </pre></blockquote>
 942
 943 <p><code>modify</code> accepts a functor (or pointer to function) that is
 944 passed a reference to the element to be changed, thus eliminating the need
 945 for spurious copies. Like <code>replace</code>, <code>modify</code> does preserve
 946 the internal orderings of all the indices of the <code>multi_index_container</code>.
 947 However, the semantics of <code>modify</code> is not entirely equivalent to
 948 <code>replace</code>. Consider what happens if a collision occurs as a result
 949 of modifying the element, i.e. the modified element clashes with another with
 950 respect to some unique ordered index. In the case of <code>replace</code>, the
 951 original value is kept and the method returns without altering the container, but
 952 <code>modify</code> cannot afford such an approach, since the modifying functor
 953 leaves no trace of the previous value of the element. Integrity constraints
 954 thus lead to the following policy: when a collision happens in the
 955 process of calling <code>modify</code>, the element is erased and the method returns
 956 <code>false</code>. There is a further version of <code>modify</code> which
 957 accepts a <i>rollback</i> functor to undo the changes in case of collision:
 958 </p>
 959
 960 <blockquote><pre>
 961 <span class=keyword>struct</span> <span class=identifier>change_id</span>
 962 <span class=special>{</span>
 963   <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>
 964
 965   <span class=keyword>void</span> <span class=keyword>operator</span><span class=special>()(</span><span class=identifier>employee</span><span class=special>&amp;</span> <span class=identifier>e</span><span class=special>)</span>
 966   <span class=special>{</span>
 967     <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>
 968   <span class=special>}</span>
 969
 970 <span class=keyword>private</span><span class=special>:</span>
 971   <span class=keyword>int</span> <span class=identifier>new_id</span><span class=special>;</span>
 972 <span class=special>};</span>
 973 <span class=special>...</span>
 974 <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=...</span>
 975
 976 <span class=keyword>int</span> <span class=identifier>old_id</span><span class=special>=</span><span class=identifier>it</span><span class=special>-&gt;</span><span class=identifier>id</span><span class=special>;</span> <span class=comment>// keep the original id
 977
 978 // try to modify the id, restore it in case of collisions</span>
 979 <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>
 980 </pre></blockquote>
 981
 982 <p>In the example, <code>change_id(old_id)</code> is invoked to restore the original
 983 conditions when the modification results in collisions with some other element.
 984 The differences in behavior between <code>replace</code>, <code>modify</code> and
 985 <code>modify</code> with rollback have to be considered by the programmer on a
 986 case-by-case basis to determine the best updating mechanism.
 987 </p>
 988
 989 <p align="center">
 990 <table cellspacing="0">
 991   <caption><b>Behavior of the different updating mechanisms.</b></caption>
 992 <tr>
 993   <th align="center">updating function</th>
 994   <th>If there is a collision...</th>
 995 </tr>
 996 <tr>
 997   <td align="center"><code>replace(it,x)</code></td>
 998   <td>replacement does not take place.</td>
 999 </tr>
1000 <tr class="odd_tr">
1001   <td align="center"><code>modify(it,mod)</code></td>
1002   <td>the element is erased.</td>
1003 </tr>
1004 <tr>
1005   <td align="center"><code>modify(it,mod,back)</code></td>
1006   <td><code>back</code> is used to restore the original conditions.
1007     (If <code>back</code> throws, the element is erased.)
1008   </td>
1009 </tr>
1010 </table>
1011 </p>
1012
1013
1014 <p>
1015 Key-based versions of <code>modify</code>, named
1016 <a href="../reference/ord_indices.html#modify_key"><code>modify_key</code></a>, are
1017 provided as well. In this case, the modifying functors are passed a reference to
1018 the <code>key_type</code> part of the element instead of the whole object.
1019 </p>
1020
1021 <blockquote><pre>
1022 <span class=keyword>struct</span> <span class=identifier>change_str</span>
1023 <span class=special>{</span>
1024   <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>&amp;</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>
1025
1026   <span class=comment>// note this is passed a string, not an employee</span>
1027   <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>&amp;</span> <span class=identifier>str</span><span class=special>)</span>
1028   <span class=special>{</span>
1029     <span class=identifier>str</span><span class=special>=</span><span class=identifier>new_str</span><span class=special>;</span>
1030   <span class=special>}</span>
1031
1032 <span class=keyword>private</span><span class=special>:</span>
1033   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>new_str</span><span class=special>;</span>
1034 <span class=special>};</span>
1035 <span class=special>...</span>
1036 <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
1037 <span class=identifier>employee_set_by_name</span><span class=special>&amp;</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>&lt;</span><span class=identifier>name</span><span class=special>&gt;();</span>
1038
1039 <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>&quot;Anna Jones&quot;</span><span class=special>);</span>
1040 <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>&quot;Anna Smith&quot;</span><span class=special>));</span>
1041 </pre></blockquote>
1042
1043 <p>
1044 Like <code>modify</code>, there are versions of <code>modify_key</code> with and
1045 without rollback. <code>modify</code> and
1046 <code>modify_key</code> are particularly well suited to use in conjunction to
1047 <a href="../../../../libs/lambda/index.html">Boost.Lambda</a>
1048 for defining the modifying functors:
1049 </p>
1050
1051 <blockquote><pre>
1052 <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>
1053
1054 <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
1055 <span class=identifier>employee_set_by_name</span><span class=special>&amp;</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>&lt;</span><span class=identifier>name</span><span class=special>&gt;();</span>
1056
1057 <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>&quot;Anna Jones&quot;</span><span class=special>);</span>
1058 <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>&quot;Anna Smith&quot;</span><span class=special>);</span>
1059 </pre></blockquote>
1060
1061 <p>
1062 <code>modify_key</code> requires that the key extractor be of
1063 a special type called
1064 <a href="key_extraction.html#read_write_key_extractors">read/write</a>:
1065 this is usually, but not always, the case.
1066 </p>
1067
1068 <h3>
1069 <a name="seq_indices">Sequenced indices</a>
1070 </h3>
1071
1072 <p>
1073 Unlike ordered indices, sequenced indices do not impose a fixed order on the
1074 elements: instead, these can be arranged in any position on the sequence, in the
1075 same way as <code>std::list</code> permits. The interface of sequenced indices
1076 is thus designed upon that of <code>std::list</code>; nearly every operation
1077 provided in the standard container is replicated here, occasionally with changes
1078 in the syntax and/or semantics to cope with the constraints imposed by
1079 Boost.MultiIndex. An important difference, commented <a href="#iterator_access">above</a>,
1080 is the fact that the values pointed to by sequenced index iterators are treated
1081 as <i>constant</i>:
1082 </p>
1083
1084 <blockquote><pre>
1085 <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
1086   <span class=keyword>int</span><span class=special>,</span>
1087   <span class=identifier>indexed_by</span><span class=special>&lt;</span><span class=identifier>sequenced</span><span class=special>&lt;&gt;</span> <span class=special>&gt;</span>
1088 <span class=special>&gt;</span> <span class=identifier>s</span><span class=special>;</span>            <span class=comment>// list-like container</span>
1089
1090 <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>
1091 <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>
1092 </pre></blockquote>
1093
1094 <p>
1095 As with any other type of index, element modification
1096 can nevertheless be done by means of
1097 <a href="#seq_updating">update operations</a>.
1098 </p>
1099
1100 <p>
1101 Consider a <code>multi_index_container</code> with two or more indices, one of them
1102 of sequenced type. If an element is inserted through another index,
1103 then it will be automatically appended to the end of the sequenced index.
1104 An example will help to clarify this:
1105 </p>
1106
1107 <blockquote><pre>
1108 <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
1109   <span class=keyword>int</span><span class=special>,</span>
1110   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
1111     <span class=identifier>sequenced</span><span class=special>&lt;&gt;,</span>           <span class=comment>// sequenced type</span>
1112     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=comment>// another index</span>
1113   <span class=special>&gt;</span>
1114 <span class=special>&gt;</span> <span class=identifier>s</span><span class=special>;</span>
1115
1116 <span class=identifier>s</span><span class=special>.</span><span class=identifier>get</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;().</span><span class=identifier>insert</span><span class=special>(</span><span class=number>1</span><span class=special>);</span> <span class=comment>// insert 1 through index #1</span>
1117 <span class=identifier>s</span><span class=special>.</span><span class=identifier>get</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;().</span><span class=identifier>insert</span><span class=special>(</span><span class=number>0</span><span class=special>);</span> <span class=comment>// insert 0 through index #1
1118
1119 // list elements through sequenced index #0</span>
1120 <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>&lt;</span><span class=keyword>int</span><span class=special>&gt;(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>));</span>
1121
1122 <span class=comment>// result: 1 0</span>
1123 </pre></blockquote>
1124
1125 <p>
1126 Thus the behavior of sequenced indices when insertions are not made through
1127 them is to preserve insertion order.
1128 </p>
1129
1130 <h4><a name="seq_spec">Specification</a></h4>
1131
1132 <p>
1133 Sequenced indices are specified with the <code>sequenced</code> construct:
1134 </p>
1135
1136 <blockquote><pre>
1137 <span class=identifier>sequenced</span><span class=special>&lt;[</span><i>(tag)</i><span class=special>]&gt;</span>
1138 </pre></blockquote>
1139
1140 <p>
1141 The <a href="#tagging">tag</a> parameter is optional.
1142 </p>
1143
1144 <h4><a name="list_ops">List operations</a></h4>
1145
1146 <p>
1147 As mentioned before, sequenced indices mimic the interface of
1148 <code>std::list</code>, and most of the original operations therein are
1149 provided as well. The semantics and complexity of these operations, however,
1150 do not always coincide with those of the standard container. Differences
1151 result mainly from the fact that insertions into a sequenced index are not
1152 guaranteed to succeed, due to the possible banning by other indices
1153 of the <code>multi_index_container</code>. Consult the
1154 <a href="../reference/seq_indices.html">reference</a> for further details.
1155 </p>
1156
1157 <h4><a name="seq_updating">Updating</a></h4>
1158
1159 <p>
1160 Like ordered indices, sequenced indices provide
1161 <a href="../reference/seq_indices.html#replace"><code>replace</code></a> and
1162 <a href="../reference/seq_indices.html#modify"><code>modify</code></a>
1163 operations, with identical functionality. There is however no analogous
1164 <code>modify_key</code>, since sequenced indices are not key-based.
1165 </p>
1166
1167 <h2><a name="projection">Projection of iterators</a></h2>
1168
1169 <p>
1170 Given indices <code>i1</code> and <code>i2</code> on the same <code>multi_index_container</code>,
1171 <a href="../reference/multi_index_container.html#projection"><code>project</code></a> can be used to
1172 retrieve an <code>i2</code>-iterator from an <code>i1</code>-iterator, both of them
1173 pointing to the same element of the container. This functionality allows the programmer to
1174 move between different indices of the same <code>multi_index_container</code> when performing
1175 elaborate operations:
1176 </p>
1177
1178 <blockquote><pre>
1179 <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special>&lt;</span><span class=identifier>name</span><span class=special>&gt;::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span>
1180 <span class=identifier>employee_set_by_name</span><span class=special>&amp;</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>&lt;</span><span class=identifier>name</span><span class=special>&gt;();</span>
1181
1182 <span class=comment>// list employees by ID starting from Robert Brown's ID</span>
1183
1184 <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>&quot;Robert Brown&quot;</span><span class=special>);</span>
1185
1186 <span class=comment>// obtain an iterator of index #0 from it1</span>
1187 <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>&lt;</span><span class=number>0</span><span class=special>&gt;(</span><span class=identifier>it1</span><span class=special>);</span>
1188
1189 <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>&lt;</span><span class=identifier>employee</span><span class=special>&gt;(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>));</span>
1190 </pre></blockquote>
1191
1192 <p>
1193 A slightly more interesting example:
1194 </p>
1195
1196 <blockquote><pre>
1197 <span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span>
1198
1199 <span class=comment>// get a view to index #1 (ordered index on the words)</span>
1200 <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;::</span><span class=identifier>type</span><span class=special>&amp;</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>&lt;</span><span class=number>1</span><span class=special>&gt;();</span>
1201
1202 <span class=comment>// prepend &quot;older&quot; to all occurrences of &quot;sister&quot;</span>
1203
1204 <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special>&lt;</span><span class=number>1</span><span class=special>&gt;::</span><span class=identifier>type</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span>
1205   <span class=identifier>sorted_index</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=string>&quot;sister&quot;</span><span class=special>);</span>
1206
1207 <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>()&amp;&amp;*</span><span class=identifier>it1</span><span class=special>==</span><span class=string>&quot;sister&quot;</span><span class=special>){</span>
1208   <span class=comment>// convert to an iterator to the sequenced index</span>
1209   <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>&lt;</span><span class=number>0</span><span class=special>&gt;(</span><span class=identifier>it1</span><span class=special>);</span>
1210
1211   <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>&quot;older&quot;</span><span class=special>);</span>
1212   <span class=special>++</span><span class=identifier>it1</span><span class=special>;</span>
1213 <span class=special>}</span>
1214 </pre></blockquote>
1215
1216 <p>
1217 When provided, <code>project</code> can also be used with
1218 <a href="#tagging">tags</a>.
1219 </p>
1220
1221 <h2><a name="complexity">Complexity and exception safety</a></h2>
1222
1223 <p>
1224 <code>multi_index_container</code> provides the same complexity and exception safety
1225 guarantees as the equivalent STL containers do. Iterator and reference validity
1226 is preserved in the face of insertions, even for replace and modify operations.
1227 </p>
1228
1229 <p>
1230 Appropriate instantiations of <code>multi_index_container</code> can in fact simulate
1231 <code>std::set</code>, <code>std::multiset</code> and (with more limitations)
1232 <code>std::list</code>, as shown in the
1233 <a href="techniques.html#emulate_std_containers">techniques</a>
1234 section. These simulations are as nearly as efficient as the original STL
1235 containers; consult the <a href="../reference/index.html">reference</a> for further
1236 information on complexity guarantees and the
1237 <a href="../performance.html">performance section</a> for practical measurements of
1238 efficiency.
1239 </p>
1240
1241 <hr>
1242
1243 <div class="prev_link"><a href="index.html"><img src="../prev.gif" alt="tutorial" border="0"><br>
1244 Boost.MultiIndex Tutorial
1245 </a></div>
1246 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
1247 Boost.MultiIndex tutorial
1248 </a></div>
1249 <div class="next_link"><a href="indices.html"><img src="../next.gif" alt="index types" border="0"><br>
1250 Index types
1251 </a></div><br clear="all" style="clear: all;">
1252
1253 <br>
1254
1255 <p>Revised November 24th 2015</p>
1256
1257 <p>&copy; Copyright 2003-2015 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
1258 Distributed under the Boost Software
1259 License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
1260 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
1261 http://www.boost.org/LICENSE_1_0.txt</a>)
1262 </p>
1263
1264 </body>
1265 </html>