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