Halaman utama Jelajahi Bantuan
Daftar Masuk
devn00b
/
EQ2EMu
9
3
Fork 0
Berkas Masalah 64 Permintaan Tarik 0 Wiki
Pohon: c6744428a8
Ranting Tag
EQ2EMu
/
EQ2
/
source
/
depends
/
boost_1_72_0
/
libs
/
multi_index
/
doc
/
reference
/
rnk_indices.html

rnk_indices.html 59 KB
Riwayat Mentahan

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645 
  1. <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
    2. 

  2. 

  3. <html>
    4. 

  4. <head>
    5. 

  5. <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
    6. 

  6. <title>Boost.MultiIndex Documentation - Ranked indices reference</title>
    7. 

  7. <link rel="stylesheet" href="../style.css" type="text/css">
    8. 

  8. <link rel="start" href="../index.html">
    9. 

  9. <link rel="prev" href="indices.html">
    10. 

  10. <link rel="up" href="index.html">
    11. 

  11. <link rel="next" href="hash_indices.html">
    12. 

  12. </head>
    13. 

  13. 

  14. <body>
    15. 

  15. <h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
    16. 

  16. "middle" width="277" height="86">Boost.MultiIndex Ranked indices reference</h1>
    17. 

  17. 

  18. <div class="prev_link"><a href="ord_indices.html"><img src="../prev.gif" alt="ordered_indices" border="0"><br>
    19. 

  19. Ordered indices
    20. 

  20. </a></div>
    21. 

  21. <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
    22. 

  22. Boost.MultiIndex reference
    23. 

  23. </a></div>
    24. 

  24. <div class="next_link"><a href="hash_indices.html"><img src="../next.gif" alt="hashed indices" border="0"><br>
    25. 

  25. Hashed indices
    26. 

  26. </a></div><br clear="all" style="clear: all;">
    27. 

  27. 

  28. <hr>
    29. 

  29. 

  30. <h2>Contents</h2>
    31. 

  31. 

  32. <ul>
    33. 

  33.   <li><a href="#rnk_index_fwd_synopsis">Header
    34. 

  34.     <code>"boost/multi_index/ranked_index_fwd.hpp"</code> synopsis</a></li>
    35. 

  35.   <li><a href="#synopsis">Header
    36. 

  36.     <code>"boost/multi_index/ranked_index.hpp"</code> synopsis</a>
    37. 

  37.     <ul>
    38. 

  38.       <li><a href="#unique_non_unique">
    39. 

  39.         Index specifiers <code>ranked_unique</code> and <code>ranked_non_unique</code>
    40. 

  40.         </a></li>
    41. 

  41.       <li><a href="#rnk_indices">Ranked indices</a>
    42. 

  42.         <ul>
    43. 

  43.           <li><a href="#complexity_signature">Complexity signature</a></li>
    44. 

  44.           <li><a href="#instantiation_types">Instantiation types</a></li>
    45. 

  45.           <li><a href="#rank_operations">Rank operations</a></li>
    46. 

  46.           <li><a href="#serialization">Serialization</a></li>
    47. 

  47.         </ul>
    48. 

  48.       </li>
    49. 

  49.     </ul>
    50. 

  50.   </li>
    51. 

  51. </ul>
    52. 

  52. 

  53. <h2>
    54. 

  54. <a name="rnk_index_fwd_synopsis">Header
    55. 

  55. <a href="../../../../boost/multi_index/ranked_index_fwd.hpp">
    56. 

  56. <code>"boost/multi_index/ranked_index_fwd.hpp"</code></a> synopsis</a></h2>
    57. 

  57. 

  58. <blockquote><pre>
    59. 

  59. <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
    60. 

  60. 

  61. <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
    62. 

  62. 

  63. <span class=comment>// index specifiers ranked_unique and ranked_non_unique</span>
    64. 

  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. 

  66. <span class=keyword>struct</span> <span class=identifier>ranked_unique</span><span class=special>;</span>
    67. 

  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. 

  68. <span class=keyword>struct</span> <span class=identifier>ranked_non_unique</span><span class=special>;</span>
    69. 

  69. 

  70. <span class=comment>// indices</span>
    71. 

  71. 

  72. <span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
    73. 

  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. 

  75. 

  76. <span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
    77. 

  77. 

  78. <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span> 
    79. 

  79. 

  80. <span class=special>}</span> <span class=comment>// namespace boost</span>
    81. 

  81. </pre></blockquote>
    82. 

  82. 

  83. <p>
    84. 

  84. <code>ranked_index_fwd.hpp</code> provides forward declarations for index specifiers 
    85. 

  85. <a href="#unique_non_unique"><code>ranked_unique</code> and <code>ranked_non_unique</code></a> and
    86. 

  86. their associated <a href="#rnk_indices">ranked index</a> classes.
    87. 

  87. </p>
    88. 

  88. 

  89. <h2>
    90. 

  90. <a name="synopsis">Header
    91. 

  91. <a href="../../../../boost/multi_index/ranked_index.hpp">
    92. 

  92. <code>"boost/multi_index/ranked_index.hpp"</code></a> synopsis</a></h2>
    93. 

  93. 

  94. <blockquote><pre>
    95. 

  95. <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>initializer_list</span><span class=special>&gt;</span>
    96. 

  96. 

  97. <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
    98. 

  98. 

  99. <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
    100. 

  100. 

  101. <span class=comment>// index specifiers ranked_unique and ranked_non_unique</span>
    102. 

  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. 

  104. <span class=keyword>struct</span> <span class=identifier>ranked_unique</span><span class=special>;</span>
    105. 

  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. 

  106. <span class=keyword>struct</span> <span class=identifier>ranked_non_unique</span><span class=special>;</span>
    107. 

  107. 

  108. <span class=comment>// indices</span>
    109. 

  109. 

  110. <span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
    111. 

  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. 

  113. 

  114. <span class=comment>// index comparison:</span>
    115. 

  115. 

  116. <span class=comment>// <b>OP</b> is any of ==,&lt;,!=,&gt;,&gt;=,&lt;=</span>
    117. 

  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. 

  119. <span class=keyword>bool</span> <span class=keyword>operator</span> <b><i>OP</i></b><span class=special>(</span>
    120. 

  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. 

  121. 

  122. <span class=comment>// index specialized algorithms:</span>
    123. 

  123. 

  124. <span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined</b><span class=special>&gt;</span>
    125. 

  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. 

  126. 

  127. <span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
    128. 

  128. 

  129. <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span> 
    130. 

  130. 

  131. <span class=special>}</span> <span class=comment>// namespace boost</span>
    132. 

  132. </pre></blockquote>
    133. 

  133. 

  134. <h3><a name="unique_non_unique">
    135. 

  135. Index specifiers <code>ranked_unique</code> and <code>ranked_non_unique</code>
    136. 

  136. </a></h3>
    137. 

  137. 

  138. <p>
    139. 

  139. These <a href="indices.html#index_specification">index specifiers</a> allow
    140. 

  140. for insertion of <a href="#rnk_indices">ranked indices</a> without and with
    141. 

  141. allowance of duplicate elements, respectively. The syntax of <code>ranked_unique</code>
    142. 

  142. and <code>ranked_non_unique</code> coincide, thus we describe them in a grouped manner.
    143. 

  143. <code>ranked_unique</code> and <code>ranked_non_unique</code> can be instantiated in
    144. 

  144. two different forms, according to whether a tag list for the index is provided or not:
    145. 

  145. </p>
    146. 

  146. 

  147. <blockquote><pre>
    148. 

  148. <span class=keyword>template</span><span class=special>&lt;</span>
    149. 

  149.   <span class=keyword>typename</span> <span class=identifier>KeyFromValue</span><span class=special>,</span>
    150. 

  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. 

  151. <span class=special>&gt;</span>
    152. 

  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. 

  153. 

  154. <span class=keyword>template</span><span class=special>&lt;</span>
    155. 

  155.   <span class=keyword>typename</span> <span class=identifier>TagList</span><span class=special>,</span>
    156. 

  156.   <span class=keyword>typename</span> <span class=identifier>KeyFromValue</span><span class=special>,</span>
    157. 

  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. 

  158. <span class=special>&gt;</span>
    159. 

  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. 

  160. </pre></blockquote>
    161. 

  161. 

  162. <p>
    163. 

  163. If provided, <code>TagList</code> must be an instantiation of the class template
    164. 

  164. <a href="indices.html#tag"><code>tag</code></a>.
    165. 

  165. The template arguments are used by the corresponding index implementation,
    166. 

  166. refer to the <a href="#rnk_indices">ranked indices</a> reference section for further
    167. 

  167. explanations on their acceptable type values.
    168. 

  168. </p>
    169. 

  169. 

  170. <h3><a name="rnk_indices">Ranked indices</a></h3>
    171. 

  171. 

  172. <p>
    173. 

  173. Ranked indices are a variation of <a href="ord_indices.html">ordered indices</a>
    174. 

  174. providing additional capabilities for calculation of and access by rank; the <i>rank</i> of an element is the
    175. 

  175. distance to it from the beginning of the index. Besides this extension, ranked indices replicate the
    176. 

  176. public interface of ordered indices with the difference, complexity-wise, that <a href="#complexity_signature">deletion</a>
    177. 

  177. is done in logarithmic rather than constant time. Also, execution times and memory consumption are
    178. 

  178. expected to be poorer due to the internal bookkeeping needed to maintain rank-related information.
    179. 

  179. As with ordered indices, ranked indices can be unique (no duplicate elements are allowed)
    180. 

  180. or non-unique: either version is associated to a different index specifier, but
    181. 

  181. the interface of both index types is the same.
    182. 

  182. </p>
    183. 

  183. 

  184. <p>
    185. 

  185. In what follows, we only describe the extra operations provided by ranked indices: for the
    186. 

  186. rest refer to the <a href="ord_indices.html#ord_indices">documentation</a> for ordered
    187. 

  187. indices, bearing in mind the occasional differences in complexity.
    188. 

  188. </p>
    189. 

  189. 

  190. <blockquote><pre>
    191. 

  191. <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
    192. 

  192. 

  193. <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
    194. 

  194. 

  195. <b>implementation defined </b><span class=identifier>unbounded</span><span class=special>;</span> <span class=comment>// see range_rank()</span>
    196. 

  196. 

  197. <span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
    198. 

  198. 

  199. <span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined: dependent on types Value, Allocator,
    200. 

  200.   TagList, KeyFromValue, Compare</b><span class=special>&gt;</span>
    201. 

  201. <span class=keyword>class</span> <b>name is implementation defined</b>
    202. 

  202. <span class=special>{</span> 
    203. 

  203. <span class=keyword>public</span><span class=special>:</span>
    204. 

  204.   <span class=comment>// types:</span>
    205. 

  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. 

  207.   <span class=keyword>typedef</span> <span class=identifier>Value</span>                                      <span class=identifier>value_type</span><span class=special>;</span>
    208. 

  208.   <span class=keyword>typedef</span> <span class=identifier>KeyFromValue</span>                               <span class=identifier>key_from_value</span><span class=special>;</span>
    209. 

  209.   <span class=keyword>typedef</span> <span class=identifier>Compare</span>                                    <span class=identifier>key_compare</span><span class=special>;</span>
    210. 

  210.   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>value_compare</span><span class=special>;</span>
    211. 

  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. 

  212.   <span class=keyword>typedef</span> <span class=identifier>TagList</span>                                    <span class=identifier>tag_list</span><span class=special>;</span>
    213. 

  213.   <span class=keyword>typedef</span> <span class=identifier>Allocator</span>                                  <span class=identifier>allocator_type</span><span class=special>;</span>
    214. 

  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. 

  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. 

  216.   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>iterator</span><span class=special>;</span>
    217. 

  217.   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>const_iterator</span><span class=special>;</span>
    218. 

  218.   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>size_type</span><span class=special>;</span>      
    219. 

  219.   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>difference_type</span><span class=special>;</span>
    220. 

  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. 

  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. 

  222.   <span class=keyword>typedef</span> <b>equivalent to
    223. 

  223.     std::reverse_iterator&lt;iterator&gt;</b>                  <span class=identifier>reverse_iterator</span><span class=special>;</span>
    224. 

  224.   <span class=keyword>typedef</span> <b>equivalent to
    225. 

  225.     std::reverse_iterator&lt;const_iterator&gt;</b>            <span class=identifier>const_reverse_iterator</span><span class=special>;</span>
    226. 

  226. 

  227.   <span class=comment>// construct/copy/destroy:</span>
    228. 

  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. 

  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. 

  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. 

  233. 

  234.   <span class=comment>// iterators:</span>
    235. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  248.  
    249. 

  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. 

  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. 

  251. 

  252.   <span class=comment>// capacity:</span>
    253. 

  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. 

  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. 

  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. 

  257. 

  258.   <span class=comment>// modifiers:</span>
    259. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  284.   
    285. 

  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. 

  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. 

  287. 

  288.   <span class=comment>// observers:</span>
    289. 

  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. 

  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. 

  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. 

  293. 

  294.   <span class=comment>// set operations:</span>
    295. 

  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. 

  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. 

  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. 

  299.   <span class=identifier>iterator</span> <span class=identifier>find</span><span class=special>(</span>
    300. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  310.   <span class=identifier>iterator</span> <span class=identifier>lower_bound</span><span class=special>(</span>
    311. 

  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. 

  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. 

  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. 

  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. 

  316.   <span class=identifier>iterator</span> <span class=identifier>upper_bound</span><span class=special>(</span>
    317. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  325. 

  326.   <span class=comment>// range:</span>
    327. 

  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. 

  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. 

  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. 

  331. 

  332.   <span class=comment>// rank operations:</span>
    333. 

  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. 

  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. 

  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. 

  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. 

  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. 

  340.   <span class=identifier>size_type</span> <span class=identifier>find_rank</span><span class=special>(</span>
    341. 

  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. 

  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. 

  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. 

  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. 

  346.   <span class=identifier>size_type</span> <span class=identifier>lower_bound_rank</span><span class=special>(</span>
    347. 

  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. 

  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. 

  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. 

  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. 

  352.   <span class=identifier>size_type</span> <span class=identifier>upper_bound_rank</span><span class=special>(</span>
    353. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  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. 

  365. <span class=special>};</span>
    366. 

  366. 

  367. <span class=comment>// index comparison:</span>
    368. 

  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. 

  370. <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>==(</span>
    371. 

  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. 

  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. 

  373. <span class=special>{</span>
    374. 

  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. 

  375. <span class=special>}</span>
    376. 

  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. 

  378. <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;(</span>
    379. 

  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. 

  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. 

  381. <span class=special>{</span>
    382. 

  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. 

  383. <span class=special>}</span>
    384. 

  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. 

  386. <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>!=(</span>
    387. 

  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. 

  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. 

  389. <span class=special>{</span>
    390. 

  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. 

  391. <span class=special>}</span>
    392. 

  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. 

  394. <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&gt;(</span>
    395. 

  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. 

  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. 

  397. <span class=special>{</span>
    398. 

  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. 

  399. <span class=special>}</span>
    400. 

  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. 

  402. <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&gt;=(</span>
    403. 

  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. 

  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. 

  405. <span class=special>{</span>
    406. 

  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. 

  407. <span class=special>}</span>
    408. 

  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. 

  410. <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;=(</span>
    411. 

  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. 

  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. 

  413. <span class=special>{</span>
    414. 

  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. 

  415. <span class=special>}</span>
    416. 

  416. 

  417. <span class=comment>// index specialized algorithms:</span>
    418. 

  418. 

  419. <span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined</b><span class=special>&gt;</span>
    420. 

  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. 

  421. 

  422. <span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
    423. 

  423. 

  424. <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span> 
    425. 

  425. 

  426. <span class=special>}</span> <span class=comment>// namespace boost</span>
    427. 

  427. </pre></blockquote>
    428. 

  428. 

  429. <h4><a name="complexity_signature">Complexity signature</a></h4>
    430. 

  430. 

  431. <p>
    432. 

  432. We follow the terminology described in the 
    433. 

  433. <a href="indices.html#complexity_signature">complexity signature
    434. 

  434. section</a>. The complexity signature of ranked indices is:
    435. 

  435. <ul>
    436. 

  436.   <li>copying: <code>c(n)=n*log(n)</code>,</li>
    437. 

  437.   <li>insertion: <code>i(n)=log(n)</code>,</li>
    438. 

  438.   <li>hinted insertion: <code>h(n)=1</code> (constant) if the hint element
    439. 

  439.     is immediately after the point of insertion, <code>h(n)=log(n)</code> otherwise,</li>
    440. 

  440.   <li>deletion: <b><code>d(n)=log(n)</code></b> ,</li>
    441. 

  441.   <li>replacement: <code>r(n)=1</code> (constant) if the element position does not
    442. 

  442.     change, <code>r(n)=log(n)</code> otherwise,</li>
    443. 

  443.   <li>modifying: <code>m(n)=1</code> (constant) if the element position does not
    444. 

  444.     change, <code>m(n)=log(n)</code> otherwise.</li>
    445. 

  445. </ul>
    446. 

  446. </p>
    447. 

  447. <p>
    448. 

  448. These complexity guarantees are the same as those of
    449. 

  449. <a href="ord_indices.html#complexity_signature">ordered indices</a>
    450. 

  450. except for deletion, which is <code>log(n)</code> here and amortized constant there.
    451. 

  451. </p>
    452. 

  452. 

  453. <h4><a name="instantiation_types">Instantiation types</a></h4>
    454. 

  454. 

  455. <p>Ordered indices are instantiated internally to <code>multi_index_container</code> and
    456. 

  456. specified by means of <a href="indices.html#indexed_by"><code>indexed_by</code></a>
    457. 

  457. with <a href="#unique_non_unique"> index specifiers <code>ranked_unique</code>
    458. 

  458. and <code>ranked_non_unique</code></a>. Instantiations are dependent on the
    459. 

  459. following types:
    460. 

  460. <ul>
    461. 

  461.   <li><code>Value</code> from <code>multi_index_container</code>,</li>
    462. 

  462.   <li><code>Allocator</code> from <code>multi_index_container</code>,</li>
    463. 

  463.   <li><code>TagList</code> from the index specifier (if provided, otherwise <code>tag&lt;&gt;</code> is assumed),</li>
    464. 

  464.   <li><code>KeyFromValue</code> from the index specifier,</li>
    465. 

  465.   <li><code>Compare</code> from the index specifier.</li>
    466. 

  466. </ul>
    467. 

  467. These types are subject to the same requirements as specified for
    468. 

  468. <a href="ord_indices.html#instantiation_types">ordered indices</a>.
    469. 

  469. </p>
    470. 

  470. 

  471. <h4><a name="rank_operations">Rank operations</a></h4>
    472. 

  472. 

  473. <p>
    474. 

  474. The <i>rank</i> of an iterator <code>it</code> of a given container <code>c</code> (and,
    475. 

  475. by extension, of the element it points to if the iterator is dereferenceable)
    476. 

  476. is <code>std::distance(c.begin(),it)</code>.
    477. 

  477. </p>
    478. 

  478. 

  479. <p>
    480. 

  480. See the documentation of ordered indices for an explanation of the notions of
    481. 

  481. <a href="ord_indices.html#set_operations"><i>compatible extension</i>, 
    482. 

  482. <i>compatible key</i></a>, 
    483. 

  483. <a href="ord_indices.html#range_operations"><i>lower bounder</i> and <i>upper bounder</i></a>, which are
    484. 

  484. referred to below.
    485. 

  485. </p>
    486. 

  486. 

  487. <code>iterator nth(size_type n)const;</code>
    488. 

  488. 

  489. <blockquote>
    490. 

  490. <b>Effects:</b> Returns an iterator with rank <code>n</code>,
    491. 

  491. or <code>end()</code> if <code>n&gt;=size()</code>.<br>
    492. 

  492. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    493. 

  493. </blockquote>
    494. 

  494. 

  495. <code>size_type rank(iterator position)const;
    496. 

  496. </code>
    497. 

  497. 

  498. <blockquote>
    499. 

  499. <b>Requires:</b> <code>position</code> is a valid iterator of the index.<br>
    500. 

  500. <b>Effects:</b> Returns the rank of <code>position</code>.<br>
    501. 

  501. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    502. 

  502. </blockquote>
    503. 

  503. 

  504. <code>template&lt;typename CompatibleKey> size_type find_rank(const CompatibleKey&amp; x)const;
    505. 

  505. </code>
    506. 

  506. 

  507. <blockquote>
    508. 

  508. <b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
    509. 

  509. <code>key_compare</code>.<br>
    510. 

  510. <b>Effects:</b> Equivalent to <code>rank(find(k))</code>.<br>
    511. 

  511. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    512. 

  512. </blockquote>
    513. 

  513. 

  514. <code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
    515. 

  515. size_type find_rank(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
    516. 

  516. </code>
    517. 

  517. 

  518. <blockquote>
    519. 

  519. <b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
    520. 

  520. is a compatible extension of <code>key_compare</code>.<br>
    521. 

  521. <b>Effects:</b> Equivalent to <code>rank(find(x,comp))</code>.<br>
    522. 

  522. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    523. 

  523. </blockquote>
    524. 

  524. 

  525. <code>template&lt;typename CompatibleKey><br>
    526. 

  526. size_type lower_bound_rank(const CompatibleKey&amp; x)const;
    527. 

  527. </code>
    528. 

  528. 

  529. <blockquote>
    530. 

  530. <b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
    531. 

  531. <code>key_compare</code>.<br>
    532. 

  532. <b>Effects:</b> Equivalent to <code>rank(lower_bound(x))</code>.<br>
    533. 

  533. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    534. 

  534. </blockquote>
    535. 

  535. 

  536. <code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
    537. 

  537. size_type lower_bound_rank(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
    538. 

  538. </code>
    539. 

  539. 

  540. <blockquote>
    541. 

  541. <b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
    542. 

  542. is a compatible extension of <code>key_compare</code>.<br>
    543. 

  543. <b>Effects:</b> Equivalent to <code>rank(lower_bound(x,comp))</code>.<br>
    544. 

  544. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    545. 

  545. </blockquote>
    546. 

  546. 

  547. <code>template&lt;typename CompatibleKey><br>
    548. 

  548. size_type upper_bound_rank(const CompatibleKey&amp; x)const;
    549. 

  549. </code>
    550. 

  550. 

  551. <blockquote>
    552. 

  552. <b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
    553. 

  553. <code>key_compare</code>.<br>
    554. 

  554. <b>Effects:</b> Equivalent to <code>rank(upper_bound(x))</code>.<br>
    555. 

  555. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    556. 

  556. </blockquote>
    557. 

  557. 

  558. <code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
    559. 

  559. size_type upper_bound_rank(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
    560. 

  560. </code>
    561. 

  561. 

  562. <blockquote>
    563. 

  563. <b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
    564. 

  564. is a compatible extension of <code>key_compare</code>.<br>
    565. 

  565. <b>Effects:</b> Equivalent to <code>rank(upper_bound(x,comp))</code>.<br>
    566. 

  566. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    567. 

  567. </blockquote>
    568. 

  568. 

  569. <code>template&lt;typename CompatibleKey><br>
    570. 

  570. std::pair&lt;size_type,size_type> equal_range_rank(<br>
    571. 

  571. &nbsp;&nbsp;const CompatibleKey&amp; x)const;
    572. 

  572. </code>
    573. 

  573. 

  574. <blockquote>
    575. 

  575. <b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
    576. 

  576. <code>key_compare</code>.<br>
    577. 

  577. <b>Effects:</b> Equivalent to <code>make_pair(lower_bound_rank(x),upper_bound_rank(x))</code>.<br>
    578. 

  578. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    579. 

  579. </blockquote>
    580. 

  580. 

  581. <code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
    582. 

  582. std::pair&lt;size_type,size_type> equal_range_rank(<br>
    583. 

  583. &nbsp;&nbsp;const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
    584. 

  584. </code>
    585. 

  585. 

  586. <blockquote>
    587. 

  587. <b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
    588. 

  588. is a compatible extension of <code>key_compare</code>.<br>
    589. 

  589. <b>Effects:</b> Equivalent to
    590. 

  590. <code>make_pair(lower_bound_rank(x,comp),upper_bound_rank(x,comp))</code>.<br>
    591. 

  591. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    592. 

  592. </blockquote>
    593. 

  593. 

  594. <code>template&lt;typename LowerBounder,typename UpperBounder><br>
    595. 

  595. std::pair&lt;size_type,size_type> range_rank(<br>
    596. 

  596. &nbsp;&nbsp;LowerBounder lower,UpperBounder upper)const;
    597. 

  597. </code>
    598. 

  598. 

  599. <blockquote>
    600. 

  600. <b>Requires:</b> <code>LowerBounder</code> and <code>UpperBounder</code> are
    601. 

  601. a lower and upper bounder of <code>key_compare</code>, respectively.<br>
    602. 

  602. <b>Effects:</b> Equivalent to 
    603. 

  603. <blockquote><pre>
    604. 

  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. 

  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. 

  606. </pre></blockquote>
    607. 

  607. <b>Complexity:</b> <code>O(log(n))</code>.<br>
    608. 

  608. <b>Variants:</b> In place of <code>lower</code> or <code>upper</code> (or both),
    609. 

  609. the singular value <code>boost::multi_index::unbounded</code> can be
    610. 

  610. provided. This acts as a predicate which all values of type <code>key_type</code>
    611. 

  611. satisfy.<br>
    612. 

  612. </blockquote>
    613. 

  613. 

  614. <h4><a name="serialization">Serialization</a></h4>
    615. 

  615. 

  616. <p>
    617. 

  617. The prerequisites and postconditions associated to serialization of
    618. 

  618. <code>multi_index_container</code>s with ranked indices are exactly the same
    619. 

  619. as those of <a href="ord_indices.html#serialization">ordered indices</a>.
    620. 

  620. 

  621. <hr>
    622. 

  622. 

  623. <div class="prev_link"><a href="ord_indices.html"><img src="../prev.gif" alt="ordered_indices" border="0"><br>
    624. 

  624. Ordered indices
    625. 

  625. </a></div>
    626. 

  626. <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
    627. 

  627. Boost.MultiIndex reference
    628. 

  628. </a></div>
    629. 

  629. <div class="next_link"><a href="hash_indices.html"><img src="../next.gif" alt="hashed indices" border="0"><br>
    630. 

  630. Hashed indices
    631. 

  631. </a></div><br clear="all" style="clear: all;">
    632. 

  632. 

  633. <br>
    634. 

  634. 

  635. <p>Revised May 4th 2015</p>
    636. 

  636. 

  637. <p>&copy; Copyright 2003-2015 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
    638. 

  638. Distributed under the Boost Software 
    639. 

  639. License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
    640. 

  640. LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
    641. 

  641. http://www.boost.org/LICENSE_1_0.txt</a>)
    642. 

  642. </p>
    643. 

  643. 

  644. </body>
    645. 

  645. </html>
    646.