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 - Ordered indices reference
</title>
7 <link rel=
"stylesheet" href=
"../style.css" type=
"text/css">
8 <link rel=
"start" href=
"../index.html">
9 <link rel=
"prev" href=
"indices.html">
10 <link rel=
"up" href=
"index.html">
11 <link rel=
"next" href=
"hash_indices.html">
15 <h1><img src=
"../../../../boost.png" alt=
"boost.png (6897 bytes)" align=
16 "middle" width=
"277" height=
"86">Boost.MultiIndex Ordered indices reference
</h1>
18 <div class=
"prev_link"><a href=
"indices.html"><img src=
"../prev.gif" alt=
"index reference" border=
"0"><br>
21 <div class=
"up_link"><a href=
"index.html"><img src=
"../up.gif" alt=
"Boost.MultiIndex reference" border=
"0"><br>
22 Boost.MultiIndex reference
24 <div class=
"next_link"><a href=
"rnk_indices.html"><img src=
"../next.gif" alt=
"ranked indices" border=
"0"><br>
26 </a></div><br clear=
"all" style=
"clear: all;">
33 <li><a href=
"#ord_index_fwd_synopsis">Header
34 <code>"boost/multi_index/ordered_index_fwd.hpp"</code> synopsis
</a></li>
35 <li><a href=
"#synopsis">Header
36 <code>"boost/multi_index/ordered_index.hpp"</code> synopsis
</a>
38 <li><a href=
"#unique_non_unique">
39 Index specifiers
<code>ordered_unique
</code> and
<code>ordered_non_unique
</code>
41 <li><a href=
"#ord_indices">Ordered indices
</a>
43 <li><a href=
"#complexity_signature">Complexity signature
</a></li>
44 <li><a href=
"#instantiation_types">Instantiation types
</a></li>
45 <li><a href=
"#constructors">Constructors, copy and assignment
</a></li>
46 <li><a href=
"#iterators">Iterators
</a></li>
47 <li><a href=
"#modifiers">Modifiers
</a></li>
48 <li><a href=
"#observers">Observers
</a></li>
49 <li><a href=
"#set_operations">Set operations
</a></li>
50 <li><a href=
"#range_operations">Range operations
</a></li>
51 <li><a href=
"#serialization">Serialization
</a></li>
59 <a name=
"ord_index_fwd_synopsis">Header
60 <a href=
"../../../../boost/multi_index/ordered_index_fwd.hpp">
61 <code>"boost/multi_index/ordered_index_fwd.hpp"</code></a> synopsis
</a></h2>
64 <span class=keyword
>namespace
</span> <span class=identifier
>boost
</span><span class=special
>{
</span>
66 <span class=keyword
>namespace
</span> <span class=identifier
>multi_index
</span><span class=special
>{
</span>
68 <span class=comment
>// index specifiers ordered_unique and ordered_non_unique
</span>
70 <span class=keyword
>template
</span><span class=special
><</span><b>consult ordered_unique reference for arguments
</b><span class=special
>></span>
71 <span class=keyword
>struct
</span> <span class=identifier
>ordered_unique
</span><span class=special
>;
</span>
72 <span class=keyword
>template
</span><span class=special
><</span><b>consult ordered_non_unique reference for arguments
</b><span class=special
>></span>
73 <span class=keyword
>struct
</span> <span class=identifier
>ordered_non_unique
</span><span class=special
>;
</span>
75 <span class=comment
>// indices
</span>
77 <span class=keyword
>namespace
</span> <span class=identifier
>detail
</span><span class=special
>{
</span>
79 <span class=keyword
>template
</span><span class=special
><</span><b>implementation defined
</b><span class=special
>></span> <span class=keyword
>class
</span> <b>index name is implementation defined
</b><span class=special
>;
</span>
81 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index::detail
</span>
83 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index
</span>
85 <span class=special
>}
</span> <span class=comment
>// namespace boost
</span>
89 <code>ordered_index_fwd.hpp
</code> provides forward declarations for index specifiers
90 <a href=
"#unique_non_unique"><code>ordered_unique
</code> and
<code>ordered_non_unique
</code></a> and
91 their associated
<a href=
"#ord_indices">ordered index
</a> classes.
95 <a name=
"synopsis">Header
96 <a href=
"../../../../boost/multi_index/ordered_index.hpp">
97 <code>"boost/multi_index/ordered_index.hpp"</code></a> synopsis
</a></h2>
100 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>initializer_list
</span><span class=special
>></span>
102 <span class=keyword
>namespace
</span> <span class=identifier
>boost
</span><span class=special
>{
</span>
104 <span class=keyword
>namespace
</span> <span class=identifier
>multi_index
</span><span class=special
>{
</span>
106 <span class=comment
>// index specifiers ordered_unique and ordered_non_unique
</span>
108 <span class=keyword
>template
</span><span class=special
><</span><b>consult ordered_unique reference for arguments
</b><span class=special
>></span>
109 <span class=keyword
>struct
</span> <span class=identifier
>ordered_unique
</span><span class=special
>;
</span>
110 <span class=keyword
>template
</span><span class=special
><</span><b>consult ordered_non_unique reference for arguments
</b><span class=special
>></span>
111 <span class=keyword
>struct
</span> <span class=identifier
>ordered_non_unique
</span><span class=special
>;
</span>
113 <span class=comment
>// indices
</span>
115 <span class=keyword
>namespace
</span> <span class=identifier
>detail
</span><span class=special
>{
</span>
117 <span class=keyword
>template
</span><span class=special
><</span><b>implementation defined
</b><span class=special
>></span> <span class=keyword
>class
</span> <b>index class name implementation defined
</b><span class=special
>;
</span>
119 <span class=comment
>// index comparison:
</span>
121 <span class=comment
>//
<b>OP
</b> is any of ==,
<,!=,
>,
>=,
<=
</span>
123 <span class=keyword
>template
</span><span class=special
><</span><b>arg set
1</b><span class=special
>,
</span><b>arg set
2</b><span class=special
>></span>
124 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span> <b><i>OP
</i></b><span class=special
>(
</span>
125 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
1</b><span class=special
>>&</span> <span class=identifier
>x
</span><span class=special
>,
</span><span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
2</b><span class=special
>>&</span> <span class=identifier
>y
</span><span class=special
>);
</span>
127 <span class=comment
>// index specialized algorithms:
</span>
129 <span class=keyword
>template
</span><span class=special
><</span><b>implementation defined
</b><span class=special
>></span>
130 <span class=keyword
>void
</span> <span class=identifier
>swap
</span><span class=special
>(
</span><b>index class name
</b><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>,
</span><b>index class name
</b><span class=special
>&</span> <span class=identifier
>y
</span><span class=special
>);
</span>
132 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index::detail
</span>
134 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index
</span>
136 <span class=special
>}
</span> <span class=comment
>// namespace boost
</span>
139 <h3><a name=
"unique_non_unique">
140 Index specifiers
<code>ordered_unique
</code> and
<code>ordered_non_unique
</code>
144 These
<a href=
"indices.html#index_specification">index specifiers
</a> allow
145 for insertion of
<a href=
"#ord_indices">ordered indices
</a> without and with
146 allowance of duplicate elements, respectively. The syntax of
<code>ordered_unique
</code>
147 and
<code>ordered_non_unique
</code> coincide, thus we describe them in a grouped manner.
148 <code>ordered_unique
</code> and
<code>ordered_non_unique
</code> can be instantiated in
149 two different forms, according to whether a tag list for the index is provided or not:
153 <span class=keyword
>template
</span><span class=special
><</span>
154 <span class=keyword
>typename
</span> <span class=identifier
>KeyFromValue
</span><span class=special
>,
</span>
155 <span class=keyword
>typename
</span> <span class=identifier
>Compare
</span><span class=special
>=
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>less
</span><span class=special
><</span><span class=identifier
>KeyFromValue
</span><span class=special
>::
</span><span class=identifier
>result_type
</span><span class=special
>></span>
156 <span class=special
>></span>
157 <span class=keyword
>struct
</span> <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><span class=special
>;
</span>
159 <span class=keyword
>template
</span><span class=special
><</span>
160 <span class=keyword
>typename
</span> <span class=identifier
>TagList
</span><span class=special
>,
</span>
161 <span class=keyword
>typename
</span> <span class=identifier
>KeyFromValue
</span><span class=special
>,
</span>
162 <span class=keyword
>typename
</span> <span class=identifier
>Compare
</span><span class=special
>=
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>less
</span><span class=special
><</span><span class=identifier
>KeyFromValue
</span><span class=special
>::
</span><span class=identifier
>result_type
</span><span class=special
>></span>
163 <span class=special
>></span>
164 <span class=keyword
>struct
</span> <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><span class=special
>;
</span>
168 If provided,
<code>TagList
</code> must be an instantiation of the class template
169 <a href=
"indices.html#tag"><code>tag
</code></a>.
170 The template arguments are used by the corresponding index implementation,
171 refer to the
<a href=
"#ord_indices">ordered indices
</a> reference section for further
172 explanations on their acceptable type values.
175 <h3><a name=
"ord_indices">Ordered indices
</a></h3>
178 An ordered index provides a set-like interface to the underlying heap of
179 elements contained in a
<code>multi_index_container
</code>. An ordered index is
180 particularized according to a given
181 <a href=
"key_extraction.html#key_extractors"><code>Key Extractor
</code></a>
182 that retrieves keys from elements of
<code>multi_index_container
</code> and a comparison
187 There are two variants of ordered indices:
<i>unique
</i>, which do
188 not allow duplicate elements (with respect to its associated comparison
189 predicate) and
<i>non-unique
</i>, which accept those duplicates.
190 The interface of these two variants is the same, so they are documented
191 together, with minor differences explicitly stated when they exist.
195 Except where noted or if the corresponding interface does not exist,
196 ordered indices (both unique and non-unique) satisfy the C++ requirements
197 for associative containers at
<b>[associative.reqmts]
</b>
198 (supporting unique and equivalent keys, respectively.)
199 Accordingly, validity of iterators and references to elements is
200 preserved. We only provide descriptions of those types and operations that
201 do not exactly conform to or are not mandated by the standard requirements.
205 <span class=keyword
>namespace
</span> <span class=identifier
>boost
</span><span class=special
>{
</span>
207 <span class=keyword
>namespace
</span> <span class=identifier
>multi_index
</span><span class=special
>{
</span>
209 <b>implementation defined
</b><span class=identifier
>unbounded
</span><span class=special
>;
</span> <span class=comment
>// see range()
</span>
211 <span class=keyword
>namespace
</span> <span class=identifier
>detail
</span><span class=special
>{
</span>
213 <span class=keyword
>template
</span><span class=special
><</span><b>implementation defined: dependent on types Value, Allocator,
214 TagList, KeyFromValue, Compare
</b><span class=special
>></span>
215 <span class=keyword
>class
</span> <b>name is implementation defined
</b>
216 <span class=special
>{
</span>
217 <span class=keyword
>public
</span><span class=special
>:
</span>
218 <span class=comment
>// types:
</span>
220 <span class=keyword
>typedef
</span> <span class=keyword
>typename
</span> <span class=identifier
>KeyFromValue
</span><span class=special
>::
</span><span class=identifier
>result_type
</span> <span class=identifier
>key_type
</span><span class=special
>;
</span>
221 <span class=keyword
>typedef
</span> <span class=identifier
>Value
</span> <span class=identifier
>value_type
</span><span class=special
>;
</span>
222 <span class=keyword
>typedef
</span> <span class=identifier
>KeyFromValue
</span> <span class=identifier
>key_from_value
</span><span class=special
>;
</span>
223 <span class=keyword
>typedef
</span> <span class=identifier
>Compare
</span> <span class=identifier
>key_compare
</span><span class=special
>;
</span>
224 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>value_compare
</span><span class=special
>;
</span>
225 <span class=keyword
>typedef
</span> <span class=identifier
>boost
</span><span class=special
>::
</span><span class=identifier
>tuple
</span><span class=special
><</span><span class=identifier
>key_from_value
</span><span class=special
>,
</span><span class=identifier
>key_compare
</span><span class=special
>></span> <span class=identifier
>ctor_args
</span><span class=special
>;
</span>
226 <span class=keyword
>typedef
</span> <span class=identifier
>TagList
</span> <span class=identifier
>tag_list
</span><span class=special
>;
</span>
227 <span class=keyword
>typedef
</span> <span class=identifier
>Allocator
</span> <span class=identifier
>allocator_type
</span><span class=special
>;
</span>
228 <span class=keyword
>typedef
</span> <span class=keyword
>typename
</span> <span class=identifier
>Allocator
</span><span class=special
>::
</span><span class=identifier
>reference
</span> <span class=identifier
>reference
</span><span class=special
>;
</span>
229 <span class=keyword
>typedef
</span> <span class=keyword
>typename
</span> <span class=identifier
>Allocator
</span><span class=special
>::
</span><span class=identifier
>const_reference
</span> <span class=identifier
>const_reference
</span><span class=special
>;
</span>
230 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>iterator
</span><span class=special
>;
</span>
231 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>const_iterator
</span><span class=special
>;
</span>
232 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>size_type
</span><span class=special
>;
</span>
233 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>difference_type
</span><span class=special
>;
</span>
234 <span class=keyword
>typedef
</span> <span class=keyword
>typename
</span> <span class=identifier
>Allocator
</span><span class=special
>::
</span><span class=identifier
>pointer
</span> <span class=identifier
>pointer
</span><span class=special
>;
</span>
235 <span class=keyword
>typedef
</span> <span class=keyword
>typename
</span> <span class=identifier
>Allocator
</span><span class=special
>::
</span><span class=identifier
>const_pointer
</span> <span class=identifier
>const_pointer
</span><span class=special
>;
</span>
236 <span class=keyword
>typedef
</span> <b>equivalent to
237 std::reverse_iterator
<iterator
></b> <span class=identifier
>reverse_iterator
</span><span class=special
>;
</span>
238 <span class=keyword
>typedef
</span> <b>equivalent to
239 std::reverse_iterator
<const_iterator
></b> <span class=identifier
>const_reverse_iterator
</span><span class=special
>;
</span>
241 <span class=comment
>// construct/copy/destroy:
</span>
243 <b>index class name
</b><span class=special
>&</span> <span class=keyword
>operator
</span><span class=special
>=(
</span><span class=keyword
>const
</span> <b>index class name
</b><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
244 <b>index class name
</b><span class=special
>&</span> <span class=keyword
>operator
</span><span class=special
>=(
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>initializer_list
</span><span class=special
><</span><span class=identifier
>value_type
</span><span class=special
>></span> <span class=identifier
>list
</span><span class=special
>);
</span>
246 <span class=identifier
>allocator_type
</span> <span class=identifier
>get_allocator
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
248 <span class=comment
>// iterators:
</span>
250 <span class=identifier
>iterator
</span> <span class=identifier
>begin
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
251 <span class=identifier
>const_iterator
</span> <span class=identifier
>begin
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
252 <span class=identifier
>iterator
</span> <span class=identifier
>end
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
253 <span class=identifier
>const_iterator
</span> <span class=identifier
>end
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
254 <span class=identifier
>reverse_iterator
</span> <span class=identifier
>rbegin
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
255 <span class=identifier
>const_reverse_iterator
</span> <span class=identifier
>rbegin
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
256 <span class=identifier
>reverse_iterator
</span> <span class=identifier
>rend
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
257 <span class=identifier
>const_reverse_iterator
</span> <span class=identifier
>rend
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
258 <span class=identifier
>const_iterator
</span> <span class=identifier
>cbegin
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
259 <span class=identifier
>const_iterator
</span> <span class=identifier
>cend
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
260 <span class=identifier
>const_reverse_iterator
</span> <span class=identifier
>crbegin
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
261 <span class=identifier
>const_reverse_iterator
</span> <span class=identifier
>crend
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
263 <span class=identifier
>iterator
</span> <span class=identifier
>iterator_to
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>value_type
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
264 <span class=identifier
>const_iterator
</span> <span class=identifier
>iterator_to
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>value_type
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
266 <span class=comment
>// capacity:
</span>
268 <span class=keyword
>bool
</span> <span class=identifier
>empty
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
269 <span class=identifier
>size_type
</span> <span class=identifier
>size
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
270 <span class=identifier
>size_type
</span> <span class=identifier
>max_size
</span><span class=special
>()
</span><span class=keyword
>const
</span> <span class=keyword
>noexcept
</span><span class=special
>;
</span>
272 <span class=comment
>// modifiers:
</span>
274 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span><span class=special
>...
</span> <span class=identifier
>Args
</span><span class=special
>></span>
275 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>iterator
</span><span class=special
>,
</span><span class=keyword
>bool
</span><span class=special
>></span> <span class=identifier
>emplace
</span><span class=special
>(
</span><span class=identifier
>Args
</span><span class=special
>&&...
</span> <span class=identifier
>args
</span><span class=special
>);
</span>
276 <span class=keyword
>template
</span> <span class=special
><</span><span class=keyword
>typename
</span><span class=special
>...
</span> <span class=identifier
>Args
</span><span class=special
>></span>
277 <span class=identifier
>iterator
</span> <span class=identifier
>emplace_hint
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>,
</span><span class=identifier
>Args
</span><span class=special
>&&...
</span> <span class=identifier
>args
</span><span class=special
>);
</span>
278 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>iterator
</span><span class=special
>,
</span><span class=keyword
>bool
</span><span class=special
>></span> <span class=identifier
>insert
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>value_type
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
279 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>iterator
</span><span class=special
>,
</span><span class=keyword
>bool
</span><span class=special
>></span> <span class=identifier
>insert
</span><span class=special
>(
</span><span class=identifier
>value_type
</span><span class=special
>&&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
280 <span class=identifier
>iterator
</span> <span class=identifier
>insert
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>value_type
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
281 <span class=identifier
>iterator
</span> <span class=identifier
>insert
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>,
</span><span class=identifier
>value_type
</span><span class=special
>&&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
282 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>InputIterator
</span><span class=special
>></span>
283 <span class=keyword
>void
</span> <span class=identifier
>insert
</span><span class=special
>(
</span><span class=identifier
>InputIterator
</span> <span class=identifier
>first
</span><span class=special
>,
</span><span class=identifier
>InputIterator
</span> <span class=identifier
>last
</span><span class=special
>);
</span>
284 <span class=keyword
>void
</span> <span class=identifier
>insert
</span><span class=special
>(
</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>initializer_list
</span><span class=special
><</span><span class=identifier
>value_type
</span><span class=special
>></span> <span class=identifier
>list
</span><span class=special
>);
</span>
286 <span class=identifier
>iterator
</span> <span class=identifier
>erase
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>);
</span>
287 <span class=identifier
>size_type
</span> <span class=identifier
>erase
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>key_type
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
288 <span class=identifier
>iterator
</span> <span class=identifier
>erase
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>first
</span><span class=special
>,
</span><span class=identifier
>iterator
</span> <span class=identifier
>last
</span><span class=special
>);
</span>
290 <span class=keyword
>bool
</span> <span class=identifier
>replace
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>value_type
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
291 <span class=keyword
>bool
</span> <span class=identifier
>replace
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>,
</span><span class=identifier
>value_type
</span><span class=special
>&&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
292 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>Modifier
</span><span class=special
>></span> <span class=keyword
>bool
</span> <span class=identifier
>modify
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>,
</span><span class=identifier
>Modifier
</span> <span class=identifier
>mod
</span><span class=special
>);
</span>
293 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>Modifier
</span><span class=special
>,
</span><span class=keyword
>typename
</span> <span class=identifier
>Rollback
</span><span class=special
>></span>
294 <span class=keyword
>bool
</span> <span class=identifier
>modify
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>,
</span><span class=identifier
>Modifier
</span> <span class=identifier
>mod
</span><span class=special
>,
</span><span class=identifier
>Rollback
</span> <span class=identifier
>back
</span><span class=special
>);
</span>
295 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>Modifier
</span><span class=special
>></span> <span class=keyword
>bool
</span> <span class=identifier
>modify_key
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>,
</span><span class=identifier
>Modifier
</span> <span class=identifier
>mod
</span><span class=special
>);
</span>
296 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>Modifier
</span><span class=special
>,
</span><span class=keyword
>typename
</span> <span class=identifier
>Rollback
</span><span class=special
>></span>
297 <span class=keyword
>bool
</span> <span class=identifier
>modify_key
</span><span class=special
>(
</span><span class=identifier
>iterator
</span> <span class=identifier
>position
</span><span class=special
>,
</span><span class=identifier
>Modifier
</span> <span class=identifier
>mod
</span><span class=special
>,
</span><span class=identifier
>Rollback
</span> <span class=identifier
>back
</span><span class=special
>);
</span>
299 <span class=keyword
>void
</span> <span class=identifier
>swap
</span><span class=special
>(
</span><b>index class name
</b><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>);
</span>
300 <span class=keyword
>void
</span> <span class=identifier
>clear
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
302 <span class=comment
>// observers:
</span>
304 <span class=identifier
>key_from_value
</span> <span class=identifier
>key_extractor
</span><span class=special
>()
</span><span class=keyword
>const
</span><span class=special
>;
</span>
305 <span class=identifier
>key_compare
</span> <span class=identifier
>key_comp
</span><span class=special
>()
</span><span class=keyword
>const
</span><span class=special
>;
</span>
306 <span class=identifier
>value_compare
</span> <span class=identifier
>value_comp
</span><span class=special
>()
</span><span class=keyword
>const
</span><span class=special
>;
</span>
308 <span class=comment
>// set operations:
</span>
310 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
311 <span class=identifier
>iterator
</span> <span class=identifier
>find
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
312 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>,
</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>></span>
313 <span class=identifier
>iterator
</span> <span class=identifier
>find
</span><span class=special
>(
</span>
314 <span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>&</span> <span class=identifier
>comp
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
316 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
317 <span class=identifier
>size_type
</span> <span class=identifier
>count
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
318 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>,
</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>></span>
319 <span class=identifier
>size_type
</span> <span class=identifier
>count
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>&</span> <span class=identifier
>comp
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
321 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
322 <span class=identifier
>iterator
</span> <span class=identifier
>lower_bound
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
323 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>,
</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>></span>
324 <span class=identifier
>iterator
</span> <span class=identifier
>lower_bound
</span><span class=special
>(
</span>
325 <span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>&</span> <span class=identifier
>comp
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
327 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
328 <span class=identifier
>iterator
</span> <span class=identifier
>upper_bound
</span><span class=special
>(
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
329 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>,
</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>></span>
330 <span class=identifier
>iterator
</span> <span class=identifier
>upper_bound
</span><span class=special
>(
</span>
331 <span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>&</span> <span class=identifier
>comp
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
333 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
334 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>iterator
</span><span class=special
>,
</span><span class=identifier
>iterator
</span><span class=special
>></span> <span class=identifier
>equal_range
</span><span class=special
>(
</span>
335 <span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
336 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>,
</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>></span>
337 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>iterator
</span><span class=special
>,
</span><span class=identifier
>iterator
</span><span class=special
>></span> <span class=identifier
>equal_range
</span><span class=special
>(
</span>
338 <span class=keyword
>const
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>,
</span><span class=keyword
>const
</span> <span class=identifier
>CompatibleCompare
</span><span class=special
>&</span> <span class=identifier
>comp
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
340 <span class=comment
>// range:
</span>
342 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>LowerBounder
</span><span class=special
>,
</span><span class=keyword
>typename
</span> <span class=identifier
>UpperBounder
</span><span class=special
>></span>
343 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>iterator
</span><span class=special
>,
</span><span class=identifier
>iterator
</span><span class=special
>></span> <span class=identifier
>range
</span><span class=special
>(
</span>
344 <span class=identifier
>LowerBounder
</span> <span class=identifier
>lower
</span><span class=special
>,
</span><span class=identifier
>UpperBounder
</span> <span class=identifier
>upper
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
345 <span class=special
>};
</span>
347 <span class=comment
>// index comparison:
</span>
349 <span class=keyword
>template
</span><span class=special
><</span><b>arg set
1</b><span class=special
>,
</span><b>arg set
2</b><span class=special
>></span>
350 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>==(
</span>
351 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
1</b><span class=special
>>&</span> <span class=identifier
>x
</span><span class=special
>,
</span>
352 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
2</b><span class=special
>>&</span> <span class=identifier
>y
</span><span class=special
>)
</span>
353 <span class=special
>{
</span>
354 <span class=keyword
>return
</span> <span class=identifier
>x
</span><span class=special
>.
</span><span class=identifier
>size
</span><span class=special
>()==
</span><span class=identifier
>y
</span><span class=special
>.
</span><span class=identifier
>size
</span><span class=special
>()
&&</span><span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>equal
</span><span class=special
>(
</span><span class=identifier
>x
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>(),
</span><span class=identifier
>x
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>(),
</span><span class=identifier
>y
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>());
</span>
355 <span class=special
>}
</span>
357 <span class=keyword
>template
</span><span class=special
><</span><b>arg set
1</b><span class=special
>,
</span><b>arg set
2</b><span class=special
>></span>
358 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
><(
</span>
359 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
1</b><span class=special
>>&</span> <span class=identifier
>x
</span><span class=special
>,
</span>
360 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
2</b><span class=special
>>&</span> <span class=identifier
>y
</span><span class=special
>)
</span>
361 <span class=special
>{
</span>
362 <span class=keyword
>return
</span> <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>lexicographical_compare
</span><span class=special
>(
</span><span class=identifier
>x
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>(),
</span><span class=identifier
>x
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>(),
</span><span class=identifier
>y
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>(),
</span><span class=identifier
>y
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>());
</span>
363 <span class=special
>}
</span>
365 <span class=keyword
>template
</span><span class=special
><</span><b>arg set
1</b><span class=special
>,
</span><b>arg set
2</b><span class=special
>></span>
366 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>!=(
</span>
367 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
1</b><span class=special
>>&</span> <span class=identifier
>x
</span><span class=special
>,
</span>
368 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
2</b><span class=special
>>&</span> <span class=identifier
>y
</span><span class=special
>)
</span>
369 <span class=special
>{
</span>
370 <span class=keyword
>return
</span> <span class=special
>!(
</span><span class=identifier
>x
</span><span class=special
>==
</span><span class=identifier
>y
</span><span class=special
>);
</span>
371 <span class=special
>}
</span>
373 <span class=keyword
>template
</span><span class=special
><</span><b>arg set
1</b><span class=special
>,
</span><b>arg set
2</b><span class=special
>></span>
374 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>>(
</span>
375 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
1</b><span class=special
>>&</span> <span class=identifier
>x
</span><span class=special
>,
</span>
376 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
2</b><span class=special
>>&</span> <span class=identifier
>y
</span><span class=special
>)
</span>
377 <span class=special
>{
</span>
378 <span class=keyword
>return
</span> <span class=identifier
>y
</span><span class=special
><</span><span class=identifier
>x
</span><span class=special
>;
</span>
379 <span class=special
>}
</span>
381 <span class=keyword
>template
</span><span class=special
><</span><b>arg set
1</b><span class=special
>,
</span><b>arg set
2</b><span class=special
>></span>
382 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>>=(
</span>
383 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
1</b><span class=special
>>&</span> <span class=identifier
>x
</span><span class=special
>,
</span>
384 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
2</b><span class=special
>>&</span> <span class=identifier
>y
</span><span class=special
>)
</span>
385 <span class=special
>{
</span>
386 <span class=keyword
>return
</span> <span class=special
>!(
</span><span class=identifier
>x
</span><span class=special
><</span><span class=identifier
>y
</span><span class=special
>);
</span>
387 <span class=special
>}
</span>
389 <span class=keyword
>template
</span><span class=special
><</span><b>arg set
1</b><span class=special
>,
</span><b>arg set
2</b><span class=special
>></span>
390 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
><=(
</span>
391 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
1</b><span class=special
>>&</span> <span class=identifier
>x
</span><span class=special
>,
</span>
392 <span class=keyword
>const
</span> <b>index class name
</b><span class=special
><</span><b>arg set
2</b><span class=special
>>&</span> <span class=identifier
>y
</span><span class=special
>)
</span>
393 <span class=special
>{
</span>
394 <span class=keyword
>return
</span> <span class=special
>!(
</span><span class=identifier
>x
</span><span class=special
>></span><span class=identifier
>y
</span><span class=special
>);
</span>
395 <span class=special
>}
</span>
397 <span class=comment
>// index specialized algorithms:
</span>
399 <span class=keyword
>template
</span><span class=special
><</span><b>implementation defined
</b><span class=special
>></span>
400 <span class=keyword
>void
</span> <span class=identifier
>swap
</span><span class=special
>(
</span><b>index class name
</b><span class=special
>&</span> <span class=identifier
>x
</span><span class=special
>,
</span><b>index class name
</b><span class=special
>&</span> <span class=identifier
>y
</span><span class=special
>);
</span>
402 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index::detail
</span>
404 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index
</span>
406 <span class=special
>}
</span> <span class=comment
>// namespace boost
</span>
409 <h4><a name=
"complexity_signature">Complexity signature
</a></h4>
412 Here and in the descriptions of operations of ordered indices, we adopt the
413 scheme outlined in the
414 <a href=
"indices.html#complexity_signature">complexity signature
415 section
</a>. The complexity signature of ordered indices is:
417 <li>copying:
<code>c(n)=n*log(n)
</code>,
</li>
418 <li>insertion:
<code>i(n)=log(n)
</code>,
</li>
419 <li>hinted insertion:
<code>h(n)=
1</code> (constant) if the hint element
420 is immediately after the point of insertion,
<code>h(n)=log(n)
</code> otherwise,
</li>
421 <li>deletion:
<code>d(n)=
1</code> (amortized constant),
</li>
422 <li>replacement:
<code>r(n)=
1</code> (constant) if the element position does not
423 change,
<code>r(n)=log(n)
</code> otherwise,
</li>
424 <li>modifying:
<code>m(n)=
1</code> (constant) if the element position does not
425 change,
<code>m(n)=log(n)
</code> otherwise.
</li>
429 <h4><a name=
"instantiation_types">Instantiation types
</a></h4>
431 <p>Ordered indices are instantiated internally to
<code>multi_index_container
</code> and
432 specified by means of
<a href=
"indices.html#indexed_by"><code>indexed_by
</code></a>
433 with
<a href=
"#unique_non_unique"> index specifiers
<code>ordered_unique
</code>
434 and
<code>ordered_non_unique
</code></a>. Instantiations are dependent on the
437 <li><code>Value
</code> from
<code>multi_index_container
</code>,
</li>
438 <li><code>Allocator
</code> from
<code>multi_index_container
</code>,
</li>
439 <li><code>TagList
</code> from the index specifier (if provided, otherwise
<code>tag
<></code> is assumed),
</li>
440 <li><code>KeyFromValue
</code> from the index specifier,
</li>
441 <li><code>Compare
</code> from the index specifier.
</li>
443 <code>TagList
</code> must be an instantiation of
444 <a href=
"indices.html#tag"><code>tag
</code></a>. The type
<code>KeyFromValue
</code>,
445 which determines the mechanism for extracting a key from
<code>Value
</code>,
446 must be a model of
<a href=
"key_extraction.html#key_extractors">
447 <code>Key Extractor
</code></a> from
<code>Value
</code>.
<code>Compare
</code> is a
448 <code>CopyConstructible
</code> binary predicate inducing a strict weak order
449 on elements of
<code>KeyFromValue::result_type
</code>.
452 <h4><a name=
"constructors">Constructors, copy and assignment
</a></h4>
455 As explained in the
<a href=
"indices.html#index_concepts">index
456 concepts section
</a>, indices do not have public constructors or destructors.
457 Assignment, on the other hand, is provided.
460 <code><b>index class name
</b>& operator=(const
<b>index class name
</b>& x);
</code>
465 <span class=identifier
>a
</span><span class=special
>=
</span><span class=identifier
>b
</span><span class=special
>;
</span>
467 where
<code>a
</code> and
<code>b
</code> are the
<code>multi_index_container
</code>
468 objects to which
<code>*this
</code> and
<code>x
</code> belong, respectively.
<br>
469 <b>Returns:
</b> <code>*this
</code>.
<br>
472 <code><b>index class name
</b>& operator=(std::initializer_list
<value_type
> list);
</code>
477 <span class=identifier
>a
</span><span class=special
>=
</span><span class=identifier
>list
</span><span class=special
>;
</span>
479 where
<code>a
</code> is the
<code>multi_index_container
</code>
480 object to which
<code>*this
</code> belongs.
<br>
481 <b>Returns:
</b> <code>*this
</code>.
<br>
484 <h4><a name=
"iterators">Iterators
</a></h4>
486 <code>iterator
iterator_to(const value_type
& x);
<br>
487 const_iterator iterator_to(const value_type
& x)const;
</code>
490 <b>Requires:
</b> <code>x
</code> is a reference to an element of the container.
<br>
491 <b>Returns:
</b> An iterator to
<code>x
</code>.
<br>
492 <b>Complexity:
</b> Constant.
<br>
493 <b>Exception safety:
</b> <code>nothrow
</code>.
<br>
496 <h4><a name=
"modifiers">Modifiers
</a></h4>
498 <code>template
<typename... Args
><br>
499 std::pair
<iterator,bool
> emplace(Args
&&... args);
</code>
502 <b>Requires:
</b> <code>value_type
</code> is
<code>EmplaceConstructible
</code>
503 into
<code>multi_index_container
</code> from
<code>args
</code>.
<br>
504 <b>Effects:
</b> Inserts a
<code>value_type
</code> object constructed with
505 <code>std::forward
<Args
>(args)...
</code> into the
<code>multi_index_container
</code> to which
508 <li>the index is non-unique OR no other element exists with
510 <li>AND insertion is allowed by all other indices of the
511 <code>multi_index_container
</code>.
</li>
513 <b>Returns:
</b> The return value is a pair
<code>p
</code>.
<code>p.second
</code>
514 is
<code>true
</code> if and only if insertion took place. On successful insertion,
515 <code>p.first
</code> points to the element inserted; otherwise,
<code>p.first
</code>
516 points to an element that caused the insertion to be banned. Note that more than
517 one element can be causing insertion not to be allowed.
<br>
518 <b>Complexity:
</b> <code>O(I(n))
</code>.
<br>
519 <b>Exception safety:
</b> Strong.
<br>
522 <code>template
<typename... Args
><br>
523 iterator emplace_hint(iterator position, Args
&&... args);
</code>
526 <b>Requires:
</b> <code>value_type
</code> is
<code>EmplaceConstructible
</code>
527 into
<code>multi_index_container
</code> from
<code>args
</code>.
528 <code>position
</code> is a valid iterator of the index.
<br>
529 <b>Effects:
</b> Inserts a
<code>value_type
</code> object constructed with
530 <code>std::forward
<Args
>(args)...
</code> into the
<code>multi_index_container
</code> to which
533 <li>the index is non-unique OR no other element exists with
535 <li>AND insertion is allowed by all other indices of the
536 <code>multi_index_container
</code>.
</li>
538 <code>position
</code> is used as a hint to improve the efficiency of the
539 operation. If successful, insertion happens as close as possible to the
540 location just prior to
<code>position
</code>.
<br>
541 <b>Returns:
</b> On successful insertion, an iterator to the newly inserted
542 element. Otherwise, an iterator to an element that caused the insertion to be
543 banned. Note that more than one element can be causing insertion not to be
545 <b>Complexity:
</b> <code>O(H(n))
</code>.
<br>
546 <b>Exception safety:
</b> Strong.
<br>
549 <code>std::pair
<iterator,bool
> insert(const value_type
& x);
</code><br>
550 <code>std::pair
<iterator,bool
> insert(value_type
&& x);
</code>
553 <b>Requires (first version):
</b> <code>value_type
</code> is
<code>CopyInsertable
</code>
554 into
<code>multi_index_container
</code>.
<br>
555 <b>Requires (second version):
</b> <code>value_type
</code> is
<code>MoveInsertable
</code>
556 into
<code>multi_index_container
</code>.
<br>
557 <b>Effects:
</b> Inserts
<code>x
</code> into the
<code>multi_index_container
</code> to which
560 <li>the index is non-unique OR no other element exists with
562 <li>AND insertion is allowed by all other indices of the
563 <code>multi_index_container
</code>.
</li>
565 <b>Returns:
</b> The return value is a pair
<code>p
</code>.
<code>p.second
</code>
566 is
<code>true
</code> if and only if insertion took place. On successful insertion,
567 <code>p.first
</code> points to the element inserted; otherwise,
<code>p.first
</code>
568 points to an element that caused the insertion to be banned. Note that more than
569 one element can be causing insertion not to be allowed.
<br>
570 <b>Complexity:
</b> <code>O(I(n))
</code>.
<br>
571 <b>Exception safety:
</b> Strong.
<br>
574 <code>iterator insert(iterator position,const value_type
& x);
</code><br>
575 <code>iterator insert(iterator position,value_type
&& x);
</code>
578 <b>Requires (first version):
</b> <code>value_type
</code> is
<code>CopyInsertable
</code>
579 into
<code>multi_index_container
</code>.
580 <code>position
</code> is a valid iterator of the index.
<br>
581 <b>Requires (second version):
</b> <code>value_type
</code> is
<code>MoveInsertable
</code>
582 into
<code>multi_index_container
</code>.
583 <code>position
</code> is a valid iterator of the index.
<br>
584 <b>Effects:
</b> Inserts
<code>x
</code> into the
<code>multi_index_container
</code> to which
587 <li>the index is non-unique OR no other element exists with
589 <li>AND insertion is allowed by all other indices of the
590 <code>multi_index_container
</code>.
</li>
592 <code>position
</code> is used as a hint to improve the efficiency of the
593 operation. If successful, insertion happens as close as possible to the
594 location just prior to
<code>position
</code>.
<br>
595 <b>Returns:
</b> On successful insertion, an iterator to the newly inserted
596 element. Otherwise, an iterator to an element that caused the insertion to be
597 banned. Note that more than one element can be causing insertion not to be
599 <b>Complexity:
</b> <code>O(H(n))
</code>.
<br>
600 <b>Exception safety:
</b> Strong.
<br>
603 <code>template
<typename InputIterator
><br>
604 void insert(InputIterator first,InputIterator last);
</code>
607 <b>Requires:
</b> <code>InputIterator
</code> is an input iterator.
608 <code>value_type
</code> is
<code>EmplaceConstructible
</code> into
609 <code>multi_index_container
</code> from
<code>*first
</code>.
610 <code>first
</code> and
<code>last
</code> are not iterators into any
611 index of the
<code>multi_index_container
</code> to which this index belongs.
612 <code>last
</code> is reachable from
<code>first
</code>.
<br>
614 For each element of [
<code>first
</code>,
<code>last
</code>), in this
615 order, inserts it into the
<code>multi_index_container
</code>
616 to which this index belongs if
618 <li>the index is non-unique OR no other element exists with
620 <li>AND insertion is allowed by all other indices of the
621 <code>multi_index_container
</code>.
</li>
623 <b>Complexity:
</b> <code>O(m*H(n+m))
</code>, where
624 <code>m
</code> is the number of elements in [
<code>first
</code>,
625 <code>last
</code>).
<br>
626 <b>Exception safety:
</b> Basic.
<br>
629 <code>void insert(std::initializer_list
<value_type
> list);
</code>
634 <span class=identifier
>insert
</span><span class=special
>(
</span><span class=identifier
>list
</span><span class=special
>.
</span><span class=identifier
>begin
</span><span class=special
>(),
</span><span class=identifier
>list
</span><span class=special
>.
</span><span class=identifier
>end
</span><span class=special
>())
</span><span class=special
>;
</span>
638 <code>iterator erase(iterator position);
</code>
641 <b>Requires:
</b> <code>position
</code> is a valid dereferenceable iterator
643 <b>Effects:
</b> Deletes the element pointed to by
<code>position
</code>.
<br>
644 <b>Returns:
</b> An iterator pointing to the element immediately following
645 the one that was deleted, or
<code>end()
</code>
646 if no such element exists.
<br>
647 <b>Complexity:
</b> <code>O(D(n))
</code>.
<br>
648 <b>Exception safety:
</b> <code>nothrow
</code>.
<br>
651 <code>size_type erase(const key_type
& x);
</code>
654 <b>Effects:
</b> Deletes the elements with key equivalent to
<code>x
</code>.
<br>
655 <b>Returns:
</b> Number of elements deleted.
<br>
656 <b>Complexity:
</b> <code>O(log(n) + m*D(n))
</code>, where
<code>m
</code> is
657 the number of elements deleted.
<br>
658 <b>Exception safety:
</b> Basic.
<br>
661 <code>iterator erase(iterator first,iterator last);
</code>
664 <b>Requires:
</b> [
<code>first
</code>,
<code>last
</code>) is a valid
665 range of the index.
<br>
666 <b>Effects:
</b> Deletes the elements in [
<code>first
</code>,
<code>last
</code>).
<br>
667 <b>Returns:
</b> <code>last
</code>.
<br>
668 <b>Complexity:
</b> <code>O(log(n) + m*D(n))
</code>, where
<code>m
</code> is
669 the number of elements in [
<code>first
</code>,
<code>last
</code>).
<br>
670 <b>Exception safety:
</b> <code>nothrow
</code>.
<br>
673 <a name=
"replace"><code>bool replace(iterator position,const value_type
& x);
</code></a><br>
674 <code>bool replace(iterator position,value_type
&& x);
</code>
677 <b>Requires (first version):
</b> <code>value_type
</code> is
<code>CopyAssignable
</code>.
678 <code>position
</code> is a valid dereferenceable iterator of the index.
<br>
679 <b>Requires (second version):
</b> <code>value_type
</code> is
<code>MoveAssignable
</code>.
680 <code>position
</code> is a valid dereferenceable iterator of the index.
<br>
681 <b>Effects:
</b> Assigns the value
<code>x
</code> to the element pointed
682 to by
<code>position
</code> into the
<code>multi_index_container
</code> to which
683 the index belongs if, for the value
<code>x
</code>
685 <li>the index is non-unique OR no other element exists
686 (except possibly
<code>*position
</code>) with equivalent key,
</li>
687 <li>AND replacing is allowed by all other indices of the
688 <code>multi_index_container
</code>.
</li>
690 <b>Postconditions:
</b> Validity of
<code>position
</code> is preserved
691 in all cases. If the key of the new value is equivalent to that of the
692 replaced value, the position of the element does not change.
<br>
693 <b>Returns:
</b> <code>true
</code> if the replacement took place,
694 <code>false
</code> otherwise.
<br>
695 <b>Complexity:
</b> <code>O(R(n))
</code>.
<br>
696 <b>Exception safety:
</b> Strong. If an exception is thrown by some
697 user-provided operation the
<code>multi_index_container
</code> to which the index
698 belongs remains in its original state.
702 <code>template
<typename Modifier
> bool modify(iterator position,Modifier mod);
</code></a>
705 <b>Requires:
</b> <code>mod
</code> is a unary function object
706 accepting arguments of type
707 <code>value_type
&</code>.
<code>position
</code> is a valid dereferenceable
708 iterator of the index.
709 The execution of
<code>mod(e)
</code>, where
<code>e
</code> is the element
710 pointed to by
<code>position
</code>, does not invoke any operation of the
711 <code>multi_index_container
</code> after
<code>e
</code> is directly modified
712 or, before modification, if the operation would invalidate
<code>position
</code>.
<br>
713 <b>Effects:
</b> Calls
<code>mod(e)
</code> where
<code>e
</code> is the element
714 pointed to by
<code>position
</code> and rearranges
<code>*position
</code> into
715 all the indices of the
<code>multi_index_container
</code>. Rearrangement is successful if
717 <li>the index is non-unique OR no other element exists
718 with equivalent key,
</li>
719 <li>AND rearrangement is allowed by all other indices of the
720 <code>multi_index_container
</code>.
</li>
722 If the rearrangement fails, the element is erased.
<br>
723 <b>Postconditions:
</b> Validity of
<code>position
</code> is preserved if the
724 operation succeeds. If the key of the modified value is equivalent to that of the
725 original value, the position of the element does not change.
<br>
726 <b>Returns:
</b> <code>true
</code> if the operation succeeded,
<code>false
</code>
728 <b>Complexity:
</b> <code>O(M(n))
</code>.
<br>
729 <b>Exception safety:
</b> Basic. If an exception is thrown by some
730 user-provided operation (except possibly
<code>mod
</code>), then
731 the element pointed to by
<code>position
</code> is erased.
734 <code>template
<typename Modifier,typename Rollback
><br>
735 bool modify(iterator position,Modifier mod,Rollback back);
</code>
738 <b>Requires:
</b> <code>mod
</code> and
<code>back
</code> are unary function
739 objects accepting arguments of type
740 <code>value_type
&</code>.
<code>position
</code> is a valid dereferenceable
741 iterator of the index.
742 The execution of
<code>mod(e)
</code>, where
<code>e
</code> is the element
743 pointed to by
<code>position
</code>, does not invoke any operation of the
744 <code>multi_index_container
</code> after
<code>e
</code> is directly modified
745 or, before modification, if the operation would invalidate
<code>position
</code>.
746 <code>back(e)
</code> does not invoke any operation of the
747 <code>multi_index_container
</code>.
748 The sequence of operations
<code>mod(e)
</code>,
749 <code>back(e)
</code> restores all keys of the element
750 to their original state.
<br>
751 <b>Effects:
</b> Calls
<code>mod(e)
</code> where
<code>e
</code> is the element
752 pointed to by
<code>position
</code> and tries to rearrange
<code>*position
</code> into
753 all the indices of the
<code>multi_index_container
</code>. Rearrangement is successful if
755 <li>the index is non-unique OR no other element exists
756 with equivalent key,
</li>
757 <li>AND rearrangement is allowed by all other indices of the
758 <code>multi_index_container
</code>.
</li>
760 If the rearrangement fails,
<code>back(e)
</code> is invoked and the
761 element is kept at its original position in all indices.
<br>
762 <b>Postconditions:
</b> Validity of
<code>position
</code> is preserved except if
763 the element is erased under the conditions described below.
764 If the key of the modified value is equivalent to that of the
765 original value, the position of the element does not change.
<br>
766 <b>Returns:
</b> <code>true
</code> if the operation succeeded,
<code>false
</code>
768 <b>Complexity:
</b> <code>O(M(n))
</code>.
<br>
769 <b>Exception safety:
</b> Strong, except if
<code>back
</code> throws an
770 exception, in which case the modified element is erased. If
<code>back
</code>
771 throws inside the handling code executing after some other user-provided
772 operation has thrown, it is the exception generated by
<code>back
</code> that
776 <a name=
"modify_key">
777 <code>template
<typename Modifier
> bool modify_key(iterator position,Modifier mod);
</code></a>
780 <b>Requires:
</b> <code>key_from_value
</code> is a read/write
781 <a href=
"key_extraction.html#key_extractors"><code>Key Extractor
</code></a>
782 from
<code>value_type
</code>.
<code>mod
</code> is a
783 unary function object accepting arguments of type
784 <code>key_type
&</code>.
<code>position
</code> is a valid dereferenceable
785 iterator of the index.
786 The execution of
<code>mod(k)
</code>, where
<code>k
</code> is the key of the element
787 pointed to by
<code>position
</code>, does not invoke any operation of the
788 <code>multi_index_container
</code> after
<code>k
</code> is directly modified
789 or, before modification, if the operation would invalidate
<code>position
</code>.
<br>
790 <b>Effects:
</b> Equivalent to
<code>modify(position,mod')
</code>,
791 with
<code>mod'
</code> defined in such a way that
792 <code>mod'(x)
</code> is the same as
<code>mod(key(x))
</code>, where
793 <code>key
</code> is the internal
<code>KeyFromValue
</code> object of the index.
796 <code>template
<typename Modifier,typename Rollback
><br>
797 bool modify_key(iterator position,Modifier mod,Rollback back);
</code>
800 <b>Requires:
</b> <code>key_from_value
</code> is a read/write
801 <a href=
"key_extraction.html#key_extractors"><code>Key Extractor
</code></a>
802 from
<code>value_type
</code>.
<code>mod
</code> and
<code>back
</code>
803 are unary function objects accepting arguments of type
804 <code>key_type
&</code>.
<code>position
</code> is a valid dereferenceable
805 iterator of the index.
806 The execution of
<code>mod(k)
</code>, where
<code>k
</code> is the key of the element
807 pointed to by
<code>position
</code>, does not invoke any operation of the
808 <code>multi_index_container
</code> after
<code>k
</code> is directly modified
809 or, before modification, if the operation would invalidate
<code>position
</code>.
810 <code>back(k)
</code> does not invoke any operation of the
811 <code>multi_index_container
</code>.
812 The sequence of operations
<code>mod(k)
</code>,
813 <code>back(k)
</code> restores
<code>k
</code> to its original state.
<br>
814 <b>Effects:
</b> Equivalent to
<code>modify(position,mod',back')
</code>,
815 with
<code>mod'
</code> and
<code>back
</code> defined in such a way that
816 <code>mod'(x)
</code> is the same as
<code>mod(key(x))
</code> and
817 <code>back'(x)
</code> is the same as
<code>back(key(x))
</code>, where
818 <code>key
</code> is the internal
<code>KeyFromValue
</code> object of the index.
821 <h4><a name=
"observers">Observers
</a></h4>
823 <p>Apart from standard
<code>key_comp
</code> and
<code>value_comp
</code>,
824 ordered indices have a member function for retrieving the internal key extractor
828 <code>key_from_value key_extractor()const;
</code>
831 Returns a copy of the
<code>key_from_value
</code> object used to construct
833 <b>Complexity:
</b> Constant.
836 <h4><a name=
"set_operations">Set operations
</a></h4>
839 Ordered indices provide the full lookup functionality required by
840 <b>[associative.reqmts]
</b>, namely
<code>find
</code>,
841 <code>count
</code>,
<code>lower_bound
</code>,
<code>upper_bound
</code>
842 and
<code>equal_range
</code>. Additionally, these member functions are
843 templatized to allow for non-standard arguments, so extending
844 the types of search operations allowed. The kind of arguments permissible
845 when invoking the lookup member functions is defined by the following
850 Consider a binary predicate
<code>Compare
</code> inducing a strict
851 weak order over values of type
<code>Key
</code>. A pair of types (
<code>CompatibleKey
</code>,
852 <code>CompatibleCompare
</code>) is said to be a
<i>compatible extension
</i>
853 of
<code>Compare
</code> if
855 <li><code>CompatibleCompare
</code> is a binary predicate over (
<code>Key
</code>,
856 <code>CompatibleKey
</code>),
</li>
857 <li><code>CompatibleCompare
</code> is a binary predicate over (
<code>CompatibleKey
</code>,
858 <code>Key
</code>),
</li>
859 <li>if
<code>c_comp(ck,k1)
</code> then
<code>!c_comp(k1,ck)
</code>,
</li>
860 <li>if
<code>!c_comp(ck,k1)
</code> and
<code>!comp(k1,k2)
</code> then
861 <code>!c_comp(ck,k2)
</code>,
</li>
862 <li>if
<code>!c_comp(k1,ck)
</code> and
<code>!comp(k2,k1)
</code> then
863 <code>!c_comp(k2,ck)
</code>,
</li>
865 for every
<code>c_comp
</code> of type
<code>CompatibleCompare
</code>,
866 <code>comp
</code> of type
<code>Compare
</code>,
<code>ck
</code> of type
867 <code>CompatibleKey
</code> and
<code>k1
</code>,
<code>k2
</code> of type
873 <p>Additionally, a type
<code>CompatibleKey
</code> is said to be a
874 <i>compatible key
</i> of
<code>Compare
</code> if (
<code>CompatibleKey
</code>,
875 <code>Compare
</code>) is a compatible extension of
<code>Compare
</code>.
876 This implies that
<code>Compare
</code>, as well as being a strict
877 weak ordering, accepts arguments of type
<code>CompatibleKey
</code>,
878 which usually means it has several overloads of
<code>operator()
</code>.
882 In the context of a compatible extension or a compatible key, the expressions
883 "equivalent",
"less than" and
"greater than" take on their obvious
887 <code>template
<typename CompatibleKey
> iterator find(const CompatibleKey
& x)const;
891 <b>Requires:
</b> <code>CompatibleKey
</code> is a compatible key of
892 <code>key_compare
</code>.
<br>
893 <b>Effects:
</b> Returns a pointer to an element whose key is equivalent to
894 <code>x
</code>, or
<code>end()
</code> if such an element does not exist.
<br>
895 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
898 <code>template
<typename CompatibleKey,typename CompatibleCompare
><br>
899 iterator find(const CompatibleKey
& x,const CompatibleCompare
& comp)const;
903 <b>Requires:
</b> (
<code>CompatibleKey
</code>,
<code>CompatibleCompare
</code>)
904 is a compatible extension of
<code>key_compare
</code>.
<br>
905 <b>Effects:
</b> Returns a pointer to an element whose key is equivalent to
906 <code>x
</code>, or
<code>end()
</code> if such an element does not exist.
<br>
907 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
910 <code>template
<typename CompatibleKey
> size_type
<br>
911 count(const CompatibleKey
& x)const;
915 <b>Requires:
</b> <code>CompatibleKey
</code> is a compatible key of
916 <code>key_compare
</code>.
<br>
917 <b>Effects:
</b> Returns the number of elements with key equivalent to
<code>x
</code>.
<br>
918 <b>Complexity:
</b> <code>O(log(n) + count(x))
</code>.
<br>
921 <code>template
<typename CompatibleKey,typename CompatibleCompare
><br>
922 size_type count(const CompatibleKey
& x,const CompatibleCompare
& comp)const;
926 <b>Requires:
</b> (
<code>CompatibleKey
</code>,
<code>CompatibleCompare
</code>)
927 is a compatible extension of
<code>key_compare
</code>.
<br>
928 <b>Effects:
</b> Returns the number of elements with key equivalent to
<code>x
</code>.
<br>
929 <b>Complexity:
</b> <code>O(log(n) + count(x,comp))
</code>.
<br>
932 <code>template
<typename CompatibleKey
><br>
933 iterator lower_bound(const CompatibleKey
& x)const;
937 <b>Requires:
</b> <code>CompatibleKey
</code> is a compatible key of
938 <code>key_compare
</code>.
<br>
939 <b>Effects:
</b> Returns an iterator pointing to the first element with
940 key not less than
<code>x
</code>, or
<code>end()
</code> if such an element does
942 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
945 <code>template
<typename CompatibleKey,typename CompatibleCompare
><br>
946 iterator lower_bound(const CompatibleKey
& x,const CompatibleCompare
& comp)const;
950 <b>Requires:
</b> (
<code>CompatibleKey
</code>,
<code>CompatibleCompare
</code>)
951 is a compatible extension of
<code>key_compare
</code>.
<br>
952 <b>Effects:
</b> Returns an iterator pointing to the first element with
953 key not less than
<code>x
</code>, or
<code>end()
</code> if such an element does
955 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
958 <code>template
<typename CompatibleKey
><br>
959 iterator upper_bound(const CompatibleKey
& x)const;
963 <b>Requires:
</b> <code>CompatibleKey
</code> is a compatible key of
964 <code>key_compare
</code>.
<br>
965 <b>Effects:
</b> Returns an iterator pointing to the first element with
966 key greater than
<code>x
</code>, or
<code>end()
</code> if such an element does
968 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
971 <code>template
<typename CompatibleKey,typename CompatibleCompare
><br>
972 iterator upper_bound(const CompatibleKey
& x,const CompatibleCompare
& comp)const;
976 <b>Requires:
</b> (
<code>CompatibleKey
</code>,
<code>CompatibleCompare
</code>)
977 is a compatible extension of
<code>key_compare
</code>.
<br>
978 <b>Effects:
</b> Returns an iterator pointing to the first element with
979 key greater than
<code>x
</code>, or
<code>end()
</code> if such an element does
981 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
984 <code>template
<typename CompatibleKey
><br>
985 std::pair
<iterator,iterator
> equal_range(
<br>
986 const CompatibleKey
& x)const;
990 <b>Requires:
</b> <code>CompatibleKey
</code> is a compatible key of
991 <code>key_compare
</code>.
<br>
992 <b>Effects:
</b> Equivalent to
<code>make_pair(lower_bound(x),upper_bound(x))
</code>.
<br>
993 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
996 <code>template
<typename CompatibleKey,typename CompatibleCompare
><br>
997 std::pair
<iterator,iterator
> equal_range(
<br>
998 const CompatibleKey
& x,const CompatibleCompare
& comp)const;
1002 <b>Requires:
</b> (
<code>CompatibleKey
</code>,
<code>CompatibleCompare
</code>)
1003 is a compatible extension of
<code>key_compare
</code>.
<br>
1004 <b>Effects:
</b> Equivalent to
1005 <code>make_pair(lower_bound(x,comp),upper_bound(x,comp))
</code>.
<br>
1006 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
1010 <h4><a name=
"range_operations">Range operations
</a></h4>
1013 The member function
<code>range
</code> is not defined for sorted associative
1014 containers, but ordered indices provide it as a convenient utility. A range
1015 or interval is defined by two conditions for the lower and upper bounds, which
1016 are modeled after the following concepts.
1020 Consider a binary predicate
<code>Compare
</code> inducing a strict
1021 weak order over values of type
<code>Key
</code>. A type
<code>LowerBounder
</code> is said to be
1022 a
<i>lower bounder
</i> of
<code>Compare
</code> if
1024 <li><code>LowerBounder
</code> is a predicate over
<code>Key
</code>,
</li>
1025 <li>if
<code>lower(k1)
</code> and
<code>!comp(k2,k1)
</code> then
1026 <code>lower(k2)
</code>,
</li>
1028 for every
<code>lower
</code> of type
<code>LowerBounder
</code>,
1029 <code>comp
</code> of type
<code>Compare
</code>, and
<code>k1
</code>,
1030 <code>k2
</code> of type
<code>Key
</code>. Similarly, an
<i>upper bounder
</i>
1031 is a type
<code>UpperBounder
</code> such that
1033 <li><code>UpperBounder
</code> is a predcate over
<code>Key
</code>,
</li>
1034 <li>if
<code>upper(k1)
</code> and
<code>!comp(k1,k2)
</code> then
1035 <code>upper(k2)
</code>,
</li>
1037 for every
<code>upper
</code> of type
<code>UpperBounder
</code>,
1038 <code>comp
</code> of type
<code>Compare
</code>, and
<code>k1
</code>,
1039 <code>k2
</code> of type
<code>Key
</code>.
1042 <code>template
<typename LowerBounder,typename UpperBounder
><br>
1043 std::pair
<iterator,iterator
> range(
<br>
1044 LowerBounder lower,UpperBounder upper)const;
1048 <b>Requires:
</b> <code>LowerBounder
</code> and
<code>UpperBounder
</code> are
1049 a lower and upper bounder of
<code>key_compare
</code>, respectively.
<br>
1050 <b>Effects:
</b> Returns a pair of iterators pointing to the beginning and one
1051 past the end of the subsequence of elements satisfying
<code>lower
</code> and
1052 <code>upper
</code> simultaneously. If no such elements exist, the iterators
1053 both point to the first element satisfying
<code>lower
</code>, or else
1054 are equal to
<code>end()
</code> if this latter element does not exist.
<br>
1055 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
1056 <b>Variants:
</b> In place of
<code>lower
</code> or
<code>upper
</code> (or both),
1057 the singular value
<code>boost::multi_index::unbounded
</code> can be
1058 provided. This acts as a predicate which all values of type
<code>key_type
</code>
1062 <h4><a name=
"serialization">Serialization
</a></h4>
1065 Indices cannot be serialized on their own, but only as part of the
1066 <code>multi_index_container
</code> into which they are embedded. In describing
1067 the additional preconditions and guarantees associated to ordered indices
1068 with respect to serialization of their embedding containers, we
1069 use the concepts defined in the
<code>multi_index_container
</code>
1070 <a href=
"multi_index_container.html#serialization">serialization section
</a>.
1073 Operation: saving of a
<code>multi_index_container
</code> <code>m
</code> to an
1074 output archive (XML archive)
<code>ar
</code>.
1077 <b>Requires:
</b> No additional requirements to those imposed by the container.
1080 Operation: loading of a
<code>multi_index_container
</code> <code>m'
</code> from an
1081 input archive (XML archive)
<code>ar
</code>.
1084 <b>Requires:
</b> Additionally to the general requirements,
<code>value_comp()
</code>
1085 must be serialization-compatible with
<code>m.get
<i
>().value_comp()
</code>,
1086 where
<code>i
</code> is the position of the ordered index in the container.
<br>
1087 <b>Postconditions:
</b> On successful loading, each of the elements of
1088 [
<code>begin()
</code>,
<code>end()
</code>) is a restored copy of the corresponding
1089 element in [
<code>m.get
<i
>().begin()
</code>,
<code>m.get
<i
>().end()
</code>).
1092 Operation: saving of an
<code>iterator
</code> or
<code>const_iterator
</code>
1093 <code>it
</code> to an output archive (XML archive)
<code>ar
</code>.
1096 <b>Requires:
</b> <code>it
</code> is a valid iterator of the index. The associated
1097 <code>multi_index_container
</code> has been previously saved.
1100 Operation: loading of an
<code>iterator
</code> or
<code>const_iterator
</code>
1101 <code>it'
</code> from an input archive (XML archive)
<code>ar
</code>.
1104 <b>Postconditions:
</b> On successful loading, if
<code>it
</code> was dereferenceable
1105 then
<code>*it'
</code> is the restored copy of
<code>*it
</code>, otherwise
1106 <code>it'==end()
</code>.
<br>
1107 <b>Note:
</b> It is allowed that
<code>it
</code> be a
<code>const_iterator
</code>
1108 and the restored
<code>it'
</code> an
<code>iterator
</code>, or viceversa.
1113 <div class=
"prev_link"><a href=
"indices.html"><img src=
"../prev.gif" alt=
"index reference" border=
"0"><br>
1116 <div class=
"up_link"><a href=
"index.html"><img src=
"../up.gif" alt=
"Boost.MultiIndex reference" border=
"0"><br>
1117 Boost.MultiIndex reference
1119 <div class=
"next_link"><a href=
"rnk_indices.html"><img src=
"../next.gif" alt=
"ranked indices" border=
"0"><br>
1121 </a></div><br clear=
"all" style=
"clear: all;">
1125 <p>Revised November
26th
2015</p>
1127 <p>© Copyright
2003-
2015 Joaqu
ín M L
ópez Mu
ñoz.
1128 Distributed under the Boost Software
1129 License, Version
1.0. (See accompanying file
<a href=
"../../../../LICENSE_1_0.txt">
1130 LICENSE_1_0.txt
</a> or copy at
<a href=
"http://www.boost.org/LICENSE_1_0.txt">
1131 http://www.boost.org/LICENSE_1_0.txt
</a>)
projects / ceph.git / blob