libs/multi_index/doc/reference/ord_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 - Ordered 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 Ordered indices reference</h1>
  17
  18 <div class="prev_link"><a href="indices.html"><img src="../prev.gif" alt="index reference" border="0"><br>
  19 Index reference
  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="#ord_index_fwd_synopsis">Header
  34     <code>"boost/multi_index/ordered_index_fwd.hpp"</code> synopsis</a></li>
  35   <li><a href="#synopsis">Header
  36     <code>"boost/multi_index/ordered_index.hpp"</code> synopsis</a>
  37     <ul>
  38       <li><a href="#unique_non_unique">
  39         Index specifiers <code>ordered_unique</code> and <code>ordered_non_unique</code>
  40         </a></li>
  41       <li><a href="#ord_indices">Ordered 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="#constructors">Constructors, copy and assignment</a></li>
  46           <li><a href="#iterators">Iterators</a></li>
  47           <li><a href="#modifiers">Modifiers</a></li>
  48           <li><a href="#observers">Observers</a></li>
  49           <li><a href="#set_operations">Set operations</a></li>
  50           <li><a href="#range_operations">Range operations</a></li>
  51           <li><a href="#serialization">Serialization</a></li>
  52         </ul>
  53       </li>
  54     </ul>
  55   </li>
  56 </ul>
  57
  58 <h2>
  59 <a name="ord_index_fwd_synopsis">Header
  60 <a href="../../../../boost/multi_index/ordered_index_fwd.hpp">
  61 <code>"boost/multi_index/ordered_index_fwd.hpp"</code></a> synopsis</a></h2>
  62
  63 <blockquote><pre>
  64 <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
  65
  66 <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
  67
  68 <span class=comment>// index specifiers ordered_unique and ordered_non_unique</span>
  69
  70 <span class=keyword>template</span><span class=special>&lt;</span><b>consult ordered_unique reference for arguments</b><span class=special>&gt;</span>
  71 <span class=keyword>struct</span> <span class=identifier>ordered_unique</span><span class=special>;</span>
  72 <span class=keyword>template</span><span class=special>&lt;</span><b>consult ordered_non_unique reference for arguments</b><span class=special>&gt;</span>
  73 <span class=keyword>struct</span> <span class=identifier>ordered_non_unique</span><span class=special>;</span>
  74
  75 <span class=comment>// indices</span>
  76
  77 <span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
  78
  79 <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>
  80
  81 <span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
  82
  83 <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
  84
  85 <span class=special>}</span> <span class=comment>// namespace boost</span>
  86 </pre></blockquote>
  87
  88 <p>
  89 <code>ordered_index_fwd.hpp</code> provides forward declarations for index specifiers
  90 <a href="#unique_non_unique"><code>ordered_unique</code> and <code>ordered_non_unique</code></a> and
  91 their associated <a href="#ord_indices">ordered index</a> classes.
  92 </p>
  93
  94 <h2>
  95 <a name="synopsis">Header
  96 <a href="../../../../boost/multi_index/ordered_index.hpp">
  97 <code>"boost/multi_index/ordered_index.hpp"</code></a> synopsis</a></h2>
  98
  99 <blockquote><pre>
 100 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>initializer_list</span><span class=special>&gt;</span>
 101
 102 <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
 103
 104 <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
 105
 106 <span class=comment>// index specifiers ordered_unique and ordered_non_unique</span>
 107
 108 <span class=keyword>template</span><span class=special>&lt;</span><b>consult ordered_unique reference for arguments</b><span class=special>&gt;</span>
 109 <span class=keyword>struct</span> <span class=identifier>ordered_unique</span><span class=special>;</span>
 110 <span class=keyword>template</span><span class=special>&lt;</span><b>consult ordered_non_unique reference for arguments</b><span class=special>&gt;</span>
 111 <span class=keyword>struct</span> <span class=identifier>ordered_non_unique</span><span class=special>;</span>
 112
 113 <span class=comment>// indices</span>
 114
 115 <span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
 116
 117 <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>
 118
 119 <span class=comment>// index comparison:</span>
 120
 121 <span class=comment>// <b>OP</b> is any of ==,&lt;,!=,&gt;,&gt;=,&lt;=</span>
 122
 123 <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>
 124 <span class=keyword>bool</span> <span class=keyword>operator</span> <b><i>OP</i></b><span class=special>(</span>
 125   <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>
 126
 127 <span class=comment>// index specialized algorithms:</span>
 128
 129 <span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined</b><span class=special>&gt;</span>
 130 <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>
 131
 132 <span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
 133
 134 <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
 135
 136 <span class=special>}</span> <span class=comment>// namespace boost</span>
 137 </pre></blockquote>
 138
 139 <h3><a name="unique_non_unique">
 140 Index specifiers <code>ordered_unique</code> and <code>ordered_non_unique</code>
 141 </a></h3>
 142
 143 <p>
 144 These <a href="indices.html#index_specification">index specifiers</a> allow
 145 for insertion of <a href="#ord_indices">ordered indices</a> without and with
 146 allowance of duplicate elements, respectively. The syntax of <code>ordered_unique</code>
 147 and <code>ordered_non_unique</code> coincide, thus we describe them in a grouped manner.
 148 <code>ordered_unique</code> and <code>ordered_non_unique</code> can be instantiated in
 149 two different forms, according to whether a tag list for the index is provided or not:
 150 </p>
 151
 152 <blockquote><pre>
 153 <span class=keyword>template</span><span class=special>&lt;</span>
 154   <span class=keyword>typename</span> <span class=identifier>KeyFromValue</span><span class=special>,</span>
 155   <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>
 156 <span class=special>&gt;</span>
 157 <span class=keyword>struct</span> <span class=special>(</span><span class=identifier>ordered_unique</span> <span class=special>|</span> <span class=identifier>ordered_non_unique</span><span class=special>)</span><span class=special>;</span>
 158
 159 <span class=keyword>template</span><span class=special>&lt;</span>
 160   <span class=keyword>typename</span> <span class=identifier>TagList</span><span class=special>,</span>
 161   <span class=keyword>typename</span> <span class=identifier>KeyFromValue</span><span class=special>,</span>
 162   <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>
 163 <span class=special>&gt;</span>
 164 <span class=keyword>struct</span> <span class=special>(</span><span class=identifier>ordered_unique</span> <span class=special>|</span> <span class=identifier>ordered_non_unique</span><span class=special>)</span><span class=special>;</span>
 165 </pre></blockquote>
 166
 167 <p>
 168 If provided, <code>TagList</code> must be an instantiation of the class template
 169 <a href="indices.html#tag"><code>tag</code></a>.
 170 The template arguments are used by the corresponding index implementation,
 171 refer to the <a href="#ord_indices">ordered indices</a> reference section for further
 172 explanations on their acceptable type values.
 173 </p>
 174
 175 <h3><a name="ord_indices">Ordered indices</a></h3>
 176
 177 <p>
 178 An ordered index provides a set-like interface to the underlying heap of
 179 elements contained in a <code>multi_index_container</code>. An ordered index is
 180 particularized according to a given
 181 <a href="key_extraction.html#key_extractors"><code>Key Extractor</code></a>
 182 that retrieves keys from elements of <code>multi_index_container</code> and a comparison
 183 predicate.
 184 </p>
 185
 186 <p>
 187 There are two variants of ordered indices: <i>unique</i>, which do
 188 not allow duplicate elements (with respect to its associated comparison
 189 predicate) and <i>non-unique</i>, which accept those duplicates.
 190 The interface of these two variants is the same, so they are documented
 191 together, with minor differences explicitly stated when they exist.
 192 </p>
 193
 194 <p>
 195 Except where noted or if the corresponding interface does not exist,
 196 ordered indices (both unique and non-unique) satisfy the C++ requirements
 197 for associative containers at <b>[associative.reqmts]</b>
 198 (supporting unique and equivalent keys, respectively.)
 199 Accordingly, validity of iterators and references to elements is
 200 preserved. We only provide descriptions of those types and operations that
 201 do not exactly conform to or are not mandated by the standard requirements.
 202 </p>
 203
 204 <blockquote><pre>
 205 <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
 206
 207 <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
 208
 209 <b>implementation defined </b><span class=identifier>unbounded</span><span class=special>;</span> <span class=comment>// see range()</span>
 210
 211 <span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span>
 212
 213 <span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined: dependent on types Value, Allocator,
 214   TagList, KeyFromValue, Compare</b><span class=special>&gt;</span>
 215 <span class=keyword>class</span> <b>name is implementation defined</b>
 216 <span class=special>{</span>
 217 <span class=keyword>public</span><span class=special>:</span>
 218   <span class=comment>// types:</span>
 219
 220   <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>
 221   <span class=keyword>typedef</span> <span class=identifier>Value</span>                                      <span class=identifier>value_type</span><span class=special>;</span>
 222   <span class=keyword>typedef</span> <span class=identifier>KeyFromValue</span>                               <span class=identifier>key_from_value</span><span class=special>;</span>
 223   <span class=keyword>typedef</span> <span class=identifier>Compare</span>                                    <span class=identifier>key_compare</span><span class=special>;</span>
 224   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>value_compare</span><span class=special>;</span>
 225   <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>
 226   <span class=keyword>typedef</span> <span class=identifier>TagList</span>                                    <span class=identifier>tag_list</span><span class=special>;</span>
 227   <span class=keyword>typedef</span> <span class=identifier>Allocator</span>                                  <span class=identifier>allocator_type</span><span class=special>;</span>
 228   <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>
 229   <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>
 230   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>iterator</span><span class=special>;</span>
 231   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>const_iterator</span><span class=special>;</span>
 232   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>size_type</span><span class=special>;</span>
 233   <span class=keyword>typedef</span> <b>implementation defined                     </b><span class=identifier>difference_type</span><span class=special>;</span>
 234   <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>
 235   <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>
 236   <span class=keyword>typedef</span> <b>equivalent to
 237     std::reverse_iterator&lt;iterator&gt;</b>                  <span class=identifier>reverse_iterator</span><span class=special>;</span>
 238   <span class=keyword>typedef</span> <b>equivalent to
 239     std::reverse_iterator&lt;const_iterator&gt;</b>            <span class=identifier>const_reverse_iterator</span><span class=special>;</span>
 240
 241   <span class=comment>// construct/copy/destroy:</span>
 242
 243   <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>
 244   <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>
 245
 246   <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>
 247
 248   <span class=comment>// iterators:</span>
 249
 250   <span class=identifier>iterator</span>               <span class=identifier>begin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
 251   <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>
 252   <span class=identifier>iterator</span>               <span class=identifier>end</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
 253   <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>
 254   <span class=identifier>reverse_iterator</span>       <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
 255   <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>
 256   <span class=identifier>reverse_iterator</span>       <span class=identifier>rend</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
 257   <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>
 258   <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>
 259   <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>
 260   <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>
 261   <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>
 262
 263   <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>
 264   <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>
 265
 266   <span class=comment>// capacity:</span>
 267
 268   <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>
 269   <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>
 270   <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>
 271
 272   <span class=comment>// modifiers:</span>
 273
 274   <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>
 275   <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>
 276   <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>
 277   <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>
 278   <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>
 279   <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>
 280   <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>
 281   <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>
 282   <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>
 283   <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>
 284   <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>
 285
 286   <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>
 287   <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>
 288   <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>
 289
 290   <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>
 291   <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>
 292   <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>
 293   <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>
 294   <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>
 295   <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>
 296   <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>
 297   <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>
 298
 299   <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>
 300   <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
 301
 302   <span class=comment>// observers:</span>
 303
 304   <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>
 305   <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>
 306   <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>
 307
 308   <span class=comment>// set operations:</span>
 309
 310   <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>
 311   <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>
 312   <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>
 313   <span class=identifier>iterator</span> <span class=identifier>find</span><span class=special>(</span>
 314     <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>
 315
 316   <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>
 317   <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>
 318   <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>
 319   <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>
 320
 321   <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>
 322   <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>
 323   <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>
 324   <span class=identifier>iterator</span> <span class=identifier>lower_bound</span><span class=special>(</span>
 325     <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>
 326
 327   <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>
 328   <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>
 329   <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>
 330   <span class=identifier>iterator</span> <span class=identifier>upper_bound</span><span class=special>(</span>
 331     <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>
 332
 333   <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>
 334   <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>
 335     <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>
 336   <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>
 337   <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>
 338     <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>
 339
 340   <span class=comment>// range:</span>
 341
 342   <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>
 343   <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>
 344     <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>
 345 <span class=special>};</span>
 346
 347 <span class=comment>// index comparison:</span>
 348
 349 <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>
 350 <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>==(</span>
 351   <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>
 352   <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>
 353 <span class=special>{</span>
 354   <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>
 355 <span class=special>}</span>
 356
 357 <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>
 358 <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;(</span>
 359   <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>
 360   <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>
 361 <span class=special>{</span>
 362   <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>
 363 <span class=special>}</span>
 364
 365 <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>
 366 <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>!=(</span>
 367   <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>
 368   <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>
 369 <span class=special>{</span>
 370   <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>
 371 <span class=special>}</span>
 372
 373 <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>
 374 <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&gt;(</span>
 375   <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>
 376   <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>
 377 <span class=special>{</span>
 378   <span class=keyword>return</span> <span class=identifier>y</span><span class=special>&lt;</span><span class=identifier>x</span><span class=special>;</span>
 379 <span class=special>}</span>
 380
 381 <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>
 382 <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&gt;=(</span>
 383   <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>
 384   <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>
 385 <span class=special>{</span>
 386   <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>
 387 <span class=special>}</span>
 388
 389 <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>
 390 <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;=(</span>
 391   <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>
 392   <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>
 393 <span class=special>{</span>
 394   <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>
 395 <span class=special>}</span>
 396
 397 <span class=comment>// index specialized algorithms:</span>
 398
 399 <span class=keyword>template</span><span class=special>&lt;</span><b>implementation defined</b><span class=special>&gt;</span>
 400 <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>
 401
 402 <span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span>
 403
 404 <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
 405
 406 <span class=special>}</span> <span class=comment>// namespace boost</span>
 407 </pre></blockquote>
 408
 409 <h4><a name="complexity_signature">Complexity signature</a></h4>
 410
 411 <p>
 412 Here and in the descriptions of operations of ordered indices, we adopt the
 413 scheme outlined in the
 414 <a href="indices.html#complexity_signature">complexity signature
 415 section</a>. The complexity signature of ordered indices is:
 416 <ul>
 417   <li>copying: <code>c(n)=n*log(n)</code>,</li>
 418   <li>insertion: <code>i(n)=log(n)</code>,</li>
 419   <li>hinted insertion: <code>h(n)=1</code> (constant) if the hint element
 420     is immediately after the point of insertion, <code>h(n)=log(n)</code> otherwise,</li>
 421   <li>deletion: <code>d(n)=1</code> (amortized constant),</li>
 422   <li>replacement: <code>r(n)=1</code> (constant) if the element position does not
 423     change, <code>r(n)=log(n)</code> otherwise,</li>
 424   <li>modifying: <code>m(n)=1</code> (constant) if the element position does not
 425     change, <code>m(n)=log(n)</code> otherwise.</li>
 426 </ul>
 427 </p>
 428
 429 <h4><a name="instantiation_types">Instantiation types</a></h4>
 430
 431 <p>Ordered indices are instantiated internally to <code>multi_index_container</code> and
 432 specified by means of <a href="indices.html#indexed_by"><code>indexed_by</code></a>
 433 with <a href="#unique_non_unique"> index specifiers <code>ordered_unique</code>
 434 and <code>ordered_non_unique</code></a>. Instantiations are dependent on the
 435 following types:
 436 <ul>
 437   <li><code>Value</code> from <code>multi_index_container</code>,</li>
 438   <li><code>Allocator</code> from <code>multi_index_container</code>,</li>
 439   <li><code>TagList</code> from the index specifier (if provided, otherwise <code>tag&lt;&gt;</code> is assumed),</li>
 440   <li><code>KeyFromValue</code> from the index specifier,</li>
 441   <li><code>Compare</code> from the index specifier.</li>
 442 </ul>
 443 <code>TagList</code> must be an instantiation of
 444 <a href="indices.html#tag"><code>tag</code></a>. The type <code>KeyFromValue</code>,
 445 which determines the mechanism for extracting a key from <code>Value</code>,
 446 must be a model of <a href="key_extraction.html#key_extractors">
 447 <code>Key Extractor</code></a> from <code>Value</code>. <code>Compare</code> is a
 448 <code>CopyConstructible</code> binary predicate inducing a strict weak order
 449 on elements of <code>KeyFromValue::result_type</code>.
 450 </p>
 451
 452 <h4><a name="constructors">Constructors, copy and assignment</a></h4>
 453
 454 <p>
 455 As explained in the <a href="indices.html#index_concepts">index
 456 concepts section</a>, indices do not have public constructors or destructors.
 457 Assignment, on the other hand, is provided.
 458 </p>
 459
 460 <code><b>index class name</b>&amp; operator=(const <b>index class name</b>&amp; x);</code>
 461
 462 <blockquote>
 463 <b>Effects:</b>
 464 <blockquote><pre>
 465 <span class=identifier>a</span><span class=special>=</span><span class=identifier>b</span><span class=special>;</span>
 466 </pre></blockquote>
 467 where <code>a</code> and <code>b</code> are the <code>multi_index_container</code>
 468 objects to which <code>*this</code> and <code>x</code> belong, respectively.<br>
 469 <b>Returns:</b> <code>*this</code>.<br>
 470 </blockquote>
 471
 472 <code><b>index class name</b>&amp; operator=(std::initializer_list&lt;value_type&gt; list);</code>
 473
 474 <blockquote>
 475 <b>Effects:</b>
 476 <blockquote><pre>
 477 <span class=identifier>a</span><span class=special>=</span><span class=identifier>list</span><span class=special>;</span>
 478 </pre></blockquote>
 479 where <code>a</code> is the <code>multi_index_container</code>
 480 object to which <code>*this</code> belongs.<br>
 481 <b>Returns:</b> <code>*this</code>.<br>
 482 </blockquote>
 483
 484 <h4><a name="iterators">Iterators</a></h4>
 485
 486 <code>iterator&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;iterator_to(const value_type&amp; x);<br>
 487 const_iterator iterator_to(const value_type&amp; x)const;</code>
 488
 489 <blockquote>
 490 <b>Requires:</b> <code>x</code> is a reference to an element of the container.<br>
 491 <b>Returns:</b> An iterator to <code>x</code>.<br>
 492 <b>Complexity:</b> Constant.<br>
 493 <b>Exception safety:</b> <code>nothrow</code>.<br>
 494 </blockquote>
 495
 496 <h4><a name="modifiers">Modifiers</a></h4>
 497
 498 <code>template&lt;typename... Args&gt;<br>
 499 std::pair&lt;iterator,bool&gt; emplace(Args&amp;&amp;... args);</code>
 500
 501 <blockquote>
 502 <b>Requires:</b> <code>value_type</code> is <code>EmplaceConstructible</code>
 503 into <code>multi_index_container</code> from <code>args</code>.<br>
 504 <b>Effects:</b> Inserts a <code>value_type</code> object constructed with
 505 <code>std::forward&lt;Args&gt;(args)...</code> into the <code>multi_index_container</code> to which
 506 the index belongs if
 507 <ul>
 508   <li>the index is non-unique OR no other element exists with
 509     equivalent key,</li>
 510   <li>AND insertion is allowed by all other indices of the
 511     <code>multi_index_container</code>.</li>
 512 </ul>
 513 <b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code>
 514 is <code>true</code> if and only if insertion took place. On successful insertion,
 515 <code>p.first</code> points to the element inserted; otherwise, <code>p.first</code>
 516 points to an element that caused the insertion to be banned. Note that more than
 517 one element can be causing insertion not to be allowed.<br>
 518 <b>Complexity:</b> <code>O(I(n))</code>.<br>
 519 <b>Exception safety:</b> Strong.<br>
 520 </blockquote>
 521
 522 <code>template&lt;typename... Args&gt;<br>
 523 iterator emplace_hint(iterator position, Args&amp;&amp;... args);</code>
 524
 525 <blockquote>
 526 <b>Requires:</b> <code>value_type</code> is <code>EmplaceConstructible</code>
 527 into <code>multi_index_container</code> from <code>args</code>.
 528 <code>position</code> is a valid iterator of the index.<br>
 529 <b>Effects:</b> Inserts a <code>value_type</code> object constructed with
 530 <code>std::forward&lt;Args&gt;(args)...</code> into the <code>multi_index_container</code> to which
 531 the index belongs if
 532 <ul>
 533   <li>the index is non-unique OR no other element exists with
 534     equivalent key,</li>
 535   <li>AND insertion is allowed by all other indices of the
 536     <code>multi_index_container</code>.</li>
 537 </ul>
 538 <code>position</code> is used as a hint to improve the efficiency of the
 539 operation. If succesful, insertion happens as close as possible to the
 540 location just prior to <code>position</code>.<br>
 541 <b>Returns:</b> On successful insertion, an iterator to the newly inserted
 542 element. Otherwise, an iterator to an element that caused the insertion to be
 543 banned. Note that more than one element can be causing insertion not to be
 544 allowed.<br>
 545 <b>Complexity:</b> <code>O(H(n))</code>.<br>
 546 <b>Exception safety:</b> Strong.<br>
 547 </blockquote>
 548
 549 <code>std::pair&lt;iterator,bool> insert(const value_type&amp; x);</code><br>
 550 <code>std::pair&lt;iterator,bool> insert(value_type&amp;&amp; x);</code>
 551
 552 <blockquote>
 553 <b>Requires (first version):</b> <code>value_type</code> is <code>CopyInsertable</code>
 554 into <code>multi_index_container</code>.<br>
 555 <b>Requires (second version):</b> <code>value_type</code> is <code>MoveInsertable</code>
 556 into <code>multi_index_container</code>.<br>
 557 <b>Effects:</b> Inserts <code>x</code> into the <code>multi_index_container</code> to which
 558 the index belongs if
 559 <ul>
 560   <li>the index is non-unique OR no other element exists with
 561     equivalent key,</li>
 562   <li>AND insertion is allowed by all other indices of the
 563     <code>multi_index_container</code>.</li>
 564 </ul>
 565 <b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code>
 566 is <code>true</code> if and only if insertion took place. On successful insertion,
 567 <code>p.first</code> points to the element inserted; otherwise, <code>p.first</code>
 568 points to an element that caused the insertion to be banned. Note that more than
 569 one element can be causing insertion not to be allowed.<br>
 570 <b>Complexity:</b> <code>O(I(n))</code>.<br>
 571 <b>Exception safety:</b> Strong.<br>
 572 </blockquote>
 573
 574 <code>iterator insert(iterator position,const value_type&amp; x);</code><br>
 575 <code>iterator insert(iterator position,value_type&amp;&amp; x);</code>
 576
 577 <blockquote>
 578 <b>Requires (first version):</b> <code>value_type</code> is <code>CopyInsertable</code>
 579 into <code>multi_index_container</code>.
 580 <code>position</code> is a valid iterator of the index.<br>
 581 <b>Requires (second version):</b> <code>value_type</code> is <code>MoveInsertable</code>
 582 into <code>multi_index_container</code>.
 583 <code>position</code> is a valid iterator of the index.<br>
 584 <b>Effects:</b> Inserts <code>x</code> into the <code>multi_index_container</code> to which
 585 the index belongs if
 586 <ul>
 587   <li>the index is non-unique OR no other element exists with
 588     equivalent key,</li>
 589   <li>AND insertion is allowed by all other indices of the
 590     <code>multi_index_container</code>.</li>
 591 </ul>
 592 <code>position</code> is used as a hint to improve the efficiency of the
 593 operation. If succesful, insertion happens as close as possible to the
 594 location just prior to <code>position</code>.<br>
 595 <b>Returns:</b> On successful insertion, an iterator to the newly inserted
 596 element. Otherwise, an iterator to an element that caused the insertion to be
 597 banned. Note that more than one element can be causing insertion not to be
 598 allowed.<br>
 599 <b>Complexity:</b> <code>O(H(n))</code>.<br>
 600 <b>Exception safety:</b> Strong.<br>
 601 </blockquote>
 602
 603 <code>template&lt;typename InputIterator><br>
 604 void insert(InputIterator first,InputIterator last);</code>
 605
 606 <blockquote>
 607 <b>Requires:</b> <code>InputIterator</code> is an input iterator.
 608 <code>value_type</code> is <code>EmplaceConstructible</code> into
 609 <code>multi_index_container</code> from <code>*first</code>.
 610 <code>first</code> and <code>last</code> are not iterators into any
 611 index of the <code>multi_index_container</code> to which this index belongs.
 612 <code>last</code> is reachable from <code>first</code>.<br>
 613 <b>Effects:</b>
 614 For each element of [<code>first</code>, <code>last</code>), in this
 615 order, inserts it into the <code>multi_index_container</code>
 616 to which this index belongs if
 617 <ul>
 618   <li>the index is non-unique OR no other element exists with
 619     equivalent key,</li>
 620   <li>AND insertion is allowed by all other indices of the
 621     <code>multi_index_container</code>.</li>
 622 </ul>
 623 <b>Complexity:</b> <code>O(m*H(n+m))</code>, where
 624 <code>m</code> is the number of elements in [<code>first</code>,
 625 <code>last</code>).<br>
 626 <b>Exception safety:</b> Basic.<br>
 627 </blockquote>
 628
 629 <code>void insert(std::initializer_list&lt;value_type&gt; list);</code>
 630
 631 <blockquote>
 632 <b>Effects:</b>
 633 <blockquote><pre>
 634 <span class=identifier>insert</span><span class=special>(</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>end</span><span class=special>())</span><span class=special>;</span>
 635 </pre></blockquote>
 636 </blockquote>
 637
 638 <code>iterator erase(iterator position);</code>
 639
 640 <blockquote>
 641 <b>Requires:</b> <code>position</code> is a valid dereferenceable  iterator
 642 of the index.<br>
 643 <b>Effects:</b> Deletes the element pointed to by <code>position</code>.<br>
 644 <b>Returns:</b> An iterator pointing to the element immediately following
 645 the one that was deleted, or <code>end()</code>
 646 if no such element exists.<br>
 647 <b>Complexity:</b> <code>O(D(n))</code>.<br>
 648 <b>Exception safety:</b> <code>nothrow</code>.<br>
 649 </blockquote>
 650
 651 <code>size_type erase(const key_type&amp; x);</code>
 652
 653 <blockquote>
 654 <b>Effects:</b> Deletes the elements with key equivalent to <code>x</code>.<br>
 655 <b>Returns:</b> Number of elements deleted.<br>
 656 <b>Complexity:</b> <code>O(log(n) + m*D(n))</code>, where <code>m</code> is
 657 the number of elements deleted.<br>
 658 <b>Exception safety:</b> Basic.<br>
 659 </blockquote>
 660
 661 <code>iterator erase(iterator first,iterator last);</code>
 662
 663 <blockquote>
 664 <b>Requires:</b> [<code>first</code>,<code>last</code>) is a valid
 665 range of the index.<br>
 666 <b>Effects:</b> Deletes the elements in [<code>first</code>,<code>last</code>).<br>
 667 <b>Returns:</b> <code>last</code>.<br>
 668 <b>Complexity:</b> <code>O(log(n) + m*D(n))</code>, where <code>m</code> is
 669 the number of elements in [<code>first</code>,<code>last</code>).<br>
 670 <b>Exception safety:</b> <code>nothrow</code>.<br>
 671 </blockquote>
 672
 673 <a name="replace"><code>bool replace(iterator position,const value_type&amp; x);</code></a><br>
 674 <code>bool replace(iterator position,value_type&amp;&amp; x);</code>
 675
 676 <blockquote>
 677 <b>Requires (first version):</b> <code>value_type</code> is <code>CopyAssignable</code>.
 678 <code>position</code> is a valid dereferenceable iterator of the index.<br>
 679 <b>Requires (second version):</b> <code>value_type</code> is <code>MoveAssignable</code>.
 680 <code>position</code> is a valid dereferenceable iterator of the index.<br>
 681 <b>Effects:</b> Assigns the value <code>x</code> to the element pointed
 682 to by <code>position</code> into the <code>multi_index_container</code> to which
 683 the index belongs if, for the value <code>x</code>
 684 <ul>
 685   <li>the index is non-unique OR no other element exists
 686     (except possibly <code>*position</code>) with equivalent key,</li>
 687   <li>AND replacing is allowed by all other indices of the
 688     <code>multi_index_container</code>.</li>
 689 </ul>
 690 <b>Postconditions:</b> Validity of <code>position</code> is preserved
 691 in all cases. If the key of the new value is equivalent to that of the
 692 replaced value, the position of the element does not change.<br>
 693 <b>Returns:</b> <code>true</code> if the replacement took place,
 694 <code>false</code> otherwise.<br>
 695 <b>Complexity:</b> <code>O(R(n))</code>.<br>
 696 <b>Exception safety:</b> Strong. If an exception is thrown by some
 697 user-provided operation the <code>multi_index_container</code> to which the index
 698 belongs remains in its original state.
 699 </blockquote>
 700
 701 <a name="modify">
 702 <code>template&lt;typename Modifier> bool modify(iterator position,Modifier mod);</code></a>
 703
 704 <blockquote>
 705 <b>Requires:</b> <code>mod</code> is a unary function object
 706 accepting arguments of type
 707 <code>value_type&amp;</code>. <code>position</code> is a valid dereferenceable
 708 iterator of the index.<br>
 709 <b>Effects:</b> Calls <code>mod(e)</code> where <code>e</code> is the element
 710 pointed to by <code>position</code> and rearranges <code>*position</code> into
 711 all the indices of the <code>multi_index_container</code>. Rearrangement is successful if
 712 <ul>
 713   <li>the index is non-unique OR no other element exists
 714     with  equivalent key,</li>
 715   <li>AND rearrangement is allowed by all other indices of the
 716     <code>multi_index_container</code>.</li>
 717 </ul>
 718 If the rearrangement fails, the element is erased.<br>
 719 <b>Postconditions:</b> Validity of <code>position</code> is preserved if the
 720 operation succeeds. If the key of the modified value is equivalent to that of the
 721 original value, the position of the element does not change.<br>
 722 <b>Returns:</b> <code>true</code> if the operation succeeded, <code>false</code>
 723 otherwise.<br>
 724 <b>Complexity:</b> <code>O(M(n))</code>.<br>
 725 <b>Exception safety:</b> Basic. If an exception is thrown by some
 726 user-provided operation (except possibly <code>mod</code>), then
 727 the element pointed to by <code>position</code> is erased.
 728 </blockquote>
 729
 730 <code>template&lt;typename Modifier,typename Rollback><br>
 731 bool modify(iterator position,Modifier mod,Rollback back);</code>
 732
 733 <blockquote>
 734 <b>Requires:</b> <code>mod</code> and <code>back</code> are unary function
 735 objects accepting arguments of type
 736 <code>value_type&amp;</code>. <code>position</code> is a valid dereferenceable
 737 iterator of the index. The sequence of operations <code>mod(e)</code>,
 738 <code>back(e)</code>, where <code>e</code> is the element
 739 pointed to by <code>position</code>, restores all keys of the element
 740 to their original state.<br>
 741 <b>Effects:</b> Calls <code>mod(e)</code> where <code>e</code> is the element
 742 pointed to by <code>position</code> and tries to rearrange <code>*position</code> into
 743 all the indices of the <code>multi_index_container</code>. Rearrangement is successful if
 744 <ul>
 745   <li>the index is non-unique OR no other element exists
 746     with  equivalent key,</li>
 747   <li>AND rearrangement is allowed by all other indices of the
 748     <code>multi_index_container</code>.</li>
 749 </ul>
 750 If the rearrangement fails, <code>back(e)</code> is invoked and the
 751 element is kept at its original position in all indices.<br>
 752 <b>Postconditions:</b> Validity of <code>position</code> is preserved except if
 753 the element is erased under the conditions described below.
 754 If the key of the modified value is equivalent to that of the
 755 original value, the position of the element does not change.<br>
 756 <b>Returns:</b> <code>true</code> if the operation succeeded, <code>false</code>
 757 otherwise.<br>
 758 <b>Complexity:</b> <code>O(M(n))</code>.<br>
 759 <b>Exception safety:</b> Strong, except if <code>back</code> throws an
 760 exception, in which case the modified element is erased. If <code>back</code>
 761 throws inside the handling code executing after some other user-provided
 762 operation has thrown, it is the exception generated by <code>back</code> that
 763 is rethrown.
 764 </blockquote>
 765
 766 <a name="modify_key">
 767 <code>template&lt;typename Modifier> bool modify_key(iterator position,Modifier mod);</code></a>
 768
 769 <blockquote>
 770 <b>Requires:</b> <code>key_from_value</code> is a read/write
 771 <a href="key_extraction.html#key_extractors"><code>Key Extractor</code></a>
 772 from <code>value_type</code>. <code>mod</code> is a
 773 unary function object accepting arguments of type
 774 <code>key_type&amp;</code>. <code>position</code> is a valid dereferenceable
 775 iterator of the index.<br>
 776 <b>Effects:</b> Equivalent to <code>modify(position,mod')</code>,
 777 with <code>mod'</code> defined in such a way that
 778 <code>mod'(x)</code> is the same as <code>mod(key(x))</code>, where
 779 <code>key</code> is the internal <code>KeyFromValue</code> object of the index.
 780 </blockquote>
 781
 782 <code>template&lt;typename Modifier,typename Rollback><br>
 783 bool modify_key(iterator position,Modifier mod,Rollback back);</code>
 784
 785 <blockquote>
 786 <b>Requires:</b> <code>key_from_value</code> is a read/write
 787 <a href="key_extraction.html#key_extractors"><code>Key Extractor</code></a>
 788 from <code>value_type</code>. <code>mod</code> and <code>back</code>
 789 are unary function objects accepting arguments of type
 790 <code>key_type&amp;</code>. <code>position</code> is a valid dereferenceable
 791 iterator of the index.
 792 The sequence of operations <code>mod(k)</code>,
 793 <code>back(k)</code>, where <code>k</code> is the key of the element
 794 pointed to by <code>position</code>, restores <code>k</code> to its original state.<br>
 795 <b>Effects:</b> Equivalent to <code>modify(position,mod',back')</code>,
 796 with <code>mod'</code> and <code>back</code> defined in such a way that
 797 <code>mod'(x)</code> is the same as <code>mod(key(x))</code> and
 798 <code>back'(x)</code> is the same as <code>back(key(x))</code>, where
 799 <code>key</code> is the internal <code>KeyFromValue</code> object of the index.
 800 </blockquote>
 801
 802 <h4><a name="observers">Observers</a></h4>
 803
 804 <p>Apart from standard <code>key_comp</code> and <code>value_comp</code>,
 805 ordered indices have a member function for retrieving the internal key extractor
 806 used.
 807 </p>
 808
 809 <code>key_from_value key_extractor()const;</code>
 810
 811 <blockquote>
 812 Returns a copy of the <code>key_from_value</code> object used to construct
 813 the index.<br>
 814 <b>Complexity:</b> Constant.
 815 </blockquote>
 816
 817 <h4><a name="set_operations">Set operations</a></h4>
 818
 819 <p>
 820 Ordered indices provide the full lookup functionality required by
 821 <b>[associative.reqmts]</b>, namely <code>find</code>,
 822 <code>count</code>, <code>lower_bound</code>, <code>upper_bound</code>
 823 and <code>equal_range</code>. Additionally, these member functions are
 824 templatized to allow for non-standard arguments, so extending
 825 the types of search operations allowed. The kind of arguments permissible
 826 when invoking the lookup member functions is defined by the following
 827 concept.
 828 </p>
 829
 830 <p>
 831 Consider a binary predicate <code>Compare</code> inducing a strict
 832 weak order over values of type <code>Key</code>. A pair of types (<code>CompatibleKey</code>,
 833 <code>CompatibleCompare</code>) is said to be a <i>compatible extension</i>
 834 of <code>Compare</code> if
 835 <ol>
 836   <li><code>CompatibleCompare</code> is a binary predicate over (<code>Key</code>,
 837     <code>CompatibleKey</code>),</li>
 838   <li><code>CompatibleCompare</code> is a binary predicate over (<code>CompatibleKey</code>,
 839     <code>Key</code>),</li>
 840   <li>if <code>c_comp(ck,k1)</code> then <code>!c_comp(k1,ck)</code>,</li>
 841   <li>if <code>!c_comp(ck,k1)</code> and <code>!comp(k1,k2)</code> then
 842     <code>!c_comp(ck,k2)</code>,</li>
 843   <li>if <code>!c_comp(k1,ck)</code> and <code>!comp(k2,k1)</code> then
 844     <code>!c_comp(k2,ck)</code>,</li>
 845 </ol>
 846 for every <code>c_comp</code> of type <code>CompatibleCompare</code>,
 847 <code>comp</code> of type <code>Compare</code>, <code>ck</code> of type
 848 <code>CompatibleKey</code> and <code>k1</code>, <code>k2</code> of type
 849 <code>Key</code>.
 850 </p>
 851
 852
 853
 854 <p>Additionally, a type <code>CompatibleKey</code> is said to be a
 855 <i>compatible key</i> of <code>Compare</code> if (<code>CompatibleKey</code>,
 856 <code>Compare</code>) is a compatible extension of <code>Compare</code>.
 857 This implies that <code>Compare</code>, as well as being a strict
 858 weak ordering, accepts arguments of type <code>CompatibleKey</code>,
 859 which usually means it has several overloads of <code>operator()</code>.
 860 </p>
 861
 862 <p>
 863 In the context of a compatible extension or a compatible key, the expressions
 864 "equivalent", "less than" and "greater than" take on their obvious
 865 interpretations.
 866 </p>
 867
 868 <code>template&lt;typename CompatibleKey> iterator find(const CompatibleKey&amp; x)const;
 869 </code>
 870
 871 <blockquote>
 872 <b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
 873 <code>key_compare</code>.<br>
 874 <b>Effects:</b> Returns a pointer to an element whose key is equivalent to
 875 <code>x</code>, or <code>end()</code> if such an element does not exist.<br>
 876 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 877 </blockquote>
 878
 879 <code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
 880 iterator find(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
 881 </code>
 882
 883 <blockquote>
 884 <b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
 885 is a compatible extension of <code>key_compare</code>.<br>
 886 <b>Effects:</b> Returns a pointer to an element whose key is equivalent to
 887 <code>x</code>, or <code>end()</code> if such an element does not exist.<br>
 888 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 889 </blockquote>
 890
 891 <code>template&lt;typename CompatibleKey> size_type<br>
 892 count(const CompatibleKey&amp; x)const;
 893 </code>
 894
 895 <blockquote>
 896 <b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
 897 <code>key_compare</code>.<br>
 898 <b>Effects:</b> Returns the number of elements with key equivalent to <code>x</code>.<br>
 899 <b>Complexity:</b> <code>O(log(n) + count(x))</code>.<br>
 900 </blockquote>
 901
 902 <code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
 903 size_type count(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
 904 </code>
 905
 906 <blockquote>
 907 <b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
 908 is a compatible extension of <code>key_compare</code>.<br>
 909 <b>Effects:</b> Returns the number of elements with key equivalent to <code>x</code>.<br>
 910 <b>Complexity:</b> <code>O(log(n) + count(x,comp))</code>.<br>
 911 </blockquote>
 912
 913 <code>template&lt;typename CompatibleKey><br>
 914 iterator lower_bound(const CompatibleKey&amp; x)const;
 915 </code>
 916
 917 <blockquote>
 918 <b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
 919 <code>key_compare</code>.<br>
 920 <b>Effects:</b> Returns an iterator pointing to the first element with
 921 key not less than <code>x</code>, or <code>end()</code> if such an element does
 922 not exist.<br>
 923 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 924 </blockquote>
 925
 926 <code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
 927 iterator lower_bound(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
 928 </code>
 929
 930 <blockquote>
 931 <b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
 932 is a compatible extension of <code>key_compare</code>.<br>
 933 <b>Effects:</b> Returns an iterator pointing to the first element with
 934 key not less than <code>x</code>, or <code>end()</code> if such an element does
 935 not exist.<br>
 936 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 937 </blockquote>
 938
 939 <code>template&lt;typename CompatibleKey><br>
 940 iterator upper_bound(const CompatibleKey&amp; x)const;
 941 </code>
 942
 943 <blockquote>
 944 <b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
 945 <code>key_compare</code>.<br>
 946 <b>Effects:</b> Returns an iterator pointing to the first element with
 947 key greater than <code>x</code>, or <code>end()</code> if such an element does
 948 not exist.<br>
 949 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 950 </blockquote>
 951
 952 <code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
 953 iterator upper_bound(const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
 954 </code>
 955
 956 <blockquote>
 957 <b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
 958 is a compatible extension of <code>key_compare</code>.<br>
 959 <b>Effects:</b> Returns an iterator pointing to the first element with
 960 key greater than <code>x</code>, or <code>end()</code> if such an element does
 961 not exist.<br>
 962 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 963 </blockquote>
 964
 965 <code>template&lt;typename CompatibleKey><br>
 966 std::pair&lt;iterator,iterator> equal_range(<br>
 967 &nbsp;&nbsp;const CompatibleKey&amp; x)const;
 968 </code>
 969
 970 <blockquote>
 971 <b>Requires:</b> <code>CompatibleKey</code> is a compatible key of
 972 <code>key_compare</code>.<br>
 973 <b>Effects:</b> Equivalent to <code>make_pair(lower_bound(x),upper_bound(x))</code>.<br>
 974 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 975 </blockquote>
 976
 977 <code>template&lt;typename CompatibleKey,typename CompatibleCompare><br>
 978 std::pair&lt;iterator,iterator> equal_range(<br>
 979 &nbsp;&nbsp;const CompatibleKey&amp; x,const CompatibleCompare&amp; comp)const;
 980 </code>
 981
 982 <blockquote>
 983 <b>Requires:</b> (<code>CompatibleKey</code>, <code>CompatibleCompare</code>)
 984 is a compatible extension of <code>key_compare</code>.<br>
 985 <b>Effects:</b> Equivalent to
 986 <code>make_pair(lower_bound(x,comp),upper_bound(x,comp))</code>.<br>
 987 <b>Complexity:</b> <code>O(log(n))</code>.<br>
 988 </blockquote>
 989
 990
 991 <h4><a name="range_operations">Range operations</a></h4>
 992
 993 <p>
 994 The member function <code>range</code> is not defined for sorted associative
 995 containers, but ordered indices provide it as a convenient utility. A range
 996 or interval is defined by two conditions for the lower and upper bounds, which
 997 are modeled after the following concepts.
 998 </p>
 999
1000 <p>
1001 Consider a binary predicate <code>Compare</code> inducing a strict
1002 weak order over values of type <code>Key</code>. A type <code>LowerBounder</code> is said to be
1003 a <i>lower bounder</i> of <code>Compare</code> if
1004 <ol>
1005   <li><code>LowerBounder</code> is a predicate over <code>Key</code>,</li>
1006   <li>if <code>lower(k1)</code> and <code>!comp(k2,k1)</code> then
1007     <code>lower(k2)</code>,</li>
1008 </ol>
1009 for every <code>lower</code> of type <code>LowerBounder</code>,
1010 <code>comp</code> of type <code>Compare</code>, and <code>k1</code>,
1011 <code>k2</code> of type <code>Key</code>. Similarly, an <i>upper bounder</i>
1012 is a type <code>UpperBounder</code> such that
1013 <ol>
1014   <li><code>UpperBounder</code> is a predcate over <code>Key</code>,</li>
1015   <li>if <code>upper(k1)</code> and <code>!comp(k1,k2)</code> then
1016     <code>upper(k2)</code>,</li>
1017 </ol>
1018 for every <code>upper</code> of type <code>UpperBounder</code>,
1019 <code>comp</code> of type <code>Compare</code>, and <code>k1</code>,
1020 <code>k2</code> of type <code>Key</code>.
1021 </p>
1022
1023 <code>template&lt;typename LowerBounder,typename UpperBounder><br>
1024 std::pair&lt;iterator,iterator> range(<br>
1025 &nbsp;&nbsp;LowerBounder lower,UpperBounder upper)const;
1026 </code>
1027
1028 <blockquote>
1029 <b>Requires:</b> <code>LowerBounder</code> and <code>UpperBounder</code> are
1030 a lower and upper bounder of <code>key_compare</code>, respectively.<br>
1031 <b>Effects:</b> Returns a pair of iterators pointing to the beginning and one
1032 past the end of the subsequence of elements satisfying <code>lower</code> and
1033 <code>upper</code> simultaneously. If no such elements exist, the iterators
1034 both point to the first element satisfying <code>lower</code>, or else
1035 are equal to <code>end()</code> if this latter element does not exist.<br>
1036 <b>Complexity:</b> <code>O(log(n))</code>.<br>
1037 <b>Variants:</b> In place of <code>lower</code> or <code>upper</code> (or both),
1038 the singular value <code>boost::multi_index::unbounded</code> can be
1039 provided. This acts as a predicate which all values of type <code>key_type</code>
1040 satisfy.<br>
1041 </blockquote>
1042
1043 <h4><a name="serialization">Serialization</a></h4>
1044
1045 <p>
1046 Indices cannot be serialized on their own, but only as part of the
1047 <code>multi_index_container</code> into which they are embedded. In describing
1048 the additional preconditions and guarantees associated to ordered indices
1049 with respect to serialization of their embedding containers, we
1050 use the concepts defined in the <code>multi_index_container</code>
1051 <a href="multi_index_container.html#serialization">serialization section</a>.
1052 </p>
1053
1054 Operation: saving of a <code>multi_index_container</code> <code>m</code> to an
1055 output archive (XML archive) <code>ar</code>.
1056
1057 <blockquote>
1058 <b>Requires:</b> No additional requirements to those imposed by the container.
1059 </blockquote>
1060
1061 Operation: loading of a <code>multi_index_container</code> <code>m'</code> from an
1062 input archive (XML archive) <code>ar</code>.
1063
1064 <blockquote>
1065 <b>Requires:</b> Additionally to the general requirements, <code>value_comp()</code>
1066 must be serialization-compatible with <code>m.get&lt;i&gt;().value_comp()</code>,
1067 where <code>i</code> is the position of the ordered index in the container.<br>
1068 <b>Postconditions:</b> On succesful loading, each of the elements of
1069 [<code>begin()</code>, <code>end()</code>) is a restored copy of the corresponding
1070 element in [<code>m.get&lt;i&gt;().begin()</code>, <code>m.get&lt;i&gt;().end()</code>).
1071 </blockquote>
1072
1073 Operation: saving of an <code>iterator</code> or <code>const_iterator</code>
1074 <code>it</code> to an output archive (XML archive) <code>ar</code>.
1075
1076 <blockquote>
1077 <b>Requires:</b> <code>it</code> is a valid iterator of the index. The associated
1078 <code>multi_index_container</code> has been previously saved.
1079 </blockquote>
1080
1081 Operation: loading of an <code>iterator</code> or <code>const_iterator</code>
1082 <code>it'</code> from an input archive (XML archive) <code>ar</code>.
1083
1084 <blockquote>
1085 <b>Postconditions:</b> On succesful loading, if <code>it</code> was dereferenceable
1086 then <code>*it'</code> is the restored copy of <code>*it</code>, otherwise
1087 <code>it'==end()</code>.<br>
1088 <b>Note:</b> It is allowed that <code>it</code> be a <code>const_iterator</code>
1089 and the restored <code>it'</code> an <code>iterator</code>, or viceversa.
1090 </blockquote>
1091
1092 <hr>
1093
1094 <div class="prev_link"><a href="indices.html"><img src="../prev.gif" alt="index reference" border="0"><br>
1095 Index reference
1096 </a></div>
1097 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
1098 Boost.MultiIndex reference
1099 </a></div>
1100 <div class="next_link"><a href="hash_indices.html"><img src="../next.gif" alt="hashed indices" border="0"><br>
1101 Hashed indices
1102 </a></div><br clear="all" style="clear: all;">
1103
1104 <br>
1105
1106 <p>Revised August 20th 2014</p>
1107
1108 <p>&copy; Copyright 2003-2014 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
1109 Distributed under the Boost Software
1110 License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
1111 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
1112 http://www.boost.org/LICENSE_1_0.txt</a>)
1113 </p>
1114
1115 </body>
1116 </html>