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 - Random access 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="seq_indices.html"> 10<link rel="up" href="index.html"> 11<link rel="next" href="key_extraction.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 Random access indices reference</h1> 17 18<div class="prev_link"><a href="seq_indices.html"><img src="../prev.gif" alt="sequenced indices" border="0"><br> 19Sequenced 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="key_extraction.html"><img src="../next.gif" alt="key extraction" border="0"><br> 25Key extraction 26</a></div><br clear="all" style="clear: all;"> 27 28<hr> 29 30<h2>Contents</h2> 31 32<ul> 33 <li><a href="#rnd_index_fwd_synopsis">Header 34 <code>"boost/multi_index/random_access_index_fwd.hpp"</code> synopsis</a></li> 35 <li><a href="#synopsis">Header 36 <code>"boost/multi_index/random_access_index.hpp"</code> synopsis</a> 37 <ul> 38 <li><a href="#random_access"><code>random_access</code> index specifier</a></li> 39 <li><a href="#rnd_indices">Random access indices</a> 40 <ul> 41 <li><a href="#complexity_signature">Complexity signature</a></li> 42 <li><a href="#instantiation_types">Instantiation types</a></li> 43 <li><a href="#constructors">Constructors, copy and assignment</a></li> 44 <li><a href="#iterators">Iterators</a></li> 45 <li><a href="#capacity">Capacity operations</a></li> 46 <li><a href="#modifiers">Modifiers</a></li> 47 <li><a href="#list_operations">List operations</a></li> 48 <li><a href="#rearrange_operations">Rearrange operations</a></li> 49 <li><a href="#serialization">Serialization</a></li> 50 </ul> 51 </li> 52 </ul> 53 </li> 54</ul> 55 56<h2> 57<a name="rnd_index_fwd_synopsis">Header 58<a href="../../../../boost/multi_index/random_access_index_fwd.hpp"> 59<code>"boost/multi_index/random_access_index_fwd.hpp"</code></a> synopsis</a></h2> 60 61<blockquote><pre> 62<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span> 63 64<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span> 65 66<span class=comment>// random_access index specifier</span> 67 68<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>TagList</span><span class=special>=</span><span class=identifier>tag</span><span class=special><></span> <span class=special>></span> <span class=keyword>struct</span> <span class=identifier>random_access</span><span class=special>;</span> 69 70<span class=comment>// indices</span> 71 72<span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span> 73 74<span class=keyword>template</span><span class=special><</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> 75 76<span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span> 77 78<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span> 79 80<span class=special>}</span> <span class=comment>// namespace boost</span> 81</pre></blockquote> 82 83<p> 84<code>random_access_index_fwd.hpp</code> provides forward declarations for the 85<a href="#random_access"><code>random_access</code></a> index specifier and 86its associated <a href="#rnd_indices">random access index</a> class. 87</p> 88 89<h2> 90<a name="synopsis">Header 91<a href="../../../../boost/multi_index/random_access_index.hpp"> 92<code>"boost/multi_index/random_access_index.hpp"</code></a> synopsis</a></h2> 93 94<blockquote><pre> 95<span class=preprocessor>#include</span> <span class=special><</span><span class=identifier>initializer_list</span><span class=special>></span> 96 97<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span> 98 99<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span> 100 101<span class=comment>// random_access index specifier</span> 102 103<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>TagList</span><span class=special>=</span><span class=identifier>tag</span><span class=special><></span> <span class=special>></span> <span class=keyword>struct</span> <span class=identifier>random_access</span><span class=special>;</span> 104 105<span class=comment>// indices</span> 106 107<span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span> 108 109<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> 110 111<span class=comment>// index comparison:</span> 112 113<span class=comment>// <b>OP</b> is any of ==,<,!=,>,>=,<=</span> 114 115<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span> 116<span class=keyword>bool</span> <span class=keyword>operator</span> <b><i>OP</i></b><span class=special>(</span> 117 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</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><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>);</span> 118 119<span class=comment>// index specialized algorithms:</span> 120 121<span class=keyword>template</span><span class=special><</span><b>implementation defined</b><span class=special>></span> 122<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> 123 124<span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span> 125 126<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span> 127 128<span class=special>}</span> <span class=comment>// namespace boost</span> 129</pre></blockquote> 130 131<h3><a name="random_access"> 132<code>random_access</code> index specifier 133</a></h3> 134 135<p> 136This index specifier allows for insertion of a <a href="#rnd_indices">random 137access index</a>.</p> 138 139<blockquote><pre> 140<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>TagList</span><span class=special>=</span><span class=identifier>tag</span><span class=special><></span> <span class=special>></span> <span class=keyword>struct</span> <span class=identifier>random_access</span><span class=special>;</span> 141</pre></blockquote> 142 143<p>If provided, <code>TagList</code> must be an instantiation of 144<a href="indices.html#tag"><code>tag</code></a>. 145</p> 146 147<h3><a name="rnd_indices">Random access indices</a></h3> 148 149<p> 150Random access indices are free-order sequences with constant time 151positional access and random access iterators. Elements in a 152random access index are by default sorted according to their order of 153insertion: this means that new elements inserted through a different index 154of the <code>multi_index_container</code> are appended to the end of the 155random access index; additionally, facilities are provided 156for further rearrangement of the elements. The public interface of 157random access indices includes that of 158<a href="seq_indices.html">sequenced indices</a>, with differences in 159the complexity of the operations, plus extra operations for 160positional access (<code>operator[]</code> and <code>at()</code>) and 161for capacity handling. 162Iterators (including to the end of the index) and pointers and references to an element 163remain valid during the lifetime of the associated container (which can change 164upon swapping) regardless of the capacity status, or until the referred-to element 165is erased or extracted; pointers and references to an extracted element, 166but not so for iterators, become valid again once the element is re-inserted. 167</p> 168 169<p> 170Except where noted or if the corresponding interface does not exist, random access 171indices verify the same container requirements as <code>std::vector</code> 172plus the requirements for <code>std::list</code> specific list operations at 173<b>[list.ops]</b>. Some of the most important differences with respect to 174<code>std::vector</code> are: 175<ul> 176 <li>Random access indices do not provide memory contiguity, and hence do not 177 have <code>data</code> member functions. 178 </li> 179 180 <li>The complexity of some operations, notably insertion and deletion, differ 181 from those of <code>std::vector</code>. 182 </li> 183 <li>Unlike as in <code>std::vector</code>, insertions into a random access index 184 may fail due to clashings with other indices. This alters the semantics 185 of the operations provided with respect to their analogues in 186 <code>std::vector</code>. 187 </li> 188 <li>Elements in a random access index are not mutable, and can only be changed 189 in place by means of <a href="#replace"><code>replace</code></a> and 190 <a href="#modify"><code>modify</code></a> member functions. 191 </li> 192 <li><code>push_front</code> and <code>pop_front</code> are provided for 193 compatibility with sequenced indices, even though they take linear time to execute. 194 </li></ul> 195</p> 196 197<blockquote><pre> 198<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span> 199 200<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span> 201 202<span class=keyword>namespace</span> <span class=identifier>detail</span><span class=special>{</span> 203 204<span class=keyword>template</span><span class=special><</span><b>implementation defined: dependent on types Value, Allocator, TagList</b><span class=special>></span> 205<span class=keyword>class</span> <b>name is implementation defined</b> 206<span class=special>{</span> 207<span class=keyword>public</span><span class=special>:</span> 208 <span class=comment>// types:</span> 209 210 <span class=keyword>typedef</span> <span class=identifier>Value</span> <span class=identifier>value_type</span><span class=special>;</span> 211 <span class=keyword>typedef</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tuples</span><span class=special>::</span><span class=identifier>null_type</span> <span class=identifier>ctor_args</span><span class=special>;</span> 212 <span class=keyword>typedef</span> <span class=identifier>TagList</span> <span class=identifier>tag_list</span><span class=special>;</span> 213 <span class=keyword>typedef</span> <span class=identifier>Allocator</span> <span class=identifier>allocator_type</span><span class=special>;</span> 214 <span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>allocator_type</span><span class=special>::</span><span class=identifier>reference</span> <span class=identifier>reference</span><span class=special>;</span> 215 <span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>allocator_type</span><span class=special>::</span><span class=identifier>const_reference</span> <span class=identifier>const_reference</span><span class=special>;</span> 216 <span class=keyword>typedef</span> <b>implementation defined</b> <span class=identifier>iterator</span><span class=special>;</span> 217 <span class=keyword>typedef</span> <b>implementation defined</b> <span class=identifier>const_iterator</span><span class=special>;</span> 218 <span class=keyword>typedef</span> <b>implementation defined</b> <span class=identifier>size_type</span><span class=special>;</span> 219 <span class=keyword>typedef</span> <b>implementation defined</b> <span class=identifier>difference_type</span><span class=special>;</span> 220 <span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>allocator_type</span><span class=special>::</span><span class=identifier>pointer</span> <span class=identifier>pointer</span><span class=special>;</span> 221 <span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>allocator_type</span><span class=special>::</span><span class=identifier>const_pointer</span> <span class=identifier>const_pointer</span><span class=special>;</span> 222 <span class=keyword>typedef</span> <b>equivalent to 223 std::reverse_iterator<iterator></b> <span class=identifier>reverse_iterator</span><span class=special>;</span> 224 <span class=keyword>typedef</span> <b>equivalent to 225 std::reverse_iterator<const_iterator></b> <span class=identifier>const_reverse_iterator</span><span class=special>;</span> 226 <span class=keyword>typedef</span> <b>same as owning container </b><span class=identifier>node_type</span><span class=special>;</span> 227 <span class=keyword>typedef</span> <b>following [container.insert.return] spec </b><span class=identifier>insert_return_type</span><span class=special>;</span> 228 229 <span class=comment>// construct/copy/destroy:</span> 230 231 <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> 232 <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> 233 234 <span class=keyword>template</span> <span class=special><</span><span class=keyword>class</span> <span class=identifier>InputIterator</span><span class=special>></span> 235 <span class=keyword>void</span> <span class=identifier>assign</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> 236 <span class=keyword>void</span> <span class=identifier>assign</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> 237 <span class=keyword>void</span> <span class=identifier>assign</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=identifier>value_type</span><span class=special>&</span> <span class=identifier>value</span><span class=special>);</span> 238 239 <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> 240 241 <span class=comment>// iterators:</span> 242 243 <span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span> 244 <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> 245 <span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span> 246 <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> 247 <span class=identifier>reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span> 248 <span class=identifier>const_reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span> 249 <span class=identifier>reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span> 250 <span class=identifier>const_reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span> 251 <span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span> 252 <span class=identifier>const_iterator</span> <span class=identifier>cend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span> 253 <span class=identifier>const_reverse_iterator</span> <span class=identifier>crbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span> 254 <span class=identifier>const_reverse_iterator</span> <span class=identifier>crend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span> 255 256 <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> 257 <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> 258 259 <span class=comment>// capacity:</span> 260 261 <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> 262 <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> 263 <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> 264 <span class=identifier>size_type</span> <span class=identifier>capacity</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span> 265 <span class=keyword>void</span> <span class=identifier>reserve</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>m</span><span class=special>);</span> 266 <span class=keyword>void</span> <span class=identifier>shrink_to_fit</span><span class=special>();</span> 267 268 <span class=keyword>void</span> <span class=identifier>resize</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>n</span><span class=special>);</span> 269 <span class=keyword>void</span> <span class=identifier>resize</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=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span> 270 271 <span class=comment>// access:</span> 272 273 <span class=identifier>const_reference</span> <span class=keyword>operator</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> 274 <span class=identifier>const_reference</span> <span class=identifier>at</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> 275 <span class=identifier>const_reference</span> <span class=identifier>front</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span> 276 <span class=identifier>const_reference</span> <span class=identifier>back</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span> 277 278 <span class=comment>// modifiers:</span> 279 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>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_front</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>push_front</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>push_front</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=keyword>void</span> <span class=identifier>pop_front</span><span class=special>();</span> 285 286 <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> 287 <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_back</span><span class=special>(</span><span class=identifier>Args</span><span class=special>&&...</span> <span class=identifier>args</span><span class=special>);</span> 288 <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>push_back</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> 289 <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>push_back</span><span class=special>(</span><span class=identifier>value_type</span><span class=special>&&</span> <span class=identifier>x</span><span class=special>);</span> 290 <span class=keyword>void</span> <span class=identifier>pop_back</span><span class=special>();</span> 291 292 <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> 293 <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>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> 294 <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>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> 295 <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>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> 296 <span class=keyword>void</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>size_type</span> <span class=identifier>m</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> 297 <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>InputIterator</span><span class=special>></span> 298 <span class=keyword>void</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>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> 299 <span class=keyword>void</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>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> 300 <span class=identifier>insert_return_type</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> 301 302 <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> 303 304 <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> 305 <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> 306 307 <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> 308 <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> 309 <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> 310 <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> 311 <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> 312 313 <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> 314 315 <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span> 316 317 <span class=comment>// list operations:</span> 318 319 <span class=keyword>void</span> <span class=identifier>splice</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span> 320 <span class=keyword>void</span> <span class=identifier>splice</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=identifier>iterator</span> <span class=identifier>i</span><span class=special>);</span> 321 <span class=keyword>void</span> <span class=identifier>splice</span><span class=special>(</span> 322 <span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</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> 323 324 <span class=keyword>void</span> <span class=identifier>remove</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>value</span><span class=special>);</span> 325 <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Predicate</span><span class=special>></span> <span class=keyword>void</span> <span class=identifier>remove_if</span><span class=special>(</span><span class=identifier>Predicate</span> <span class=identifier>pred</span><span class=special>);</span> 326 327 <span class=keyword>void</span> <span class=identifier>unique</span><span class=special>();</span> 328 <span class=keyword>template</span> <span class=special><</span><span class=keyword>class</span> <span class=identifier>BinaryPredicate</span><span class=special>></span> 329 <span class=keyword>void</span> <span class=identifier>unique</span><span class=special>(</span><span class=identifier>BinaryPredicate</span> <span class=identifier>binary_pred</span><span class=special>);</span> 330 331 <span class=keyword>void</span> <span class=identifier>merge</span><span class=special>(</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span> 332 <span class=keyword>template</span> <span class=special><</span><span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>></span> <span class=keyword>void</span> <span class=identifier>merge</span><span class=special>(</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=identifier>Compare</span> <span class=identifier>comp</span><span class=special>);</span> 333 334 <span class=keyword>void</span> <span class=identifier>sort</span><span class=special>();</span> 335 <span class=keyword>template</span> <span class=special><</span><span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>></span> <span class=keyword>void</span> <span class=identifier>sort</span><span class=special>(</span><span class=identifier>Compare</span> <span class=identifier>comp</span><span class=special>);</span> 336 337 <span class=keyword>void</span> <span class=identifier>reverse</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span> 338 339 <span class=comment>// rearrange operations:</span> 340 341 <span class=keyword>void</span> <span class=identifier>relocate</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>iterator</span> <span class=identifier>i</span><span class=special>);</span> 342 <span class=keyword>void</span> <span class=identifier>relocate</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</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> 343 <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>InputIterator</span><span class=special>></span> <span class=keyword>void</span> <span class=identifier>rearrange</span><span class=special>(</span><span class=identifier>InputIterator</span> <span class=identifier>first</span><span class=special>);</span> 344<span class=special>}</span> 345 346<span class=comment>// index comparison:</span> 347 348<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span> 349<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>==(</span> 350 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span> 351 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span> 352<span class=special>{</span> 353 <span class=keyword>return</span> <span class=identifier>x</span><span class=special>.</span><span class=identifier>size</span><span class=special>()==</span><span class=identifier>y</span><span class=special>.</span><span class=identifier>size</span><span class=special>()&&</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>equal</span><span class=special>(</span><span class=identifier>x</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>x</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>y</span><span class=special>.</span><span class=identifier>begin</span><span class=special>());</span> 354<span class=special>}</span> 355 356<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span> 357<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special><(</span> 358 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span> 359 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span> 360<span class=special>{</span> 361 <span class=keyword>return</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>lexicographical_compare</span><span class=special>(</span><span class=identifier>x</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>x</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>y</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>y</span><span class=special>.</span><span class=identifier>end</span><span class=special>());</span> 362<span class=special>}</span> 363 364<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span> 365<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>!=(</span> 366 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span> 367 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</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=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span> 373<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>>(</span> 374 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span> 375 <span class=special>,</span><span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span> 376<span class=special>{</span> 377 <span class=keyword>return</span> <span class=identifier>y</span><span class=special><</span><span class=identifier>x</span><span class=special>;</span> 378<span class=special>}</span> 379 380<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span> 381<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>>=(</span> 382 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span> 383 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span> 384<span class=special>{</span> 385 <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> 386<span class=special>}</span> 387 388<span class=keyword>template</span><span class=special><</span><b>arg set 1</b><span class=special>,</span><b>arg set 2</b><span class=special>></span> 389<span class=keyword>bool</span> <span class=keyword>operator</span><span class=special><=(</span> 390 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 1</b><span class=special>>&</span> <span class=identifier>x</span><span class=special>,</span> 391 <span class=keyword>const</span> <b>index class name</b><span class=special><</span><b>arg set 2</b><span class=special>>&</span> <span class=identifier>y</span><span class=special>)</span> 392<span class=special>{</span> 393 <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> 394<span class=special>}</span> 395 396<span class=comment>// index specialized algorithms:</span> 397 398<span class=keyword>template</span><span class=special><</span><b>implementation defined</b><span class=special>></span> 399<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> 400 401<span class=special>}</span> <span class=comment>// namespace boost::multi_index::detail</span> 402 403<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span> 404 405<span class=special>}</span> <span class=comment>// namespace boost</span> 406</pre></blockquote> 407 408<h4><a name="complexity_signature">Complexity signature</a></h4> 409 410<p> 411Here and in the descriptions of operations of random access indices, we 412adopt the scheme outlined in the 413<a href="indices.html#complexity_signature">complexity signature 414section</a>. The complexity signature of random access indices is: 415<ul> 416 <li>copying: <code>c(n)=n*log(n)</code>,</li> 417 <li>insertion: <code>i(n)=1</code> (amortized constant),</li> 418 <li>hinted insertion: <code>h(n)=1</code> (amortized constant),</li> 419 <li>deletion: <code>d(n)=m</code>, where <code>m</code> is the distance 420 from the deleted element to the end of the sequence,</li> 421 <li>replacement: <code>r(n)=1</code> (constant),</li> 422 <li>modifying: <code>m(n)=1</code> (constant).</li> 423</ul> 424The following expressions are also used as a convenience for writing down some 425of the complexity formulas: 426</p> 427 428<blockquote> 429<code>shl(a,b)</code> = <code>a+b</code> if a is nonzero, <code>0</code> otherwise.<br> 430<code>rel(a,b,c)</code> = if <code>a<b</code>, <code>c-a</code>, else <code>a-b</code>, 431</blockquote> 432 433<p> 434(<code>shl</code> and <code>rel</code> stand for <i>shift left</i> and 435<i>relocate</i>, respectively.) 436</p> 437 438<h4><a name="instantiation_types">Instantiation types</a></h4> 439 440<p>Random access indices are instantiated internally to <code>multi_index_container</code> 441and specified by means of <a href="indices.html#indexed_by"> 442<code>indexed_by</code></a> with the <a href="#random_access"><code>random_access</code></a> 443index specifier. Instantiations are dependent on the following types: 444<ul> 445 <li><code>Value</code> from <code>multi_index_container</code>,</li> 446 <li><code>Allocator</code> from <code>multi_index_container</code>,</li> 447 <li><code>TagList</code> from the index specifier (if provided, otherwise <code>tag<></code> is assumed).</li> 448</ul> 449<code>TagList</code> must be an instantiation of 450<a href="indices.html#tag"><code>tag</code></a>. 451</p> 452 453<h4><a name="constructors">Constructors, copy and assignment</a></h4> 454 455<p> 456As explained in the <a href="indices.html#index_concepts">index 457concepts section</a>, indices do not have public constructors or destructors. 458Assignment, on the other hand, is provided. 459</p> 460 461<code><b>index class name</b>& operator=(const <b>index class name</b>& x);</code> 462 463<blockquote> 464<b>Effects:</b> 465<blockquote><pre> 466<span class=identifier>a</span><span class=special>=</span><span class=identifier>b</span><span class=special>;</span> 467</pre></blockquote> 468where <code>a</code> and <code>b</code> are the <code>multi_index_container</code> 469objects to which <code>*this</code> and <code>x</code> belong, respectively.<br> 470<b>Returns:</b> <code>*this</code>.<br> 471</blockquote> 472 473<code><b>index class name</b>& operator=(std::initializer_list<value_type> list);</code> 474 475<blockquote> 476<b>Effects:</b> 477<blockquote><pre> 478<span class=identifier>a</span><span class=special>=</span><span class=identifier>list</span><span class=special>;</span> 479</pre></blockquote> 480where <code>a</code> is the <code>multi_index_container</code> 481object to which <code>*this</code> belongs.<br> 482<b>Returns:</b> <code>*this</code>.<br> 483</blockquote> 484 485<code>template <class InputIterator><br> 486void assign(InputIterator first,InputIterator last);</code> 487 488<blockquote> 489<b>Effects:</b> 490<blockquote><pre> 491<span class=identifier>clear</span><span class=special>();</span> 492<span class=identifier>insert</span><span class=special>(</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>first</span><span class=special>,</span><span class=identifier>last</span><span class=special>);</span> 493</pre></blockquote> 494</blockquote> 495 496<code>void assign(std::initializer_list<value_type> list);</code> 497 498<blockquote> 499<b>Effects:</b> 500<blockquote><pre> 501<span class=identifier>assign</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> 502</pre></blockquote> 503</blockquote> 504 505<code>void assign(size_type n,const value_type& value);</code> 506 507<blockquote> 508<b>Effects:</b> 509<blockquote><pre> 510<span class=identifier>clear</span><span class=special>();</span> 511<span class=keyword>for</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>i</span><span class=special>=</span><span class=number>0</span><span class=special>;</span><span class=identifier>i</span><span class=special><</span><span class=identifier>n</span><span class=special>;++</span><span class=identifier>n</span><span class=special>)</span><span class=identifier>push_back</span><span class=special>(</span><span class=identifier>v</span><span class=special>);</span> 512</pre></blockquote> 513</blockquote> 514 515<h4><a name="iterators">Iterators</a></h4> 516 517<code>iterator iterator_to(const value_type& x);<br> 518const_iterator iterator_to(const value_type& x)const;</code> 519 520<blockquote> 521<b>Requires:</b> <code>x</code> is a reference to an element of the container.<br> 522<b>Returns:</b> An iterator to <code>x</code>.<br> 523<b>Complexity:</b> Constant.<br> 524<b>Exception safety:</b> <code>nothrow</code>.<br> 525</blockquote> 526 527<h4><a name="capacity">Capacity operations</a></h4> 528 529<a name="capacity_memfun"><code>size_type capacity()const noexcept;</code></a> 530 531<blockquote> 532<b>Returns:</b> The total number of elements <code>c</code> such that, when 533<code>size()<c</code>, back insertions happen in constant time (the 534general case as described by 535<a href="#complexity_signature"><code>i(n)</code></a> is <i>amortized</i> 536constant time.)<br> 537<b>Note:</b> Validity of iterators and references to elements 538is preserved in all insertions, regardless of the capacity status. 539</blockquote> 540 541<a name="reserve"><code>void reserve(size_type m);</code></a> 542 543<blockquote> 544<b>Effects:</b> If the previous value of <code>capacity()</code> 545was greater than or equal to <code>m</code>, nothing is done; 546otherwise, the internal capacity is changed so that 547<code>capacity()>=m</code>.<br> 548<b>Complexity:</b> If the capacity is not changed, constant; 549otherwise <code>O(n)</code>.<br> 550<b>Exception safety:</b> If the capacity is not changed, <code>nothrow</code>; 551otherwise, strong.<br> 552</blockquote> 553 554<code>void shrink_to_fit();</code> 555 556<blockquote> 557<b>Effects:</b> Reduces <code>capacity()</code> to <code>size()</code>.<br> 558<b>Complexity:</b> If the capacity is not changed, constant; 559otherwise <code>O(n)</code>.<br> 560<b>Exception safety:</b> If the capacity is not changed, <code>nothrow</code>; 561otherwise, strong.<br> 562</blockquote> 563 564<code>void resize(size_type n);<br> 565void resize(size_type n,const value_type& x);</code> 566 567<blockquote> 568<b>Requires (first version):</b> <code>value_type</code> is <code>DefaultInsertable</code> 569into <code>multi_index_container</code>.<br> 570<b>Requires (second version):</b> <code>value_type</code> is <code>CopyInsertable</code> 571into <code>multi_index_container</code>.<br> 572<b>Effects:</b> If <code>size()<n</code>, tries to append <code>n-size()</code> default-inserted 573elements (first version) or copies of <code>x</code> (second version) at the end of 574the index. If <code>n<size()</code>, erases the last <code>size()-n</code> elements.<br> 575<b>Note:</b> If an expansion is requested, the size of the index is not guaranteed 576to be <code>n</code> after this operation (other indices may ban insertions.) 577</blockquote> 578 579<h4><a name="modifiers">Modifiers</a></h4> 580 581<code>template<typename... Args><br> 582std::pair<iterator,bool> emplace_front(Args&&... args);</code> 583 584<blockquote> 585<b>Effects:</b> 586<blockquote><pre> 587<span class=identifier>emplace</span><span class=special>(</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>forward</span><span class=special><</span><span class=identifier>Args</span><span class=special>>(</span><span class=identifier>args</span><span class=special>)...);</span> 588</pre></blockquote> 589<b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code> 590is <code>true</code> if and only if insertion took place. On successful 591insertion, <code>p.first</code> points to the element inserted; otherwise, 592<code>p.first</code> points to an element that caused the insertion to be banned. 593Note that more than one element can be causing insertion not to be allowed.<br> 594</blockquote> 595 596<code>std::pair<iterator,bool> push_front(const value_type& x);</code><br> 597<code>std::pair<iterator,bool> push_front(value_type&& x);</code> 598 599<blockquote> 600<b>Effects:</b> 601<blockquote><pre> 602<span class=identifier>insert</span><span class=special>(</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>x</span><span class=special>);</span> <span class=comment>// lvalue ref version</span> 603<span class=identifier>insert</span><span class=special>(</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>move</span><span class=special>(</span><span class=identifier>x</span><span class=special>));</span> <span class=comment>// rvalue ref version</span> 604</pre></blockquote> 605<b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code> 606is <code>true</code> if and only if insertion took place. On successful 607insertion, <code>p.first</code> points to the element inserted; otherwise, 608<code>p.first</code> points to an element that caused the insertion to be banned. 609Note that more than one element can be causing insertion not to be allowed.<br> 610</blockquote> 611 612<code>template<typename... Args><br> 613std::pair<iterator,bool> emplace_back(Args&&... args);</code> 614 615<blockquote> 616<b>Effects:</b> 617<blockquote><pre> 618<span class=identifier>emplace</span><span class=special>(</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>forward</span><span class=special><</span><span class=identifier>Args</span><span class=special>>(</span><span class=identifier>args</span><span class=special>)...);</span> 619</pre></blockquote> 620<b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code> 621is <code>true</code> if and only if insertion took place. On successful 622insertion, <code>p.first</code> points to the element inserted; otherwise, 623<code>p.first</code> points to an element that caused the insertion to be banned. 624Note that more than one element can be causing insertion not to be allowed.<br> 625</blockquote> 626 627<code>std::pair<iterator,bool> push_back(const value_type& x);</code><br> 628<code>std::pair<iterator,bool> push_back(value_type&& x);</code> 629 630<blockquote> 631<b>Effects:</b> 632<blockquote><pre> 633<span class=identifier>insert</span><span class=special>(</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>x</span><span class=special>);</span> <span class=comment>// lvalue ref version</span> 634<span class=identifier>insert</span><span class=special>(</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>move</span><span class=special>(</span><span class=identifier>x</span><span class=special>));</span> <span class=comment>// rvalue ref version</span> 635</pre></blockquote> 636<b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code> 637is <code>true</code> if and only if insertion took place. On successful 638insertion, <code>p.first</code> points to the element inserted; otherwise, 639<code>p.first</code> points to an element that caused the insertion to be banned. 640Note that more than one element can be causing insertion not to be allowed.<br> 641</blockquote> 642 643<code>template<typename... Args><br> 644 std::pair<iterator,bool> emplace(iterator position,Args&&... args);</code> 645 646<blockquote> 647<b>Requires:</b> <code>value_type</code> is <code>EmplaceConstructible</code> 648into <code>multi_index_container</code> from <code>args</code>.<br> 649<b>Effects:</b> Inserts a <code>value_type</code> object constructed with 650<code>std::forward<Args>(args)...</code> before <code>position</code> if insertion 651is allowed by all other indices of the <code>multi_index_container</code>.<br> 652<b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code> 653is <code>true</code> if and only if insertion took place. On successful insertion, 654<code>p.first</code> points to the element inserted; otherwise, <code>p.first</code> 655points to an element that caused the insertion to be banned. Note that more than 656one element can be causing insertion not to be allowed.<br> 657<b>Complexity:</b> <code>O(shl(end()-position,1) + I(n))</code>.<br> 658<b>Exception safety:</b> Strong.<br> 659</blockquote> 660 661<code>std::pair<iterator,bool> insert(iterator position,const value_type& x);</code><br> 662<code>std::pair<iterator,bool> insert(iterator position,value_type&& x);</code> 663 664<blockquote> 665<b>Requires (first version):</b> <code>value_type</code> is <code>CopyInsertable</code> 666into <code>multi_index_container</code>. 667<code>position</code> is a valid iterator of the index.<br> 668<b>Requires (second version):</b> <code>value_type</code> is <code>MoveInsertable</code> 669into <code>multi_index_container</code>. 670<code>position</code> is a valid iterator of the index.<br> 671<b>Effects:</b> Inserts <code>x</code> before <code>position</code> if insertion 672is allowed by all other indices of the <code>multi_index_container</code>.<br> 673<b>Returns:</b> The return value is a pair <code>p</code>. <code>p.second</code> 674is <code>true</code> if and only if insertion took place. On successful 675insertion, <code>p.first</code> points to the element inserted; otherwise, 676<code>p.first</code> points to an element that caused the insertion to be banned. 677Note that more than one element can be causing insertion not to be allowed.<br> 678<b>Complexity:</b> <code>O(shl(end()-position,1) + I(n))</code>.<br> 679<b>Exception safety:</b> Strong. 680</blockquote> 681 682<code>void insert(iterator position,size_type m,const value_type& x);</code> 683 684<blockquote> 685<b>Requires:</b> <code>position</code> is a valid iterator of the index.<br> 686<b>Effects:</b> 687<blockquote><pre> 688<span class=keyword>for</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>i</span><span class=special>=</span><span class=number>0</span><span class=special>;</span><span class=identifier>i</span><span class=special><</span><span class=identifier>m</span><span class=special>;++</span><span class=identifier>i</span><span class=special>)</span><span class=identifier>insert</span><span class=special>(</span><span class=identifier>position</span><span class=special>,</span><span class=identifier>x</span><span class=special>);</span> 689</pre></blockquote> 690<b>Complexity:</b> <code>O(shl(end()-position,m) + m*I(n+m))</code>. 691</blockquote> 692 693<code>template<typename InputIterator><br> 694void insert(iterator position,InputIterator first,InputIterator last);</code> 695 696<blockquote> 697<b>Requires:</b> <code>position</code> is a valid iterator of the index. 698<code>InputIterator</code> is an input iterator. 699<code>value_type</code> is 700<code>EmplaceConstructible</code> into 701<code>multi_index_container</code> from <code>*first</code>. 702<code>first</code> and <code>last</code> are not iterators into any 703index of the <code>multi_index_container</code> to which this index belongs. 704<code>last</code> is reachable from <code>first</code>.<br> 705<b>Effects:</b> 706For each element of [<code>first</code>, <code>last</code>), in this 707order, inserts it before <code>position</code> if insertion is allowed by all 708other indices of the <code>multi_index_container</code>.<br> 709<b>Complexity:</b> <code>O(shl(end()-position,m) + m*I(n+m))</code>, 710where <code>m</code> is the number of elements in 711[<code>first</code>,<code>last</code>).<br> 712<b>Exception safety:</b> Basic. 713</blockquote> 714 715<code>void insert(iterator position,std::initializer_list<value_type> list);</code> 716 717<blockquote> 718<b>Effects:</b> 719<blockquote><pre> 720<span class=identifier>insert</span><span class=special>(</span><span class=identifier>position</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> 721</pre></blockquote> 722</blockquote> 723 724<code>insert_return_type insert(const_iterator position,node_type&& nh);</code> 725 726<blockquote> 727<b>Requires:</b> <code>nh.empty() || get_allocator()==nh.get_allocator()</code>.<br> 728<b>Effects:</b> Does nothing if <code>nh</code> is empty; otherwise, 729inserts the node owned by <code>nh</code> before <code>position</code> if insertion 730is allowed by all other indices of the <code>multi_index_container</code>.<br> 731<b>Postconditions:</b> <code>nh</code> is empty.<br> 732<b>Returns:</b> A value <code>p</code> of type <code>insert_return_type</code>. 733If <code>nh</code> is empty, <code>p.position</code> is <code>end()</code>, 734<code>p.inserted</code> is <code>false</code> and <code>p.node</code> is empty; 735on successful insertion, <code>p.position</code> points to the element inserted, 736<code>p.inserted</code> is <code>true</code> and <code>p.node</code> 737is empty; 738if the insertion failed, <code>p.position</code> points to an element that caused 739the insertion to be banned, <code>p.inserted</code> is <code>false</code> and 740<code>p.node</code> owns the original node. 741Note that more than one element can be causing insertion not to be allowed.<br> 742<b>Complexity:</b> <code>O(shl(end()-position,1) + I(n))</code>.<br> 743<b>Exception safety:</b> Strong. If an exception 744is thrown, <code>nh</code> is not changed.<br> 745</blockquote> 746 747<code>node_type extract(const_iterator position);</code> 748 749<blockquote> 750<b>Requires:</b> <code>position</code> is a valid dereferenceable iterator 751of the index.<br> 752<b>Effects:</b> Extracts the node of the element pointed to by <code>position</code>.<br> 753<b>Returns:</b> A node handle owning the extracted node.<br> 754<b>Complexity:</b> <code>O(D(n))</code>.<br> 755<b>Exception safety:</b> <code>nothrow</code>.<br> 756</blockquote> 757 758<code>iterator erase(iterator position);</code> 759 760<blockquote> 761<b>Requires:</b> <code>position</code> is a valid dereferenceable iterator 762of the index.<br> 763<b>Effects:</b> Deletes the element pointed to by <code>position</code>.<br> 764<b>Returns:</b> An iterator pointing to the element immediately following 765the one that was deleted, or <code>end()</code> 766if no such element exists.<br> 767<b>Complexity:</b> <code>O(D(n))</code>.<br> 768<b>Exception safety:</b> <code>nothrow</code>.<br> 769</blockquote> 770 771<code>iterator erase(iterator first,iterator last);</code> 772 773<blockquote> 774<b>Requires:</b> [<code>first</code>,<code>last</code>) is a valid 775range of the index.<br> 776<b>Effects:</b> Deletes the elements in [<code>first</code>,<code>last</code>).<br> 777<b>Returns:</b> <code>last</code>.<br> 778<b>Complexity:</b> <code>O(m*D(n))</code>, where <code>m</code> is 779the number of elements in [<code>first</code>,<code>last</code>).<br> 780<b>Exception safety:</b> <code>nothrow</code>.<br> 781</blockquote> 782 783<a name="replace"><code>bool replace(iterator position,const value_type& x);</code></a><br> 784<code>bool replace(iterator position,value_type&& x);</code> 785 786<blockquote> 787<b>Requires (first version):</b> <code>value_type</code> is <code>CopyAssignable</code>. 788<code>position</code> is a valid dereferenceable iterator of the index.<br> 789<b>Requires (second version):</b> <code>value_type</code> is <code>MoveAssignable</code>. 790<code>position</code> is a valid dereferenceable iterator of the index.<br> 791<b>Effects:</b> Assigns the value <code>x</code> to the element pointed 792to by <code>position</code> into the <code>multi_index_container</code> to which 793the index belongs if replacing is allowed by all other indices of the 794<code>multi_index_container</code>.<br> 795<b>Postconditions:</b> Validity of <code>position</code> is preserved 796in all cases.<br> 797<b>Returns:</b> <code>true</code> if the replacement took place, 798<code>false</code> otherwise.<br> 799<b>Complexity:</b> <code>O(R(n))</code>.<br> 800<b>Exception safety:</b> Strong. If an exception is thrown by some 801user-provided operation the <code>multi_index_container</code> to which the index 802belongs remains in its original state. 803</blockquote> 804 805<a name="modify"> 806<code>template<typename Modifier> bool modify(iterator position,Modifier mod);</code></a> 807 808<blockquote> 809<b>Requires:</b> <code>mod</code> is a unary function object 810accepting arguments of type 811<code>value_type&</code>. <code>position</code> is a valid dereferenceable 812iterator of the index. 813The execution of <code>mod(e)</code>, where <code>e</code> is the element 814pointed to by <code>position</code>, does not invoke any operation of the 815<code>multi_index_container</code> after <code>e</code> is directly modified 816or, before modification, if the operation would invalidate <code>position</code>.<br> 817<b>Effects:</b> Calls <code>mod(e)</code> where <code>e</code> is the element 818pointed to by <code>position</code> and rearranges <code>*position</code> into 819all the indices of the <code>multi_index_container</code>. Rearrangement on sequenced 820indices does not change the position of the element with respect to the index; 821rearrangement on other indices may or might not succeed. If the rearrangement 822fails, the element is erased.<br> 823<b>Postconditions:</b> Validity of <code>position</code> is preserved if the 824operation succeeds.<br> 825<b>Returns:</b> <code>true</code> if the operation succeeded, <code>false</code> 826otherwise.<br> 827<b>Complexity:</b> <code>O(M(n))</code>.<br> 828<b>Exception safety:</b> Basic. If an exception is thrown by some 829user-provided operation (including <code>mod</code>), then 830the element pointed to by <code>position</code> is erased. 831</blockquote> 832 833<code>template<typename Modifier,typename Rollback><br> 834bool modify(iterator position,Modifier mod,Rollback back);</code> 835 836<blockquote> 837<b>Requires:</b> <code>mod</code> and <code>back</code> are unary function 838objects accepting arguments of type 839<code>value_type&</code>. <code>position</code> is a valid dereferenceable 840iterator of the index. 841The execution of <code>mod(e)</code>, where <code>e</code> is the element 842pointed to by <code>position</code>, does not invoke any operation of the 843<code>multi_index_container</code> after <code>e</code> is directly modified 844or, before modification, if the operation would invalidate <code>position</code>. 845<code>back(e)</code> does not invoke any operation of the 846<code>multi_index_container</code>.<br> 847<b>Effects:</b> Calls <code>mod(e)</code> where <code>e</code> is the element 848pointed to by <code>position</code> and tries to rearrange <code>*position</code> into 849all the indices of the <code>multi_index_container</code>. Rearrangement on sequenced 850indices does not change the position of the element with respect to the index; 851rearrangement on other indices may or might not succeed. 852If the rearrangement fails, <code>back(e)</code> is invoked: if the resulting value 853of <code>e</code> is consistent with its original position and constraints in all 854indices, the element is kept, otherwise it is erased.<br> 855<b>Postconditions:</b> Validity of <code>position</code> is preserved except if 856the element is erased under the conditions described below.<br> 857<b>Returns:</b> <code>true</code> if the operation succeeded, <code>false</code> 858otherwise.<br> 859<b>Complexity:</b> <code>O(M(n))</code>.<br> 860<b>Exception safety:</b> Strong, except if <code>mod</code> or <code>back</code> throw an 861exception or <code>back(e)</code> fails to properly restore the element or there is 862a throwing user-provided operation after invoking <code>back(e)</code>, in which cases 863the modified element is erased. If <code>back</code> 864throws inside the handling code executing after some other user-provided 865operation has thrown, it is the exception generated by <code>back</code> that 866is rethrown. 867</blockquote> 868 869<h4><a name="list_operations">List operations</a></h4> 870 871<p> 872Random access indices replicate the interface of sequenced indices, which 873in turn includes the list operations provided by <code>std::list</code>. 874The syntax and behavior of these operations exactly matches those 875of sequenced indices, but the associated complexity bounds differ in general. 876</p> 877 878<code>void splice(iterator position,<b>index class name</b>& x);</code> 879 880<blockquote> 881<b>Requires:</b> <code>position</code> is a valid iterator of the index. 882<code>&x!=this</code>.<br> 883<b>Effects:</b> Inserts the contents of <code>x</code> before <code>position</code>, 884in the same order as they were in <code>x</code>. Those elements successfully 885inserted are erased from <code>x</code>.<br> 886<b>Complexity:</b> <code>O(shl(end()-position,x.size()) + x.size()*I(n+x.size()) + x.size()*D(x.size()))</code>.<br> 887<b>Exception safety:</b> Basic.<br> 888</blockquote> 889 890<code>void splice(iterator position,<b>index class name</b>& x,iterator i);</code> 891 892<blockquote> 893<b>Requires:</b> <code>position</code> is a valid iterator of the index. 894<code>i</code> is a valid dereferenceable iterator <code>x</code>.<br> 895<b>Effects:</b> Inserts the element pointed to by <code>i</code> before 896<code>position</code>: if insertion is successful, the element is erased from 897<code>x</code>. In the special case <code>&x==this</code>, no copy or 898deletion is performed, and the operation is always successful. If 899<code>position==i</code>, no operation is performed.<br> 900<b>Postconditions:</b> If <code>&x==this</code>, no iterator or reference 901is invalidated.<br> 902<b>Complexity:</b> If <code>&x==this</code>, <code>O(rel(position,i,i+1))</code>; 903otherwise <code>O(shl(end()-position,1) + I(n) + D(n))</code>.<br> 904<b>Exception safety:</b> If <code>&x==this</code>, <code>nothrow</code>; 905otherwise, strong.<br> 906</blockquote> 907 908<code>void splice(iterator position,<b>index class name&</b> x,iterator first,iterator last);</code> 909 910<blockquote> 911<b>Requires:</b> <code>position</code> is a valid iterator of the index. 912<code>first</code> and <code>last</code> are valid iterators of <code>x</code>. 913<code>last</code> is reachable from <code>first</code>. <code>position</code> 914is not in the range [<code>first</code>,<code>last</code>).<br> 915<b>Effects:</b> For each element in the range [<code>first</code>,<code>last</code>), 916insertion is tried before <code>position</code>; if the operation is successful, 917the element is erased from <code>x</code>. In the special case 918<code>&x==this</code>, no copy or deletion is performed, and insertions are 919always successful.<br> 920<b>Postconditions:</b> If <code>&x==this</code>, no iterator or reference 921is invalidated.<br> 922<b>Complexity:</b> If <code>&x==this</code>, 923<code>O(rel(position,first,last))</code>; otherwise 924<code>O(shl(end()-position,m) + m*I(n+m) + m*D(x.size()))</code> 925where <code>m</code> is the number of elements in [<code>first</code>,<code>last</code>).<br> 926<b>Exception safety:</b> If <code>&x==this</code>, <code>nothrow</code>; 927otherwise, basic.<br> 928</blockquote> 929 930<code>void remove(const value_type& value);</code> 931 932<blockquote> 933<b>Effects:</b> Erases all elements of the index which compare equal to 934<code>value</code>.<br> 935<b>Complexity:</b> <code>O(n + m*D(n))</code>, where <code>m</code> 936is the number of elements erased.<br> 937<b>Exception safety:</b> Basic. 938</blockquote> 939 940<code>template<typename Predicate> void remove_if(Predicate pred);</code> 941 942<blockquote> 943<b>Effects:</b> Erases all elements <code>x</code> of the index for which 944<code>pred(x)</code> holds.<br> 945<b>Complexity:</b> <code>O(n + m*D(n))</code>, where <code>m</code> 946is the number of elements erased.<br> 947<b>Exception safety:</b> Basic. 948</blockquote> 949 950<code>void unique();</code> 951 952<blockquote> 953<b>Effects:</b> Eliminates all but the first element from every consecutive 954group of equal elements referred to by the iterator <code>i</code> in the range 955[<code>first+1</code>,<code>last</code>) for which <code>*i==*(i-1)</code>.<br> 956<b>Complexity:</b> <code>O(n + m*D(n))</code>, where <code>m</code> 957is the number of elements erased.<br> 958<b>Exception safety:</b> Basic. 959</blockquote> 960 961<code>template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);</code> 962 963<blockquote> 964<b>Effects:</b> Eliminates all but the first element from every consecutive 965group of elements referred to by the iterator <code>i</code> in the range 966[<code>first+1</code>,<code>last</code>) for which 967<code>binary_pred(*i,*(i-1))</code> holds.<br> 968<b>Complexity:</b> <code>O(n + m*D(n))</code>, where <code>m</code> 969is the number of elements erased.<br> 970<b>Exception safety:</b> Basic. 971</blockquote> 972 973<code>void merge(index class name& x);</code> 974 975<blockquote> 976<b>Requires:</b> <code>std::less<value_type></code> induces a 977strict weak ordering over <code>value_type</code>. 978Both the index and <code>x</code> are sorted according to 979<code>std::less<value_type></code>.<br> 980<b>Effects:</b> Attempts to insert every element of <code>x</code> into the 981corresponding position of the index (according to the order). Elements 982successfully inserted are erased from <code>x</code>. The resulting sequence 983is stable, i.e. equivalent elements of either container preserve their 984relative position. In the special case <code>&x==this</code>, no operation 985is performed.<br> 986<b>Postconditions:</b> Elements in the index and remaining elements in 987<code>x</code> are sorted. 988Validity of iterators to the index and of non-erased elements of <code>x</code> 989references is preserved.<br> 990<b>Complexity:</b> If <code>&x==this</code>, constant; otherwise 991<code>O(n + x.size()*I(n+x.size()) + x.size()*D(x.size()))</code>.<br> 992<b>Exception safety:</b> If <code>&x==this</code>, <code>nothrow</code>; 993otherwise, basic.<br> 994</blockquote> 995 996<code>template <typename Compare> void merge(index class name& x,Compare comp);</code> 997 998<blockquote> 999<b>Requires:</b> <code>Compare</code> induces a 1000strict weak ordering over <code>value_type</code>. 1001Both the index and <code>x</code> are sorted according to <code>comp</code>.<br> 1002<b>Effects:</b> Attempts to insert every element of <code>x</code> into the 1003corresponding position of the index (according to <code>comp</code>). 1004Elements successfully inserted are erased from <code>x</code>. The resulting 1005sequence is stable, i.e. equivalent elements of either container preserve 1006their relative position. In the special case <code>&x==this</code>, no 1007operation is performed.<br> 1008<b>Postconditions:</b> Elements in the index and remaining elements in 1009<code>x</code> are sorted according to <code>comp</code>. 1010Validity of iterators to the index and of non-erased elements of <code>x</code> 1011references is preserved.<br> 1012<b>Complexity:</b> If <code>&x==this</code>, constant; otherwise 1013<code>O(n + x.size()*I(n+x.size()) + x.size()*D(x.size()))</code>.<br> 1014<b>Exception safety:</b> If <code>&x==this</code>, <code>nothrow</code>; 1015otherwise, basic.<br> 1016</blockquote> 1017 1018<code>void sort();</code> 1019 1020<blockquote> 1021<b>Requires:</b> <code>std::less<value_type></code> induces a 1022strict weark ordering over <code>value_type</code>.<br> 1023<b>Effects:</b> Sorts the index according to 1024<code>std::less<value_type></code>. The sorting is stable, i.e. 1025equivalent elements preserve their relative position.<br> 1026<b>Postconditions:</b> Validity of iterators and references is preserved.<br> 1027<b>Complexity:</b> <code>O(n*log(n))</code>.<br> 1028<b>Exception safety:</b> Basic. 1029</blockquote> 1030 1031<code>template <typename Compare> void sort(Compare comp);</code> 1032 1033<blockquote> 1034<b>Requires:</b> <code>Compare</code> induces a 1035strict weak ordering over <code>value_type</code>.<br> 1036<b>Effects:</b> Sorts the index according to <code>comp</code>. The sorting 1037is stable, i.e. equivalent elements preserve their relative position.<br> 1038<b>Postconditions:</b> Validity of iterators and references is preserved.<br> 1039<b>Complexity:</b> <code>O(n*log(n))</code>.<br> 1040<b>Exception safety:</b> Basic. 1041</blockquote> 1042 1043<code>void reverse()noexcept;</code> 1044 1045<blockquote> 1046<b>Effects:</b> Reverses the order of the elements in the index.<br> 1047<b>Postconditions:</b> Validity of iterators and references is preserved.<br> 1048<b>Complexity:</b> <code>O(n)</code>.<br> 1049</blockquote> 1050 1051<h4><a name="rearrange_operations">Rearrange operations</a></h4> 1052 1053<p> 1054These operations, without counterpart in STL sequence containers 1055(although <code>std::list::splice</code> provides partially overlapping 1056functionality), perform individual and global repositioning of elements 1057inside the index. 1058</p> 1059 1060<code>void relocate(iterator position,iterator i);</code> 1061 1062<blockquote> 1063<b>Requires:</b> <code>position</code> is a valid iterator of the index. 1064<code>i</code> is a valid dereferenceable iterator of the index.<br> 1065<b>Effects:</b> Inserts the element pointed to by <code>i</code> before 1066<code>position</code>. If <code>position==i</code>, no operation is 1067performed.<br> 1068<b>Postconditions:</b> No iterator or reference is invalidated.<br> 1069<b>Complexity:</b> <code>O(rel(position,i,i+1))</code>.<br> 1070<b>Exception safety:</b> <code>nothrow</code>.<br> 1071</blockquote> 1072 1073<code>void relocate(iterator position,iterator first,iterator last);</code> 1074 1075<blockquote> 1076<b>Requires:</b> <code>position</code> is a valid iterator of the index. 1077<code>first</code> and <code>last</code> are valid iterators of the index. 1078<code>last</code> is reachable from <code>first</code>. <code>position</code> 1079is not in the range [<code>first</code>,<code>last</code>).<br> 1080<b>Effects:</b> The range of elements [<code>first</code>,<code>last</code>) 1081is repositioned just before <code>position</code>.<br> 1082<b>Postconditions:</b> No iterator or reference is invalidated.<br> 1083<b>Complexity:</b> <code>O(rel(position,first,last))</code>.<br> 1084<b>Exception safety:</b> <code>nothrow</code>.<br> 1085</blockquote> 1086 1087<a name="rearrange"><code>template<typename InputIterator> void rearrange(InputIterator first);</code></a> 1088 1089<blockquote> 1090<b>Requires:</b> The range [<code>first</code>, 1091<code>std::advance(first,n)</code>), 1092where <code>n</code> is the size of the index, is a 1093<a href="indices.html#views">free view</a> of the index.<br> 1094<b>Effects:</b> The elements are rearranged so as to match the 1095order of the previously described view.<br> 1096<b>Postconditions:</b> No iterator or reference is invalidated.<br> 1097<b>Complexity:</b> <code>O(n)</code>.<br> 1098<b>Exception safety:</b> Basic.<br> 1099</blockquote> 1100 1101<h4><a name="serialization">Serialization</a></h4> 1102 1103<p> 1104Indices cannot be serialized on their own, but only as part of the 1105<code>multi_index_container</code> into which they are embedded. In describing 1106the additional preconditions and guarantees associated to random access indices 1107with respect to serialization of their embedding containers, we 1108use the concepts defined in the <code>multi_index_container</code> 1109<a href="multi_index_container.html#serialization">serialization section</a>. 1110</p> 1111 1112Operation: saving of a <code>multi_index_container</code> <code>m</code> to an 1113output archive (XML archive) <code>ar</code>. 1114 1115<blockquote> 1116<b>Requires:</b> No additional requirements to those imposed by the container. 1117</blockquote> 1118 1119Operation: loading of a <code>multi_index_container</code> <code>m'</code> from an 1120input archive (XML archive) <code>ar</code>. 1121 1122<blockquote> 1123<b>Requires:</b> No additional requirements to those imposed by the container.<br> 1124<b>Postconditions:</b> On successful loading, each of the elements of 1125[<code>begin()</code>, <code>end()</code>) is a restored copy of the corresponding 1126element in [<code>m.get<i>().begin()</code>, <code>m.get<i>().end()</code>), 1127where <code>i</code> is the position of the random access index in the container. 1128</blockquote> 1129 1130Operation: saving of an <code>iterator</code> or <code>const_iterator</code> 1131<code>it</code> to an output archive (XML archive) <code>ar</code>. 1132 1133<blockquote> 1134<b>Requires:</b> <code>it</code> is a valid iterator of the index. The associated 1135<code>multi_index_container</code> has been previously saved. 1136</blockquote> 1137 1138Operation: loading of an <code>iterator</code> or <code>const_iterator</code> 1139<code>it'</code> from an input archive (XML archive) <code>ar</code>. 1140 1141<blockquote> 1142<b>Postconditions:</b> On successful loading, if <code>it</code> was dereferenceable 1143then <code>*it'</code> is the restored copy of <code>*it</code>, otherwise 1144<code>it'==end()</code>.<br> 1145<b>Note:</b> It is allowed that <code>it</code> be a <code>const_iterator</code> 1146and the restored <code>it'</code> an <code>iterator</code>, or viceversa. 1147</blockquote> 1148 1149<hr> 1150 1151<div class="prev_link"><a href="seq_indices.html"><img src="../prev.gif" alt="sequenced indices" border="0"><br> 1152Sequenced indices 1153</a></div> 1154<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br> 1155Boost.MultiIndex reference 1156</a></div> 1157<div class="next_link"><a href="key_extraction.html"><img src="../next.gif" alt="key extraction" border="0"><br> 1158Key extraction 1159</a></div><br clear="all" style="clear: all;"> 1160 1161<br> 1162 1163<p>Revised May 9th 2020</p> 1164 1165<p>© Copyright 2003-2020 Joaquín M López Muñoz. 1166Distributed under the Boost Software 1167License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt"> 1168LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt"> 1169http://www.boost.org/LICENSE_1_0.txt</a>) 1170</p> 1171 1172</body> 1173</html> 1174
