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 - Ranked 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 Ranked indices reference
</h1>
18 <div class=
"prev_link"><a href=
"ord_indices.html"><img src=
"../prev.gif" alt=
"ordered_indices" 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=
"hash_indices.html"><img src=
"../next.gif" alt=
"hashed indices" border=
"0"><br>
26 </a></div><br clear=
"all" style=
"clear: all;">
33 <li><a href=
"#rnk_index_fwd_synopsis">Header
34 <code>"boost/multi_index/ranked_index_fwd.hpp"</code> synopsis
</a></li>
35 <li><a href=
"#synopsis">Header
36 <code>"boost/multi_index/ranked_index.hpp"</code> synopsis
</a>
38 <li><a href=
"#unique_non_unique">
39 Index specifiers
<code>ranked_unique
</code> and
<code>ranked_non_unique
</code>
41 <li><a href=
"#rnk_indices">Ranked 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=
"#rank_operations">Rank operations
</a></li>
46 <li><a href=
"#serialization">Serialization
</a></li>
54 <a name=
"rnk_index_fwd_synopsis">Header
55 <a href=
"../../../../boost/multi_index/ranked_index_fwd.hpp">
56 <code>"boost/multi_index/ranked_index_fwd.hpp"</code></a> synopsis
</a></h2>
59 <span class=keyword
>namespace
</span> <span class=identifier
>boost
</span><span class=special
>{
</span>
61 <span class=keyword
>namespace
</span> <span class=identifier
>multi_index
</span><span class=special
>{
</span>
63 <span class=comment
>// index specifiers ranked_unique and ranked_non_unique
</span>
65 <span class=keyword
>template
</span><span class=special
><</span><b>consult ranked_unique reference for arguments
</b><span class=special
>></span>
66 <span class=keyword
>struct
</span> <span class=identifier
>ranked_unique
</span><span class=special
>;
</span>
67 <span class=keyword
>template
</span><span class=special
><</span><b>consult ranked_non_unique reference for arguments
</b><span class=special
>></span>
68 <span class=keyword
>struct
</span> <span class=identifier
>ranked_non_unique
</span><span class=special
>;
</span>
70 <span class=comment
>// indices
</span>
72 <span class=keyword
>namespace
</span> <span class=identifier
>detail
</span><span class=special
>{
</span>
74 <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>
76 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index::detail
</span>
78 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index
</span>
80 <span class=special
>}
</span> <span class=comment
>// namespace boost
</span>
84 <code>ranked_index_fwd.hpp
</code> provides forward declarations for index specifiers
85 <a href=
"#unique_non_unique"><code>ranked_unique
</code> and
<code>ranked_non_unique
</code></a> and
86 their associated
<a href=
"#rnk_indices">ranked index
</a> classes.
90 <a name=
"synopsis">Header
91 <a href=
"../../../../boost/multi_index/ranked_index.hpp">
92 <code>"boost/multi_index/ranked_index.hpp"</code></a> synopsis
</a></h2>
95 <span class=preprocessor
>#include
</span> <span class=special
><</span><span class=identifier
>initializer_list
</span><span class=special
>></span>
97 <span class=keyword
>namespace
</span> <span class=identifier
>boost
</span><span class=special
>{
</span>
99 <span class=keyword
>namespace
</span> <span class=identifier
>multi_index
</span><span class=special
>{
</span>
101 <span class=comment
>// index specifiers ranked_unique and ranked_non_unique
</span>
103 <span class=keyword
>template
</span><span class=special
><</span><b>consult ranked_unique reference for arguments
</b><span class=special
>></span>
104 <span class=keyword
>struct
</span> <span class=identifier
>ranked_unique
</span><span class=special
>;
</span>
105 <span class=keyword
>template
</span><span class=special
><</span><b>consult ranked_non_unique reference for arguments
</b><span class=special
>></span>
106 <span class=keyword
>struct
</span> <span class=identifier
>ranked_non_unique
</span><span class=special
>;
</span>
108 <span class=comment
>// indices
</span>
110 <span class=keyword
>namespace
</span> <span class=identifier
>detail
</span><span class=special
>{
</span>
112 <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>
114 <span class=comment
>// index comparison:
</span>
116 <span class=comment
>//
<b>OP
</b> is any of ==,
<,!=,
>,
>=,
<=
</span>
118 <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>
119 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span> <b><i>OP
</i></b><span class=special
>(
</span>
120 <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>
122 <span class=comment
>// index specialized algorithms:
</span>
124 <span class=keyword
>template
</span><span class=special
><</span><b>implementation defined
</b><span class=special
>></span>
125 <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>
127 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index::detail
</span>
129 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index
</span>
131 <span class=special
>}
</span> <span class=comment
>// namespace boost
</span>
134 <h3><a name=
"unique_non_unique">
135 Index specifiers
<code>ranked_unique
</code> and
<code>ranked_non_unique
</code>
139 These
<a href=
"indices.html#index_specification">index specifiers
</a> allow
140 for insertion of
<a href=
"#rnk_indices">ranked indices
</a> without and with
141 allowance of duplicate elements, respectively. The syntax of
<code>ranked_unique
</code>
142 and
<code>ranked_non_unique
</code> coincide, thus we describe them in a grouped manner.
143 <code>ranked_unique
</code> and
<code>ranked_non_unique
</code> can be instantiated in
144 two different forms, according to whether a tag list for the index is provided or not:
148 <span class=keyword
>template
</span><span class=special
><</span>
149 <span class=keyword
>typename
</span> <span class=identifier
>KeyFromValue
</span><span class=special
>,
</span>
150 <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>
151 <span class=special
>></span>
152 <span class=keyword
>struct
</span> <span class=special
>(
</span><span class=identifier
>ranked_unique
</span> <span class=special
>|
</span> <span class=identifier
>ranked_non_unique
</span><span class=special
>)
</span><span class=special
>;
</span>
154 <span class=keyword
>template
</span><span class=special
><</span>
155 <span class=keyword
>typename
</span> <span class=identifier
>TagList
</span><span class=special
>,
</span>
156 <span class=keyword
>typename
</span> <span class=identifier
>KeyFromValue
</span><span class=special
>,
</span>
157 <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>
158 <span class=special
>></span>
159 <span class=keyword
>struct
</span> <span class=special
>(
</span><span class=identifier
>ranked_unique
</span> <span class=special
>|
</span> <span class=identifier
>ranked_non_unique
</span><span class=special
>)
</span><span class=special
>;
</span>
163 If provided,
<code>TagList
</code> must be an instantiation of the class template
164 <a href=
"indices.html#tag"><code>tag
</code></a>.
165 The template arguments are used by the corresponding index implementation,
166 refer to the
<a href=
"#rnk_indices">ranked indices
</a> reference section for further
167 explanations on their acceptable type values.
170 <h3><a name=
"rnk_indices">Ranked indices
</a></h3>
173 Ranked indices are a variation of
<a href=
"ord_indices.html">ordered indices
</a>
174 providing additional capabilities for calculation of and access by rank; the
<i>rank
</i> of an element is the
175 distance to it from the beginning of the index. Besides this extension, ranked indices replicate the
176 public interface of ordered indices with the difference, complexity-wise, that
<a href=
"#complexity_signature">deletion
</a>
177 is done in logarithmic rather than constant time. Also, execution times and memory consumption are
178 expected to be poorer due to the internal bookkeeping needed to maintain rank-related information.
179 As with ordered indices, ranked indices can be unique (no duplicate elements are allowed)
180 or non-unique: either version is associated to a different index specifier, but
181 the interface of both index types is the same.
185 In what follows, we only describe the extra operations provided by ranked indices: for the
186 rest refer to the
<a href=
"ord_indices.html#ord_indices">documentation
</a> for ordered
187 indices, bearing in mind the occasional differences in complexity.
191 <span class=keyword
>namespace
</span> <span class=identifier
>boost
</span><span class=special
>{
</span>
193 <span class=keyword
>namespace
</span> <span class=identifier
>multi_index
</span><span class=special
>{
</span>
195 <b>implementation defined
</b><span class=identifier
>unbounded
</span><span class=special
>;
</span> <span class=comment
>// see range_rank()
</span>
197 <span class=keyword
>namespace
</span> <span class=identifier
>detail
</span><span class=special
>{
</span>
199 <span class=keyword
>template
</span><span class=special
><</span><b>implementation defined: dependent on types Value, Allocator,
200 TagList, KeyFromValue, Compare
</b><span class=special
>></span>
201 <span class=keyword
>class
</span> <b>name is implementation defined
</b>
202 <span class=special
>{
</span>
203 <span class=keyword
>public
</span><span class=special
>:
</span>
204 <span class=comment
>// types:
</span>
206 <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>
207 <span class=keyword
>typedef
</span> <span class=identifier
>Value
</span> <span class=identifier
>value_type
</span><span class=special
>;
</span>
208 <span class=keyword
>typedef
</span> <span class=identifier
>KeyFromValue
</span> <span class=identifier
>key_from_value
</span><span class=special
>;
</span>
209 <span class=keyword
>typedef
</span> <span class=identifier
>Compare
</span> <span class=identifier
>key_compare
</span><span class=special
>;
</span>
210 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>value_compare
</span><span class=special
>;
</span>
211 <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>
212 <span class=keyword
>typedef
</span> <span class=identifier
>TagList
</span> <span class=identifier
>tag_list
</span><span class=special
>;
</span>
213 <span class=keyword
>typedef
</span> <span class=identifier
>Allocator
</span> <span class=identifier
>allocator_type
</span><span class=special
>;
</span>
214 <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>
215 <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>
216 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>iterator
</span><span class=special
>;
</span>
217 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>const_iterator
</span><span class=special
>;
</span>
218 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>size_type
</span><span class=special
>;
</span>
219 <span class=keyword
>typedef
</span> <b>implementation defined
</b><span class=identifier
>difference_type
</span><span class=special
>;
</span>
220 <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>
221 <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>
222 <span class=keyword
>typedef
</span> <b>equivalent to
223 std::reverse_iterator
<iterator
></b> <span class=identifier
>reverse_iterator
</span><span class=special
>;
</span>
224 <span class=keyword
>typedef
</span> <b>equivalent to
225 std::reverse_iterator
<const_iterator
></b> <span class=identifier
>const_reverse_iterator
</span><span class=special
>;
</span>
227 <span class=comment
>// construct/copy/destroy:
</span>
229 <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>
230 <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>
232 <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>
234 <span class=comment
>// iterators:
</span>
236 <span class=identifier
>iterator
</span> <span class=identifier
>begin
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
237 <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>
238 <span class=identifier
>iterator
</span> <span class=identifier
>end
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
239 <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>
240 <span class=identifier
>reverse_iterator
</span> <span class=identifier
>rbegin
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
241 <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>
242 <span class=identifier
>reverse_iterator
</span> <span class=identifier
>rend
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
243 <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>
244 <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>
245 <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>
246 <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>
247 <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>
249 <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>
250 <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>
252 <span class=comment
>// capacity:
</span>
254 <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>
255 <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>
256 <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>
258 <span class=comment
>// modifiers:
</span>
260 <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>
261 <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>
262 <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>
263 <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>
264 <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>
265 <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>
266 <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>
267 <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>
268 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>InputIterator
</span><span class=special
>></span>
269 <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>
270 <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>
272 <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>
273 <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>
274 <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>
276 <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>
277 <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>
278 <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>
279 <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>
280 <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>
281 <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>
282 <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>
283 <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>
285 <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>
286 <span class=keyword
>void
</span> <span class=identifier
>clear
</span><span class=special
>()
</span><span class=keyword
>noexcept
</span><span class=special
>;
</span>
288 <span class=comment
>// observers:
</span>
290 <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>
291 <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>
292 <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>
294 <span class=comment
>// set operations:
</span>
296 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
297 <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>
298 <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>
299 <span class=identifier
>iterator
</span> <span class=identifier
>find
</span><span class=special
>(
</span>
300 <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>
302 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
303 <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>
304 <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>
305 <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>
307 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
308 <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>
309 <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>
310 <span class=identifier
>iterator
</span> <span class=identifier
>lower_bound
</span><span class=special
>(
</span>
311 <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>
313 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
314 <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>
315 <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>
316 <span class=identifier
>iterator
</span> <span class=identifier
>upper_bound
</span><span class=special
>(
</span>
317 <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>
319 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
320 <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>
321 <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>
322 <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>
323 <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>
324 <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>
326 <span class=comment
>// range:
</span>
328 <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>
329 <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>
330 <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>
332 <span class=comment
>// rank operations:
</span>
334 <span class=identifier
>iterator
</span> <span class=identifier
>nth
</span><span class=special
>(
</span><span class=identifier
>size_type
</span> <span class=identifier
>n
</span><span class=special
>)
</span><span class=keyword
>const
</span><span class=special
>;
</span>
335 <span class=identifier
>size_type
</span> <span class=identifier
>rank
</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=special
>;
</span>
337 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
338 <span class=identifier
>size_type
</span> <span class=identifier
>find_rank
</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>
339 <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>
340 <span class=identifier
>size_type
</span> <span class=identifier
>find_rank
</span><span class=special
>(
</span>
341 <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>
343 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
344 <span class=identifier
>size_type
</span> <span class=identifier
>lower_bound_rank
</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>
345 <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>
346 <span class=identifier
>size_type
</span> <span class=identifier
>lower_bound_rank
</span><span class=special
>(
</span>
347 <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>
349 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
350 <span class=identifier
>size_type
</span> <span class=identifier
>upper_bound_rank
</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>
351 <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>
352 <span class=identifier
>size_type
</span> <span class=identifier
>upper_bound_rank
</span><span class=special
>(
</span>
353 <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>
355 <span class=keyword
>template
</span><span class=special
><</span><span class=keyword
>typename
</span> <span class=identifier
>CompatibleKey
</span><span class=special
>></span>
356 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>size_type
</span><span class=special
>,
</span><span class=identifier
>size_type
</span><span class=special
>></span> <span class=identifier
>equal_range_rank
</span><span class=special
>(
</span>
357 <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>
358 <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>
359 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>size_type
</span><span class=special
>,
</span><span class=identifier
>size_type
</span><span class=special
>></span> <span class=identifier
>equal_range_rank
</span><span class=special
>(
</span>
360 <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>
362 <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>
363 <span class=identifier
>std
</span><span class=special
>::
</span><span class=identifier
>pair
</span><span class=special
><</span><span class=identifier
>size_type
</span><span class=special
>,
</span><span class=identifier
>size_type
</span><span class=special
>></span>
364 <span class=identifier
>range_rank
</span><span class=special
>(
</span><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>
365 <span class=special
>};
</span>
367 <span class=comment
>// index comparison:
</span>
369 <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>
370 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>==(
</span>
371 <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>
372 <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>
373 <span class=special
>{
</span>
374 <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>
375 <span class=special
>}
</span>
377 <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>
378 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
><(
</span>
379 <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>
380 <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>
381 <span class=special
>{
</span>
382 <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>
383 <span class=special
>}
</span>
385 <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>
386 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>!=(
</span>
387 <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>
388 <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>
389 <span class=special
>{
</span>
390 <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>
391 <span class=special
>}
</span>
393 <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>
394 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>>(
</span>
395 <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>
396 <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>
397 <span class=special
>{
</span>
398 <span class=keyword
>return
</span> <span class=identifier
>y
</span><span class=special
><</span><span class=identifier
>x
</span><span class=special
>;
</span>
399 <span class=special
>}
</span>
401 <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>
402 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
>>=(
</span>
403 <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>
404 <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>
405 <span class=special
>{
</span>
406 <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>
407 <span class=special
>}
</span>
409 <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>
410 <span class=keyword
>bool
</span> <span class=keyword
>operator
</span><span class=special
><=(
</span>
411 <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>
412 <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>
413 <span class=special
>{
</span>
414 <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>
415 <span class=special
>}
</span>
417 <span class=comment
>// index specialized algorithms:
</span>
419 <span class=keyword
>template
</span><span class=special
><</span><b>implementation defined
</b><span class=special
>></span>
420 <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>
422 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index::detail
</span>
424 <span class=special
>}
</span> <span class=comment
>// namespace boost::multi_index
</span>
426 <span class=special
>}
</span> <span class=comment
>// namespace boost
</span>
429 <h4><a name=
"complexity_signature">Complexity signature
</a></h4>
432 We follow the terminology described in the
433 <a href=
"indices.html#complexity_signature">complexity signature
434 section
</a>. The complexity signature of ranked indices is:
436 <li>copying:
<code>c(n)=n*log(n)
</code>,
</li>
437 <li>insertion:
<code>i(n)=log(n)
</code>,
</li>
438 <li>hinted insertion:
<code>h(n)=
1</code> (constant) if the hint element
439 is immediately after the point of insertion,
<code>h(n)=log(n)
</code> otherwise,
</li>
440 <li>deletion:
<b><code>d(n)=log(n)
</code></b> ,
</li>
441 <li>replacement:
<code>r(n)=
1</code> (constant) if the element position does not
442 change,
<code>r(n)=log(n)
</code> otherwise,
</li>
443 <li>modifying:
<code>m(n)=
1</code> (constant) if the element position does not
444 change,
<code>m(n)=log(n)
</code> otherwise.
</li>
448 These complexity guarantees are the same as those of
449 <a href=
"ord_indices.html#complexity_signature">ordered indices
</a>
450 except for deletion, which is
<code>log(n)
</code> here and amortized constant there.
453 <h4><a name=
"instantiation_types">Instantiation types
</a></h4>
455 <p>Ordered indices are instantiated internally to
<code>multi_index_container
</code> and
456 specified by means of
<a href=
"indices.html#indexed_by"><code>indexed_by
</code></a>
457 with
<a href=
"#unique_non_unique"> index specifiers
<code>ranked_unique
</code>
458 and
<code>ranked_non_unique
</code></a>. Instantiations are dependent on the
461 <li><code>Value
</code> from
<code>multi_index_container
</code>,
</li>
462 <li><code>Allocator
</code> from
<code>multi_index_container
</code>,
</li>
463 <li><code>TagList
</code> from the index specifier (if provided, otherwise
<code>tag
<></code> is assumed),
</li>
464 <li><code>KeyFromValue
</code> from the index specifier,
</li>
465 <li><code>Compare
</code> from the index specifier.
</li>
467 These types are subject to the same requirements as specified for
468 <a href=
"ord_indices.html#instantiation_types">ordered indices
</a>.
471 <h4><a name=
"rank_operations">Rank operations
</a></h4>
474 The
<i>rank
</i> of an iterator
<code>it
</code> of a given container
<code>c
</code> (and,
475 by extension, of the element it points to if the iterator is dereferenceable)
476 is
<code>std::distance(c.begin(),it)
</code>.
480 See the documentation of ordered indices for an explanation of the notions of
481 <a href=
"ord_indices.html#set_operations"><i>compatible extension
</i>,
482 <i>compatible key
</i></a>,
483 <a href=
"ord_indices.html#range_operations"><i>lower bounder
</i> and
<i>upper bounder
</i></a>, which are
487 <code>iterator nth(size_type n)const;
</code>
490 <b>Effects:
</b> Returns an iterator with rank
<code>n
</code>,
491 or
<code>end()
</code> if
<code>n
>=size()
</code>.
<br>
492 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
495 <code>size_type rank(iterator position)const;
499 <b>Requires:
</b> <code>position
</code> is a valid iterator of the index.
<br>
500 <b>Effects:
</b> Returns the rank of
<code>position
</code>.
<br>
501 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
504 <code>template
<typename CompatibleKey
> size_type find_rank(const CompatibleKey
& x)const;
508 <b>Requires:
</b> <code>CompatibleKey
</code> is a compatible key of
509 <code>key_compare
</code>.
<br>
510 <b>Effects:
</b> Equivalent to
<code>rank(find(k))
</code>.
<br>
511 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
514 <code>template
<typename CompatibleKey,typename CompatibleCompare
><br>
515 size_type find_rank(const CompatibleKey
& x,const CompatibleCompare
& comp)const;
519 <b>Requires:
</b> (
<code>CompatibleKey
</code>,
<code>CompatibleCompare
</code>)
520 is a compatible extension of
<code>key_compare
</code>.
<br>
521 <b>Effects:
</b> Equivalent to
<code>rank(find(x,comp))
</code>.
<br>
522 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
525 <code>template
<typename CompatibleKey
><br>
526 size_type lower_bound_rank(const CompatibleKey
& x)const;
530 <b>Requires:
</b> <code>CompatibleKey
</code> is a compatible key of
531 <code>key_compare
</code>.
<br>
532 <b>Effects:
</b> Equivalent to
<code>rank(lower_bound(x))
</code>.
<br>
533 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
536 <code>template
<typename CompatibleKey,typename CompatibleCompare
><br>
537 size_type lower_bound_rank(const CompatibleKey
& x,const CompatibleCompare
& comp)const;
541 <b>Requires:
</b> (
<code>CompatibleKey
</code>,
<code>CompatibleCompare
</code>)
542 is a compatible extension of
<code>key_compare
</code>.
<br>
543 <b>Effects:
</b> Equivalent to
<code>rank(lower_bound(x,comp))
</code>.
<br>
544 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
547 <code>template
<typename CompatibleKey
><br>
548 size_type upper_bound_rank(const CompatibleKey
& x)const;
552 <b>Requires:
</b> <code>CompatibleKey
</code> is a compatible key of
553 <code>key_compare
</code>.
<br>
554 <b>Effects:
</b> Equivalent to
<code>rank(upper_bound(x))
</code>.
<br>
555 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
558 <code>template
<typename CompatibleKey,typename CompatibleCompare
><br>
559 size_type upper_bound_rank(const CompatibleKey
& x,const CompatibleCompare
& comp)const;
563 <b>Requires:
</b> (
<code>CompatibleKey
</code>,
<code>CompatibleCompare
</code>)
564 is a compatible extension of
<code>key_compare
</code>.
<br>
565 <b>Effects:
</b> Equivalent to
<code>rank(upper_bound(x,comp))
</code>.
<br>
566 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
569 <code>template
<typename CompatibleKey
><br>
570 std::pair
<size_type,size_type
> equal_range_rank(
<br>
571 const CompatibleKey
& x)const;
575 <b>Requires:
</b> <code>CompatibleKey
</code> is a compatible key of
576 <code>key_compare
</code>.
<br>
577 <b>Effects:
</b> Equivalent to
<code>make_pair(lower_bound_rank(x),upper_bound_rank(x))
</code>.
<br>
578 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
581 <code>template
<typename CompatibleKey,typename CompatibleCompare
><br>
582 std::pair
<size_type,size_type
> equal_range_rank(
<br>
583 const CompatibleKey
& x,const CompatibleCompare
& comp)const;
587 <b>Requires:
</b> (
<code>CompatibleKey
</code>,
<code>CompatibleCompare
</code>)
588 is a compatible extension of
<code>key_compare
</code>.
<br>
589 <b>Effects:
</b> Equivalent to
590 <code>make_pair(lower_bound_rank(x,comp),upper_bound_rank(x,comp))
</code>.
<br>
591 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
594 <code>template
<typename LowerBounder,typename UpperBounder
><br>
595 std::pair
<size_type,size_type
> range_rank(
<br>
596 LowerBounder lower,UpperBounder upper)const;
600 <b>Requires:
</b> <code>LowerBounder
</code> and
<code>UpperBounder
</code> are
601 a lower and upper bounder of
<code>key_compare
</code>, respectively.
<br>
602 <b>Effects:
</b> Equivalent to
604 <span class=keyword
>auto
</span> <span class=identifier
>p
</span><span class=special
>=
</span><span class=identifier
>range
</span><span class=special
>(
</span><span class=identifier
>lower
</span><span class=special
>,
</span><span class=identifier
>upper
</span><span class=special
>);
</span>
605 <span class=keyword
>return
</span> <span class=identifier
>make_pair
</span><span class=special
>(
</span><span class=identifier
>rank
</span><span class=special
>(
</span><span class=identifier
>p
</span><span class=special
>.
</span><span class=identifier
>first
</span><span class=special
>),
</span><span class=identifier
>rank
</span><span class=special
>(
</span><span class=identifier
>p
</span><span class=special
>.
</span><span class=identifier
>second
</span><span class=special
>));
</span>
607 <b>Complexity:
</b> <code>O(log(n))
</code>.
<br>
608 <b>Variants:
</b> In place of
<code>lower
</code> or
<code>upper
</code> (or both),
609 the singular value
<code>boost::multi_index::unbounded
</code> can be
610 provided. This acts as a predicate which all values of type
<code>key_type
</code>
614 <h4><a name=
"serialization">Serialization
</a></h4>
617 The prerequisites and postconditions associated to serialization of
618 <code>multi_index_container
</code>s with ranked indices are exactly the same
619 as those of
<a href=
"ord_indices.html#serialization">ordered indices
</a>.
623 <div class=
"prev_link"><a href=
"ord_indices.html"><img src=
"../prev.gif" alt=
"ordered_indices" border=
"0"><br>
626 <div class=
"up_link"><a href=
"index.html"><img src=
"../up.gif" alt=
"Boost.MultiIndex reference" border=
"0"><br>
627 Boost.MultiIndex reference
629 <div class=
"next_link"><a href=
"hash_indices.html"><img src=
"../next.gif" alt=
"hashed indices" border=
"0"><br>
631 </a></div><br clear=
"all" style=
"clear: all;">
635 <p>Revised May
4th
2015</p>
637 <p>© Copyright
2003-
2015 Joaqu
ín M L
ópez Mu
ñoz.
638 Distributed under the Boost Software
639 License, Version
1.0. (See accompanying file
<a href=
"../../../../LICENSE_1_0.txt">
640 LICENSE_1_0.txt
</a> or copy at
<a href=
"http://www.boost.org/LICENSE_1_0.txt">
641 http://www.boost.org/LICENSE_1_0.txt
</a>)