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