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