ceph/src/boost/libs/multi_index/doc/reference/rnk_indices.html

   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>
  19 Ordered indices
  20 </a></div>
  21 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
  22 Boost.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>
  25 Hashed 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
  86 their 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">
 135 Index specifiers <code>ranked_unique</code> and <code>ranked_non_unique</code>
 136 </a></h3>
 137
 138 <p>
 139 These <a href="indices.html#index_specification">index specifiers</a> allow
 140 for insertion of <a href="#rnk_indices">ranked indices</a> without and with
 141 allowance of duplicate elements, respectively. The syntax of <code>ranked_unique</code>
 142 and <code>ranked_non_unique</code> coincide, thus we describe them in a grouped manner.
 143 <code>ranked_unique</code> and <code>ranked_non_unique</code> can be instantiated in
 144 two different forms, according to whether a tag list for the index is provided or not:
 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>
 163 If provided, <code>TagList</code> must be an instantiation of the class template
 164 <a href="indices.html#tag"><code>tag</code></a>.
 165 The template arguments are used by the corresponding index implementation,
 166 refer to the <a href="#rnk_indices">ranked indices</a> reference section for further
 167 explanations on their acceptable type values.
 168 </p>
 169
 170 <h3><a name="rnk_indices">Ranked indices</a></h3>
 171
 172 <p>
 173 Ranked indices are a variation of <a href="ord_indices.html">ordered indices</a>
 174 providing additional capabilities for calculation of and access by rank; the <i>rank</i> of an element is the
 175 distance to it from the beginning of the index. Besides this extension, ranked indices replicate the
 176 public interface of ordered indices with the difference, complexity-wise, that <a href="#complexity_signature">deletion</a>
 177 is done in logarithmic rather than constant time. Also, execution times and memory consumption are
 178 expected to be poorer due to the internal bookkeeping needed to maintain rank-related information.
 179 As with ordered indices, ranked indices can be unique (no duplicate elements are allowed)
 180 or non-unique: either version is associated to a different index specifier, but
 181 the interface of both index types is the same.
 182 </p>
 183
 184 <p>
 185 In what follows, we only describe the extra operations provided by ranked indices: for the
 186 rest refer to the <a href="ord_indices.html#ord_indices">documentation</a> for ordered
 187 indices, bearing in mind the occasional differences in complexity.
 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>
 432 We follow the terminology described in the
 433 <a href="indices.html#complexity_signature">complexity signature
 434 section</a>. The complexity signature of ranked indices is:
 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>
 448 These complexity guarantees are the same as those of
 449 <a href="ord_indices.html#complexity_signature">ordered indices</a>
 450 except for deletion, which is <code>log(n)</code> here and amortized constant there.
 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
 456 specified by means of <a href="indices.html#indexed_by"><code>indexed_by</code></a>
 457 with <a href="#unique_non_unique"> index specifiers <code>ranked_unique</code>
 458 and <code>ranked_non_unique</code></a>. Instantiations are dependent on the
 459 following 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>
 467 These 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>
 474 The <i>rank</i> of an iterator <code>it</code> of a given container <code>c</code> (and,
 475 by extension, of the element it points to if the iterator is dereferenceable)
 476 is <code>std::distance(c.begin(),it)</code>.
 477 </p>
 478
 479 <p>
 480 See the documentation of ordered indices for an explanation of the notions of
 481 <a href="ord_indices.html#set_operations"><i>compatible extension</i>,
 482 <i>compatible key</i></a>,
 483 <a href="ord_indices.html#range_operations"><i>lower bounder</i> and <i>upper bounder</i></a>, which are
 484 referred 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>,
 491 or <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>
 515 size_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>)
 520 is a compatible extension of <code>key_compare</code>.<br>
 521 <b>Effects:</b> Equivalent to <code>rank(find(x,comp))</code>.<br>
 522 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 523 </blockquote>
 524
 525 <code>template&lt;typename CompatibleKey><br>
 526 size_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>
 537 size_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>)
 542 is a compatible extension of <code>key_compare</code>.<br>
 543 <b>Effects:</b> Equivalent to <code>rank(lower_bound(x,comp))</code>.<br>
 544 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 545 </blockquote>
 546
 547 <code>template&lt;typename CompatibleKey><br>
 548 size_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>
 559 size_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>)
 564 is a compatible extension of <code>key_compare</code>.<br>
 565 <b>Effects:</b> Equivalent to <code>rank(upper_bound(x,comp))</code>.<br>
 566 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 567 </blockquote>
 568
 569 <code>template&lt;typename CompatibleKey><br>
 570 std::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>
 582 std::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>)
 588 is a compatible extension of <code>key_compare</code>.<br>
 589 <b>Effects:</b> Equivalent to
 590 <code>make_pair(lower_bound_rank(x,comp),upper_bound_rank(x,comp))</code>.<br>
 591 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 592 </blockquote>
 593
 594 <code>template&lt;typename LowerBounder,typename UpperBounder><br>
 595 std::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
 601 a 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),
 609 the singular value <code>boost::multi_index::unbounded</code> can be
 610 provided. This acts as a predicate which all values of type <code>key_type</code>
 611 satisfy.<br>
 612 </blockquote>
 613
 614 <h4><a name="serialization">Serialization</a></h4>
 615
 616 <p>
 617 The prerequisites and postconditions associated to serialization of
 618 <code>multi_index_container</code>s with ranked indices are exactly the same
 619 as those of <a href="ord_indices.html#serialization">ordered indices</a>.
 620
 621 <hr>
 622
 623 <div class="prev_link"><a href="ord_indices.html"><img src="../prev.gif" alt="ordered_indices" border="0"><br>
 624 Ordered indices
 625 </a></div>
 626 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
 627 Boost.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>
 630 Hashed 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.
 638 Distributed under the Boost Software
 639 License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
 640 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
 641 http://www.boost.org/LICENSE_1_0.txt</a>)
 642 </p>
 643
 644 </body>
 645 </html>