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><</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> 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><</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> 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><</span><span class=identifier>initializer_list</span><span class=special>></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><</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> 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><</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> 113 114<span class=comment>// index comparison:</span> 115 116<span class=comment>// <b>OP</b> is any of ==,<,!=,>,>=,<=</span> 117 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> 121 122<span class=comment>// index specialized algorithms:</span> 123 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> 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><</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> 153 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> 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><</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> 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><</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> 226 227 <span class=comment>// construct/copy/destroy:</span> 228 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> 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>&</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> 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><</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> 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>&</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>&</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> 284 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> 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><</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> 301 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> 306 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> 312 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> 318 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> 325 326 <span class=comment>// range:</span> 327 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> 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><</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> 342 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> 348 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> 354 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> 361 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> 366 367<span class=comment>// index comparison:</span> 368 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> 376 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> 384 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> 392 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> 400 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> 408 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> 416 417<span class=comment>// index specialized algorithms:</span> 418 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> 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<></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>=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<typename CompatibleKey> size_type find_rank(const CompatibleKey& 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<typename CompatibleKey,typename CompatibleCompare><br> 515size_type find_rank(const CompatibleKey& x,const CompatibleCompare& 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<typename CompatibleKey><br> 526size_type lower_bound_rank(const CompatibleKey& 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<typename CompatibleKey,typename CompatibleCompare><br> 537size_type lower_bound_rank(const CompatibleKey& x,const CompatibleCompare& 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<typename CompatibleKey><br> 548size_type upper_bound_rank(const CompatibleKey& 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<typename CompatibleKey,typename CompatibleCompare><br> 559size_type upper_bound_rank(const CompatibleKey& x,const CompatibleCompare& 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<typename CompatibleKey><br> 570std::pair<size_type,size_type> equal_range_rank(<br> 571 const CompatibleKey& 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<typename CompatibleKey,typename CompatibleCompare><br> 582std::pair<size_type,size_type> equal_range_rank(<br> 583 const CompatibleKey& x,const CompatibleCompare& 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<typename LowerBounder,typename UpperBounder><br> 595std::pair<size_type,size_type> range_rank(<br> 596 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>© Copyright 2003-2015 Joaquín M López Muñ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> 646
