]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/license |
2 | ||
3 | Boost.Bimap | |
4 | ||
5 | Copyright (c) 2006-2007 Matias Capeletto | |
6 | ||
7 | Distributed under the Boost Software License, Version 1.0. | |
8 | (See accompanying file LICENSE_1_0.txt or copy at | |
9 | http://www.boost.org/LICENSE_1_0.txt) | |
10 | ||
11 | ] | |
12 | ||
13 | [/ QuickBook Document version 1.4 ] | |
14 | ||
15 | [section vector_of Reference] | |
16 | ||
17 | [section Header "boost/bimap/vector_of.hpp" synopsis] | |
18 | ||
19 | namespace boost { | |
20 | namespace bimaps { | |
21 | ||
22 | ||
23 | template< class KeyType > | |
24 | struct vector_of; | |
25 | ||
26 | struct vector_of_relation; | |
27 | ||
28 | ||
29 | } // namespace bimap | |
30 | } // namespace boost | |
31 | ||
32 | ||
33 | [endsect] | |
34 | ||
35 | [section vector_of views] | |
36 | ||
37 | vector_of views are free-order sequences with constant time positional | |
38 | access and random access iterators. Elements in a vector_of view are by | |
39 | default sorted according to their order of insertion: this means that new elements | |
40 | inserted through a different view of the `bimap` are appended to | |
41 | the end of the vector_of view; additionally, facilities are provided for | |
42 | further rearrangement of the elements. The public interface of vector_of views | |
43 | includes that of list_of views, with differences in the complexity | |
44 | of the operations, plus extra operations for positional access | |
45 | (`operator[]` and `at()`) and for capacity handling. Validity of iterators and | |
46 | references to elements is preserved in all operations, regardless of the | |
47 | capacity status. | |
48 | ||
49 | As is the case with list_of views, vector_of views have the following | |
50 | limitations with respect to STL sequence containers: | |
51 | ||
52 | * vector_of views | |
53 | are not __SGI_ASSIGNABLE__ (like any other view.) | |
54 | * Insertions into a vector_of view may fail due to clashings with other views. | |
55 | This alters the semantics of the operations provided with respect to their analogues | |
56 | in STL sequence containers. | |
57 | * Elements in a vector_of view are not mutable, and can only be changed by | |
58 | means of replace and modify member functions. | |
59 | ||
60 | Having these restrictions into account, vector of views are models of | |
61 | __SGI_RANDOM_ACCESS_CONTAINER__ and __SGI_BACK_INSERTION_SEQUENCE__. Although these views | |
62 | do not model __SGI_FRONT_INSERTION_SEQUENCE__, because front insertion and deletion | |
63 | take linear time, front operations are nonetheless provided to match the interface | |
64 | of list_of views. We only describe those types and operations that are either | |
65 | not present in the concepts modeled or do not exactly conform to the requirements | |
66 | for these types of containers. | |
67 | ||
68 | ||
69 | namespace boost { | |
70 | namespace bimaps { | |
71 | namespace views { | |
72 | ||
73 | template< ``['-implementation defined parameter list-]`` > | |
74 | class ``['-implementation defined view name-]`` | |
75 | { | |
76 | public: | |
77 | ||
78 | // types | |
79 | ||
80 | typedef ``['-unspecified-]`` value_type; | |
81 | typedef ``['-unspecified-]`` allocator_type; | |
82 | typedef ``['-unspecified-]`` reference; | |
83 | typedef ``['-unspecified-]`` const_reference; | |
84 | typedef ``['-unspecified-]`` iterator; | |
85 | typedef ``['-unspecified-]`` const_iterator; | |
86 | typedef ``['-unspecified-]`` size_type; | |
87 | typedef ``['-unspecified-]`` difference_type; | |
88 | typedef ``['-unspecified-]`` pointer; | |
89 | typedef ``['-unspecified-]`` const_pointer; | |
90 | typedef ``['-unspecified-]`` reverse_iterator; | |
91 | typedef ``['-unspecified-]`` const_reverse_iterator; | |
92 | ||
93 | typedef ``['-unspecified-]`` info_type; | |
94 | ||
95 | // construct / copy / destroy | |
96 | ||
97 | this_type & operator=(this_type & x); | |
98 | ||
99 | template< class InputIterator > | |
100 | void ``[link reference_vector_of_assign_iterator_iterator assign]``(InputIterator first, InputIterator last); | |
101 | ||
102 | void ``[link reference_vector_of_assign_size_value assign]``(size_type n, const value_type & value); | |
103 | ||
104 | allocator_type get_allocator() const; | |
105 | ||
106 | // iterators | |
107 | ||
108 | iterator begin(); | |
109 | const_iterator begin() const; | |
110 | ||
111 | iterator end(); | |
112 | const_iterator end() const; | |
113 | ||
114 | reverse_iterator rbegin(); | |
115 | const_reverse_iterator rbegin() const; | |
116 | ||
117 | reverse_iterator rend(); | |
118 | const_reverse_iterator rend() const; | |
119 | ||
120 | // capacity | |
121 | ||
122 | bool empty() const; | |
123 | ||
124 | size_type size() const; | |
125 | ||
126 | size_type max_size() const; | |
127 | ||
128 | size_type ``[link reference_vector_of_capacity capacity]``() const; | |
129 | ||
130 | void ``[link reference_vector_of_reserve_size reserve]``(size_type m); | |
131 | ||
132 | void ``[link reference_vector_of_resize_size_value resize]``(size_type n, const value_type & x = value_type()); | |
133 | ||
134 | // access | |
135 | ||
136 | const_reference operator[](size_type n) const; | |
137 | ||
138 | const_reference at(size_type n) const; | |
139 | ||
140 | const_reference front() const; | |
141 | ||
142 | const_reference back() const; | |
143 | ||
144 | // modifiers | |
145 | ||
146 | std::pair<iterator,bool> ``[link reference_vector_of_push_front_value push_front]``(const value_type & x); | |
147 | void pop_front(); | |
148 | ||
149 | std::pair<iterator,bool> ``[link reference_vector_of_push_back_value push_back]``(const value_type & x); | |
150 | void pop_back(); | |
151 | ||
152 | std::pair<iterator,bool> ``[link reference_vector_of_insert_iterator_value insert]``(iterator position, const value_type & x); | |
153 | ||
154 | void ``[link reference_vector_of_insert_iterator_size_value insert]``(iterator position, size_type m, const value_type & x); | |
155 | ||
156 | template< class InputIterator> | |
157 | void ``[link reference_vector_of_insert_iterator_iterator_iterator insert]``(iterator position, InputIterator first, InputIterator last); | |
158 | ||
159 | iterator ``[link reference_vector_of_erase_iterator erase]``(iterator position); | |
160 | iterator ``[link reference_vector_of_erase_iterator_iterator erase]``(iterator first, iterator last); | |
161 | ||
162 | bool ``[link reference_vector_of_replace_iterator_value replace]``(iterator position, const value_type & x); | |
163 | ||
164 | // Only in map views | |
165 | // { | |
166 | typedef ``['-unspecified-]`` key_type; | |
167 | typedef ``['-unspecified-]`` mapped_type; | |
168 | typedef ``['-unspecified-]`` data_type; // Equal to mapped_type | |
169 | ||
170 | template< class CompatibleKey > | |
171 | bool ``[link reference_vector_of_replace_key_iterator_key replace_key]``(iterator position, const CompatibleKey & x); | |
172 | ||
173 | template< class CompatibleData > | |
174 | bool ``[link reference_vector_of_replace_data_iterator_data replace_data]``(iterator position, const CompatibleData & x); | |
175 | ||
176 | template< class KeyModifier > | |
177 | bool ``[link reference_vector_of_modify_key_iterator_modifier modify_key]``(iterator position, KeyModifier mod); | |
178 | ||
179 | template< class DataModifier > | |
180 | bool ``[link reference_vector_of_modify_data_iterator_modifier modify_data]``(iterator position, DataModifier mod); | |
181 | ||
182 | // } | |
183 | ||
184 | ||
185 | void clear(); | |
186 | ||
187 | // list operations | |
188 | ||
189 | void ``[link reference_vector_of_splice_iterator_this splice]``(iterator position, this_type & x); | |
190 | void ``[link reference_vector_of_splice_iterator_this_iterator splice]``(iterator position, this_type & x, iterator i); | |
191 | void ``[link reference_vector_of_splice_iterator_this_iterator_iterator splice]``( | |
192 | iterator position, this_type & x, iterator first, iterator last); | |
193 | ||
194 | void ``[link reference_vector_of_remove_value remove]``(const value_type & value); | |
195 | ||
196 | template< class Predicate > | |
197 | void ``[link reference_vector_of_remove_if_predicate remove_if]``(Predicate pred); | |
198 | ||
199 | void ``[link reference_vector_of_unique unique]``(); | |
200 | ||
201 | template< class BinaryPredicate > | |
202 | void ``[link reference_vector_of_unique_predicate unique]``(BinaryPredicate binary_pred); | |
203 | ||
204 | void ``[link reference_vector_of_merge_this merge]``(this_type & x); | |
205 | ||
206 | template< typename Compare > | |
207 | void ``[link reference_vector_of_merge_this_compare merge]``(this_type & x, Compare comp); | |
208 | ||
209 | void ``[link reference_vector_of_sort sort]``(); | |
210 | ||
211 | template< typename Compare > | |
212 | void ``[link reference_vector_of_sort_compare sort]``(Compare comp); | |
213 | ||
214 | void ``[link reference_vector_of_reverse reverse]``(); | |
215 | ||
216 | // rearrange operations | |
217 | ||
218 | void ``[link reference_vector_of_relocate_iterator_iterator relocate]``(iterator position, iterator i); | |
219 | void ``[link reference_vector_of_relocate_iterator_iterator_iterator relocate]``(iterator position, iterator first, iterator last); | |
220 | }; | |
221 | ||
222 | // view comparison | |
223 | ||
224 | bool operator==(const this_type & v1, const this_type & v2 ); | |
225 | bool operator< (const this_type & v1, const this_type & v2 ); | |
226 | bool operator!=(const this_type & v1, const this_type & v2 ); | |
227 | bool operator> (const this_type & v1, const this_type & v2 ); | |
228 | bool operator>=(const this_type & v1, const this_type & v2 ); | |
229 | bool operator<=(const this_type & v1, const this_type & v2 ); | |
230 | ||
231 | } // namespace views | |
232 | } // namespace bimap | |
233 | } // namespace boost | |
234 | ||
235 | ||
236 | ||
237 | In the case of a `bimap< vector_of<Left>, ... >` | |
238 | ||
239 | In the set view: | |
240 | ||
241 | typedef signature-compatible with relation< Left, ... > key_type; | |
242 | typedef signature-compatible with relation< Left, ... > value_type; | |
243 | ||
244 | In the left map view: | |
245 | ||
246 | typedef Left key_type; | |
247 | typedef ... mapped_type; | |
248 | ||
249 | typedef signature-compatible with std::pair< Left, ... > value_type; | |
250 | ||
251 | In the right map view: | |
252 | ||
253 | typedef ... key_type; | |
254 | typedef Left mapped_type; | |
255 | ||
256 | typedef signature-compatible with std::pair< ... , Left > value_type; | |
257 | ||
258 | ||
259 | [#vector_of_complexity_signature] | |
260 | ||
261 | [section Complexity signature] | |
262 | ||
263 | Here and in the descriptions of operations of `vector_of` views, we adopt | |
264 | the scheme outlined in the | |
265 | [link complexity_signature_explanation complexity signature section]. | |
266 | The complexity signature of `vector_of` view is: | |
267 | ||
268 | * copying: `c(n) = n * log(n)`, | |
269 | * insertion: `i(n) = 1` (amortized constant), | |
270 | * hinted insertion: `h(n) = 1` (amortized constant), | |
271 | * deletion: `d(n) = m`, where m is the distance from the deleted element to the | |
272 | end of the sequence, | |
273 | * replacement: `r(n) = 1` (constant), | |
274 | * modifying: `m(n) = 1` (constant). | |
275 | ||
276 | The following expressions are also used as a convenience for writing down some | |
277 | of the complexity formulas: | |
278 | ||
279 | [blurb | |
280 | `shl(a,b) = a+b` if a is nonzero, 0 otherwise. | |
281 | `rel(a,b,c) =` if `a<b`, `c-a`, else `a-b`, | |
282 | ] | |
283 | ||
284 | (`shl` and `rel` stand for ['shift left] and ['relocate], respectively.) | |
285 | ||
286 | [endsect] | |
287 | ||
288 | [section Instantiation types] | |
289 | ||
290 | `vector_of` views are instantiated internally to `bimap` and specified | |
291 | by means of the collection type specifiers and the bimap itself. | |
292 | Instantiations are dependent on the following types: | |
293 | ||
294 | * `Value` from `vector_of`, | |
295 | * `Allocator` from `bimap`, | |
296 | ||
297 | [endsect] | |
298 | ||
299 | [section Constructors, copy and assignment] | |
300 | ||
301 | As explained in the views concepts section, | |
302 | views do not have public constructors or destructors. | |
303 | Assignment, on the other hand, is provided. | |
304 | ||
305 | this_type & operator=(const this_type & x); | |
306 | ||
307 | * [*Effects: ] `a=b;` | |
308 | where a and b are the `bimap` objects to which `*this` and | |
309 | `x` belong, respectively. | |
310 | * [*Returns: ] `*this`. | |
311 | ||
312 | ||
313 | [#reference_vector_of_assign_iterator_iterator] | |
314 | ||
315 | template< class InputIterator > | |
316 | void assign(InputIterator first, InputIterator last); | |
317 | ||
318 | * [*Requires: ] `InputIterator` is a model of __SGI_INPUT_ITERATOR__ over elements | |
319 | of type `value_type` or a type convertible to `value_type`. `first` and `last` are | |
320 | not iterators into any view of the `bimap` to which this | |
321 | view belongs. `last` is reachable from `first`. | |
322 | * [*Effects: ] `clear(); insert(end(),first,last);` | |
323 | ||
324 | ||
325 | [#reference_vector_of_assign_size_value] | |
326 | ||
327 | void assign(size_type n, const value_type & value); | |
328 | ||
329 | * [*Effects: ] `clear(); for(size_type i = 0; i < n; ++n) push_back(v);` | |
330 | ||
331 | [endsect] | |
332 | ||
333 | [section Capacity operations] | |
334 | ||
335 | [#reference_vector_of_capacity] | |
336 | ||
337 | size_type capacity() const; | |
338 | ||
339 | * [*Returns:] The total number of elements `c` such that, when `size() < c`, | |
340 | back insertions happen in constant time (the general case as described by | |
341 | i(n) is ['amortized] constant time.) | |
342 | * [*Note:] Validity of iterators and references to elements is preserved | |
343 | in all insertions, regardless of the capacity status. | |
344 | ||
345 | ||
346 | [#reference_vector_of_reserve_size] | |
347 | ||
348 | void reserve(size_type m); | |
349 | ||
350 | * [*Effects:] If the previous value of `capacity()` was greater than or equal | |
351 | to `m`, nothing is done; otherwise, the internal capacity is changed so that | |
352 | `capacity()>=m`. | |
353 | * [*Complexity:] If the capacity is not changed, constant; otherwise O(n). | |
354 | * [*Exception safety:] If the capacity is not changed, nothrow; otherwise, strong. | |
355 | ||
356 | ||
357 | [#reference_vector_of_resize_size_value] | |
358 | ||
359 | void resize(size_type n, const value_type & x = value_type()); | |
360 | ||
361 | * [*Effects: ] `if( n > size() ) insert(end(), n-size(), x);` | |
362 | `else if( n<size() ) erase(begin()+n,end());` | |
363 | * [*Note:] If an expansion is requested, the size of the view is not guaranteed | |
364 | to be n after this operation (other views may ban insertions.) | |
365 | ||
366 | ||
367 | [endsect] | |
368 | ||
369 | [section Modifiers] | |
370 | ||
371 | [#reference_vector_of_push_front_value] | |
372 | ||
373 | std::pair<iterator,bool> push_front(const value_type & x); | |
374 | ||
375 | * [*Effects:] Inserts x at the beginning of the sequence if no other view | |
376 | of the `bimap` bans the insertion. | |
377 | * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only if | |
378 | insertion took place. On successful insertion, `p.first` points to the element | |
379 | inserted; otherwise, `p.first` points to an element that caused the insertion | |
380 | to be banned. Note that more than one element can be causing insertion not | |
381 | to be allowed. | |
382 | * [link vector_of_complexity_signature [*Complexity:]] O(n+I(n)). | |
383 | * [*Exception safety:] Strong. | |
384 | ||
385 | ||
386 | [#reference_vector_of_push_back_value] | |
387 | ||
388 | std::pair<iterator,bool> push_back(const value_type & x); | |
389 | ||
390 | * [*Effects:] Inserts `x` at the end of the sequence if no other view of | |
391 | the `bimap` bans the insertion. | |
392 | * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only | |
393 | if insertion took place. On successful insertion, `p.first` points to the | |
394 | element inserted; otherwise, `p.first` points to an element that caused | |
395 | the insertion to be banned. Note that more than one element can be | |
396 | causing insertion not to be allowed. | |
397 | * [link vector_of_complexity_signature [*Complexity:]] O(I(n)). | |
398 | * [*Exception safety:] Strong. | |
399 | ||
400 | ||
401 | [#reference_vector_of_insert_iterator_value] | |
402 | ||
403 | std::pair<iterator,bool> insert(iterator position, const value_type & x); | |
404 | ||
405 | * [*Requires: ] `position` is a valid iterator of the view. | |
406 | * [*Effects:] Inserts `x` before position if insertion is allowed by all | |
407 | other views of the `bimap`. | |
408 | * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only | |
409 | if insertion took place. On successful insertion, `p.first` points to the | |
410 | element inserted; otherwise, `p.first` points to an element that caused the | |
411 | insertion to be banned. Note that more than one element can be causing | |
412 | insertion not to be allowed. | |
413 | * [link vector_of_complexity_signature [*Complexity:]] O(shl(end()-position,1) + I(n)). | |
414 | * [*Exception safety:] Strong. | |
415 | ||
416 | ||
417 | [#reference_vector_of_insert_iterator_size_value] | |
418 | ||
419 | void insert(iterator position, size_type m, const value_type & x); | |
420 | ||
421 | * [*Requires: ] `position` is a valid iterator of the view. | |
422 | * [*Effects: ] `for(size_type i = 0; i < m; ++i) insert(position, x);` | |
423 | * [link vector_of_complexity_signature | |
424 | [*Complexity:]] O(shl(end()-position,m) + m*I(n+m)). | |
425 | ||
426 | ||
427 | [#reference_vector_of_insert_iterator_iterator_iterator] | |
428 | ||
429 | template< class InputIterator > | |
430 | void insert(iterator position, InputIterator first, InputIterator last); | |
431 | ||
432 | * [*Requires: ] `position` is a valid iterator of the view. `InputIterator` | |
433 | is a model of __SGI_INPUT_ITERATOR__ over elements of type `value_type` or a type | |
434 | convertible to `value_type`. `first` and `last` are not iterators into any view | |
435 | of the `bimap` to which this view belongs. `last` is reachable | |
436 | from `first`. | |
437 | * [*Effects: ] `while(first!=last)insert(position,*first++);` | |
438 | * [link vector_of_complexity_signature | |
439 | [*Complexity:]] O(shl(end()-position,m) + m*I(n+m)), where m is the number | |
440 | of elements in `[first,last)`. | |
441 | * [*Exception safety:] Basic. | |
442 | ||
443 | ||
444 | [#reference_vector_of_erase_iterator] | |
445 | ||
446 | iterator erase(iterator position); | |
447 | ||
448 | * [*Requires: ] `position` is a valid dereferenceable iterator of the view. | |
449 | * [*Effects:] Deletes the element pointed to by `position`. | |
450 | * [*Returns:] An iterator pointing to the element immediately following the | |
451 | one that was deleted, or `end()` if no such element exists. | |
452 | * [link vector_of_complexity_signature [*Complexity:]] O(D(n)). | |
453 | * [*Exception safety:] nothrow. | |
454 | ||
455 | ||
456 | [#reference_vector_of_erase_iterator_iterator] | |
457 | ||
458 | iterator erase(iterator first, iterator last); | |
459 | ||
460 | * [*Requires: ] `[first,last)` is a valid range of the view. | |
461 | * [*Effects:] Deletes the elements in `[first,last)`. | |
462 | * [*Returns:] last. | |
463 | * [link vector_of_complexity_signature | |
464 | [*Complexity:]] O(m*D(n)), where m is the number of elements in `[first,last)`. | |
465 | * [*Exception safety:] nothrow. | |
466 | ||
467 | ||
468 | [#reference_vector_of_replace_iterator_value] | |
469 | ||
470 | bool replace(iterator position, const value_type & x); | |
471 | ||
472 | * [*Requires: ] `position` is a valid dereferenceable iterator of the view. | |
473 | * [*Effects:] Assigns the value x to the element pointed to by position into | |
474 | the `bimap` to which the view belongs if replacing is allowed | |
475 | by all other views of the `bimap`. | |
476 | * [*Postconditions:] Validity of position is preserved in all cases. | |
477 | * [*Returns: ] `true` if the replacement took place, `false` otherwise. | |
478 | * [link vector_of_complexity_signature | |
479 | [*Complexity:]] O(R(n)). | |
480 | * [*Exception safety:] Strong. If an exception is thrown by some user-provided | |
481 | operation the `bimap` to which the view belongs remains in its | |
482 | original state. | |
483 | ||
484 | ||
485 | ||
486 | [#reference_vector_of_replace_key_iterator_key] | |
487 | ||
488 | template< class CompatibleKey > | |
489 | bool replace_key(iterator position, const CompatibleKey & x); | |
490 | ||
491 | * [*Requires: ] `position` is a valid dereferenceable iterator of the set view. | |
492 | `CompatibleKey` can be assigned to `key_type`. | |
493 | * [*Effects:] Assigns the value `x` to `e.first`, where `e` is the element pointed | |
494 | to by `position` into the `bimap` to which the set view belongs if replacing is allowed by | |
495 | all other views of the `bimap`. | |
496 | * [*Postconditions:] Validity of position is preserved in all cases. | |
497 | * [*Returns: ] `true` if the replacement took place, `false` otherwise. | |
498 | * [link vector_of_complexity_signature | |
499 | [*Complexity:]] O(R(n)). | |
500 | * [*Exception safety:] Strong. If an exception is thrown by some user-provided | |
501 | operation, the `bimap` to which the set view belongs remains in | |
502 | its original state. | |
503 | ||
504 | ||
505 | [#reference_vector_of_replace_data_iterator_data] | |
506 | ||
507 | template< class CompatibleData > | |
508 | bool replace_data(iterator position, const CompatibleData & x); | |
509 | ||
510 | * [*Requires: ] `position` is a valid dereferenceable iterator of the set view. | |
511 | `CompatibleKey` can be assigned to `mapped_type`. | |
512 | * [*Effects:] Assigns the value `x` to `e.second`, where `e` is the element pointed | |
513 | to by `position` into the `bimap` to which the set view belongs if replacing is allowed by | |
514 | all other views of the `bimap`. | |
515 | * [*Postconditions:] Validity of position is preserved in all cases. | |
516 | * [*Returns: ] `true` if the replacement took place, `false` otherwise. | |
517 | * [link vector_of_complexity_signature | |
518 | [*Complexity:]] O(R(n)). | |
519 | * [*Exception safety:] Strong. If an exception is thrown by some user-provided | |
520 | operation, the `bimap` to which the set view belongs remains in | |
521 | its original state. | |
522 | ||
523 | ||
524 | [#reference_vector_of_modify_key_iterator_modifier] | |
525 | ||
526 | template< class KeyModifier > | |
527 | bool modify_key(iterator position, KeyModifier mod); | |
528 | ||
529 | * [*Requires: ] `KeyModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of | |
530 | type: `key_type&`; `position` is a valid dereferenceable iterator of the view. | |
531 | * [*Effects:] Calls `mod(e.first)` where e is the element pointed to by position and | |
532 | rearranges `*position` into all the views of the `bimap`. | |
533 | If the rearrangement fails, the element is erased. | |
534 | It is successful if the rearrangement is allowed by all other views of the `bimap`. | |
535 | * [*Postconditions:] Validity of `position` is preserved if the operation succeeds. | |
536 | * [*Returns: ] `true` if the operation succeeded, `false` otherwise. | |
537 | * [link vector_of_complexity_signature | |
538 | [*Complexity:]] O(M(n)). | |
539 | * [*Exception safety:] Basic. If an exception is thrown by some user-provided | |
540 | operation (except possibly mod), then the element pointed to by position is erased. | |
541 | * [*Note:] Only provided for map views. | |
542 | ||
543 | ||
544 | [#reference_vector_of_modify_data_iterator_modifier] | |
545 | ||
546 | template< class DataModifier > | |
547 | bool modify_data(iterator position, DataModifier mod); | |
548 | ||
549 | * [*Requires: ] `DataModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of | |
550 | type: `mapped_type&`; `position` is a valid dereferenceable iterator of the view. | |
551 | * [*Effects:] Calls `mod(e.second)` where e is the element pointed to by position and | |
552 | rearranges `*position` into all the views of the `bimap`. | |
553 | If the rearrangement fails, the element is erased. | |
554 | It is successful if the rearrangement is allowed by all other views of the `bimap`. | |
555 | * [*Postconditions:] Validity of `position` is preserved if the operation succeeds. | |
556 | * [*Returns: ] `true` if the operation succeeded, `false` otherwise. | |
557 | * [link vector_of_complexity_signature | |
558 | [*Complexity:]] O(M(n)). | |
559 | * [*Exception safety:] Basic. If an exception is thrown by some user-provided | |
560 | operation (except possibly mod), then the element pointed to by position is erased. | |
561 | * [*Note:] Only provided for map views. | |
562 | ||
563 | [/ | |
564 | [#reference_vector_of_modify_iterator_modifier] | |
565 | ||
566 | template< class Modifier > | |
567 | bool modify(iterator position, Modifier mod); | |
568 | ||
569 | * [*Requires: ] `Modifier` is a model of __SGI_BINARY_FUNCTION__ accepting arguments of | |
570 | type: `first_type&` and `second_type&` for ['Map View] or `left_type&` and `right_type&` | |
571 | for ['Set View]; `position` is a valid dereferenceable iterator of the view. | |
572 | * [*Effects:] Calls `mod(e.first,e.second)` for ['Map View:] or calls `mod(e.left,e.right)` | |
573 | for ['Set View] where e is the element pointed to by `position` and | |
574 | rearranges `*position` into all the views of the `bimap`. | |
575 | Rearrangement on `vector_of` views does not change the position of the | |
576 | element with respect to the view; rearrangement on other views may or | |
577 | might not suceed. If the rearrangement fails, the element is erased. | |
578 | * [*Postconditions:] Validity of `position` is preserved if the operation succeeds. | |
579 | * [*Returns: ] `true` if the operation succeeded, `false` otherwise. | |
580 | * [link vector_of_complexity_signature [*Complexity:]] O(M(n)). | |
581 | * [*Exception safety:] Basic. If an exception is thrown by some user-provided | |
582 | operation (except possibly `mod`), then the element pointed to by position | |
583 | is erased. | |
584 | ] | |
585 | ||
586 | ||
587 | [endsect] | |
588 | ||
589 | [section List operations] | |
590 | ||
591 | `vector_of` views replicate the interface of `list_of` views, which | |
592 | in turn includes the list operations provided by `std::list`. The syntax and | |
593 | behavior of these operations exactly matches those of `list_of` views, but | |
594 | the associated complexity bounds differ in general. | |
595 | ||
596 | ||
597 | [#reference_vector_of_splice_iterator_this] | |
598 | ||
599 | void splice(iterator position, this_type & x); | |
600 | ||
601 | * [*Requires: ] `position` is a valid iterator of the view. `&x!=this`. | |
602 | * [*Effects:] Inserts the contents of `x` before position, in the same order | |
603 | as they were in `x`. Those elements successfully inserted are erased from `x`. | |
604 | * [link vector_of_complexity_signature | |
605 | [*Complexity:]] O(shl(end()-position,x.size()) + x.size()*I(n+x.size()) + x.size()*D(x.size())). | |
606 | * [*Exception safety:] Basic. | |
607 | ||
608 | ||
609 | [#reference_vector_of_splice_iterator_this_iterator] | |
610 | ||
611 | void splice(iterator position, this_type & x,iterator i); | |
612 | ||
613 | * [*Requires: ] `position` is a valid iterator of the view. `i` is a valid | |
614 | dereferenceable iterator `x`. | |
615 | * [*Effects:] Inserts the element pointed to by `i` before `position`: if | |
616 | insertion is successful, the element is erased from `x`. In the special | |
617 | case `&x==this`, no copy or deletion is performed, and the operation is | |
618 | always successful. If `position==i`, no operation is performed. | |
619 | * [*Postconditions:] If `&x==this`, no iterator or reference is invalidated. | |
620 | * [link vector_of_complexity_signature | |
621 | [*Complexity:]] If `&x==this`, O(rel(position,i,i+1)); | |
622 | otherwise O(shl(end()-position,1) + I(n) + D(n)). | |
623 | * [*Exception safety:] If `&x==this`, nothrow; otherwise, strong. | |
624 | ||
625 | ||
626 | [#reference_vector_of_splice_iterator_this_iterator_iterator] | |
627 | ||
628 | void splice(iterator position, this_type & x, iterator first, iterator last); | |
629 | ||
630 | * [*Requires: ] `position` is a valid iterator of the view. `first` and | |
631 | `last` are valid iterators of `x`. `last` is reachable from `first`. `position` is | |
632 | not in the range `[first,last)`. | |
633 | * [*Effects:] For each element in the range `[first,last)`, insertion is | |
634 | tried before `position`; if the operation is successful, the element is | |
635 | erased from `x`. In the special case `&x==this`, no copy or deletion is | |
636 | performed, and insertions are always successful. | |
637 | * [*Postconditions:] If `&x==this`, no iterator or reference is invalidated. | |
638 | * [link vector_of_complexity_signature | |
639 | [*Complexity:]] If `&x==this`, O(rel(position,first,last)); | |
640 | otherwise O(shl(end()-position,m) + m*I(n+m) + m*D(x.size())) | |
641 | where m is the number of elements in `[first,last)`. | |
642 | * [*Exception safety:] If `&x==this`, nothrow; otherwise, basic. | |
643 | ||
644 | ||
645 | [#reference_vector_of_remove_value] | |
646 | ||
647 | void remove(const value_type & value); | |
648 | ||
649 | * [*Effects:] Erases all elements of the view which compare equal to `value`. | |
650 | * [link vector_of_complexity_signature | |
651 | [*Complexity:]] O(n + m*D(n)), where m is the number of elements erased. | |
652 | * [*Exception safety:] Basic. | |
653 | ||
654 | ||
655 | [#reference_vector_of_remove_if_predicate] | |
656 | ||
657 | template< class Predicate > | |
658 | void remove_if(Predicate pred); | |
659 | ||
660 | * [*Effects:] Erases all elements `x` of the view for which `pred(x)` holds. | |
661 | * [link vector_of_complexity_signature | |
662 | [*Complexity:]] O(n + m*D(n)), where m is the number of elements erased. | |
663 | * [*Exception safety:] Basic. | |
664 | ||
665 | ||
666 | [#reference_vector_of_unique] | |
667 | ||
668 | void unique(); | |
669 | ||
670 | * [*Effects:] Eliminates all but the first element from every consecutive | |
671 | group of equal elements referred to by the iterator `i` in the range | |
672 | `[first+1,last)` for which `*i==*(i-1)`. | |
673 | * [link vector_of_complexity_signature | |
674 | [*Complexity:]] O(n + m*D(n)), where m is the number of elements erased. | |
675 | * [*Exception safety:] Basic. | |
676 | ||
677 | ||
678 | [#reference_vector_of_unique_predicate] | |
679 | ||
680 | template< class BinaryPredicate > | |
681 | void unique(BinaryPredicate binary_pred); | |
682 | ||
683 | * [*Effects:] Eliminates all but the first element from every consecutive | |
684 | group of elements referred to by the iterator i in the range `[first+1,last)` | |
685 | for which `binary_pred(*i, *(i-1))` holds. | |
686 | * [link vector_of_complexity_signature | |
687 | [*Complexity:]] O(n + m*D(n)), where m is the number of elements erased. | |
688 | * [*Exception safety:] Basic. | |
689 | ||
690 | ||
691 | [#reference_vector_of_merge_this] | |
692 | ||
693 | void merge(this_type & x); | |
694 | ||
695 | * [*Requires: ] `std::less<value_type>` is a __SGI_STRICT_WEAK_ORDERING__ over | |
696 | `value_type`. Both the view and `x` are sorted according to `std::less<value_type>`. | |
697 | * [*Effects:] Attempts to insert every element of x into the corresponding | |
698 | position of the view (according to the order). Elements successfully | |
699 | inserted are erased from `x`. The resulting sequence is stable, i.e. equivalent | |
700 | elements of either container preserve their relative position. In the special | |
701 | case `&x==this`, no operation is performed. | |
702 | * [*Postconditions:] Elements in the view and remaining elements in `x` are | |
703 | sorted. Validity of iterators to the view and of non-erased elements of `x` | |
704 | references is preserved. | |
705 | * [link vector_of_complexity_signature | |
706 | [*Complexity:]] If `&x==this`, constant; | |
707 | otherwise O(n + x.size()*I(n+x.size()) + x.size()*D(x.size())). | |
708 | * [*Exception safety:] If `&x==this`, nothrow; otherwise, basic. | |
709 | ||
710 | ||
711 | [#reference_vector_of_merge_this_compare] | |
712 | ||
713 | template< class Compare > | |
714 | void merge(this_type & x, Compare comp); | |
715 | ||
716 | * [*Requires: ] `Compare` is a __SGI_STRICT_WEAK_ORDERING__ over `value_type`. | |
717 | Both the view and `x` are sorted according to comp. | |
718 | * [*Effects:] Attempts to insert every element of `x` into the corresponding | |
719 | position of the view (according to `comp`). Elements successfully inserted | |
720 | are erased from `x`. The resulting sequence is stable, i.e. equivalent | |
721 | elements of either container preserve their relative position. In the | |
722 | special case `&x==this`, no operation is performed. | |
723 | * [*Postconditions:] Elements in the view and remaining elements in `x` are | |
724 | sorted according to `comp`. Validity of iterators to the view and of | |
725 | non-erased elements of `x` references is preserved. | |
726 | * [link vector_of_complexity_signature | |
727 | [*Complexity:]] If `&x==this`, constant; | |
728 | otherwise O(n + x.size()*I(n+x.size()) + x.size()*D(x.size())). | |
729 | * [*Exception safety:] If `&x==this`, nothrow; otherwise, basic. | |
730 | ||
731 | ||
732 | [#reference_vector_of_sort] | |
733 | ||
734 | void sort(); | |
735 | ||
736 | * [*Requires: ] `std::less<value_type>` is a __SGI_STRICT_WEAK_ORDERING__ over `value_type`. | |
737 | * [*Effects:] Sorts the view according to `std::less<value_type>`. | |
738 | The sorting is stable, i.e. equivalent elements preserve their relative position. | |
739 | * [*Postconditions:] Validity of iterators and references is preserved. | |
740 | * [*Complexity:] O(n*log(n)). | |
741 | * [*Exception safety:] Basic. | |
742 | ||
743 | ||
744 | [#reference_vector_of_sort_compare] | |
745 | ||
746 | template< class Compare > | |
747 | void sort(Compare comp); | |
748 | ||
749 | * [*Requires:] Compare is a __SGI_STRICT_WEAK_ORDERING__ over `value_type`. | |
750 | * [*Effects:] Sorts the view according to `comp`. The sorting is stable, i.e. | |
751 | equivalent elements preserve their relative position. | |
752 | * [*Postconditions:] Validity of iterators and references is preserved. | |
753 | * [*Complexity:] O(n*log(n)). | |
754 | * [*Exception safety:] Basic. | |
755 | ||
756 | ||
757 | [#reference_vector_of_reverse] | |
758 | ||
759 | void reverse(); | |
760 | ||
761 | * [*Effects:] Reverses the order of the elements in the view. | |
762 | * [*Postconditions:] Validity of iterators and references is preserved. | |
763 | * [*Complexity:] O(n). | |
764 | * [*Exception safety:] nothrow. | |
765 | ||
766 | ||
767 | [endsect] | |
768 | ||
769 | [section Rearrange operations] | |
770 | ||
771 | These operations, without counterpart in `std::list` (although splice provides | |
772 | partially overlapping functionality), perform individual and global repositioning | |
773 | of elements inside the index. | |
774 | ||
775 | ||
776 | [#reference_vector_of_relocate_iterator_iterator] | |
777 | ||
778 | void relocate(iterator position, iterator i); | |
779 | ||
780 | * [*Requires: ] `position` is a valid iterator of the view. `i` is a valid | |
781 | dereferenceable iterator of the view. | |
782 | * [*Effects:] Inserts the element pointed to by `i` before `position`. | |
783 | If `position==i`, no operation is performed. | |
784 | * [*Postconditions:] No iterator or reference is invalidated. | |
785 | * [*Complexity:] Constant. | |
786 | * [*Exception safety:] nothrow. | |
787 | ||
788 | ||
789 | [#reference_vector_of_relocate_iterator_iterator_iterator] | |
790 | ||
791 | void relocate(iterator position, iterator first, iterator last); | |
792 | ||
793 | * [*Requires: ] `position` is a valid iterator of the view. `first` and `last` are | |
794 | valid iterators of the view. `last` is reachable from `first`. `position` is not | |
795 | in the range `[first,last)`. | |
796 | * [*Effects:] The range of elements `[first,last)` is repositioned just before | |
797 | `position`. | |
798 | * [*Postconditions:] No iterator or reference is invalidated. | |
799 | * [*Complexity:] Constant. | |
800 | * [*Exception safety:] nothrow. | |
801 | ||
802 | ||
803 | [endsect] | |
804 | ||
805 | ||
806 | [section Serialization] | |
807 | ||
808 | Views cannot be serialized on their own, but only as part of the `bimap` | |
809 | into which they are embedded. In describing the additional preconditions and guarantees | |
810 | associated to `vector_of` views with respect to serialization of their embedding | |
811 | containers, we use the concepts defined in the `bimap` serialization section. | |
812 | ||
813 | [blurb [*Operation:] saving of a `bimap` b to an output archive (XML archive) ar.] | |
814 | ||
815 | * [*Requires:] No additional requirements to those imposed by the container. | |
816 | ||
817 | ||
818 | [blurb [*Operation:] loading of a `bimap` b' from an input archive (XML archive) ar.] | |
819 | ||
820 | * [*Requires:] No additional requirements to those imposed by the container. | |
821 | * [*Postconditions:] On successful loading, each of the elements of `[begin(), end())` is a | |
822 | restored copy of the corresponding element in `[m.get<i>().begin(), m.get<i>().end())`, | |
823 | where `i` is the position of the `vector_of` view in the container. | |
824 | ||
825 | ||
826 | ||
827 | [blurb [*Operation:] saving of an `iterator` or `const_iterator` `it` to an output archive (XML archive) ar.] | |
828 | ||
829 | * [*Requires: ] `it` is a valid iterator of the view. The associated `bimap` | |
830 | has been previously saved. | |
831 | ||
832 | ||
833 | ||
834 | [blurb [*Operation:] loading of an `iterator` or `const_iterator` `it`' from an input archive (XML archive) ar.] | |
835 | ||
836 | * [*Postconditions:] On successful loading, if it was dereferenceable then `*it`' is the | |
837 | restored copy of `*it`, otherwise `it`'`==end()`. | |
838 | * [*Note:] It is allowed that it be a `const_iterator` and the restored `it`' an `iterator`, | |
839 | or viceversa. | |
840 | ||
841 | ||
842 | [endsect] | |
843 | [endsect] | |
844 | ||
845 | ||
846 | [endsect] |