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