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