Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/multi_index/doc/tutorial.html @ 13

Last change on this file since 13 was 12, checked in by landauf, 18 years ago

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