Gitiles
Code Review Sign In
realtimeroboticsgroup.org / RealtimeRoboticsGroup / test / 3cbbaca6b1a4c98b648739251c948e49c6980ad9 / . / doc / reference / rnk_indices.html
blob: 9a5a960c0441665e051c587696bfb949f4234629 [file] [log] [blame]
Brian Silverman3cbbaca2018-08-04 23:38:07 -0700[diff] [blame^]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
2
3<html>
4<head>
5<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
6<title>Boost.MultiIndex Documentation - 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">
12</head>
13
14<body>
15<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
16"middle" width="277" height="86">Boost.MultiIndex Ranked indices reference</h1>
17
18<div class="prev_link"><a href="ord_indices.html"><img src="../prev.gif" alt="ordered_indices" border="0"><br>
19Ordered indices
20</a></div>
21<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
22Boost.MultiIndex reference
23</a></div>
24<div class="next_link"><a href="hash_indices.html"><img src="../next.gif" alt="hashed indices" border="0"><br>
25Hashed indices
26</a></div><br clear="all" style="clear: all;">
27
28<hr>
29
30<h2>Contents</h2>
31
32<ul>
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>
37 <ul>
38 <li><a href="#unique_non_unique">
39 Index specifiers <code>ranked_unique</code> and <code>ranked_non_unique</code>
40 </a></li>
41 <li><a href="#rnk_indices">Ranked indices</a>
42 <ul>
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>
47 </ul>
48 </li>
49 </ul>
50 </li>
51</ul>
52
53<h2>
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>
57
58<blockquote><pre>
59<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
60
61<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
62
63<span class=comment>// index specifiers ranked_unique and ranked_non_unique</span>
64
65<span class=keyword>template</span><span class=special>&lt;</span><b>consult ranked_unique reference for arguments</b><span class=special>&gt;</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>&lt;</span><b>consult ranked_non_unique reference for arguments</b><span class=special>&gt;</span>
68<span class=keyword>struct</span> <span class=identifier>ranked_non_unique</span><span class=special>;</span>
69
70<span class=comment>// indices</span>
71
72<span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
73
74<span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined</b><span class=special>&gt;</span> <span class=keyword>class</span> <b>index name is implementation defined</b><span class=special>;</span>
75
76<span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
77
78<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
79
80<span class=special>}</span> <span class=comment>// namespace boost</span>
81</pre></blockquote>
82
83<p>
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
86their associated <a href="#rnk_indices">ranked index</a> classes.
87</p>
88
89<h2>
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>
93
94<blockquote><pre>
95<span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>initializer_list</span><span class=special>&gt;</span>
96
97<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
98
99<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
100
101<span class=comment>// index specifiers ranked_unique and ranked_non_unique</span>
102
103<span class=keyword>template</span><span class=special>&lt;</span><b>consult ranked_unique reference for arguments</b><span class=special>&gt;</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>&lt;</span><b>consult ranked_non_unique reference for arguments</b><span class=special>&gt;</span>
106<span class=keyword>struct</span> <span class=identifier>ranked_non_unique</span><span class=special>;</span>
107
108<span class=comment>// indices</span>
109
110<span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
111
112<span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined</b><span class=special>&gt;</span> <span class=keyword>class</span> <b>index class name implementation defined</b><span class=special>;</span>
113
114<span class=comment>// index comparison:</span>
115
116<span class=comment>// <b>OP</b> is any of ==,&lt;,!=,&gt;,&gt;=,&lt;=</span>
117
118<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</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>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</span> <span class=identifier>y</span><span class=special>);</span>
121
122<span class=comment>// index specialized algorithms:</span>
123
124<span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined</b><span class=special>&gt;</span>
125<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>,</span><b>index class name</b><span class=special>&amp;</span> <span class=identifier>y</span><span class=special>);</span>
126
127<span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
128
129<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
130
131<span class=special>}</span> <span class=comment>// namespace boost</span>
132</pre></blockquote>
133
134<h3><a name="unique_non_unique">
135Index specifiers <code>ranked_unique</code> and <code>ranked_non_unique</code>
136</a></h3>
137
138<p>
139These <a href="indices.html#index_specification">index specifiers</a> allow
140for insertion of <a href="#rnk_indices">ranked indices</a> without and with
141allowance of duplicate elements, respectively. The syntax of <code>ranked_unique</code>
142and <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
144two different forms, according to whether a tag list for the index is provided or not:
145</p>
146
147<blockquote><pre>
148<span class=keyword>template</span><span class=special>&lt;</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>&lt;</span><span class=identifier>KeyFromValue</span><span class=special>::</span><span class=identifier>result_type</span><span class=special>&gt;</span>
151<span class=special>&gt;</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>
153
154<span class=keyword>template</span><span class=special>&lt;</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>&lt;</span><span class=identifier>KeyFromValue</span><span class=special>::</span><span class=identifier>result_type</span><span class=special>&gt;</span>
158<span class=special>&gt;</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>
160</pre></blockquote>
161
162<p>
163If provided, <code>TagList</code> must be an instantiation of the class template
164<a href="indices.html#tag"><code>tag</code></a>.
165The template arguments are used by the corresponding index implementation,
166refer to the <a href="#rnk_indices">ranked indices</a> reference section for further
167explanations on their acceptable type values.
168</p>
169
170<h3><a name="rnk_indices">Ranked indices</a></h3>
171
172<p>
173Ranked indices are a variation of <a href="ord_indices.html">ordered indices</a>
174providing additional capabilities for calculation of and access by rank; the <i>rank</i> of an element is the
175distance to it from the beginning of the index. Besides this extension, ranked indices replicate the
176public interface of ordered indices with the difference, complexity-wise, that <a href="#complexity_signature">deletion</a>
177is done in logarithmic rather than constant time. Also, execution times and memory consumption are
178expected to be poorer due to the internal bookkeeping needed to maintain rank-related information.
179As with ordered indices, ranked indices can be unique (no duplicate elements are allowed)
180or non-unique: either version is associated to a different index specifier, but
181the interface of both index types is the same.
182</p>
183
184<p>
185In what follows, we only describe the extra operations provided by ranked indices: for the
186rest refer to the <a href="ord_indices.html#ord_indices">documentation</a> for ordered
187indices, bearing in mind the occasional differences in complexity.
188</p>
189
190<blockquote><pre>
191<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
192
193<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
194
195<b>implementation defined </b><span class=identifier>unbounded</span><span class=special>;</span> <span class=comment>// see range_rank()</span>
196
197<span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
198
199<span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined: dependent on types Value, Allocator,
200 TagList, KeyFromValue, Compare</b><span class=special>&gt;</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>
205
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>&lt;</span><span class=identifier>key_from_value</span><span class=special>,</span><span class=identifier>key_compare</span><span class=special>&gt;</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&lt;iterator&gt;</b> <span class=identifier>reverse_iterator</span><span class=special>;</span>
224 <span class=keyword>typedef</span> <b>equivalent to
225 std::reverse_iterator&lt;const_iterator&gt;</b> <span class=identifier>const_reverse_iterator</span><span class=special>;</span>
226
227 <span class=comment>// construct/copy/destroy:</span>
228
229 <b>index class name</b><span class=special>&amp;</span> <span class=keyword>operator</span><span class=special>=(</span><span class=keyword>const</span> <b>index class name</b><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>);</span>
230 <b>index class name</b><span class=special>&amp;</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>&lt;</span><span class=identifier>value_type</span><span class=special>&gt;</span> <span class=identifier>list</span><span class=special>);</span>
231
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>
233
234 <span class=comment>// iterators:</span>
235
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>
248
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>&amp;</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>&amp;</span> <span class=identifier>x</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
251
252 <span class=comment>// capacity:</span>
253
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>
257
258 <span class=comment>// modifiers:</span>
259
260 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span><span class=special>...</span> <span class=identifier>Args</span><span class=special>&gt;</span>
261 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=keyword>bool</span><span class=special>&gt;</span> <span class=identifier>emplace</span><span class=special>(</span><span class=identifier>Args</span><span class=special>&amp;&amp;...</span> <span class=identifier>args</span><span class=special>);</span>
262 <span class=keyword>template</span> <span class=special>&lt;</span><span class=keyword>typename</span><span class=special>...</span> <span class=identifier>Args</span><span class=special>&gt;</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>&amp;&amp;...</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>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=keyword>bool</span><span class=special>&gt;</span> <span class=identifier>insert</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&amp;</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>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=keyword>bool</span><span class=special>&gt;</span> <span class=identifier>insert</span><span class=special>(</span><span class=identifier>value_type</span><span class=special>&amp;&amp;</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>&amp;</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>&amp;&amp;</span> <span class=identifier>x</span><span class=special>);</span>
268 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>InputIterator</span><span class=special>&gt;</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>&lt;</span><span class=identifier>value_type</span><span class=special>&gt;</span> <span class=identifier>list</span><span class=special>);</span>
271
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>&amp;</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>
275
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>&amp;</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>&amp;&amp;</span> <span class=identifier>x</span><span class=special>);</span>
278 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>Modifier</span><span class=special>&gt;</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>&lt;</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>&gt;</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>&lt;</span><span class=keyword>typename</span> <span class=identifier>Modifier</span><span class=special>&gt;</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>&lt;</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>&gt;</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>
284
285 <span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&amp;</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>
287
288 <span class=comment>// observers:</span>
289
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>
293
294 <span class=comment>// set operations:</span>
295
296 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
301
302 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
306
307 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
312
313 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
318
319 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</span>
320 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>iterator</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</span>
323 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>iterator</span><span class=special>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
325
326 <span class=comment>// range:</span>
327
328 <span class=keyword>template</span><span class=special>&lt;</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>&gt;</span>
329 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>iterator</span><span class=special>&gt;</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>
331
332 <span class=comment>// rank operations:</span>
333
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>
336
337 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
342
343 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
348
349 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
354
355 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>CompatibleKey</span><span class=special>&gt;</span>
356 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>size_type</span><span class=special>,</span><span class=identifier>size_type</span><span class=special>&gt;</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>&amp;</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>&lt;</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>&gt;</span>
359 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>size_type</span><span class=special>,</span><span class=identifier>size_type</span><span class=special>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>CompatibleCompare</span><span class=special>&amp;</span> <span class=identifier>comp</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
361
362 <span class=keyword>template</span><span class=special>&lt;</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>&gt;</span>
363 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>size_type</span><span class=special>,</span><span class=identifier>size_type</span><span class=special>&gt;</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>
366
367<span class=comment>// index comparison:</span>
368
369<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</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>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
372 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>()&amp;&amp;</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>
376
377<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</span>
378<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;(</span>
379 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
380 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>
384
385<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</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>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
388 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>
392
393<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</span>
394<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&gt;(</span>
395 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
396 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>&lt;</span><span class=identifier>x</span><span class=special>;</span>
399<span class=special>}</span>
400
401<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</span>
402<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&gt;=(</span>
403 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
404 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>&lt;</span><span class=identifier>y</span><span class=special>);</span>
407<span class=special>}</span>
408
409<span class=keyword>template</span><span class=special>&lt;</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>&gt;</span>
410<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;=(</span>
411 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 1</b><span class=special>&gt;&amp;</span> <span class=identifier>x</span><span class=special>,</span>
412 <span class=keyword>const</span> <b>index class name</b><span class=special>&lt;</span><b>arg set 2</b><span class=special>&gt;&amp;</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>&gt;</span><span class=identifier>y</span><span class=special>);</span>
415<span class=special>}</span>
416
417<span class=comment>// index specialized algorithms:</span>
418
419<span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined</b><span class=special>&gt;</span>
420<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>,</span><b>index class name</b><span class=special>&amp;</span> <span class=identifier>y</span><span class=special>);</span>
421
422<span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
423
424<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
425
426<span class=special>}</span> <span class=comment>// namespace boost</span>
427</pre></blockquote>
428
429<h4><a name="complexity_signature">Complexity signature</a></h4>
430
431<p>
432We follow the terminology described in the
433<a href="indices.html#complexity_signature">complexity signature
434section</a>. The complexity signature of ranked indices is:
435<ul>
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>
445</ul>
446</p>
447<p>
448These complexity guarantees are the same as those of
449<a href="ord_indices.html#complexity_signature">ordered indices</a>
450except for deletion, which is <code>log(n)</code> here and amortized constant there.
451</p>
452
453<h4><a name="instantiation_types">Instantiation types</a></h4>
454
455<p>Ordered indices are instantiated internally to <code>multi_index_container</code> and
456specified by means of <a href="indices.html#indexed_by"><code>indexed_by</code></a>
457with <a href="#unique_non_unique"> index specifiers <code>ranked_unique</code>
458and <code>ranked_non_unique</code></a>. Instantiations are dependent on the
459following types:
460<ul>
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&lt;&gt;</code> is assumed),</li>
464 <li><code>KeyFromValue</code> from the index specifier,</li>
465 <li><code>Compare</code> from the index specifier.</li>
466</ul>
467These types are subject to the same requirements as specified for
468<a href="ord_indices.html#instantiation_types">ordered indices</a>.
469</p>
470
471<h4><a name="rank_operations">Rank operations</a></h4>
472
473<p>
474The <i>rank</i> of an iterator <code>it</code> of a given container <code>c</code> (and,
475by extension, of the element it points to if the iterator is dereferenceable)
476is <code>std::distance(c.begin(),it)</code>.
477</p>
478
479<p>
480See 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
484referred to below.
485</p>
486
487<code>iterator nth(size_type n)const;</code>
488
489<blockquote>
490<b>Effects:</b> Returns an iterator with rank <code>n</code>,
491or <code>end()</code> if <code>n&gt;=size()</code>.<br>
492<b>Complexity:</b> <code>O(log(n))</code>.<br>
493</blockquote>
494
495<code>size_type rank(iterator position)const;
496</code>
497
498<blockquote>
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>
502</blockquote>
503
504<code>template&lt;typename CompatibleKey> size_type find_rank(const CompatibleKey&amp; x)const;
505</code>
506
507<blockquote>
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>
512</blockquote>
513
514<code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
515size_type find_rank(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
516</code>
517
518<blockquote>
519<b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
520is 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>
523</blockquote>
524
525<code>template&lt;typename CompatibleKey><br>
526size_type lower_bound_rank(const CompatibleKey&amp; x)const;
527</code>
528
529<blockquote>
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>
534</blockquote>
535
536<code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
537size_type lower_bound_rank(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
538</code>
539
540<blockquote>
541<b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
542is 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>
545</blockquote>
546
547<code>template&lt;typename CompatibleKey><br>
548size_type upper_bound_rank(const CompatibleKey&amp; x)const;
549</code>
550
551<blockquote>
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>
556</blockquote>
557
558<code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
559size_type upper_bound_rank(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
560</code>
561
562<blockquote>
563<b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
564is 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>
567</blockquote>
568
569<code>template&lt;typename CompatibleKey><br>
570std::pair&lt;size_type,size_type> equal_range_rank(<br>
571&nbsp;&nbsp;const CompatibleKey&amp; x)const;
572</code>
573
574<blockquote>
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>
579</blockquote>
580
581<code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
582std::pair&lt;size_type,size_type> equal_range_rank(<br>
583&nbsp;&nbsp;const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
584</code>
585
586<blockquote>
587<b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
588is 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>
592</blockquote>
593
594<code>template&lt;typename LowerBounder,typename UpperBounder><br>
595std::pair&lt;size_type,size_type> range_rank(<br>
596&nbsp;&nbsp;LowerBounder lower,UpperBounder upper)const;
597</code>
598
599<blockquote>
600<b>Requires:</b> <code>LowerBounder</code> and <code>UpperBounder</code> are
601a lower and upper bounder of <code>key_compare</code>, respectively.<br>
602<b>Effects:</b> Equivalent to
603<blockquote><pre>
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>
606</pre></blockquote>
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),
609the singular value <code>boost::multi_index::unbounded</code> can be
610provided. This acts as a predicate which all values of type <code>key_type</code>
611satisfy.<br>
612</blockquote>
613
614<h4><a name="serialization">Serialization</a></h4>
615
616<p>
617The prerequisites and postconditions associated to serialization of
618<code>multi_index_container</code>s with ranked indices are exactly the same
619as those of <a href="ord_indices.html#serialization">ordered indices</a>.
620
621<hr>
622
623<div class="prev_link"><a href="ord_indices.html"><img src="../prev.gif" alt="ordered_indices" border="0"><br>
624Ordered indices
625</a></div>
626<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
627Boost.MultiIndex reference
628</a></div>
629<div class="next_link"><a href="hash_indices.html"><img src="../next.gif" alt="hashed indices" border="0"><br>
630Hashed indices
631</a></div><br clear="all" style="clear: all;">
632
633<br>
634
635<p>Revised May 4th 2015</p>
636
637<p>&copy; Copyright 2003-2015 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
638Distributed under the Boost Software
639License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
640LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
641http://www.boost.org/LICENSE_1_0.txt</a>)
642</p>
643
644</body>
645</html>