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