1 <!DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.0.1 Transitional//EN">
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=ISO-8859-1">
6 <title>Boost.MultiIndex Documentation - Tutorial - Basics
</title>
7 <link rel=
"stylesheet" href=
"../style.css" type=
"text/css">
8 <link rel=
"start" href=
"../index.html">
9 <link rel=
"prev" href=
"index.html">
10 <link rel=
"up" href=
"index.html">
11 <link rel=
"next" href=
"indices.html">
15 <h1><img src=
"../../../../boost.png" alt=
"boost.png (6897 bytes)" align=
16 "middle" width=
"277" height=
"86">Boost.MultiIndex Tutorial: Basics
</h1>
18 <div class=
"prev_link"><a href=
"index.html"><img src=
"../prev.gif" alt=
"Boost.MultiIndex tutorial" border=
"0"><br>
19 Boost.MultiIndex tutorial
21 <div class=
"up_link"><a href=
"index.html"><img src=
"../up.gif" alt=
"Boost.MultiIndex tutorial" border=
"0"><br>
22 Boost.MultiIndex tutorial
24 <div class=
"next_link"><a href=
"indices.html"><img src=
"../next.gif" alt=
"index types" border=
"0"><br>
26 </a></div><br clear=
"all" style=
"clear: all;">
33 <li><a href=
"#intro">Introduction
</a>
35 <li><a href=
"#multiple_sort">Multiple sorts on a single set
</a></li>
36 <li><a href=
"#list_fast_lookup">A bidirectional list with fast lookup
</a></li>
39 <li><a href=
"#index_spec">Index specification
</a></li>
40 <li><a href=
"#tagging">Tagging
</a></li>
41 <li><a href=
"#iterator_access">Iterator access
</a></li>
42 <li><a href=
"#index_types">Index types
</a>
44 <li><a href=
"#ord_indices">Ordered indices
</a>
46 <li><a href=
"#unique_non_unique">Unique and non-unique variants
</a></li>
47 <li><a href=
"#ord_spec">Specification
</a></li>
48 <li><a href=
"#key_extraction">Key extraction
</a></li>
49 <li><a href=
"#comparison_predicates">Comparison predicates
</a></li>
50 <li><a href=
"#special_lookup">Special lookup operations
</a></li>
51 <li><a href=
"#range">Retrieval of ranges
</a></li>
52 <li><a href=
"#ord_updating">Updating
</a></li>
55 <li><a href=
"#seq_indices">Sequenced indices
</a>
57 <li><a href=
"#seq_spec">Specification
</a></li>
58 <li><a href=
"#list_ops">List operations
</a></li>
59 <li><a href=
"#seq_updating">Updating
</a></li>
64 <li><a href=
"#projection">Projection of iterators
</a></li>
65 <li><a href=
"#complexity">Complexity and exception safety
</a></li>
68 <h2><a name=
"intro">Introduction
</a></h2>
71 We introduce the main concepts of Boost.MultiIndex through the study of
72 two typical use cases.
75 <h3><a name=
"multiple_sort">Multiple sorts on a single set
</a></h3>
78 STL sets and multisets are varying-length containers where elements are efficiently
79 sorted according to a given comparison predicate. These container classes fall short
80 of functionality when the programmer wishes to efficiently sort and look up the elements
81 following a different sorting criterion. Consider for instance:
85 <span class=keyword
>struct
</span> <span class=identifier
>employee
</span>
86 <span class=special
>{
</span>
87 <span class=keyword
>int
</span> <span class=identifier
>id
</span><span class=special
>;
</span>
88 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span> <span class=identifier
>name
</span><span class=special
>;
</span>
90 <span class=identifier
>employee
</span><span class=special
>(
</span><span class=keyword
>int
</span> <span class=identifier
>id
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</span> <span class=identifier
>name
</span><span class=special
>):
</span><span class=identifier
>id
</span><span class=special
>(
</span><span class=identifier
>id
</span><span class=special
>),
</span><span class=identifier
>name
</span><span class=special
>(
</span><span class=identifier
>name
</span><span class=special
>){}
</span>
92 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
><(
</span><span class=keyword
>const
</span> <span class=identifier
>employee
</span><span class=special
>&</span> <span class=identifier
>e
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>{
</span><span class=keyword
>return
</span> <span class=identifier
>id
</span><span class=special
><</span><span class=identifier
>e
</span><span class=special
>.
</span><span class=identifier
>id
</span><span class=special
>;}
</span>
93 <span class=special
>};
</span>
96 <p>The fact that IDs are unique to each employee is reflected by the way
97 <code>operator
<</code> is defined, so a natural data structure for storing of
98 <code>employee
</code>s is just a
<code>std::set
<employee
></code>. Now,
99 if one wishes to print out a listing of all employees in alphabetical order, available
100 solutions may have disadvantages either in terms of storage space, complexity or ease
103 <li>Copy the employee set into a vector or similar and sort this by a comparison
104 functor dependent upon
<code>employee::name
</code>.
105 <li>Keep a secondary data structure of pointers to the elements of the set, appropriately
108 Of these, probably the second solution will be the one adopted by most programmers
109 concerned about efficiency, but it imposes the annoying burden of keeping the two
110 structures in sync. If the code is additionally required to be exception-safe, this
111 construct easily becomes unmaintainable.
115 Boost.MultiIndex features
<a href=
"#ord_indices"><i>ordered indices
</i></a>, which
116 sort the elements according to a particular key, and are designed to help programmers
117 in need of sequences of elements for which
<i>more than one
</i> sorting criteria are
118 relevant. We do so by defining a
<code>multi_index_container
</code>
119 instantiation composed of several ordered indices: each index, viewed in isolation,
120 behaves much as an ordered
<code>std::set
</code> (or
<code>std::multiset
</code>), whilst
121 the overall integrity of the entire data structure is preserved. Our example problem
122 thus can be solved with Boost.MultiIndex as follows:
126 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>boost
</span><span class=special
>/
</span><span class=identifier
>multi_index_container
</span><span class=special
>.
</span><span class=identifier
>hpp
</span><span class=special
>></span>
127 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>boost
</span><span class=special
>/
</span><span class=identifier
>multi_index
</span><span class=special
>/
</span><span class=identifier
>ordered_index
</span><span class=special
>.
</span><span class=identifier
>hpp
</span><span class=special
>></span>
128 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>boost
</span><span class=special
>/
</span><span class=identifier
>multi_index
</span><span class=special
>/
</span><span class=identifier
>identity
</span><span class=special
>.
</span><span class=identifier
>hpp
</span><span class=special
>></span>
129 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>boost
</span><span class=special
>/
</span><span class=identifier
>multi_index
</span><span class=special
>/
</span><span class=identifier
>member
</span><span class=special
>.
</span><span class=identifier
>hpp
</span><span class=special
>></span>
131 <span class=comment
>// define a multiply indexed set with indices by id and name
</span>
132 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span>
133 <span class=identifier
>employee
</span><span class=special
>,
</span>
134 <span class=identifier
>indexed_by
</span><span class=special
><</span>
135 <span class=comment
>// sort by employee::operator
<</span>
136 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>></span> <span class=special
>>,
</span>
138 <span class=comment
>// sort by less
<string
> on name
</span>
139 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span><span class=identifier
>member
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>,
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
&</span><span class=identifier
>employee
</span><span class=special
>::
</span><span class=identifier
>name
</span><span class=special
>></span> <span class=special
>></span>
140 <span class=special
>></span>
141 <span class=special
>></span> <span class=identifier
>employee_set
</span><span class=special
>;
</span>
143 <span class=keyword
>void
</span> <span class=identifier
>print_out_by_name
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>employee_set
</span><span class=special
>&</span> <span class=identifier
>es
</span><span class=special
>)
</span>
144 <span class=special
>{
</span>
145 <span class=comment
>// get a view to index #
1 (name)
</span>
146 <span class=keyword
>const
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>nth_index
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>::
</span><span class=identifier
>type
</span><span class=special
>&</span> <span class=identifier
>name_index
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>();
</span>
147 <span class=comment
>// use name_index as a regular std::set
</span>
148 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>copy
</span><span class=special
>(
</span>
149 <span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>(),
</span><span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>(),
</span>
150 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>ostream_iterator
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>>(
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>cout
</span><span class=special
>));
</span>
151 <span class=special
>}
</span>
155 Instead of a single comparison predicate type, as it happens for STL associative
156 containers,
<code>multi_index_container
</code> is passed a
157 <a href=
"../reference/multi_index_container.html#multi_index_container">list
</a> of index
158 specifications (
<code>indexed_by
</code>), each one inducing the corresponding index.
159 Indices are accessed via
160 <a href=
"../reference/multi_index_container.html#index_retrieval"><code>get
</code></a><code><N
>()
</code>
161 where
<i>N
</i> ranges between
0 and the number of comparison
162 predicates minus one. The functionality of index #
0 can be accessed directly from a
163 <code>multi_index_container
</code> object without using
<code>get
<0>()
</code>: for instance,
164 <code>es.begin()
</code> is equivalent to
<code>es.get
<0>().begin()
</code>.
168 Note that
<code>get
</code> returns a
<i>reference
</i> to the index, and not
169 an index object. Indices cannot be constructed as separate objects from the
170 container they belong to, so the following
174 <span class=comment
>// Wrong: we forgot the
& after employee_set::nth_index
<1>::type
</span>
175 <span class=keyword
>const
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>nth_index
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>name_index
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>();
</span>
179 does not compile, since it is trying to construct the index object
180 <code>name_index
</code>. This is a common source of errors in user code.
183 <h3><a name=
"list_fast_lookup">A bidirectional list with fast lookup
</a></h3>
186 This study case allows us to introduce so-called
187 <a href=
"#seq_indices"><i>sequenced indices
</i></a>, and how they
188 interact with ordered indices to construct powerful containers. Suppose
189 we have a text parsed into words and stored in a list like this:
193 <span class=keyword
>typedef
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>list
</span><span class=special
><</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>></span> <span class=identifier
>text_container
</span><span class=special
>;
</span>
195 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span> <span class=identifier
>text
</span><span class=special
>=
</span>
196 <span class=string
>"Alice was beginning to get very tired of sitting by her sister on the
"</span>
197 <span class=string
>"bank, and of having nothing to do: once or twice she had peeped into the
"</span>
198 <span class=string
>"book her sister was reading, but it had no pictures or conversations in
"</span>
199 <span class=string
>"it, 'and what is the use of a book,' thought Alice 'without pictures or
"</span>
200 <span class=string
>"conversation?'
"</span><span class=special
>;
</span>
202 <span class=comment
>// feed the text into the list
</span>
203 <span class=identifier
>text_container
</span> <span class=identifier
>tc
</span><span class=special
>;
</span>
204 <span class=identifier
>boost
</span><span class=special
>::
</span><span class=identifier
>tokenizer
</span><span class=special
><</span><span class=identifier
>boost
</span><span class=special
>::
</span><span class=identifier
>char_separator
</span><span class=special
><</span><span class=keyword
>char
</span><span class=special
>></span> <span class=special
>></span> <span class=identifier
>tok
</span>
205 <span class=special
>(
</span><span class=identifier
>text
</span><span class=special
>,
</span><span class=identifier
>boost
</span><span class=special
>::
</span><span class=identifier
>char_separator
</span><span class=special
><</span><span class=keyword
>char
</span><span class=special
>>(
</span><span class=string
>" \t\n.,;:!?'\
"-
"</span><span class=special
>));
</span>
206 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>copy
</span><span class=special
>(
</span><span class=identifier
>tok
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>(),
</span><span class=identifier
>tok
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>(),
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>back_inserter
</span><span class=special
>(
</span><span class=identifier
>tc
</span><span class=special
>));
</span>
210 If we want to count the occurrences of a given word into the text we will resort
211 to
<code>std::count
</code>:
215 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>size_t
</span> <span class=identifier
>occurrences
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</span> <span class=identifier
>word
</span><span class=special
>)
</span>
216 <span class=special
>{
</span>
217 <span class=keyword
>return
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>count
</span><span class=special
>(
</span><span class=identifier
>tc
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>(),
</span><span class=identifier
>tc
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>(),
</span><span class=identifier
>word
</span><span class=special
>);
</span>
218 <span class=special
>}
</span>
222 But this implementation of
<code>occurrences
</code> performs in linear time, which
223 could be unacceptable for large quantities of text. Similarly, other operations like
224 deletion of selected words are just too costly to carry out on a
225 <code>std::list
</code>:
229 <span class=keyword
>void
</span> <span class=identifier
>delete_word
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</span> <span class=identifier
>word
</span><span class=special
>)
</span>
230 <span class=special
>{
</span>
231 <span class=identifier
>tc
</span><span class=special
>.
</span><span class=identifier
>remove
</span><span class=special
>(
</span><span class=identifier
>word
</span><span class=special
>);
</span> <span class=comment
>// scans the entire list looking for word
</span>
232 <span class=special
>}
</span>
236 When performance is a concern, we will need an additional data structure that indexes
237 the elements in
<code>tc
</code>, presumably in alphabetical order. Boost.MultiIndex
238 does precisely this through the combination of sequenced and ordered indices:
242 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>boost
</span><span class=special
>/
</span><span class=identifier
>multi_index_container
</span><span class=special
>.
</span><span class=identifier
>hpp
</span><span class=special
>></span>
243 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>boost
</span><span class=special
>/
</span><span class=identifier
>multi_index
</span><span class=special
>/
</span><span class=identifier
>sequenced_index
</span><span class=special
>.
</span><span class=identifier
>hpp
</span><span class=special
>></span>
244 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>boost
</span><span class=special
>/
</span><span class=identifier
>multi_index
</span><span class=special
>/
</span><span class=identifier
>ordered_index
</span><span class=special
>.
</span><span class=identifier
>hpp
</span><span class=special
>></span>
245 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>boost
</span><span class=special
>/
</span><span class=identifier
>multi_index
</span><span class=special
>/
</span><span class=identifier
>identity
</span><span class=special
>.
</span><span class=identifier
>hpp
</span><span class=special
>></span>
247 <span class=comment
>// define a multi_index_container with a list-like index and an ordered index
</span>
248 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span>
249 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
</span>
250 <span class=identifier
>indexed_by
</span><span class=special
><</span>
251 <span class=identifier
>sequenced
</span><span class=special
><>,
</span> <span class=comment
>// list-like index
</span>
252 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>></span> <span class=special
>></span> <span class=comment
>// words by alphabetical order
</span>
253 <span class=special
>></span>
254 <span class=special
>></span> <span class=identifier
>text_container
</span><span class=special
>;
</span>
256 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span> <span class=identifier
>text
</span><span class=special
>=...
</span>
258 <span class=comment
>// feed the text into the list
</span>
259 <span class=identifier
>text_container
</span> <span class=identifier
>tc
</span><span class=special
>;
</span>
260 <span class=identifier
>boost
</span><span class=special
>::
</span><span class=identifier
>tokenizer
</span><span class=special
><</span><span class=identifier
>boost
</span><span class=special
>::
</span><span class=identifier
>char_separator
</span><span class=special
><</span><span class=keyword
>char
</span><span class=special
>></span> <span class=special
>></span> <span class=identifier
>tok
</span>
261 <span class=special
>(
</span><span class=identifier
>text
</span><span class=special
>,
</span><span class=identifier
>boost
</span><span class=special
>::
</span><span class=identifier
>char_separator
</span><span class=special
><</span><span class=keyword
>char
</span><span class=special
>>(
</span><span class=string
>" \t\n.,;:!?'\
"-
"</span><span class=special
>));
</span>
262 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>copy
</span><span class=special
>(
</span><span class=identifier
>tok
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>(),
</span><span class=identifier
>tok
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>(),
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>back_inserter
</span><span class=special
>(
</span><span class=identifier
>tc
</span><span class=special
>));
</span>
266 So far, the substitution of
<code>multi_index_container
</code> for
<code>std::list
</code>
267 does not show any advantage. The code for inserting the text into the container
268 does not change as sequenced indices provide an interface similar to that of
269 <code>std::list
</code> (no explicit access to this index through
270 <code>get
<0>()
</code> is needed as
<code>multi_index_container
</code> inherits the
271 functionality of index #
0.) But the specification of an additional ordered index
272 allows us to implement
<code>occurrences
</code> and
<code>delete_word
</code>
273 in a much more efficient manner:
277 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>size_t
</span> <span class=identifier
>occurrences
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</span> <span class=identifier
>word
</span><span class=special
>)
</span>
278 <span class=special
>{
</span>
279 <span class=comment
>// get a view to index #
1</span>
280 <span class=identifier
>text_container
</span><span class=special
>::
</span><span class=identifier
>nth_index
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>::
</span><span class=identifier
>type
</span><span class=special
>&</span> <span class=identifier
>sorted_index
</span><span class=special
>=
</span><span class=identifier
>tc
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>();
</span>
282 <span class=comment
>// use sorted_index as a regular std::set
</span>
283 <span class=keyword
>return
</span> <span class=identifier
>sorted_index
</span><span class=special
>.
</span><span class=identifier
>count
</span><span class=special
>(
</span><span class=identifier
>word
</span><span class=special
>);
</span>
284 <span class=special
>}
</span>
286 <span class=keyword
>void
</span> <span class=identifier
>delete_word
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</span> <span class=identifier
>word
</span><span class=special
>)
</span>
287 <span class=special
>{
</span>
288 <span class=comment
>// get a view to index #
1</span>
289 <span class=identifier
>text_container
</span><span class=special
>::
</span><span class=identifier
>nth_index
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>::
</span><span class=identifier
>type
</span><span class=special
>&</span> <span class=identifier
>sorted_index
</span><span class=special
>=
</span><span class=identifier
>tc
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>();
</span>
291 <span class=comment
>// use sorted_index as a regular std::set
</span>
292 <span class=identifier
>sorted_index
</span><span class=special
>.
</span><span class=identifier
>erase
</span><span class=special
>(
</span><span class=identifier
>word
</span><span class=special
>);
</span>
293 <span class=special
>}
</span>
297 Now,
<code>occurrences
</code> and
<code>delete_word
</code> have logarithmic
298 complexity. The programmer can use index #
0 for accessing the text as with
299 <code>std::list
</code>, and use index #
1 when logarithmic lookup is needed.
303 <a name=
"index_spec">Index specification
</a>
307 The indices of a
<code>multi_index_container
</code> instantiation are specified by
308 means of the
<a href=
"../reference/indices.html#indexed_by">
309 <code>indexed_by
</code></a> construct. For instance, the instantiation
313 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span>
314 <span class=identifier
>employee
</span><span class=special
>,
</span>
315 <span class=identifier
>indexed_by
</span><span class=special
><</span>
316 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>></span> <span class=special
>>,
</span>
317 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span><span class=identifier
>member
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>,
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
&</span><span class=identifier
>employee
</span><span class=special
>::
</span><span class=identifier
>name
</span><span class=special
>></span> <span class=special
>></span>
318 <span class=special
>></span>
319 <span class=special
>></span> <span class=identifier
>employee_set
</span><span class=special
>;
</span>
323 is comprised of a
<a href=
"#unique_non_unique">unique ordered index
</a> and a
324 <a href=
"#unique_non_unique">non-unique ordered index
</a>, while in
328 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span>
329 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
</span>
330 <span class=identifier
>indexed_by
</span><span class=special
><</span>
331 <span class=identifier
>sequenced
</span><span class=special
><>,
</span>
332 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>></span> <span class=special
>></span>
333 <span class=special
>></span>
334 <span class=special
>></span> <span class=identifier
>text_container
</span><span class=special
>;
</span>
338 we specifiy two indices, the first of
<a href=
"#seq_indices">sequenced type
</a>,
339 the second a non-unique
<a href=
"#ord_indices">ordered index
</a>. In general, we
340 can specify an arbitrary number of indices: each of the arguments of
341 <code>indexed_by
</code> is called an
342 <a href=
"../reference/indices.html#index_specification"><i>index specifier
</i></a>.
343 Depending on the type of index being specified, the corresponding specifier
344 will need additional information: for instance, the specifiers
<code>ordered_unique
</code>
345 and
<code>ordered_non_unique
</code> are provided with a
346 <a href=
"#key_extraction">key extractor
</a> and an optional
347 <a href=
"#comparison_predicates">comparison predicate
</a> which jointly indicate
348 how the sorting of elements will be performed.
352 A
<code>multi_index_container
</code> instantiation can be declared without supplying
353 the
<code>indexed_by
</code> part: in this case, default index values are taken
354 so that the resulting type is equivalent to a regular
<code>std::set
</code>.
355 Concretely, the instantiation
359 <span class=identifier
>multi_index_container
</span><span class=special
><</span><i>(element)
</i><span class=special
>></span>
367 <span class=identifier
>multi_index_container
</span><span class=special
><</span>
368 <i>(element)
</i><span class=special
>,
</span>
369 <span class=identifier
>indexed_by
</span><span class=special
><</span>
370 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><(
</span><span class=identifier
>element
</span><span class=special
>)
></span> <span class=special
>></span>
371 <span class=special
>></span>
372 <span class=special
>></span>
375 <h2><a name=
"tagging">Tagging
</a></h2>
378 In order to retrieve (a reference to) an index of a given
<code>multi_index_container
</code>,
379 the programmer must provide its order number, which is cumbersome and not very
380 self-descriptive. Optionally, indices can be assigned
<i>tags
</i> (C++ types) that
381 act as more convenient mnemonics. If provided, tags must be passed as the
382 first parameter of the corresponding index specifier. The following is a revised version of
383 <code>employee_set
</code> with inclusion of tags:
387 <span class=comment
>// tags
</span>
388 <span class=keyword
>struct
</span> <span class=identifier
>name
</span><span class=special
>{};
</span>
390 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span>
391 <span class=identifier
>employee
</span><span class=special
>,
</span>
392 <span class=identifier
>indexed_by
</span><span class=special
><</span>
393 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>></span> <span class=special
>>,
</span>
394 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span><span class=identifier
>tag
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>,
</span><span class=identifier
>member
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>,
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
&</span><span class=identifier
>employee
</span><span class=special
>::
</span><span class=identifier
>name
</span><span class=special
>></span> <span class=special
>></span>
395 <span class=special
>></span>
396 <span class=special
>></span> <span class=identifier
>employee_set
</span><span class=special
>;
</span>
400 Tags have to be passed inside the
<a href=
"../reference/indices.html#tag"><code>tag
</code></a>
401 construct. Any type can be used as a tag for an index, although in general one will choose
402 names that are descriptive of the index they are associated with. The tagging mechanism allows
403 us to write expressions like
</p>
406 <span class=keyword
>typedef
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>index
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>employee_set_by_name
</span><span class=special
>;
</span>
407 <span class=identifier
>employee_set_by_name
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>().
</span><span class=identifier
>begin
</span><span class=special
>();
</span>
411 If no tag is provided for an index (as is the case for index #
0 of the previous
412 example), access to that index can only be performed by number. Note the existence
413 of two different
<code>typedef
</code>s
<code>nth_index
</code> and
414 <code>index
</code> for referring to an index by number and by tag, respectively;
417 <li><code>employee_set::nth_index
<1>::type
</code> is the type of
419 <li><code>employee_set::index
<name
>::type
</code> is the type of the index
420 tagged with
<code>name
</code> (the same index #
1 in this case.)
</li>
422 <code>get()
</code>, on the other hand, is overloaded to serve both styles of access:
426 <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>index
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>::
</span><span class=identifier
>type
</span><span class=special
>&</span> <span class=identifier
>name_index
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>();
</span>
427 <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>nth_index
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>::
</span><span class=identifier
>type
</span><span class=special
>&</span> <span class=identifier
>name_index2
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>();
</span> <span class=comment
>// same index
</span>
431 Additionally, the
<code>tag
</code> class template accepts several tags for one
432 index, that we can use interchangeably: for instance, the specification of index #
1
433 in the previous example can be rewritten to hold two different tags
434 <code>name
</code> and
<code>by_name
</code>:
438 <span class=comment
>// tags
</span>
439 <span class=keyword
>struct
</span> <span class=identifier
>name
</span><span class=special
>{};
</span>
440 <span class=keyword
>struct
</span> <span class=identifier
>by_name
</span><span class=special
>{};
</span>
442 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span>
443 <span class=special
>...
</span>
444 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span>
445 <span class=identifier
>tag
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>,
</span><span class=identifier
>by_name
</span><span class=special
>>,
</span>
446 <span class=identifier
>member
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>,
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
&</span><span class=identifier
>employee
</span><span class=special
>::
</span><span class=identifier
>name
</span><span class=special
>></span>
447 <span class=special
>></span>
448 <span class=special
>...
</span>
449 <span class=special
>></span> <span class=identifier
>employee_set
</span><span class=special
>;
</span>
452 <h2><a name=
"iterator_access">Iterator access
</a></h2>
455 Each index of a
<code>multi_index_container
</code> uses its own
456 iterator types, which are different from those of another indices. As is
457 the rule with STL containers, these iterators are defined as nested
462 <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>nth_index
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>::
</span><span class=identifier
>type
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it
</span><span class=special
>=
</span>
463 <span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>().
</span><span class=identifier
>find
</span><span class=special
>(
</span><span class=string
>"Judy Smith
"</span><span class=special
>);
</span>
467 This kind of expressions can be rendered more readable by
468 means of user-defined
<code>typedef
</code>s:
472 <span class=keyword
>typedef
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>nth_index
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>employee_set_by_name
</span><span class=special
>;
</span>
473 <span class=identifier
>employee_set_by_name
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it
</span><span class=special
>=
</span>
474 <span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>().
</span><span class=identifier
>find
</span><span class=special
>(
</span><span class=string
>"Judy Smith
"</span><span class=special
>);
</span>
478 The iterators provided by every index are
<i>constant
</i>, that is, the elements they point to
479 cannot be mutated directly. This follows the interface of
<code>std::set
</code> for ordered
480 indices but might come as a surprise for other types such as sequenced indices, which are modeled after
481 <code>std::list
</code>, where this limitation does not happen. This seemingly odd behavior
482 is imposed by the way
<code>multi_index_container
</code>s work; if elements were
483 allowed to be mutated indiscriminately, we could introduce inconsistencies
484 in the ordered indices of the
<code>multi_index_container
</code> without the container
485 being notified about it. Element modification is properly done by means of
486 <a href=
"#ord_updating">update operations
</a> on any index.
490 <a name=
"index_types">Index types
</a>
494 Currently, Boost.MultiIndex provides the following index types:
496 <li>Ordered indices sort the elements like
<code>std::set
</code>s do and
497 provide a similar interface. There are
<i>unique
</i> and
<i>non-unique
</i>
498 variants: the former do not allow for duplicates, while the latter permit
499 them (like
<code>std::multiset
</code>.)
</li>
500 <li>Ranked indices are a variation of ordered indices providing extra capabilities
501 for querying and accessing elements based on their
<i>rank
</i> (the numerical position
502 they occupy in the index).
504 <li>Sequenced indices are modeled after the semantics and interface of
505 <code>std::list
</code>: they arrange the elements as if in a bidirectional
507 <li>Hashed indices provide fast access to the elements through hashing
508 techniques, in a similar way as non-standard
<code>hash_set
</code>s provided
509 by some vendors. Recently,
<i>unordered associative containers
</i> have been
510 proposed as part of an extension of the C++ standard library known
511 in the standardization commitee as TR1. Hashed indices closely model this
513 <li>Random access indices provide an interface similar to that of
514 sequenced indices, and additionally feature random access iterators
515 and positional access to the elements.
</li>
517 The examples in the
<a href=
"#intro">introduction
</a> exercise ordered and sequenced
518 indices, which are the most commonly used; the other kinds of indices are presented
519 in the
<a href=
"indices.html">index types
</a> section of the tutorial.
523 <a name=
"ord_indices">Ordered indices
</a>
527 Ordered indices sort the elements in a
<code>multi_index_container
</code> according
528 to a specified key and an associated comparison predicate. These indices can
529 be viewed as analogues of the standard container
<code>std::set
</code>, and in fact
530 they do replicate its interface, albeit with some minor differences dictated
531 by the general constraints of Boost.MultiIndex.
535 <a name=
"unique_non_unique">Unique and non-unique variants
</a>
539 Ordered indices are classified into
<i>unique
</i>, which prohibit two
540 elements to have the same key value, and
<i>non-unique
</i> indices,
541 which allow for duplicates. Consider again the definition
545 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span>
546 <span class=identifier
>employee
</span><span class=special
>,
</span>
547 <span class=identifier
>indexed_by
</span><span class=special
><</span>
548 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>></span> <span class=special
>>,
</span>
549 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span><span class=identifier
>member
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>,
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
&</span><span class=identifier
>employee
</span><span class=special
>::
</span><span class=identifier
>name
</span><span class=special
>></span> <span class=special
>></span>
550 <span class=special
>></span>
551 <span class=special
>></span> <span class=identifier
>employee_set
</span><span class=special
>;
</span>
555 In this instantiation of
<code>multi_index_container
</code>, the first index is to be
556 treated as unique (since IDs are exclusive to each employee) and thus is declared using
557 <code>ordered_unique
</code>, whereas the second index is non-unique (as the possibility exists
558 that say two John Smiths are hired in the same company), which is specified by the use
559 of
<code>ordered_non_unique
</code>.
563 The classification of ordered indices in unique and non-unique has an impact on which
564 elements are allowed to be inserted into a given
<code>multi_index_container
</code>; briefly put,
565 unique ordered indices mimic the behavior of
<code>std::set
</code>s while non-unique
566 ordered indices are similar to
<code>std::multiset
</code>s. For instance, an
567 <code>employee_set
</code> can hold the objects
<code>employee(
0,
"George Brown")
</code>
568 and
<code>employee(
1,
"George Brown")
</code>, but will not accept the insertion of an
569 <code>employee
</code> object whose ID coincides with that of some previously inserted
574 More than one unique index can be specified. For instance, if we augment
575 <code>employee
</code> to include an additional member for the Social Security number,
576 which is reasonably treated as unique, the following captures this design:
580 <span class=keyword
>struct
</span> <span class=identifier
>employee
</span>
581 <span class=special
>{
</span>
582 <span class=keyword
>int
</span> <span class=identifier
>id
</span><span class=special
>;
</span>
583 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span> <span class=identifier
>name
</span><span class=special
>;
</span>
584 <span class=keyword
>int
</span> <span class=identifier
>ssnumber
</span><span class=special
>;
</span>
586 <span class=identifier
>employee
</span><span class=special
>(
</span><span class=keyword
>int
</span> <span class=identifier
>id
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</span> <span class=identifier
>name
</span><span class=special
>,
</span><span class=keyword
>int
</span> <span class=identifier
>ssnumber
</span><span class=special
>):
</span>
587 <span class=identifier
>id
</span><span class=special
>(
</span><span class=identifier
>id
</span><span class=special
>),
</span><span class=identifier
>name
</span><span class=special
>(
</span><span class=identifier
>name
</span><span class=special
>),
</span><span class=identifier
>ssnumber
</span><span class=special
>(
</span><span class=identifier
>ssnumber
</span><span class=special
>){}
</span>
589 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
><(
</span><span class=keyword
>const
</span> <span class=identifier
>employee
</span><span class=special
>&</span> <span class=identifier
>e
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>{
</span><span class=keyword
>return
</span> <span class=identifier
>id
</span><span class=special
><</span><span class=identifier
>e
</span><span class=special
>.
</span><span class=identifier
>id
</span><span class=special
>;}
</span>
590 <span class=special
>};
</span>
592 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span>
593 <span class=identifier
>employee
</span><span class=special
>,
</span>
594 <span class=identifier
>indexed_by
</span><span class=special
><</span>
595 <span class=comment
>// sort by employee::operator
<</span>
596 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>></span> <span class=special
>>,
</span>
598 <span class=comment
>// sort by less
<string
> on name
</span>
599 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span><span class=identifier
>member
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>,
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
&</span><span class=identifier
>employee
</span><span class=special
>::
</span><span class=identifier
>name
</span><span class=special
>></span> <span class=special
>>,
</span>
601 <span class=comment
>// sort by less
<int
> on ssnumber
</span>
602 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>member
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>,
</span><span class=keyword
>int
</span><span class=special
>,
&</span><span class=identifier
>employee
</span><span class=special
>::
</span><span class=identifier
>ssnumber
</span><span class=special
>></span> <span class=special
>></span>
603 <span class=special
>></span>
604 <span class=special
>></span> <span class=identifier
>employee_set
</span><span class=special
>;
</span>
608 <a name=
"ord_spec">Specification
</a>
612 Ordered index specifiers in
<code>indexed_by
</code> must conform to one of the
617 <span class=special
>(
</span><span class=identifier
>ordered_unique
</span> <span class=special
>|
</span> <span class=identifier
>ordered_non_unique
</span><span class=special
>)
618 </span><span class=special
><[
</span><i>(tag)
</i><span class=special
>[,
</span><i>(key extractor)
</i><span class=special
>[,
</span><i>(comparison predicate)
</i><span class=special
>]]]
></span>
620 <span class=special
>(
</span><span class=identifier
>ordered_unique
</span> <span class=special
>|
</span> <span class=identifier
>ordered_non_unique
</span><span class=special
>)
</span>
621 <span class=special
><[
</span><i>(key extractor)
</i><span class=special
>[,
</span><i>(comparison predicate)
</i><span class=special
>]]
></span>
625 The first optional argument is used if
<a href=
"#tagging">tags
</a> are associated
626 with the index. We now proceed to briefly discuss the remaining arguments
627 of an ordered index specifier.
631 <a name=
"key_extraction">Key extraction
</a>
635 The first template parameter (or the second, if tags are supplied)
636 in the specification of an ordered index provides a
<i>key extraction
</i> predicate.
637 This predicate takes a whole element (in our example, a reference to an
638 <code>employee
</code> object) and returns the piece of information by which
639 the sorting is performed. In most cases, one of the following two situations arises:
641 <li>The whole element serves as the key, as is the case of the first index
642 in
<code>employee_set
</code>. The predefined
643 <a href=
"key_extraction.html#identity"><code>identity
</code></a> predicate
644 can be used here as a key extractor;
<code>identity
</code> returns as the key the
645 same object passed as argument.
</li>
646 <li>The comparison is performed on a particular data member of the element; this
647 closely follows the specification of indices on a column of a table in relational
648 databases. Boost.MultiIndex provides
649 <a href=
"key_extraction.html#member"><code>member
</code></a>, which returns
650 as the key a member of the element specified by a given pointer.
</li>
652 As an example, consider again the definition of
<code>employee_set
</code>. The
653 definition of the first index:
657 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>></span> <span class=special
>></span>
661 specifies by means of
<code>identity
</code> that
<code>element
</code>
662 objects themselves serve as key for this index. On the other hand, in the second
667 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span><span class=identifier
>member
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>,
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
&</span><span class=identifier
>employee
</span><span class=special
>::
</span><span class=identifier
>name
</span><span class=special
>></span> <span class=special
>></span>
671 we use
<code>member
</code> to extract the
<code>name
</code> part of the
672 <code>employee
</code> object. The key type of this index is then
673 <code>std::string
</code>.
677 Apart from
<code>identity
</code> and
<code>member
</code>, Boost.MultiIndex provides
678 several other predefined key extractors and powerful ways to combine them.
679 Key extractors can also be defined by the user.
680 Consult the
<a href=
"key_extraction.html">key extraction section
</a> of
681 the tutorial for a more detailed exposition of this topic.
684 <h4><a name=
"comparison_predicates">Comparison predicates
</a></h4>
687 The last part of the specification of an ordered index is the associated
688 <i>comparison predicate
</i>, which must order the keys in a less-than fashion.
689 These comparison predicates are not different from those used by STL containers like
690 <code>std::set
</code>. By default (i.e. if no comparison predicate is provided),
691 an index with keys of type
<code>key_type
</code> sorts the elements by
692 <code>std::less
<key_type
></code>. Should other comparison criteria be needed,
693 they can be specified as an additional parameter in the index declaration:
697 <span class=comment
>// define a multiply indexed set with indices by id and by name
698 // in reverse alphabetical order
</span>
699 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span>
700 <span class=identifier
>employee
</span><span class=special
>,
</span>
701 <span class=identifier
>indexed_by
</span><span class=special
><</span>
702 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>></span> <span class=special
>>,
</span> <span class=comment
>// as usual
</span>
703 <span class=identifier
>ordered_non_unique
</span><span class=special
><</span>
704 <span class=identifier
>member
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>,
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>,
&</span><span class=identifier
>employee
</span><span class=special
>::
</span><span class=identifier
>name
</span><span class=special
>>,
</span>
705 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>greater
</span><span class=special
><</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>></span> <span class=comment
>// default would be std::less
<std::string
></span>
706 <span class=special
>></span>
707 <span class=special
>></span>
708 <span class=special
>></span> <span class=identifier
>employee_set
</span><span class=special
>;
</span>
711 <h4><a name=
"special_lookup">Special lookup operations
</a></h4>
714 A given ordered index allows for lookup based on its key type, rather than the
715 whole element. For instance, to find Veronica Cruz in an
716 <code>employee_set
</code> one would write:
720 <span class=identifier
>employee_set
</span> <span class=identifier
>es
</span><span class=special
>;
</span>
721 <span class=special
>...
</span>
722 <span class=keyword
>typedef
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>index
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>employee_set_by_name
</span><span class=special
>;
</span>
723 <span class=identifier
>employee_set_by_name
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>().
</span><span class=identifier
>find
</span><span class=special
>(
</span><span class=string
>"Veronica Cruz
"</span><span class=special
>);
</span>
726 <p>As a plus, Boost.MultiIndex provides lookup operations accepting search keys
727 different from the
<code>key_type
</code> of the index, which is a specially useful
728 facility when
<code>key_type
</code> objects are expensive to create. Ordered STL containers
729 fail to provide this functionality, which often leads to inelegant workarounds: consider for
730 instance the problem of determining the employees whose IDs fall in the range [
0,
100]. Given
731 that the key of
<code>employee_set
</code> index #
0
732 is
<code>employee
</code> itself, on a first approach one would write the following:
736 <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>p0
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>lower_bound
</span><span class=special
>(
</span><span class=identifier
>employee
</span><span class=special
>(
</span><span class=number
>0</span><span class=special
>,
</span><span class=string
>""</span><span class=special
>));
</span>
737 <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>p1
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>upper_bound
</span><span class=special
>(
</span><span class=identifier
>employee
</span><span class=special
>(
</span><span class=number
>100</span><span class=special
>,
</span><span class=string
>""</span><span class=special
>));
</span>
741 Note however that
<code>std::less
<employee
></code> actually only depends
742 on the IDs of the employees, so it would be more convenient to avoid
743 the creation of entire
<code>employee
</code> objects just for the sake of
744 their IDs. Boost.MultiIndex allows for this: define an appropriate
749 <span class=keyword
>struct
</span> <span class=identifier
>comp_id
</span>
750 <span class=special
>{
</span>
751 <span class=comment
>// compare an ID and an employee
</span>
752 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>()(
</span><span class=keyword
>int
</span> <span class=identifier
>x
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>employee
</span><span class=special
>&</span> <span class=identifier
>e2
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>{
</span><span class=keyword
>return
</span> <span class=identifier
>x
</span><span class=special
><</span><span class=identifier
>e2
</span><span class=special
>.
</span><span class=identifier
>id
</span><span class=special
>;}
</span>
754 <span class=comment
>// compare an employee and an ID
</span>
755 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>()(
</span><span class=keyword
>const
</span> <span class=identifier
>employee
</span><span class=special
>&</span> <span class=identifier
>e1
</span><span class=special
>,
</span><span class=keyword
>int
</span> <span class=identifier
>x
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>{
</span><span class=keyword
>return
</span> <span class=identifier
>e1
</span><span class=special
>.
</span><span class=identifier
>id
</span><span class=special
><</span><span class=identifier
>x
</span><span class=special
>;}
</span>
756 <span class=special
>};
</span>
759 <p>and now write the search as
</p>
762 <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>p0
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>lower_bound
</span><span class=special
>(
</span><span class=number
>0</span><span class=special
>,
</span><span class=identifier
>comp_id
</span><span class=special
>());
</span>
763 <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>p1
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>upper_bound
</span><span class=special
>(
</span><span class=number
>100</span><span class=special
>,
</span><span class=identifier
>comp_id
</span><span class=special
>());
</span>
767 Here we are not only passing IDs instead of
<code>employee
</code> objects:
768 an alternative comparison predicate is passed as well. In general, lookup operations
769 of ordered indices are overloaded to accept
770 <a href=
"../reference/ord_indices.html#set_operations"><i>compatible sorting
771 criteria
</i></a>. The somewhat cumbersone definition of compatibility in this context
772 is given in the reference, but roughly speaking we say that a comparison predicate
773 <code>C1
</code> is compatible with
<code>C2
</code> if any sequence sorted by
774 <code>C2
</code> is also sorted with respect to
<code>C1
</code>.
775 The following shows a more interesting use of compatible predicates:
779 <span class=comment
>// sorting by name's initial
</span>
780 <span class=keyword
>struct
</span> <span class=identifier
>comp_initial
</span>
781 <span class=special
>{
</span>
782 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>()(
</span><span class=keyword
>char
</span> <span class=identifier
>ch
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</span> <span class=identifier
>s
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>{
</span>
783 <span class=keyword
>if
</span><span class=special
>(
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>empty
</span><span class=special
>())
</span><span class=keyword
>return
</span> <span class=keyword
>false
</span><span class=special
>;
</span>
784 <span class=keyword
>return
</span> <span class=identifier
>ch
</span><span class=special
><</span><span class=identifier
>s
</span><span class=special
>[
</span><span class=number
>0</span><span class=special
>];
</span>
785 <span class=special
>}
</span>
787 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>()(
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</span> <span class=identifier
>s
</span><span class=special
>,
</span><span class=keyword
>char
</span> <span class=identifier
>ch
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>{
</span>
788 <span class=keyword
>if
</span><span class=special
>(
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>empty
</span><span class=special
>())
</span><span class=keyword
>return
</span> <span class=keyword
>true
</span><span class=special
>;
</span>
789 <span class=keyword
>return
</span> <span class=identifier
>s
</span><span class=special
>[
</span><span class=number
>0</span><span class=special
>]
<</span><span class=identifier
>ch
</span><span class=special
>;
</span>
790 <span class=special
>}
</span>
791 <span class=special
>};
</span>
793 <span class=comment
>// obtain first employee whose name begins with 'J' (ordered by name)
</span>
794 <span class=keyword
>typedef
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>index
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>employee_set_by_name
</span><span class=special
>;
</span>
795 <span class=identifier
>employee_set_by_name
</span><span class=special
>&</span> <span class=identifier
>name_index
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>();
</span>
796 <span class=identifier
>employee_set_by_name
</span><span class=special
>::
</span><span class=identifier
>const_iterator
</span> <span class=identifier
>it
</span><span class=special
>=
</span>
797 <span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>lower_bound
</span><span class=special
>(
</span><span class=literal
>'J'
</span><span class=special
>,
</span><span class=identifier
>comp_initial
</span><span class=special
>());
</span>
800 <h4><a name=
"range">Retrieval of ranges
</a></h4>
803 Range searching, i.e. the lookup of all elements in a given interval, is a very
804 frequent operation for which standard
<code>lower_bound
</code> and
805 <code>upper_bound
</code> can be resorted to, though in a cumbersome manner.
806 For instance, the following code retrieves the elements of an
807 <code>multi_index_container
<double
></code> in the interval [
100,
200]:
811 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span><span class=keyword
>double
</span><span class=special
>></span> <span class=identifier
>double_set
</span><span class=special
>;
</span>
812 <span class=comment
>// note: default template parameters resolve to
813 // multi_index_container
<double,indexed_by
<unique
<identity
<double
> > > >.
</span>
815 <span class=identifier
>double_set
</span> <span class=identifier
>s
</span><span class=special
>;
</span>
816 <span class=special
>...
</span>
817 <span class=identifier
>double_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it0
</span><span class=special
>=
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>lower_bound
</span><span class=special
>(
</span><span class=number
>100.0</span><span class=special
>);
</span>
818 <span class=identifier
>double_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it1
</span><span class=special
>=
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>upper_bound
</span><span class=special
>(
</span><span class=number
>200.0</span><span class=special
>);
</span>
819 <span class=comment
>// range [it0,it1) contains the elements in [
100,
200]
</span>
823 Subtle changes to the code are required when strict inequalities are considered.
824 To retrieve the elements
<i>greater
</i> than
100 and
<i>less
</i> than
200, the
825 code has to be rewritten as
829 <span class=identifier
>double_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it0
</span><span class=special
>=
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>upper_bound
</span><span class=special
>(
</span><span class=number
>100.0</span><span class=special
>);
</span>
830 <span class=identifier
>double_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it1
</span><span class=special
>=
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>lower_bound
</span><span class=special
>(
</span><span class=number
>200.0</span><span class=special
>);
</span>
831 <span class=comment
>// range [it0,it1) contains the elements in (
100,
200)
</span>
835 To add to this complexity, the careful programmer has to take into account
836 that the lower and upper bounds of the interval searched be compatible: for
837 instance, if the lower bound is
200 and the upper bound is
100, the iterators
838 <code>it0
</code> and
<code>it1
</code> produced by the code above will be in reverse
839 order, with possibly catastrophic results if a traversal from
<code>it0
</code>
840 to
<code>it1
</code> is tried. All these details make range searching a tedious
841 and error prone task.
845 The
<a href=
"../reference/ord_indices.html#range_operations"><code>range
</code></a>
846 member function, often in combination with
847 <a href=
"../../../../libs/lambda/index.html">Boost.Lambda
</a> expressions, can
848 greatly help alleviate this situation:
852 <span class=keyword
>using
</span> <span class=keyword
>namespace
</span> <span class=identifier
>boost
</span><span class=special
>::
</span><span class=identifier
>lambda
</span><span class=special
>;
</span>
854 <span class=keyword
>typedef
</span> <span class=identifier
>multi_index_container
</span><span class=special
><</span><span class=keyword
>double
</span><span class=special
>></span> <span class=identifier
>double_set
</span><span class=special
>;
</span>
855 <span class=identifier
>double_set
</span> <span class=identifier
>s
</span><span class=special
>;
</span>
856 <span class=special
>...
</span>
857 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>double_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span><span class=special
>,
</span><span class=identifier
>double_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span><span class=special
>></span> <span class=identifier
>p
</span><span class=special
>=
</span>
858 <span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>range
</span><span class=special
>(
</span><span class=number
>100.0</span><span class=special
><=
</span><span class=identifier
>_1
</span><span class=special
>,
</span><span class=identifier
>_1
</span><span class=special
><=
</span><span class=number
>200</span><span class=special
>);
</span> <span class=comment
>//
100<= x
<=
200</span>
859 <span class=special
>...
</span>
860 <span class=identifier
>p
</span><span class=special
>=
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>range
</span><span class=special
>(
</span><span class=number
>100.0</span><span class=special
><</span><span class=identifier
>_1
</span><span class=special
>,
</span><span class=identifier
>_1
</span><span class=special
><</span><span class=number
>200</span><span class=special
>);
</span> <span class=comment
>//
100< x
< 200</span>
861 <span class=special
>...
</span>
862 <span class=identifier
>p
</span><span class=special
>=
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>range
</span><span class=special
>(
</span><span class=number
>100.0</span><span class=special
><=
</span><span class=identifier
>_1
</span><span class=special
>,
</span><span class=identifier
>_1
</span><span class=special
><</span><span class=number
>200</span><span class=special
>);
</span> <span class=comment
>//
100<= x
< 200</span>
866 <code>range
</code> simply accepts predicates specifying the lower and upper bounds
867 of the interval searched. Please consult the reference for a detailed explanation
868 of the permissible predicates passed to
<code>range
</code>.
</p>
871 One or both bounds can be omitted with the special
<code>unbounded
</code> marker:
875 <span class=identifier
>p
</span><span class=special
>=
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>range
</span><span class=special
>(
</span><span class=number
>100.0</span><span class=special
><=
</span><span class=identifier
>_1
</span><span class=special
>,
</span><span class=identifier
>unbounded
</span><span class=special
>);
</span> <span class=comment
>//
100 <= x
</span>
876 <span class=identifier
>p
</span><span class=special
>=
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>range
</span><span class=special
>(
</span><span class=identifier
>unbounded
</span><span class=special
>,
</span><span class=identifier
>_1
</span><span class=special
><</span><span class=number
>200.0</span><span class=special
>);
</span> <span class=comment
>// x
< 200</span>
877 <span class=identifier
>p
</span><span class=special
>=
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>range
</span><span class=special
>(
</span><span class=identifier
>unbounded
</span><span class=special
>,
</span><span class=identifier
>unbounded
</span><span class=special
>);
</span> <span class=comment
>// equiv. to std::make_pair(s.begin(),s.end())
</span>
880 <h4><a name=
"ord_updating">Updating
</a></h4>
883 The
<a href=
"../reference/ord_indices.html#replace"><code>replace
</code></a> member function
884 performs in-place replacement of a given element as the following example shows:
888 <span class=keyword
>typedef
</span> <span class=identifier
>index
</span><span class=special
><</span><span class=identifier
>employee_set
</span><span class=special
>,
</span><span class=identifier
>name
</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>employee_set_by_name
</span><span class=special
>;
</span>
889 <span class=identifier
>employee_set_by_name
</span><span class=special
>&</span> <span class=identifier
>name_index
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>();
</span>
891 <span class=identifier
>employee_set_by_name
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it
</span><span class=special
>=
</span><span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>find
</span><span class=special
>(
</span><span class=string
>"Anna Jones
"</span><span class=special
>);
</span>
892 <span class=identifier
>employee
</span> <span class=identifier
>anna
</span><span class=special
>=*
</span><span class=identifier
>it
</span><span class=special
>;
</span>
893 <span class=identifier
>anna
</span><span class=special
>.
</span><span class=identifier
>name
</span><span class=special
>=
</span><span class=string
>"Anna Smith
"</span><span class=special
>;
</span> <span class=comment
>// she just got married to Calvin Smith
</span>
894 <span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>replace
</span><span class=special
>(
</span><span class=identifier
>it
</span><span class=special
>,
</span><span class=identifier
>anna
</span><span class=special
>);
</span> <span class=comment
>// update her record
</span>
898 <code>replace
</code> performs this substitution in such a manner that:
900 <li>The complexity is constant time if the changed element retains its original
901 order with respect to all indices; it is logarithmic otherwise.
902 <li>Iterator and reference validity are preserved.
903 <li>The operation is strongly exception-safe, i.e. the
<code>multi_index_container
</code>
904 remains unchanged if some exception (originated by the system or the user's data
907 <code>replace
</code> is a powerful operation not provided by standard STL
908 containers, and one that is specially handy when strong exception-safety is
913 The observant reader might have noticed that the convenience of
<code>replace
</code>
914 comes at a cost: namely the whole element has to be copied
<i>twice
</i> to do
915 the updating (when retrieving it and inside
<code>replace
</code>). If elements
916 are expensive to copy, this may be quite a computational cost for the modification
917 of just a tiny part of the object. To cope with this situation, Boost.MultiIndex
918 provides an alternative updating mechanism called
919 <a href=
"../reference/ord_indices.html#modify"><code>modify
</code></a>:
923 <span class=keyword
>struct
</span> <span class=identifier
>change_name
</span>
924 <span class=special
>{
</span>
925 <span class=identifier
>change_name
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</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>
927 <span class=keyword
>void
</span> <span class=keyword
>operator
</span><span class=special
>()(
</span><span class=identifier
>employee
</span><span class=special
>&</span> <span class=identifier
>e
</span><span class=special
>)
</span>
928 <span class=special
>{
</span>
929 <span class=identifier
>e
</span><span class=special
>.
</span><span class=identifier
>name
</span><span class=special
>=
</span><span class=identifier
>new_name
</span><span class=special
>;
</span>
930 <span class=special
>}
</span>
932 <span class=keyword
>private
</span><span class=special
>:
</span>
933 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span> <span class=identifier
>new_name
</span><span class=special
>;
</span>
934 <span class=special
>};
</span>
935 <span class=special
>...
</span>
936 <span class=keyword
>typedef
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>index
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>employee_set_by_name
</span><span class=special
>;
</span>
937 <span class=identifier
>employee_set_by_name
</span><span class=special
>&</span> <span class=identifier
>name_index
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>();
</span>
939 <span class=identifier
>employee_set_by_name
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it
</span><span class=special
>=
</span><span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>find
</span><span class=special
>(
</span><span class=string
>"Anna Jones
"</span><span class=special
>);
</span>
940 <span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>modify
</span><span class=special
>(
</span><span class=identifier
>it
</span><span class=special
>,
</span><span class=identifier
>change_name
</span><span class=special
>(
</span><span class=string
>"Anna Smith
"</span><span class=special
>));
</span>
943 <p><code>modify
</code> accepts a functor (or pointer to function) that is
944 passed a reference to the element to be changed, thus eliminating the need
945 for spurious copies. Like
<code>replace
</code>,
<code>modify
</code> does preserve
946 the internal orderings of all the indices of the
<code>multi_index_container
</code>.
947 However, the semantics of
<code>modify
</code> is not entirely equivalent to
948 <code>replace
</code>. Consider what happens if a collision occurs as a result
949 of modifying the element, i.e. the modified element clashes with another with
950 respect to some unique ordered index. In the case of
<code>replace
</code>, the
951 original value is kept and the method returns without altering the container, but
952 <code>modify
</code> cannot afford such an approach, since the modifying functor
953 leaves no trace of the previous value of the element. Integrity constraints
954 thus lead to the following policy: when a collision happens in the
955 process of calling
<code>modify
</code>, the element is erased and the method returns
956 <code>false
</code>. There is a further version of
<code>modify
</code> which
957 accepts a
<i>rollback
</i> functor to undo the changes in case of collision:
961 <span class=keyword
>struct
</span> <span class=identifier
>change_id
</span>
962 <span class=special
>{
</span>
963 <span class=identifier
>change_id
</span><span class=special
>(
</span><span class=keyword
>int
</span> <span class=identifier
>new_id
</span><span class=special
>):
</span><span class=identifier
>new_id
</span><span class=special
>(
</span><span class=identifier
>new_id
</span><span class=special
>){}
</span>
965 <span class=keyword
>void
</span> <span class=keyword
>operator
</span><span class=special
>()(
</span><span class=identifier
>employee
</span><span class=special
>&</span> <span class=identifier
>e
</span><span class=special
>)
</span>
966 <span class=special
>{
</span>
967 <span class=identifier
>e
</span><span class=special
>.
</span><span class=identifier
>id
</span><span class=special
>=
</span><span class=identifier
>new_id
</span><span class=special
>;
</span>
968 <span class=special
>}
</span>
970 <span class=keyword
>private
</span><span class=special
>:
</span>
971 <span class=keyword
>int
</span> <span class=identifier
>new_id
</span><span class=special
>;
</span>
972 <span class=special
>};
</span>
973 <span class=special
>...
</span>
974 <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it
</span><span class=special
>=...
</span>
976 <span class=keyword
>int
</span> <span class=identifier
>old_id
</span><span class=special
>=
</span><span class=identifier
>it
</span><span class=special
>-
></span><span class=identifier
>id
</span><span class=special
>;
</span> <span class=comment
>// keep the original id
978 // try to modify the id, restore it in case of collisions
</span>
979 <span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>modify
</span><span class=special
>(
</span><span class=identifier
>it
</span><span class=special
>,
</span><span class=identifier
>change_id
</span><span class=special
>(
</span><span class=number
>321</span><span class=special
>),
</span><span class=identifier
>change_id
</span><span class=special
>(
</span><span class=identifier
>old_id
</span><span class=special
>));
</span>
982 <p>In the example,
<code>change_id(old_id)
</code> is invoked to restore the original
983 conditions when the modification results in collisions with some other element.
984 The differences in behavior between
<code>replace
</code>,
<code>modify
</code> and
985 <code>modify
</code> with rollback have to be considered by the programmer on a
986 case-by-case basis to determine the best updating mechanism.
990 <table cellspacing=
"0">
991 <caption><b>Behavior of the different updating mechanisms.
</b></caption>
993 <th align=
"center">updating function
</th>
994 <th>If there is a collision...
</th>
997 <td align=
"center"><code>replace(it,x)
</code></td>
998 <td>replacement does not take place.
</td>
1001 <td align=
"center"><code>modify(it,mod)
</code></td>
1002 <td>the element is erased.
</td>
1005 <td align=
"center"><code>modify(it,mod,back)
</code></td>
1006 <td><code>back
</code> is used to restore the original conditions.
1007 (If
<code>back
</code> throws, the element is erased.)
1015 Key-based versions of
<code>modify
</code>, named
1016 <a href=
"../reference/ord_indices.html#modify_key"><code>modify_key
</code></a>, are
1017 provided as well. In this case, the modifying functors are passed a reference to
1018 the
<code>key_type
</code> part of the element instead of the whole object.
1022 <span class=keyword
>struct
</span> <span class=identifier
>change_str
</span>
1023 <span class=special
>{
</span>
1024 <span class=identifier
>change_str
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</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>
1026 <span class=comment
>// note this is passed a string, not an employee
</span>
1027 <span class=keyword
>void
</span> <span class=keyword
>operator
</span><span class=special
>()(
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span><span class=special
>&</span> <span class=identifier
>str
</span><span class=special
>)
</span>
1028 <span class=special
>{
</span>
1029 <span class=identifier
>str
</span><span class=special
>=
</span><span class=identifier
>new_str
</span><span class=special
>;
</span>
1030 <span class=special
>}
</span>
1032 <span class=keyword
>private
</span><span class=special
>:
</span>
1033 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>string
</span> <span class=identifier
>new_str
</span><span class=special
>;
</span>
1034 <span class=special
>};
</span>
1035 <span class=special
>...
</span>
1036 <span class=keyword
>typedef
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>index
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>employee_set_by_name
</span><span class=special
>;
</span>
1037 <span class=identifier
>employee_set_by_name
</span><span class=special
>&</span> <span class=identifier
>name_index
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>();
</span>
1039 <span class=identifier
>employee_set_by_name
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it
</span><span class=special
>=
</span><span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>find
</span><span class=special
>(
</span><span class=string
>"Anna Jones
"</span><span class=special
>);
</span>
1040 <span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>modify_key
</span><span class=special
>(
</span><span class=identifier
>it
</span><span class=special
>,
</span><span class=identifier
>change_str
</span><span class=special
>(
</span><span class=string
>"Anna Smith
"</span><span class=special
>));
</span>
1044 Like
<code>modify
</code>, there are versions of
<code>modify_key
</code> with and
1045 without rollback.
<code>modify
</code> and
1046 <code>modify_key
</code> are particularly well suited to use in conjunction to
1047 <a href=
"../../../../libs/lambda/index.html">Boost.Lambda
</a>
1048 for defining the modifying functors:
1052 <span class=keyword
>using
</span> <span class=keyword
>namespace
</span> <span class=identifier
>boost
</span><span class=special
>::
</span><span class=identifier
>lambda
</span><span class=special
>;
</span>
1054 <span class=keyword
>typedef
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>index
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>employee_set_by_name
</span><span class=special
>;
</span>
1055 <span class=identifier
>employee_set_by_name
</span><span class=special
>&</span> <span class=identifier
>name_index
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>();
</span>
1057 <span class=identifier
>employee_set_by_name
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it
</span><span class=special
>=
</span><span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>find
</span><span class=special
>(
</span><span class=string
>"Anna Jones
"</span><span class=special
>);
</span>
1058 <span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>modify_key
</span><span class=special
>(
</span><span class=identifier
>it
</span><span class=special
>,
</span><span class=identifier
>_1
</span><span class=special
>=
</span><span class=string
>"Anna Smith
"</span><span class=special
>);
</span>
1062 <code>modify_key
</code> requires that the key extractor be of
1063 a special type called
1064 <a href=
"key_extraction.html#read_write_key_extractors">read/write
</a>:
1065 this is usually, but not always, the case.
1069 <a name=
"seq_indices">Sequenced indices
</a>
1073 Unlike ordered indices, sequenced indices do not impose a fixed order on the
1074 elements: instead, these can be arranged in any position on the sequence, in the
1075 same way as
<code>std::list
</code> permits. The interface of sequenced indices
1076 is thus designed upon that of
<code>std::list
</code>; nearly every operation
1077 provided in the standard container is replicated here, occasionally with changes
1078 in the syntax and/or semantics to cope with the constraints imposed by
1079 Boost.MultiIndex. An important difference, commented
<a href=
"#iterator_access">above
</a>,
1080 is the fact that the values pointed to by sequenced index iterators are treated
1085 <span class=identifier
>multi_index_container
</span><span class=special
><</span>
1086 <span class=keyword
>int
</span><span class=special
>,
</span>
1087 <span class=identifier
>indexed_by
</span><span class=special
><</span><span class=identifier
>sequenced
</span><span class=special
><></span> <span class=special
>></span>
1088 <span class=special
>></span> <span class=identifier
>s
</span><span class=special
>;
</span> <span class=comment
>// list-like container
</span>
1090 <span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>push_front
</span><span class=special
>(
</span><span class=number
>0</span><span class=special
>);
</span>
1091 <span class=special
>*(
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>())=
</span><span class=number
>1</span><span class=special
>;
</span> <span class=comment
>// ERROR: the element cannot be changed
</span>
1095 As with any other type of index, element modification
1096 can nevertheless be done by means of
1097 <a href=
"#seq_updating">update operations
</a>.
1101 Consider a
<code>multi_index_container
</code> with two or more indices, one of them
1102 of sequenced type. If an element is inserted through another index,
1103 then it will be automatically appended to the end of the sequenced index.
1104 An example will help to clarify this:
1108 <span class=identifier
>multi_index_container
</span><span class=special
><</span>
1109 <span class=keyword
>int
</span><span class=special
>,
</span>
1110 <span class=identifier
>indexed_by
</span><span class=special
><</span>
1111 <span class=identifier
>sequenced
</span><span class=special
><>,
</span> <span class=comment
>// sequenced type
</span>
1112 <span class=identifier
>ordered_unique
</span><span class=special
><</span><span class=identifier
>identity
</span><span class=special
><</span><span class=keyword
>int
</span><span class=special
>></span> <span class=special
>></span> <span class=comment
>// another index
</span>
1113 <span class=special
>></span>
1114 <span class=special
>></span> <span class=identifier
>s
</span><span class=special
>;
</span>
1116 <span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>().
</span><span class=identifier
>insert
</span><span class=special
>(
</span><span class=number
>1</span><span class=special
>);
</span> <span class=comment
>// insert
1 through index #
1</span>
1117 <span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>().
</span><span class=identifier
>insert
</span><span class=special
>(
</span><span class=number
>0</span><span class=special
>);
</span> <span class=comment
>// insert
0 through index #
1
1119 // list elements through sequenced index #
0</span>
1120 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>copy
</span><span class=special
>(
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>(),
</span><span class=identifier
>s
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>(),
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>ostream_iterator
</span><span class=special
><</span><span class=keyword
>int
</span><span class=special
>>(
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>cout
</span><span class=special
>));
</span>
1122 <span class=comment
>// result:
1 0</span>
1126 Thus the behavior of sequenced indices when insertions are not made through
1127 them is to preserve insertion order.
1130 <h4><a name=
"seq_spec">Specification
</a></h4>
1133 Sequenced indices are specified with the
<code>sequenced
</code> construct:
1137 <span class=identifier
>sequenced
</span><span class=special
><[
</span><i>(tag)
</i><span class=special
>]
></span>
1141 The
<a href=
"#tagging">tag
</a> parameter is optional.
1144 <h4><a name=
"list_ops">List operations
</a></h4>
1147 As mentioned before, sequenced indices mimic the interface of
1148 <code>std::list
</code>, and most of the original operations therein are
1149 provided as well. The semantics and complexity of these operations, however,
1150 do not always coincide with those of the standard container. Differences
1151 result mainly from the fact that insertions into a sequenced index are not
1152 guaranteed to succeed, due to the possible banning by other indices
1153 of the
<code>multi_index_container
</code>. Consult the
1154 <a href=
"../reference/seq_indices.html">reference
</a> for further details.
1157 <h4><a name=
"seq_updating">Updating
</a></h4>
1160 Like ordered indices, sequenced indices provide
1161 <a href=
"../reference/seq_indices.html#replace"><code>replace
</code></a> and
1162 <a href=
"../reference/seq_indices.html#modify"><code>modify
</code></a>
1163 operations, with identical functionality. There is however no analogous
1164 <code>modify_key
</code>, since sequenced indices are not key-based.
1167 <h2><a name=
"projection">Projection of iterators
</a></h2>
1170 Given indices
<code>i1
</code> and
<code>i2
</code> on the same
<code>multi_index_container
</code>,
1171 <a href=
"../reference/multi_index_container.html#projection"><code>project
</code></a> can be used to
1172 retrieve an
<code>i2
</code>-iterator from an
<code>i1
</code>-iterator, both of them
1173 pointing to the same element of the container. This functionality allows the programmer to
1174 move between different indices of the same
<code>multi_index_container
</code> when performing
1175 elaborate operations:
1179 <span class=keyword
>typedef
</span> <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>index
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>::
</span><span class=identifier
>type
</span> <span class=identifier
>employee_set_by_name
</span><span class=special
>;
</span>
1180 <span class=identifier
>employee_set_by_name
</span><span class=special
>&</span> <span class=identifier
>name_index
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=identifier
>name
</span><span class=special
>>();
</span>
1182 <span class=comment
>// list employees by ID starting from Robert Brown's ID
</span>
1184 <span class=identifier
>employee_set_by_name
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it1
</span><span class=special
>=
</span><span class=identifier
>name_index
</span><span class=special
>.
</span><span class=identifier
>find
</span><span class=special
>(
</span><span class=string
>"Robert Brown
"</span><span class=special
>);
</span>
1186 <span class=comment
>// obtain an iterator of index #
0 from it1
</span>
1187 <span class=identifier
>employee_set
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it2
</span><span class=special
>=
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>project
</span><span class=special
><</span><span class=number
>0</span><span class=special
>>(
</span><span class=identifier
>it1
</span><span class=special
>);
</span>
1189 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>copy
</span><span class=special
>(
</span><span class=identifier
>it2
</span><span class=special
>,
</span><span class=identifier
>es
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>(),
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>ostream_iterator
</span><span class=special
><</span><span class=identifier
>employee
</span><span class=special
>>(
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>cout
</span><span class=special
>));
</span>
1193 A slightly more interesting example:
1197 <span class=identifier
>text_container
</span> <span class=identifier
>tc
</span><span class=special
>;
</span>
1199 <span class=comment
>// get a view to index #
1 (ordered index on the words)
</span>
1200 <span class=identifier
>text_container
</span><span class=special
>::
</span><span class=identifier
>nth_index
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>::
</span><span class=identifier
>type
</span><span class=special
>&</span> <span class=identifier
>sorted_index
</span><span class=special
>=
</span><span class=identifier
>tc
</span><span class=special
>.
</span><span class=identifier
>get
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>();
</span>
1202 <span class=comment
>// prepend
"older
" to all occurrences of
"sister
"</span>
1204 <span class=identifier
>text_container
</span><span class=special
>::
</span><span class=identifier
>nth_index
</span><span class=special
><</span><span class=number
>1</span><span class=special
>>::
</span><span class=identifier
>type
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it1
</span><span class=special
>=
</span>
1205 <span class=identifier
>sorted_index
</span><span class=special
>.
</span><span class=identifier
>lower_bound
</span><span class=special
>(
</span><span class=string
>"sister
"</span><span class=special
>);
</span>
1207 <span class=keyword
>while
</span><span class=special
>(
</span><span class=identifier
>it1
</span><span class=special
>!=
</span><span class=identifier
>sorted_index
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>()
&&*
</span><span class=identifier
>it1
</span><span class=special
>==
</span><span class=string
>"sister
"</span><span class=special
>){
</span>
1208 <span class=comment
>// convert to an iterator to the sequenced index
</span>
1209 <span class=identifier
>text_container
</span><span class=special
>::
</span><span class=identifier
>iterator
</span> <span class=identifier
>it2
</span><span class=special
>=
</span><span class=identifier
>tc
</span><span class=special
>.
</span><span class=identifier
>project
</span><span class=special
><</span><span class=number
>0</span><span class=special
>>(
</span><span class=identifier
>it1
</span><span class=special
>);
</span>
1211 <span class=identifier
>tc
</span><span class=special
>.
</span><span class=identifier
>insert
</span><span class=special
>(
</span><span class=identifier
>it2
</span><span class=special
>,
</span><span class=string
>"older
"</span><span class=special
>);
</span>
1212 <span class=special
>++
</span><span class=identifier
>it1
</span><span class=special
>;
</span>
1213 <span class=special
>}
</span>
1217 When provided,
<code>project
</code> can also be used with
1218 <a href=
"#tagging">tags
</a>.
1221 <h2><a name=
"complexity">Complexity and exception safety
</a></h2>
1224 <code>multi_index_container
</code> provides the same complexity and exception safety
1225 guarantees as the equivalent STL containers do. Iterator and reference validity
1226 is preserved in the face of insertions, even for replace and modify operations.
1230 Appropriate instantiations of
<code>multi_index_container
</code> can in fact simulate
1231 <code>std::set
</code>,
<code>std::multiset
</code> and (with more limitations)
1232 <code>std::list
</code>, as shown in the
1233 <a href=
"techniques.html#emulate_std_containers">techniques
</a>
1234 section. These simulations are as nearly as efficient as the original STL
1235 containers; consult the
<a href=
"../reference/index.html">reference
</a> for further
1236 information on complexity guarantees and the
1237 <a href=
"../performance.html">performance section
</a> for practical measurements of
1243 <div class=
"prev_link"><a href=
"index.html"><img src=
"../prev.gif" alt=
"tutorial" border=
"0"><br>
1244 Boost.MultiIndex Tutorial
1246 <div class=
"up_link"><a href=
"index.html"><img src=
"../up.gif" alt=
"Boost.MultiIndex tutorial" border=
"0"><br>
1247 Boost.MultiIndex tutorial
1249 <div class=
"next_link"><a href=
"indices.html"><img src=
"../next.gif" alt=
"index types" border=
"0"><br>
1251 </a></div><br clear=
"all" style=
"clear: all;">
1255 <p>Revised November
24th
2015</p>
1257 <p>© Copyright
2003-
2015 Joaqu
ín M L
ópez Mu
ñoz.
1258 Distributed under the Boost Software
1259 License, Version
1.0. (See accompanying file
<a href=
"../../../../LICENSE_1_0.txt">
1260 LICENSE_1_0.txt
</a> or copy at
<a href=
"http://www.boost.org/LICENSE_1_0.txt">
1261 http://www.boost.org/LICENSE_1_0.txt
</a>)