]>
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 set_of Reference] | |
16 | ||
17 | [section Header "boost/bimap/set_of.hpp" synopsis] | |
18 | ||
19 | namespace boost { | |
20 | namespace bimaps { | |
21 | ||
22 | ||
23 | template | |
24 | < | |
25 | class KeyType, | |
26 | class KeyCompare = std::less< KeyType > | |
27 | > | |
28 | struct set_of; | |
29 | ||
30 | ||
31 | template | |
32 | < | |
33 | class KeyCompare = std::less< _relation > | |
34 | > | |
35 | struct set_of_relation; | |
36 | ||
37 | ||
38 | } // namespace bimap | |
39 | } // namespace boost | |
40 | ||
41 | ||
42 | [endsect] | |
43 | ||
44 | [section Header "boost/bimap/multiset_of.hpp" synopsis] | |
45 | ||
46 | ||
47 | namespace boost { | |
48 | namespace bimaps { | |
49 | ||
50 | ||
51 | template | |
52 | < | |
53 | class KeyType, | |
54 | class KeyCompare = std::less< KeyType > | |
55 | > | |
56 | struct multiset_of; | |
57 | ||
58 | ||
59 | template | |
60 | < | |
61 | class KeyCompare = std::less< _relation > | |
62 | > | |
63 | struct multiset_of_relation; | |
64 | ||
65 | ||
66 | } // namespace bimap | |
67 | } // namespace boost | |
68 | ||
69 | ||
70 | [endsect] | |
71 | ||
72 | ||
73 | [section Collection type specifiers set_of and multiset_of] | |
74 | ||
75 | These collection type specifiers allow for insertion of sets disallowing or | |
76 | allowing duplicate elements, respectively. The syntaxes of `set_of` and | |
77 | `multiset_of` coincide, so they are described together. | |
78 | ||
79 | [endsect] | |
80 | ||
81 | ||
82 | [section \[multi\]set_of Views] | |
83 | ||
84 | A \[multi\]set_of set view is a std::\[multi\]set signature-compatible | |
85 | interface to the underlying heap of elements contained in a `bimap`. | |
86 | ||
87 | There are two variants: set_of, which does not allow duplicate elements | |
88 | (with respect to its associated comparison predicate) and multiset_of, | |
89 | which does accept those duplicates. The interface of these two variants | |
90 | is largely the same, so they are documented together with their | |
91 | differences explicitly noted where they exist. | |
92 | ||
93 | If you look the bimap from a side, you will use a map view, and if you | |
94 | look at it as a whole, you will be using a set view. | |
95 | ||
96 | ||
97 | ||
98 | namespace boost { | |
99 | namespace bimaps { | |
100 | namespace views { | |
101 | ||
102 | template< ``['-implementation defined parameter list-]`` > | |
103 | class ``['-implementation defined view name-]`` | |
104 | { | |
105 | public: | |
106 | ||
107 | typedef ``['-unspecified-]`` key_type; | |
108 | typedef ``['-unspecified-]`` value_type; | |
109 | typedef ``['-unspecified-]`` key_compare; | |
110 | typedef ``['-unspecified-]`` value_compare; | |
111 | typedef ``['-unspecified-]`` allocator_type; | |
112 | typedef ``['-unspecified-]`` reference; | |
113 | typedef ``['-unspecified-]`` const_reference; | |
114 | typedef ``['-unspecified-]`` iterator; | |
115 | typedef ``['-unspecified-]`` const_iterator; | |
116 | typedef ``['-unspecified-]`` size_type; | |
117 | typedef ``['-unspecified-]`` difference_type; | |
118 | typedef ``['-unspecified-]`` pointer; | |
119 | typedef ``['-unspecified-]`` const_pointer; | |
120 | typedef ``['-unspecified-]`` reverse_iterator; | |
121 | typedef ``['-unspecified-]`` const_reverse_iterator; | |
122 | ||
123 | typedef ``['-unspecified-]`` info_type; | |
124 | ||
125 | this_type & operator=(const this_type & x); | |
126 | ||
127 | allocator_type get_allocator() const; | |
128 | ||
129 | // iterators | |
130 | ||
131 | iterator begin(); | |
132 | const_iterator begin() const; | |
133 | ||
134 | iterator end(); | |
135 | const_iterator end() const; | |
136 | ||
137 | reverse_iterator rbegin(); | |
138 | const_reverse_iterator rbegin() const; | |
139 | ||
140 | reverse_iterator rend(); | |
141 | const_reverse_iterator rend() const; | |
142 | ||
143 | // capacity | |
144 | ||
145 | bool empty() const; | |
146 | ||
147 | size_type size() const; | |
148 | ||
149 | size_type max_size() const; | |
150 | ||
151 | // modifiers | |
152 | ||
153 | std::pair<iterator,bool> ``[link reference_set_of_insert_value insert]``(const value_type & x); | |
154 | ||
155 | iterator ``[link reference_set_of_insert_iterator_value insert]``(iterator position, const value_type & x); | |
156 | ||
157 | template< class InputIterator> | |
158 | void ``[link reference_set_of_insert_iterator_iterator insert]``(InputIterator first, InputIterator last); | |
159 | ||
160 | iterator ``[link reference_set_of_erase_iterator erase]``(iterator position); | |
161 | ||
162 | template< class CompatibleKey > | |
163 | size_type ``[link reference_set_of_erase_key erase]``(const CompatibleKey & x); | |
164 | ||
165 | iterator ``[link reference_set_of_erase_iterator_iterator erase]``(iterator first, iterator last); | |
166 | ||
167 | bool ``[link reference_set_of_replace_iterator_value replace]``(iterator position, const value_type& x); | |
168 | ||
169 | // Only in map views | |
170 | // { | |
171 | ||
172 | template< class CompatibleKey > | |
173 | bool ``[link reference_set_of_replace_key_iterator_key replace_key]``(iterator position, const CompatibleKey & x); | |
174 | ||
175 | template< class CompatibleData > | |
176 | bool ``[link reference_set_of_replace_data_iterator_data replace_data]``(iterator position, const CompatibleData & x); | |
177 | ||
178 | template< class KeyModifier > | |
179 | bool ``[link reference_set_of_modify_key_iterator_modifier modify_key]``(iterator position, KeyModifier mod); | |
180 | ||
181 | template< class DataModifier > | |
182 | bool ``[link reference_set_of_modify_data_iterator_modifier modify_data]``(iterator position, DataModifier mod); | |
183 | ||
184 | // } | |
185 | ||
186 | void swap(this_type & x); | |
187 | ||
188 | void clear(); | |
189 | ||
190 | // observers | |
191 | ||
192 | key_compare key_comp() const; | |
193 | ||
194 | value_compare value_comp() const; | |
195 | ||
196 | // set operations | |
197 | ||
198 | template< class CompatibleKey > | |
199 | iterator ``[link reference_set_of_find_key find]``(const CompatibleKey & x); | |
200 | ||
201 | template< class CompatibleKey > | |
202 | const_iterator ``[link reference_set_of_find_key find]``(const CompatibleKey & x) const; | |
203 | ||
204 | ||
205 | template< class CompatibleKey > | |
206 | size_type ``[link reference_set_of_count_key count]``(const CompatibleKey & x) const; | |
207 | ||
208 | ||
209 | template< class CompatibleKey > | |
210 | iterator ``[link reference_set_of_lower_bound_key lower_bound]``(const CompatibleKey & x); | |
211 | ||
212 | template< class CompatibleKey > | |
213 | const_iterator ``[link reference_set_of_lower_bound_key lower_bound]``(const CompatibleKey & x) const; | |
214 | ||
215 | ||
216 | template< class CompatibleKey > | |
217 | iterator ``[link reference_set_of_upper_bound_key upper_bound]``(const CompatibleKey & x); | |
218 | ||
219 | template< class CompatibleKey > | |
220 | const_iterator ``[link reference_set_of_upper_bound_key upper_bound]``(const CompatibleKey & x) const; | |
221 | ||
222 | ||
223 | template< class CompatibleKey > | |
224 | std::pair<iterator,iterator> | |
225 | ``[link reference_set_of_equal_range_key equal_range]``(const CompatibleKey & x); | |
226 | ||
227 | template< class CompatibleKey > | |
228 | std::pair<const_iterator,const_iterator> | |
229 | ``[link reference_set_of_equal_range_key equal_range]``(const CompatibleKey & x) const; | |
230 | ||
231 | // Only in maps views | |
232 | // { | |
233 | ||
234 | template< class LowerBounder, class UpperBounder> | |
235 | std::pair<iterator,iterator> ``[link reference_set_of_range_lower_upper range]``( | |
236 | LowerBounder lower, UpperBounder upper); | |
237 | ||
238 | template< class LowerBounder, class UpperBounder> | |
239 | std::pair<const_iterator,const_iterator> ``[link reference_set_of_range_lower_upper range]``( | |
240 | LowerBounder lower, UpperBounder upper) const; | |
241 | ||
242 | typedef ``['-unspecified-]`` mapped_type; | |
243 | typedef ``['-unspecified-]`` data_type; // Equal to mapped_type | |
244 | ||
245 | // Only in for `set_of` collection type | |
246 | // { | |
247 | ||
248 | template< class CompatibleKey > | |
249 | const mapped_type & ``[link reference_set_of_at_key_const at]``(const CompatibleKey & k) const; | |
250 | ||
251 | // Only if the other collection type is mutable | |
252 | // { | |
253 | ||
254 | template< class CompatibleKey > | |
255 | mapped_type & ``[link reference_set_of_operator_bracket_key operator\[\]]``(const CompatibleKey & k); | |
256 | ||
257 | template< class CompatibleKey > | |
258 | mapped_type & ``[link reference_set_of_at_key at]``(const CompatibleKey & k); | |
259 | ||
260 | // } | |
261 | ||
262 | // Only if info_hook is used | |
263 | // { | |
264 | ||
265 | template< class CompatibleKey > | |
266 | info_type & ``[link reference_set_of_info_at_key info_at]``(const CompatibleKey & k); | |
267 | ||
268 | template< class CompatibleKey > | |
269 | const info_type & ``[link reference_set_of_info_at_key info_at]``(const CompatibleKey & k) const; | |
270 | ||
271 | // } | |
272 | ||
273 | // } | |
274 | ||
275 | // } | |
276 | }; | |
277 | ||
278 | // view comparison | |
279 | ||
280 | bool operator==(const this_type & v1, const this_type & v2 ); | |
281 | bool operator< (const this_type & v1, const this_type & v2 ); | |
282 | bool operator!=(const this_type & v1, const this_type & v2 ); | |
283 | bool operator> (const this_type & v1, const this_type & v2 ); | |
284 | bool operator>=(const this_type & v1, const this_type & v2 ); | |
285 | bool operator<=(const this_type & v1, const this_type & v2 ); | |
286 | ||
287 | } // namespace views | |
288 | } // namespace bimap | |
289 | } // namespace boost | |
290 | ||
291 | ||
292 | ||
293 | [/ Functions that may be implemented some day | |
294 | ||
295 | template< class Modifier> | |
296 | bool ``[link reference_set_of_modify_iterator_modifier modify]``(iterator position, Modifier mod); | |
297 | ||
298 | template< class CompatibleKey, class CompatibleCompare > | |
299 | iterator find(const CompatibleKey & x, | |
300 | const CompatibleCompare & comp); | |
301 | ||
302 | template< class CompatibleKey, class CompatibleCompare > | |
303 | const_iterator find(const CompatibleKey & x, | |
304 | const CompatibleCompare & comp) const; | |
305 | ||
306 | template< class CompatibleKey, class CompatibleCompare > | |
307 | size_type count(const CompatibleKey & x, | |
308 | const CompatibleCompare & comp) const; | |
309 | ||
310 | template< class CompatibleKey, class CompatibleCompare > | |
311 | iterator lower_bound(const CompatibleKey & x, | |
312 | const CompatibleCompare & comp); | |
313 | ||
314 | template< class CompatibleKey, class CompatibleCompare > | |
315 | const_iterator lower_bound(const CompatibleKey & x, | |
316 | const CompatibleCompare & comp) const; | |
317 | ||
318 | template< class CompatibleKey, class CompatibleCompare > | |
319 | iterator upper_bound(const CompatibleKey & x, | |
320 | const CompatibleCompare & comp); | |
321 | ||
322 | template< class CompatibleKey, class CompatibleCompare > | |
323 | const_iterator upper_bound(const CompatibleKey & x, | |
324 | const CompatibleCompare & comp) const; | |
325 | ||
326 | template< class CompatibleKey, class CompatibleCompare > | |
327 | std::pair<iterator,iterator> equal_range( | |
328 | const CompatibleKey & x, const CompatibleCompare & comp); | |
329 | ||
330 | template< class CompatibleKey, class CompatibleCompare > | |
331 | std::pair<const_iterator,const_iterator> equal_range( | |
332 | const CompatibleKey & x, const CompatibleCompare & comp) const; | |
333 | ||
334 | ] | |
335 | ||
336 | ||
337 | In the case of a `bimap< {multi}set_of<Left>, ... >` | |
338 | ||
339 | In the set view: | |
340 | ||
341 | typedef signature-compatible with relation< Left, ... > key_type; | |
342 | typedef signature-compatible with relation< const Left, ... > value_type; | |
343 | ||
344 | In the left map view: | |
345 | ||
346 | typedef Left key_type; | |
347 | typedef ... mapped_type; | |
348 | ||
349 | typedef signature-compatible with std::pair< const Left, ... > value_type; | |
350 | ||
351 | In the right map view: | |
352 | ||
353 | typedef ... key_type; | |
354 | typedef Left mapped_type; | |
355 | ||
356 | typedef signature-compatible with std::pair< ... ,const Left > value_type; | |
357 | ||
358 | ||
359 | [#set_of_complexity_signature] | |
360 | ||
361 | [section Complexity signature] | |
362 | ||
363 | Here and in the descriptions of operations of this view, we adopt the | |
364 | scheme outlined in the [link complexity_signature_explanation complexity signature section]. | |
365 | The complexity signature of \[multi\]set_of view is: | |
366 | ||
367 | * copying: `c(n) = n * log(n)`, | |
368 | * insertion: `i(n) = log(n)`, | |
369 | * hinted insertion: `h(n) = 1` (constant) if the hint element precedes the point of | |
370 | insertion, `h(n) = log(n)` otherwise, | |
371 | * deletion: `d(n) = 1` (amortized constant), | |
372 | * replacement: `r(n) = 1` (constant) if the element position does not change, | |
373 | `r(n) = log(n)` otherwise, | |
374 | * modifying: `m(n) = 1` (constant) if the element position does not change, | |
375 | `m(n) = log(n)` otherwise. | |
376 | ||
377 | [endsect] | |
378 | ||
379 | [section Instantiation types] | |
380 | ||
381 | Set views are instantiated internally to a `bimap`. | |
382 | Instantiations are dependent on the following types: | |
383 | ||
384 | * `Value` from the set specifier, | |
385 | * `Allocator` from `bimap`, | |
386 | * `Compare` from the set specifier. | |
387 | ||
388 | `Compare` is a __SGI_STRICT_WEAK_ORDERING__ on elements of `Value`. | |
389 | ||
390 | [endsect] | |
391 | ||
392 | [section Constructors, copy and assignment] | |
393 | ||
394 | Set views do not have public constructors or destructors. | |
395 | Assignment, on the other hand, is provided. | |
396 | ||
397 | this_type & operator=(const this_type & x); | |
398 | ||
399 | * [*Effects: ] `a = b;` | |
400 | where a and b are the `bimap` objects to which `*this` and x | |
401 | belong, respectively. | |
402 | * [*Returns: ] `*this`. | |
403 | ||
404 | ||
405 | ||
406 | [endsect] | |
407 | ||
408 | [section Modifiers] | |
409 | ||
410 | [#reference_set_of_insert_value] | |
411 | ||
412 | std::pair<iterator,bool> insert(const value_type & x); | |
413 | ||
414 | * [*Effects:] Inserts `x` into the `bimap` to which the set view belongs if | |
415 | * the set view is non-unique OR no other element with equivalent key exists, | |
416 | * AND insertion is allowed by the other set specifications the `bimap`. | |
417 | * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only if insertion | |
418 | took place. On successful insertion, `p.first` points to the element inserted; | |
419 | otherwise, `p.first` points to an element that caused the insertion to be banned. | |
420 | Note that more than one element can be causing insertion not to be allowed. | |
421 | * [link set_of_complexity_signature | |
422 | [*Complexity:]] O(I(n)). | |
423 | * [*Exception safety:] Strong. | |
424 | ||
425 | ||
426 | [#reference_set_of_insert_iterator_value] | |
427 | ||
428 | iterator insert(iterator position, const value_type & x); | |
429 | ||
430 | * [*Requires: ] `position` is a valid iterator of the view. | |
431 | * [*Effects: ] `position` is used as a hint to improve the efficiency of the operation. Inserts `x` into the `bimap` to which the view belongs if | |
432 | * the set view is non-unique OR no other element with equivalent key exists, | |
433 | * AND insertion is allowed by all other views of the `bimap`. | |
434 | * [*Returns:] On successful insertion, an iterator to the newly inserted | |
435 | element. Otherwise, an iterator to an element that caused the insertion to be | |
436 | banned. Note that more than one element can be causing insertion not to be allowed. | |
437 | * [link set_of_complexity_signature | |
438 | [*Complexity:]] O(H(n)). | |
439 | * [*Exception safety:] Strong. | |
440 | ||
441 | ||
442 | [#reference_set_of_insert_iterator_iterator] | |
443 | ||
444 | template< class InputIterator > | |
445 | void insert(InputIterator first, InputIterator last); | |
446 | ||
447 | * [*Requires: ] `InputIterator` is a model of __SGI_INPUT_ITERATOR__ over elements of | |
448 | type `value_type` or a type convertible to value_type. `first` and `last` are not | |
449 | iterators into any view of the `bimap` to which this index | |
450 | belongs. `last` is reachable from `first`. | |
451 | * [*Effects: ] | |
452 | `iterator hint = end()`; | |
453 | `while( first != last ) hint = insert( hint, *first++ );` | |
454 | * [link set_of_complexity_signature | |
455 | [*Complexity:]] O(m*H(n+m)), where m is the number of elements in | |
456 | `[first, last)`. | |
457 | * [*Exception safety:] Basic. | |
458 | ||
459 | ||
460 | [#reference_set_of_erase_iterator] | |
461 | ||
462 | iterator erase(iterator position); | |
463 | ||
464 | * [*Requires: ] `position` is a valid dereferenceable iterator if the set view. | |
465 | * [*Effects:] Deletes the element pointed to by `position`. | |
466 | * [*Returns:] An iterator pointing to the element immediately following | |
467 | the one that was deleted, or `end()` if no such element exists. | |
468 | * [link set_of_complexity_signature | |
469 | [*Complexity:]] O(D(n)). | |
470 | * [*Exception safety:] nothrow. | |
471 | ||
472 | ||
473 | [#reference_set_of_erase_key] | |
474 | ||
475 | template< class CompatibleKey > | |
476 | size_type erase(const CompatibleKey & x); | |
477 | ||
478 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
479 | * [*Effects:] Deletes the elements with key equivalent to `x`. | |
480 | * [*Returns:] Number of elements deleted. | |
481 | * [link set_of_complexity_signature | |
482 | [*Complexity:]] O(log(n) + m*D(n)), where m is the number of elements deleted. | |
483 | * [*Exception safety:] Basic. | |
484 | ||
485 | ||
486 | [#reference_set_of_erase_iterator_iterator] | |
487 | ||
488 | iterator erase(iterator first, iterator last); | |
489 | ||
490 | * [*Requires: ] `[first,last)` is a valid range of the view. | |
491 | * [*Effects:] Deletes the elements in `[first,last)`. | |
492 | * [*Returns:] last. | |
493 | * [link set_of_complexity_signature | |
494 | [*Complexity:]] O(log(n) + m*D(n)), where m is the number of elements | |
495 | in `[first,last)`. | |
496 | * [*Exception safety:] nothrow. | |
497 | ||
498 | ||
499 | [#reference_set_of_replace_iterator_value] | |
500 | ||
501 | bool replace(iterator position, const value_type& x); | |
502 | ||
503 | * [*Requires: ] `position` is a valid dereferenceable iterator of the set view. | |
504 | * [*Effects:] Assigns the value `x` to the element pointed to by `position` into | |
505 | the `bimap` to which the set view belongs if, for the value `x` | |
506 | * the set view is non-unique OR no other element with equivalent key exists | |
507 | (except possibly `*position`), | |
508 | * AND replacing is allowed by all other views of the `bimap`. | |
509 | * [*Postconditions:] Validity of position is preserved in all cases. | |
510 | * [*Returns: ] `true` if the replacement took place, `false` otherwise. | |
511 | * [link set_of_complexity_signature | |
512 | [*Complexity:]] O(R(n)). | |
513 | * [*Exception safety:] Strong. If an exception is thrown by some user-provided | |
514 | operation, the `bimap` to which the set view belongs remains in | |
515 | its original state. | |
516 | ||
517 | ||
518 | [#reference_set_of_replace_key_iterator_key] | |
519 | ||
520 | template< class CompatibleKey > | |
521 | bool replace_key(iterator position, const CompatibleKey & x); | |
522 | ||
523 | * [*Requires: ] `position` is a valid dereferenceable iterator of the set view. | |
524 | `CompatibleKey` can be assigned to `key_type`. | |
525 | * [*Effects:] Assigns the value `x` to `e.first`, where `e` is the element pointed | |
526 | to by `position` into the `bimap` to which the set view belongs if, | |
527 | * the map view is non-unique OR no other element with equivalent key exists | |
528 | (except possibly `*position`), | |
529 | * AND replacing is allowed by all other views of the `bimap`. | |
530 | * [*Postconditions:] Validity of position is preserved in all cases. | |
531 | * [*Returns: ] `true` if the replacement took place, `false` otherwise. | |
532 | * [link set_of_complexity_signature | |
533 | [*Complexity:]] O(R(n)). | |
534 | * [*Exception safety:] Strong. If an exception is thrown by some user-provided | |
535 | operation, the `bimap` to which the set view belongs remains in | |
536 | its original state. | |
537 | ||
538 | ||
539 | [#reference_set_of_replace_data_iterator_data] | |
540 | ||
541 | template< class CompatibleData > | |
542 | bool replace_data(iterator position, const CompatibleData & x); | |
543 | ||
544 | * [*Requires: ] `position` is a valid dereferenceable iterator of the set view. | |
545 | `CompatibleKey` can be assigned to `mapped_type`. | |
546 | * [*Effects:] Assigns the value `x` to `e.second`, where `e` is the element pointed | |
547 | to by `position` into the `bimap` to which the set view belongs if, | |
548 | * the map view is non-unique OR no other element with equivalent key exists | |
549 | (except possibly `*position`), | |
550 | * AND replacing is allowed by all other views of the `bimap`. | |
551 | * [*Postconditions:] Validity of position is preserved in all cases. | |
552 | * [*Returns: ] `true` if the replacement took place, `false` otherwise. | |
553 | * [link set_of_complexity_signature | |
554 | [*Complexity:]] O(R(n)). | |
555 | * [*Exception safety:] Strong. If an exception is thrown by some user-provided | |
556 | operation, the `bimap` to which the set view belongs remains in | |
557 | its original state. | |
558 | ||
559 | ||
560 | [#reference_set_of_modify_key_iterator_modifier] | |
561 | ||
562 | template< class KeyModifier > | |
563 | bool modify_key(iterator position, KeyModifier mod); | |
564 | ||
565 | * [*Requires: ] `KeyModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of | |
566 | type: `key_type&`; `position` is a valid dereferenceable iterator of the view. | |
567 | * [*Effects:] Calls `mod(e.first)` where e is the element pointed to by position and | |
568 | rearranges `*position` into all the views of the `bimap`. | |
569 | If the rearrangement fails, the element is erased. | |
570 | Rearrangement is successful if | |
571 | * the map view is non-unique OR no other element with equivalent key exists, | |
572 | * AND rearrangement is allowed by all other views of the `bimap`. | |
573 | * [*Postconditions:] Validity of `position` is preserved if the operation succeeds. | |
574 | * [*Returns: ] `true` if the operation succeeded, `false` otherwise. | |
575 | * [link set_of_complexity_signature | |
576 | [*Complexity:]] O(M(n)). | |
577 | * [*Exception safety:] Basic. If an exception is thrown by some user-provided | |
578 | operation (except possibly mod), then the element pointed to by position is erased. | |
579 | * [*Note:] Only provided for map views. | |
580 | ||
581 | ||
582 | [#reference_set_of_modify_data_iterator_modifier] | |
583 | ||
584 | template< class DataModifier > | |
585 | bool modify_data(iterator position, DataModifier mod); | |
586 | ||
587 | * [*Requires: ] `DataModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of | |
588 | type: `mapped_type&`; `position` is a valid dereferenceable iterator of the view. | |
589 | * [*Effects:] Calls `mod(e.second)` where e is the element pointed to by position and | |
590 | rearranges `*position` into all the views of the `bimap`. | |
591 | If the rearrangement fails, the element is erased. | |
592 | Rearrangement is successful if | |
593 | * the oppositte map view is non-unique OR no other element with equivalent key in that | |
594 | view exists, | |
595 | * AND rearrangement is allowed by all other views of the `bimap`. | |
596 | * [*Postconditions:] Validity of `position` is preserved if the operation succeeds. | |
597 | * [*Returns: ] `true` if the operation succeeded, `false` otherwise. | |
598 | * [link set_of_complexity_signature | |
599 | [*Complexity:]] O(M(n)). | |
600 | * [*Exception safety:] Basic. If an exception is thrown by some user-provided | |
601 | operation (except possibly mod), then the element pointed to by position is erased. | |
602 | * [*Note:] Only provided for map views. | |
603 | ||
604 | [/ | |
605 | ||
606 | [#reference_set_of_modify_iterator_modifier] | |
607 | ||
608 | template< class Modifier > | |
609 | bool modify(iterator position, Modifier mod); | |
610 | ||
611 | * [*Requires: ] `Modifier` is a model of __SGI_BINARY_FUNCTION__ accepting arguments of | |
612 | type: `first_type&` and `second_type&` for ['Map View] or `left_type&` and `right_type&` | |
613 | ['Set View]; `position` is a valid dereferenceable iterator of the view. | |
614 | * [*Effects:] Calls `mod(e.first,e.second)` for ['Map View] or Calls `mod(e.left,e.right)` | |
615 | for ['Set View] where e is the element pointed to by position and rearranges `*position` | |
616 | into all the views of the `bimap`. | |
617 | If the rearrangement fails, the element is erased. | |
618 | Rearrangement is successful if | |
619 | * the view is non-unique OR no other element with equivalent key exists, | |
620 | * AND rearrangement is allowed by all other views of the `bimap`. | |
621 | * [*Postconditions:] Validity of `position` is preserved if the operation succeeds. | |
622 | * [*Returns: ] `true` if the operation succeeded, `false` otherwise. | |
623 | * [link set_of_complexity_signature | |
624 | [*Complexity:]] O(M(n)). | |
625 | * [*Exception safety:] Basic. If an exception is thrown by some user-provided | |
626 | operation (except possibly mod), then the element pointed to by position is erased. | |
627 | ||
628 | ] | |
629 | ||
630 | [endsect] | |
631 | ||
632 | [section Set operations] | |
633 | ||
634 | `[multi]set_of` views provide the full lookup functionality required by | |
635 | __SGI_SORTED_ASSOCIATIVE_CONTAINER__ and __SGI_UNIQUE_ASSOCIATIVE_CONTAINER__, | |
636 | namely `find`, `count`, `lower_bound`, `upper_bound` and `equal_range`. | |
637 | Additionally, these member functions are templatized to allow for non-standard | |
638 | arguments, so extending the types of search operations allowed. | |
639 | ||
640 | [/ | |
641 | The kinds of arguments permissible when invoking the lookup member functions | |
642 | are defined by the following concept. | |
643 | ||
644 | Consider a __SGI_STRICT_WEAK_ORDERING__ `Compare` over values of type `Key`. A pair of | |
645 | types `(CompatibleKey, CompatibleCompare)` is said to be a ['compatible extension] | |
646 | of Compare if | |
647 | ||
648 | * `CompatibleCompare` is a __SGI_BINARY_PREDICATE__ over `(Key, CompatibleKey)`, | |
649 | * `CompatibleCompare` is a __SGI_BINARY_PREDICATE__ over `(CompatibleKey, Key)`, | |
650 | * if `c_comp(ck,k1)` then `!c_comp(k1,ck)`, | |
651 | * if `!c_comp(ck,k1)` and `!comp(k1,k2)` then `!c_comp(ck,k2)`, | |
652 | * if `!c_comp(k1,ck)` and `!comp(k2,k1)` then `!c_comp(k2,ck)`, | |
653 | ||
654 | for every `c_comp` of type `CompatibleCompare`, `comp` of type `Compare`, `ck` of type | |
655 | `CompatibleKey` and `k1`, `k2` of type `Key`. | |
656 | ] | |
657 | A type `CompatibleKey` is said to be a ['compatible key] of `Compare` | |
658 | if `(CompatibleKey, Compare)` is a compatible extension of `Compare`. This implies | |
659 | that `Compare`, as well as being a strict weak ordering, accepts arguments of type | |
660 | `CompatibleKey`, which usually means it has several overloads of `operator()`. | |
661 | ||
662 | [/ | |
663 | In the context of a compatible extension or a compatible key, the expressions | |
664 | "equivalent", "less than" and "greater than" take on their obvious interpretations. | |
665 | ] | |
666 | ||
667 | [#reference_set_of_find_key] | |
668 | ||
669 | template< class CompatibleKey > | |
670 | iterator find(const CompatibleKey & x); | |
671 | ||
672 | template< class CompatibleKey > | |
673 | const_iterator find(const CompatibleKey & x) const; | |
674 | ||
675 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
676 | * [*Effects:] Returns a pointer to an element whose key is equivalent to `x`, or | |
677 | `end()` if such an element does not exist. | |
678 | * [*Complexity:] O(log(n)). | |
679 | ||
680 | [/ | |
681 | template< class CompatibleKey, class CompatibleCompare > | |
682 | iterator find(const CompatibleKey & x, | |
683 | const CompatibleCompare & comp); | |
684 | ||
685 | template< class CompatibleKey, class CompatibleCompare > | |
686 | const_iterator find(const CompatibleKey & x, | |
687 | const CompatibleCompare & comp) const; | |
688 | ||
689 | * [*Requires: ] `(CompatibleKey, CompatibleCompare)` is a compatible extension of | |
690 | `key_compare.` | |
691 | * [*Effects:] Returns a pointer to an element whose key is | |
692 | equivalent to `x`, or `end()` if such an element does not exist. | |
693 | * [*Complexity:] O(log(n)). | |
694 | ] | |
695 | ||
696 | [#reference_set_of_count_key] | |
697 | ||
698 | template< class CompatibleKey > | |
699 | size_type count(const key_type & x) const; | |
700 | ||
701 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
702 | * [*Effects:] Returns the number of elements with key equivalent to `x`. | |
703 | * [*Complexity:] O(log(n) + count(x)). | |
704 | ||
705 | [/ | |
706 | template< class CompatibleKey, class CompatibleCompare > | |
707 | size_type count(const CompatibleKey & x, | |
708 | const CompatibleCompare & comp) const; | |
709 | ||
710 | * [*Requires: ] `(CompatibleKey, CompatibleCompare)` is a compatible extension of | |
711 | `key_compare.` | |
712 | * [*Effects:] Returns the number of elements with key equivalent to `x`. | |
713 | * [*Complexity:] O(log(n) + count(x)). | |
714 | ] | |
715 | ||
716 | [#reference_set_of_lower_bound_key] | |
717 | ||
718 | template< class CompatibleKey > | |
719 | iterator lower_bound(const key_type & x); | |
720 | ||
721 | template< class CompatibleKey > | |
722 | const_iterator lower_bound(const key_type & x) const; | |
723 | ||
724 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
725 | * [*Effects:] Returns an iterator pointing to the first element with key not | |
726 | less than `x`, or `end()` if such an element does not exist. | |
727 | * [*Complexity:] O(log(n)). | |
728 | ||
729 | ||
730 | [#reference_set_of_upper_bound_key] | |
731 | ||
732 | template< class CompatibleKey > | |
733 | iterator upper_bound(const key_type & x); | |
734 | ||
735 | template< class CompatibleKey > | |
736 | const_iterator upper_bound(const key_type & x) const; | |
737 | ||
738 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
739 | * [*Effects:] Returns an iterator pointing to the first element with key greater | |
740 | than `x`, or `end()` if such an element does not exist. | |
741 | * [*Complexity:] O(log(n)). | |
742 | ||
743 | ||
744 | [#reference_set_of_equal_range_key] | |
745 | ||
746 | template< class CompatibleKey > | |
747 | std::pair<iterator,iterator> | |
748 | equal_range(const key_type & x); | |
749 | ||
750 | template< class CompatibleKey > | |
751 | std::pair<const_iterator,const_iterator> | |
752 | equal_range(const key_type & x) const; | |
753 | ||
754 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
755 | * [*Effects:] Equivalent to `make_pair(lower_bound(x),upper_bound(x))`. | |
756 | * [*Complexity:] O(log(n)). | |
757 | ||
758 | ||
759 | ||
760 | [endsect] | |
761 | ||
762 | [section Range operations] | |
763 | ||
764 | The member function range is not defined for sorted associative | |
765 | containers, but `[multi]set_of` map views provide it as a convenient utility. | |
766 | A range or interval is defined by two conditions for the lower and upper | |
767 | bounds, which are modelled after the following concepts. | |
768 | ||
769 | Consider a __SGI_STRICT_WEAK_ORDERING__ `Compare` over values of type Key. | |
770 | A type `LowerBounder` is said to be a lower bounder of `Compare` if | |
771 | ||
772 | * `LowerBounder` is a `Predicate` over `Key`, | |
773 | * if `lower(k1)` and `!comp(k2,k1)` then `lower(k2)`, | |
774 | ||
775 | for every `lower` of type `LowerBounder`, `comp` of type `Compare`, and `k1`, `k2` | |
776 | of type `Key`. | |
777 | Similarly, an upper bounder is a type `UpperBounder` such that | |
778 | ||
779 | * `UpperBounder` is a `Predicate` over `Key`, | |
780 | * if `upper(k1)` and `!comp(k1,k2)` then `upper(k2)`, | |
781 | ||
782 | for every `upper` of type `UpperBounder`, `comp` of type `Compare`, and `k1`, `k2` | |
783 | of type `Key`. | |
784 | ||
785 | [#reference_set_of_range_lower_upper] | |
786 | ||
787 | template< class LowerBounder, class UpperBounder> | |
788 | std::pair<const_iterator,const_iterator> range( | |
789 | LowerBounder lower, UpperBounder upper) const; | |
790 | ||
791 | * [*Requires: ] `LowerBounder` and `UpperBounder` are a lower and upper bounder of | |
792 | `key_compare`, respectively. | |
793 | * [*Effects:] Returns a pair of iterators pointing to | |
794 | the beginning and one past the end of the subsequence of elements satisfying | |
795 | lower and upper simultaneously. If no such elements exist, the iterators both | |
796 | point to the first element satisfying lower, or else are equal to `end()` if this | |
797 | latter element does not exist. | |
798 | * [*Complexity:] O(log(n)). | |
799 | * [*Variants:] In place of lower or upper (or both), the singular value | |
800 | `boost::bimap::unbounded` can be provided. This acts as a predicate which | |
801 | all values of type `key_type` satisfy. | |
802 | * [*Note:] Only provided for map views. | |
803 | ||
804 | [endsect] | |
805 | ||
806 | [section at(), info_at() and operator\[\] - set_of only] | |
807 | ||
808 | [#reference_set_of_at_key_const] | |
809 | ||
810 | template< class CompatibleKey > | |
811 | const mapped_type & at(const CompatibleKey & k) const; | |
812 | ||
813 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
814 | * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or | |
815 | throws `std::out_of_range` if such key does not exist. | |
816 | * [*Complexity:] O(log(n)). | |
817 | * [*Note:] Only provided when `set_of` is used. | |
818 | ||
819 | The symmetry of bimap imposes some constraints on `operator[]` and the | |
820 | non constant version of at() that are not found in `std::maps`. | |
821 | Tey are only provided if the other collection type is mutable | |
822 | (`list_of`, `vector_of` and `unconstrained_set_of`). | |
823 | ||
824 | [#reference_set_of_operator_bracket_key] | |
825 | ||
826 | template< class CompatibleKey > | |
827 | mapped_type & operator[](const CompatibleKey & k); | |
828 | ||
829 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
830 | * [*Effects: ] `return insert(value_type(k,mapped_type()))->second;` | |
831 | * [*Complexity:] O(log(n)). | |
832 | * [*Note:] Only provided when `set_of` is used and the other collection | |
833 | type is mutable. | |
834 | ||
835 | [#reference_set_of_at_key] | |
836 | ||
837 | template< class CompatibleKey > | |
838 | mapped_type & at(const CompatibleKey & k); | |
839 | ||
840 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
841 | * [*Effects: ] Returns the `mapped_type` reference that is associated with `k`, or | |
842 | throws `std::out_of_range` if such key does not exist. | |
843 | * [*Complexity:] O(log(n)). | |
844 | * [*Note:] Only provided when `set_of` is used and the other collection | |
845 | type is mutable. | |
846 | ||
847 | [/ | |
848 | The symmetry of bimap imposes some constraints on `operator[]` that are | |
849 | not found in `std::maps`. If other views are unique, | |
850 | `bimap::duplicate_value` is thrown whenever an assignment is attempted to | |
851 | a value that is already a key in these views. As for | |
852 | `bimap::value_not_found`, this exception is thrown while trying to access | |
853 | a non-existent key: this behaviour differs from that of `std::map`, which | |
854 | automatically assigns a default value to non-existent keys referred to | |
855 | by `operator[]`. | |
856 | ||
857 | const mapped_type & operator[](const typename key_type & k) const; | |
858 | ||
859 | * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or | |
860 | throws `bimap::value_not_found` if such an element does not exist. | |
861 | * [*Complexity:] O(log(n)). | |
862 | ||
863 | ||
864 | ``['-unspecified mapped_type proxy-]`` operator[](const typename key_type & k); | |
865 | ||
866 | * [*Effects:] Returns a proxy to a `mapped_type` associated with `k` and the | |
867 | bimap. The proxy behaves as a reference to the `mapped_type` object. If this | |
868 | proxy is read and `k` was not in the bimap, the bimap::value_not_found is | |
869 | thrown. If it is written then `bimap::duplicate_value` is thrown if the | |
870 | assignment is not allowed by one of the other views of the `bimap`. | |
871 | * [link set_of_complexity_signature | |
872 | [*Complexity:]] If the assignment operator of the proxy is not used, then | |
873 | the order is O(log(n)). If it is used, the order is O(I(n)) if `k` was not | |
874 | in the bimap and O(R(n)) if it existed in the bimap. | |
875 | ] | |
876 | ||
877 | ||
878 | [#reference_set_of_info_at_key] | |
879 | ||
880 | template< class CompatibleKey > | |
881 | info_type & info_at(const CompatibleKey & k); | |
882 | ||
883 | template< class CompatibleKey > | |
884 | const info_type & info_at(const CompatibleKey & k) const; | |
885 | ||
886 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
887 | * [*Effects:] Returns the `info_type` reference that is associated with `k`, or | |
888 | throws `std::out_of_range` if such key does not exist. | |
889 | * [*Complexity:] O(log(n)). | |
890 | * [*Note:] Only provided when `set_of` and `info_hook` are used | |
891 | ||
892 | ||
893 | [endsect] | |
894 | ||
895 | [section Serialization] | |
896 | ||
897 | Views cannot be serialized on their own, but only as part of the `bimap` | |
898 | into which they are embedded. In describing the additional preconditions and guarantees | |
899 | associated to `[multi]set_of` views with respect to serialization of their embedding containers, | |
900 | we use the concepts defined in the `bimap` serialization section. | |
901 | ||
902 | [blurb [*Operation:] saving of a `bimap` m to an output archive (XML archive) ar.] | |
903 | ||
904 | * [*Requires:] No additional requirements to those imposed by the container. | |
905 | ||
906 | ||
907 | [blurb [*Operation:] loading of a `bimap` m' from an input archive (XML archive) ar.] | |
908 | ||
909 | * [*Requires:] In addition to the general requirements, `value_comp()` must be | |
910 | serialization-compatible with `m.get<i>().value_comp()`, where i is the position | |
911 | of the ordered view in the container. | |
912 | * [*Postconditions:] On successful loading, each of the elements of `[begin(), end())` | |
913 | is a restored copy of the corresponding element in `[m.get<i>().begin(), m.get<i>().end())`. | |
914 | ||
915 | ||
916 | ||
917 | [blurb [*Operation:] saving of an iterator or `const_iterator` it to an output archive | |
918 | (XML archive) ar.] | |
919 | ||
920 | * [*Requires: ] `it` is a valid iterator of the view. The associated `bimap` | |
921 | has been previously saved. | |
922 | ||
923 | ||
924 | [blurb [*Operation:] loading of an `iterator` or `const_iterator` `it`' from an input archive ( | |
925 | XML archive) ar.] | |
926 | ||
927 | * [*Postconditions:] On successful loading, if it was dereferenceable then `*it`' is the | |
928 | restored copy of `*it`, otherwise `it`'` == end()`. | |
929 | * [*Note:] It is allowed that it be a `const_iterator` and the restored `it`' an iterator, | |
930 | or viceversa. | |
931 | ||
932 | ||
933 | [endsect] | |
934 | [endsect] | |
935 | ||
936 | [endsect] |