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