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