]>
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 unordered_set_of Reference] | |
16 | ||
17 | [section Header "boost/bimap/unordered_set_of.hpp" synopsis] | |
18 | ||
19 | namespace boost { | |
20 | namespace bimaps { | |
21 | ||
22 | ||
23 | template | |
24 | < | |
25 | class KeyType, | |
26 | class HashFunctor = hash< KeyType >, | |
27 | class EqualKey = std::equal_to< KeyType > | |
28 | > | |
29 | struct unordered_set_of; | |
30 | ||
31 | ||
32 | template | |
33 | < | |
34 | class HashFunctor = hash< _relation >, | |
35 | class EqualKey = std::equal_to< _relation > | |
36 | > | |
37 | struct unordered_set_of_relation; | |
38 | ||
39 | ||
40 | } // namespace bimap | |
41 | } // namespace boost | |
42 | ||
43 | ||
44 | [endsect] | |
45 | ||
46 | [section Header "boost/bimap/unordered_multiset_of.hpp" synopsis] | |
47 | ||
48 | namespace boost { | |
49 | namespace bimaps { | |
50 | ||
51 | ||
52 | template | |
53 | < | |
54 | class KeyType, | |
55 | class HashFunctor = hash< KeyType >, | |
56 | class EqualKey = std::equal_to< KeyType > | |
57 | > | |
58 | struct unordered_multiset_of; | |
59 | ||
60 | ||
61 | template | |
62 | < | |
63 | class HashFunctor = hash< _relation >, | |
64 | class EqualKey = std::equal_to< _relation > | |
65 | > | |
66 | struct unordered_multiset_of_relation; | |
67 | ||
68 | ||
69 | } // namespace bimap | |
70 | } // namespace boost | |
71 | ||
72 | ||
73 | [endsect] | |
74 | ||
75 | [section Collection type specifiers unordered_set_of and unordered_multiset_of] | |
76 | ||
77 | These collection types specifiers allow for set views without and | |
78 | with allowance of duplicate elements, respectively. The syntax of | |
79 | `set_of` and `multiset_of` coincide, thus we describe them | |
80 | in a grouped manner. | |
81 | ||
82 | [endsect] | |
83 | ||
84 | [section unordered_\[multi\]set_of Views] | |
85 | ||
86 | An unordered_\[multi\]set_of set view is a tr1::unordered\[multi\]set signature compatible | |
87 | interface to the underlying heap of elements contained in a `bimap`. | |
88 | ||
89 | The interface and semantics of `unordered_[multi]set_of` views are | |
90 | modeled according to the proposal for unordered associative containers given | |
91 | in the __CPP_STANDARD_LIBRARY_TECHNICAL_REPORT__, also known as TR1. | |
92 | An `unordered_[multi]set_of` view is particularized according to a given | |
93 | `Hash` function object which returns hash values for the keys and a | |
94 | binary predicate `Pred` acting as an equivalence relation on values of Key. | |
95 | ||
96 | There are two variants: unordered_set_of, which do not allow duplicate elements | |
97 | (with respect to its associated comparison predicate) and unordered_multiset_of, | |
98 | which accept those duplicates. The interface of these two variants is the same | |
99 | to a great extent, so they are documented together with their differences | |
100 | explicitly noted when they exist. | |
101 | ||
102 | If you look the bimap by a side, you will use a map view and if you looked | |
103 | it as a whole you will be using a set view. | |
104 | ||
105 | Except where noted, `unordered_[multi]set_of` views (both unique and non-unique) are models | |
106 | of [^Unordered Associative Container]. | |
107 | Validity of iterators and references to elements is preserved in all cases. | |
108 | Occasionally, the exception safety guarantees provided are actually stronger | |
109 | than required by the extension draft. We only provide descriptions of those | |
110 | types and operations that are either not present in the concepts modeled or | |
111 | do not exactly conform to the requirements for unordered associative containers. | |
112 | ||
113 | ||
114 | namespace boost { | |
115 | namespace bimap { | |
116 | namespace views { | |
117 | ||
118 | template< ``['-implementation defined parameter list-]`` > | |
119 | class ``['-implementation defined view name-]`` | |
120 | { | |
121 | public: | |
122 | ||
123 | // types | |
124 | ||
125 | typedef ``['-unspecified-]`` key_type; | |
126 | typedef ``['-unspecified-]`` value_type; | |
127 | typedef ``['-unspecified-]`` key_compare; | |
128 | typedef ``['-unspecified-]`` value_compare; | |
129 | typedef ``['-unspecified-]`` hasher; | |
130 | typedef ``['-unspecified-]`` key_equal; | |
131 | typedef ``['-unspecified-]`` allocator_type; | |
132 | typedef ``['-unspecified-]`` reference; | |
133 | typedef ``['-unspecified-]`` const_reference; | |
134 | typedef ``['-unspecified-]`` iterator; | |
135 | typedef ``['-unspecified-]`` const_iterator; | |
136 | typedef ``['-unspecified-]`` size_type; | |
137 | typedef ``['-unspecified-]`` difference_type; | |
138 | typedef ``['-unspecified-]`` pointer; | |
139 | typedef ``['-unspecified-]`` const_pointer; | |
140 | typedef ``['-unspecified-]`` local_iterator; | |
141 | typedef ``['-unspecified-]`` const_local_iterator; | |
142 | ||
143 | typedef ``['-unspecified-]`` info_type; | |
144 | ||
145 | // construct/destroy/copy: | |
146 | ||
147 | this_type & operator=(const this_type & x); | |
148 | ||
149 | allocator_type get_allocator() const; | |
150 | ||
151 | // size and capacity | |
152 | ||
153 | bool empty() const; | |
154 | size_type size() const; | |
155 | size_type max_size() const; | |
156 | ||
157 | // iterators | |
158 | ||
159 | iterator begin(); | |
160 | const_iterator begin() const; | |
161 | iterator end(); | |
162 | const_iterator end() const; | |
163 | ||
164 | // modifiers | |
165 | ||
166 | std::pair< iterator, bool > ``[link reference_unordered_set_of_insert_value insert]``(const value_type & x); | |
167 | ||
168 | iterator ``[link reference_unordered_set_of_insert_iterator_value insert]``(iterator position, const value_type & x); | |
169 | ||
170 | template< class InputIterator > | |
171 | void ``[link reference_unordered_set_of_insert_iterator_iterator insert]``(InputIterator first, InputIterator last); | |
172 | ||
173 | iterator ``[link reference_unordered_set_of_erase_iterator erase]``(iterator position); | |
174 | ||
175 | template< class CompatibleKey > | |
176 | size_type ``[link reference_unordered_set_of_erase_key erase]``(const CompatibleKey & x); | |
177 | ||
178 | iterator ``[link reference_unordered_set_of_erase_iterator_iterator erase]``(iterator first, iterator last); | |
179 | ||
180 | bool ``[link reference_unordered_set_of_replace_iterator_value replace]``(iterator position, const value_type & x); | |
181 | ||
182 | // Only in map views | |
183 | // { | |
184 | ||
185 | typedef ``['-unspecified-]`` mapped_type; | |
186 | typedef ``['-unspecified-]`` data_type; // Equal to mapped_type | |
187 | ||
188 | template< class CompatibleKey > | |
189 | bool ``[link reference_unordered_set_of_replace_key_iterator_key replace_key]``(iterator position, const CompatibleKey & x); | |
190 | ||
191 | template< class CompatibleData > | |
192 | bool ``[link reference_unordered_set_of_replace_data_iterator_data replace_data]``(iterator position, const CompatibleData & x); | |
193 | ||
194 | template< class KeyModifier > | |
195 | bool ``[link reference_unordered_set_of_modify_key_iterator_modifier modify_key]``(iterator position, KeyModifier mod); | |
196 | ||
197 | template< class DataModifier > | |
198 | bool ``[link reference_unordered_set_of_modify_data_iterator_modifier modify_data]``(iterator position, DataModifier mod); | |
199 | ||
200 | // } | |
201 | ||
202 | ||
203 | void clear(); | |
204 | ||
205 | // observers | |
206 | ||
207 | key_from_value key_extractor() const; | |
208 | hasher hash_function() const; | |
209 | key_equal key_eq() const; | |
210 | ||
211 | // lookup | |
212 | ||
213 | template< class CompatibleKey > | |
214 | iterator ``[link reference_unordered_set_of_find_key find]``(const CompatibleKey & x); | |
215 | ||
216 | template< class CompatibleKey > | |
217 | const_iterator ``[link reference_unordered_set_of_find_key find]``(const CompatibleKey & x) const; | |
218 | ||
219 | template< class CompatibleKey > | |
220 | size_type ``[link reference_unordered_set_of_count_key count]``(const CompatibleKey & x) const; | |
221 | ||
222 | template< class CompatibleKey > | |
223 | std::pair<iterator,iterator> | |
224 | ``[link reference_unordered_set_of_equal_range_key equal_range]``(const CompatibleKey & x); | |
225 | ||
226 | template< class CompatibleKey > | |
227 | std::pair<const_iterator,const_iterator> | |
228 | ``[link reference_unordered_set_of_equal_range_key equal_range]``(const CompatibleKey & x) const; | |
229 | ||
230 | // bucket interface | |
231 | ||
232 | size_type bucket_count() const; | |
233 | size_type max_bucket_count() const; | |
234 | size_type bucket_size(size_type n) const; | |
235 | size_type bucket(const key_type & k) const; | |
236 | ||
237 | local_iterator begin(size_type n); | |
238 | const_local_iterator begin(size_type n) const; | |
239 | local_iterator end(size_type n); | |
240 | const_local_iterator end(size_type n) const; | |
241 | ||
242 | // hash policy | |
243 | ||
244 | float load_factor() const; | |
245 | float max_load_factor() const; | |
246 | void max_load_factor(float z); | |
247 | void ``[link reference_unordered_set_of_rehash_size rehash]``(size_type n); | |
248 | ||
249 | // Only in maps views | |
250 | // { | |
251 | ||
252 | typedef ``['-unspecified-]`` mapped_type; | |
253 | ||
254 | // Only in for `unordered_set_of` collection type | |
255 | // { | |
256 | ||
257 | template<class CompatibleKey> | |
258 | const mapped_type & ``[link reference_unordered_set_of_at_key_const at]``(const CompatibleKey & k) const; | |
259 | ||
260 | // Only if the other collection type is mutable | |
261 | // { | |
262 | ||
263 | template<class CompatibleKey> | |
264 | mapped_type & ``[link reference_unordered_set_of_operator_bracket_key operator\[\]]``(const CompatibleKey & k); | |
265 | ||
266 | template<class CompatibleKey> | |
267 | mapped_type & ``[link reference_unordered_set_of_at_key at]``(const CompatibleKey & k); | |
268 | ||
269 | // } | |
270 | ||
271 | // Only if info_hook is used | |
272 | // { | |
273 | ||
274 | template< class CompatibleKey > | |
275 | info_type & ``[link reference_unordered_set_of_info_at_key info_at]``(const CompatibleKey & k); | |
276 | ||
277 | template< class CompatibleKey > | |
278 | const info_type & ``[link reference_unordered_set_of_info_at_key info_at]``(const CompatibleKey & k) const; | |
279 | ||
280 | // } | |
281 | ||
282 | // } | |
283 | ||
284 | }; | |
285 | ||
286 | } // namespace views | |
287 | } // namespace bimap | |
288 | } // namespace boost | |
289 | ||
290 | ||
291 | ||
292 | In the case of a `bimap< unordered_{multi}set_of<Left>, ... >` | |
293 | ||
294 | In the set view: | |
295 | ||
296 | typedef signature-compatible with relation< Left, ... > key_type; | |
297 | typedef signature-compatible with relation< const Left, ... > value_type; | |
298 | ||
299 | In the left map view: | |
300 | ||
301 | typedef Left key_type; | |
302 | typedef ... mapped_type; | |
303 | ||
304 | typedef signature-compatible with std::pair< const Left, ... > value_type; | |
305 | ||
306 | In the right map view: | |
307 | ||
308 | typedef ... key_type; | |
309 | typedef Left mapped_type; | |
310 | ||
311 | typedef signature-compatible with std::pair< ... ,const Left > value_type; | |
312 | ||
313 | ||
314 | ||
315 | [#unordered_set_of_complexity_signature] | |
316 | ||
317 | [section Complexity signature] | |
318 | ||
319 | Here and in the descriptions of operations of `unordered_[multi]set_of` views, | |
320 | we adopt the scheme outlined in the | |
321 | [link complexity_signature_explanation complexity signature section]. | |
322 | The complexity signature of `unordered_[multi]set_of` view is: | |
323 | ||
324 | * copying: `c(n) = n * log(n)`, | |
325 | * insertion: average case `i(n) = 1` (constant), worst case `i(n) = n`, | |
326 | * hinted insertion: average case `h(n) = 1` (constant), worst case `h(n) = n`, | |
327 | * deletion: average case `d(n) = 1` (constant), worst case `d(n) = n`, | |
328 | * replacement: | |
329 | * if the new element key is equivalent to the original, `r(n) = 1` (constant), | |
330 | * otherwise, average case `r(n) = 1` (constant), worst case `r(n) = n`, | |
331 | * modifying: average case `m(n) = 1` (constant), worst case `m(n) = n`. | |
332 | ||
333 | [endsect] | |
334 | ||
335 | ||
336 | [section Instantiation types] | |
337 | ||
338 | `unordered_[multi]set_of` views are instantiated internally to `bimap` | |
339 | specified by means of the collection type specifiers and the `bimap` itself. | |
340 | Instantiations are dependent on the following types: | |
341 | ||
342 | * `Value` from `bimap`, | |
343 | * `Allocator` from `bimap`, | |
344 | * `Hash` from the collection type specifier, | |
345 | * `Pred` from the collection type specifier. | |
346 | ||
347 | `Hash` is a __SGI_UNARY_FUNCTION__ taking a single argument of type | |
348 | `key_type` and returning a value of type `std::size_t` in the range | |
349 | `[0, std::numeric_limits<std::size_t>::max())`. | |
350 | Pred is a __SGI_BINARY_PREDICATE__ inducing an equivalence relation on elements of | |
351 | `key_type`. It is required that the `Hash` object return the same value for | |
352 | keys equivalent under `Pred`. | |
353 | ||
354 | [endsect] | |
355 | ||
356 | [section Nested types] | |
357 | ||
358 | iterator | |
359 | const_iterator | |
360 | local_iterator | |
361 | const_local_iterator | |
362 | ||
363 | [: These types are models of __SGI_FORWARD_ITERATOR__. | |
364 | ] | |
365 | ||
366 | ||
367 | [endsect] | |
368 | ||
369 | [section Constructors, copy and assignment] | |
370 | ||
371 | As explained in the concepts section, | |
372 | views do not have public constructors or destructors. Assignment, on the other | |
373 | hand, is provided. | |
374 | Upon construction, `max_load_factor()` is 1.0. | |
375 | ||
376 | this_type & operator=(const this_type & x); | |
377 | ||
378 | * [*Effects: ] `a = b`; | |
379 | where a and b are the `bimap` objects to which `*this` | |
380 | and x belong, respectively. | |
381 | * [*Returns: ] `*this.` | |
382 | ||
383 | ||
384 | ||
385 | [endsect] | |
386 | ||
387 | [section Modifiers] | |
388 | ||
389 | [#reference_unordered_set_of_insert_value] | |
390 | ||
391 | std::pair<iterator,bool> insert(const value_type & x); | |
392 | ||
393 | * [*Effects:] Inserts `x` into the `bimap` to which the view belongs if | |
394 | * the view is non-unique OR no other element with equivalent key exists, | |
395 | * AND insertion is allowed by all other views of the `bimap`. | |
396 | * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only if | |
397 | insertion took place. On successful insertion, `p.first` points to the element | |
398 | inserted; otherwise, `p.first` points to an element that caused the insertion to | |
399 | be banned. Note that more than one element can be causing insertion not to be | |
400 | allowed. | |
401 | * [link unordered_set_of_complexity_signature | |
402 | [*Complexity:]] O(I(n)). | |
403 | * [*Exception safety:] Strong. | |
404 | ||
405 | [#reference_unordered_set_of_insert_iterator_value] | |
406 | ||
407 | iterator insert(iterator position, const value_type & x); | |
408 | ||
409 | * [*Requires: ] `position` is a valid iterator of the view. | |
410 | * [*Effects: ] `position` is used as a hint to improve the efficiency of the operation. | |
411 | Inserts `x` into the `bimap` to which the view belongs if | |
412 | * the view is non-unique OR no other element with equivalent key exists, | |
413 | * AND insertion is allowed by all other views of the `bimap`. | |
414 | * [*Returns:] On successful insertion, an iterator to the newly inserted element. | |
415 | Otherwise, an iterator to an element that caused the insertion to be banned. | |
416 | Note that more than one element can be causing insertion not to be allowed. | |
417 | * [link unordered_set_of_complexity_signature [*Complexity:]] O(H(n)). | |
418 | * [*Exception safety:] Strong. | |
419 | ||
420 | [#reference_unordered_set_of_insert_iterator_iterator] | |
421 | ||
422 | template< class InputIterator> | |
423 | void insert(InputIterator first, InputIterator last); | |
424 | ||
425 | * [*Requires: ] `InputIterator` is a model of __SGI_INPUT_ITERATOR__ over elements of type | |
426 | `value_type`. `first` and `last` are not iterators into any views of the | |
427 | `bimap` to which this view belongs. `last` is reachable from first. | |
428 | * [*Effects: ] | |
429 | `iterator hint = end();` | |
430 | `while(first != last) hint = insert(hint, *first++);` | |
431 | * [link unordered_set_of_complexity_signature | |
432 | [*Complexity:]] O(m*H(n+m)), where m is the number of elements in `[first, last)`. | |
433 | * [*Exception safety:] Basic. | |
434 | ||
435 | [#reference_unordered_set_of_erase_iterator] | |
436 | ||
437 | iterator erase(iterator position); | |
438 | ||
439 | * [*Requires: ] `position` is a valid dereferenceable `iterator` of the view. | |
440 | * [*Effects:] Deletes the element pointed to by `position`. | |
441 | * [*Returns:] An `iterator` pointing to the element immediately following the one | |
442 | that was deleted, or `end()` if no such element exists. | |
443 | * [link unordered_set_of_complexity_signature | |
444 | [*Complexity:]] O(D(n)). | |
445 | * [*Exception safety:] nothrow. | |
446 | ||
447 | ||
448 | [#reference_unordered_set_of_erase_key] | |
449 | ||
450 | template< class CompatibleKey > | |
451 | size_type erase(const CompatibleKey & x); | |
452 | ||
453 | * [*Effects:] Deletes the elements with key equivalent to `x`. | |
454 | * [*Returns:] Number of elements deleted. | |
455 | * [link unordered_set_of_complexity_signature | |
456 | [*Complexity:]] Average case, O(1 + m*D(n)), worst case O(n + m*D(n)), | |
457 | where m is the number of elements deleted. | |
458 | * [*Exception safety:] Basic. | |
459 | ||
460 | ||
461 | [#reference_unordered_set_of_erase_iterator_iterator] | |
462 | ||
463 | iterator erase(iterator first, iterator last); | |
464 | ||
465 | * [*Requires: ] `[first,last)` is a valid range of the view. | |
466 | * [*Effects:] Deletes the elements in `[first,last)`. | |
467 | * [*Returns: ] `last`. | |
468 | * [link unordered_set_of_complexity_signature | |
469 | [*Complexity:]] O(m*D(n)), where m is the number of elements in `[first,last)`. | |
470 | * [*Exception safety:] nothrow. | |
471 | ||
472 | ||
473 | [#reference_unordered_set_of_replace_iterator_value] | |
474 | ||
475 | bool replace(iterator position, const value_type & x); | |
476 | ||
477 | * [*Requires: ] `position` is a valid dereferenceable `iterator` of the view. | |
478 | * [*Effects:] Assigns the value `x` to the element pointed to by `position` into | |
479 | the `bimap` to which the view belongs if, for the value `x` | |
480 | * the view is non-unique OR no other element with equivalent key exists | |
481 | (except possibly `*position`), | |
482 | * AND replacing is allowed by all other views of the `bimap`. | |
483 | * [*Postconditions:] Validity of position is preserved in all cases. | |
484 | * [*Returns: ] `true` if the replacement took place, `false` otherwise. | |
485 | * [link unordered_set_of_complexity_signature | |
486 | [*Complexity:]] O(R(n)). | |
487 | * [*Exception safety:] Strong. If an exception is thrown by some user-provided | |
488 | operation the `bimap` to which the view belongs remains in its original state. | |
489 | ||
490 | ||
491 | [#reference_unordered_set_of_replace_key_iterator_key] | |
492 | ||
493 | template< class CompatibleKey > | |
494 | bool replace_key(iterator position, const CompatibleKey & x); | |
495 | ||
496 | * [*Requires: ] `position` is a valid dereferenceable iterator of the set view. | |
497 | `CompatibleKey` can be assigned to `key_type`. | |
498 | * [*Effects:] Assigns the value `x` to `e.first`, where `e` is the element pointed | |
499 | to by `position` into the `bimap` to which the set view belongs if, | |
500 | * the map view is non-unique OR no other element with equivalent key exists | |
501 | (except possibly `*position`), | |
502 | * AND replacing is allowed by all other views of the `bimap`. | |
503 | * [*Postconditions:] Validity of position is preserved in all cases. | |
504 | * [*Returns: ] `true` if the replacement took place, `false` otherwise. | |
505 | * [link unordered_set_of_complexity_signature | |
506 | [*Complexity:]] O(R(n)). | |
507 | * [*Exception safety:] Strong. If an exception is thrown by some user-provided | |
508 | operation, the `bimap` to which the set view belongs remains in | |
509 | its original state. | |
510 | ||
511 | ||
512 | [#reference_unordered_set_of_replace_data_iterator_data] | |
513 | ||
514 | template< class CompatibleData > | |
515 | bool replace_data(iterator position, const CompatibleData & x); | |
516 | ||
517 | * [*Requires: ] `position` is a valid dereferenceable iterator of the set view. | |
518 | `CompatibleKey` can be assigned to `mapped_type`. | |
519 | * [*Effects:] Assigns the value `x` to `e.second`, where `e` is the element pointed | |
520 | to by `position` into the `bimap` to which the set view belongs if, | |
521 | * the map view is non-unique OR no other element with equivalent key exists | |
522 | (except possibly `*position`), | |
523 | * AND replacing is allowed by all other views of the `bimap`. | |
524 | * [*Postconditions:] Validity of position is preserved in all cases. | |
525 | * [*Returns: ] `true` if the replacement took place, `false` otherwise. | |
526 | * [link unordered_set_of_complexity_signature | |
527 | [*Complexity:]] O(R(n)). | |
528 | * [*Exception safety:] Strong. If an exception is thrown by some user-provided | |
529 | operation, the `bimap` to which the set view belongs remains in | |
530 | its original state. | |
531 | ||
532 | ||
533 | [#reference_unordered_set_of_modify_key_iterator_modifier] | |
534 | ||
535 | template< class KeyModifier > | |
536 | bool modify_key(iterator position, KeyModifier mod); | |
537 | ||
538 | * [*Requires: ] `KeyModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of | |
539 | type: `key_type&`; `position` is a valid dereferenceable iterator of the view. | |
540 | * [*Effects:] Calls `mod(e.first)` where e is the element pointed to by position and | |
541 | rearranges `*position` into all the views of the `bimap`. | |
542 | If the rearrangement fails, the element is erased. | |
543 | Rearrangement is successful if | |
544 | * the map view is non-unique OR no other element with equivalent key exists, | |
545 | * AND rearrangement is allowed by all other views of the `bimap`. | |
546 | * [*Postconditions:] Validity of `position` is preserved if the operation succeeds. | |
547 | * [*Returns: ] `true` if the operation succeeded, `false` otherwise. | |
548 | * [link unordered_set_of_complexity_signature | |
549 | [*Complexity:]] O(M(n)). | |
550 | * [*Exception safety:] Basic. If an exception is thrown by some user-provided | |
551 | operation (except possibly mod), then the element pointed to by position is erased. | |
552 | * [*Note:] Only provided for map views. | |
553 | ||
554 | ||
555 | [#reference_unordered_set_of_modify_data_iterator_modifier] | |
556 | ||
557 | template< class DataModifier > | |
558 | bool modify_data(iterator position, DataModifier mod); | |
559 | ||
560 | * [*Requires: ] `DataModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of | |
561 | type: `mapped_type&`; `position` is a valid dereferenceable iterator of the view. | |
562 | * [*Effects:] Calls `mod(e.second)` where e is the element pointed to by position and | |
563 | rearranges `*position` into all the views of the `bimap`. | |
564 | If the rearrangement fails, the element is erased. | |
565 | Rearrangement is successful if | |
566 | * the oppositte map view is non-unique OR no other element with equivalent key in that | |
567 | view exists, | |
568 | * AND rearrangement is allowed by all other views of the `bimap`. | |
569 | * [*Postconditions:] Validity of `position` is preserved if the operation succeeds. | |
570 | * [*Returns: ] `true` if the operation succeeded, `false` otherwise. | |
571 | * [link unordered_set_of_complexity_signature | |
572 | [*Complexity:]] O(M(n)). | |
573 | * [*Exception safety:] Basic. If an exception is thrown by some user-provided | |
574 | operation (except possibly mod), then the element pointed to by position is erased. | |
575 | * [*Note:] Only provided for map views. | |
576 | ||
577 | [/ | |
578 | [#reference_unordered_set_of_modify_iterator_modifier] | |
579 | ||
580 | template< class Modifier> | |
581 | bool modify(iterator position, Modifier mod); | |
582 | ||
583 | * [*Requires: ] `Modifier` is a model of __SGI_BINARY_FUNCTION__ accepting arguments of | |
584 | type: `first_type&` and `second_type&` for ['Map View] or `left_type&` and `right_type&` | |
585 | for ['Set View]; `position` is a valid dereferenceable iterator of the view. | |
586 | * [*Effects:] Calls `mod(e.first,e.second)` for ['Map View:] or calls `mod(e.left,e.right)` | |
587 | for ['Set View] where `e` is the element pointed to by `position` and | |
588 | rearranges `*position` into all the views of the `bimap`. | |
589 | If the rearrangement fails, the element is erased. | |
590 | Rearrangement is successful if | |
591 | * the view is non-unique OR no other element with equivalent key exists, | |
592 | * AND rearrangement is allowed by all other views of the `bimap`. | |
593 | * [*Postconditions:] Validity of position is preserved if the operation succeeds. | |
594 | * [*Returns: ] `true` if the operation succeeded, `false` otherwise. | |
595 | * [link unordered_set_of_complexity_signature | |
596 | [*Complexity:]] O(M(n)). | |
597 | * [*Exception safety:] Basic. If an exception is thrown by some user-provided | |
598 | operation (except possibly `mod`), then the element pointed to by `position` is erased. | |
599 | /] | |
600 | ||
601 | [endsect] | |
602 | ||
603 | [section Lookup] | |
604 | ||
605 | `unordered_[multi]set_of` views provide the full lookup functionality required by unordered | |
606 | associative containers, namely `find`, `count`, and `equal_range`. Additionally, | |
607 | these member functions are templatized to allow for non-standard arguments, | |
608 | so extending the types of search operations allowed. The kind of arguments | |
609 | permissible when invoking the lookup member functions is defined by the | |
610 | following concept. | |
611 | ||
612 | [/ | |
613 | Consider a pair `(Hash, Pred)` where `Hash` is a hash functor over values of type | |
614 | `Key` and `Pred` is a __SGI_BINARY_PREDICATE__ inducing an equivalence relation on `Key`, | |
615 | with the additional constraint that equivalent keys have the same hash value. | |
616 | A triplet of types `(CompatibleKey, CompatibleHash, CompatiblePred)` is said to | |
617 | be a ['compatible extension] of `(Hash, Pred)` if | |
618 | ||
619 | * `CompatibleHash` is a hash functor on values of type `CompatibleKey`, | |
620 | * `CompatiblePred` is a __SGI_BINARY_PREDICATE__ over `(Key, CompatibleKey)`, | |
621 | * `CompatiblePred` is a __SGI_BINARY_PREDICATE__ over `(CompatibleKey, Key)`, | |
622 | * if `c_eq(ck,k1)` then `c_eq(k1,ck)`, | |
623 | * if `c_eq(ck,k1)` and `eq(k1,k2)` then `c_eq(ck,k2)`, | |
624 | * if `c_eq(ck,k1)` and `c_eq(ck,k2)` then `eq(k1,k2)`, | |
625 | * if `c_eq(ck,k1)` then `c_hash(ck)==hash(k1)`, | |
626 | ||
627 | for every `c_hash` of type `CompatibleHash`, `c_eq` of type `CompatiblePred`, hash of | |
628 | type `Hash`, `eq` of type `Pred`, `ck` of type `CompatibleKey` and `k1`, `k2` of type `Key`. | |
629 | ] | |
630 | ||
631 | A type `CompatibleKey` is said to be a ['compatible key] of `(Hash, Pred)` | |
632 | if `(CompatibleKey, Hash, Pred)` is a compatible extension of `(Hash, Pred)`. This | |
633 | implies that `Hash` and `Pred` accept arguments of type `CompatibleKey`, which usually | |
634 | means they have several overloads of their corresponding `operator()` member | |
635 | functions. | |
636 | ||
637 | [/ | |
638 | In the context of a compatible extension or a compatible key, the expression | |
639 | "equivalent key" takes on its obvious interpretation. | |
640 | ] | |
641 | ||
642 | [#reference_unordered_set_of_find_key] | |
643 | ||
644 | template< class CompatibleKey > | |
645 | iterator find(const CompatibleKey & x); | |
646 | ||
647 | template< class CompatibleKey > | |
648 | const_iterator find(const CompatibleKey & x) const; | |
649 | ||
650 | * [*Effects:] Returns a pointer to an element whose key is equivalent to `x`, | |
651 | or `end()` if such an element does not exist. | |
652 | * [*Complexity:] Average case O(1) (constant), worst case O(n). | |
653 | ||
654 | ||
655 | [#reference_unordered_set_of_count_key] | |
656 | ||
657 | template< class CompatibleKey > | |
658 | size_type count(const CompatibleKey & x) const; | |
659 | ||
660 | * [*Effects:] Returns the number of elements with key equivalent to `x`. | |
661 | * [*Complexity:] Average case O(count(x)), worst case O(n). | |
662 | ||
663 | ||
664 | [#reference_unordered_set_of_equal_range_key] | |
665 | ||
666 | template< class CompatibleKey > | |
667 | std::pair<iterator,iterator> | |
668 | equal_range(const CompatibleKey & x); | |
669 | ||
670 | template< class CompatibleKey > | |
671 | std::pair<const_iterator,const_iterator> | |
672 | equal_range(const CompatibleKey & x) const; | |
673 | ||
674 | * [*Effects:] Returns a range containing all elements with keys equivalent | |
675 | to `x` (and only those). | |
676 | * [*Complexity:] Average case O(count(x)), worst case O(n). | |
677 | ||
678 | ||
679 | ||
680 | [endsect] | |
681 | ||
682 | [section at(), info_at() and operator\[\] - set_of only] | |
683 | ||
684 | ||
685 | [#reference_unordered_set_of_at_key_const] | |
686 | ||
687 | template< class CompatibleKey > | |
688 | const mapped_type & at(const CompatibleKey & k) const; | |
689 | ||
690 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
691 | * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or | |
692 | throws `std::out_of_range` if such key does not exist. | |
693 | * [*Complexity:] Average case O(1) (constant), worst case O(n). | |
694 | * [*Note:] Only provided when `unordered_set_of` is used. | |
695 | ||
696 | The symmetry of bimap imposes some constraints on `operator[]` and the | |
697 | non constant version of at() that are not found in `std::maps`. | |
698 | Tey are only provided if the other collection type is mutable | |
699 | (`list_of`, `vector_of` and `unconstrained_set_of`). | |
700 | ||
701 | ||
702 | [#reference_unordered_set_of_operator_bracket_key] | |
703 | ||
704 | template< class CompatibleKey > | |
705 | mapped_type & operator[](const CompatibleKey & k); | |
706 | ||
707 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
708 | * [*Effects: ] `return insert(value_type(k,mapped_type()))->second;` | |
709 | * [*Complexity:] If the insertion is performed O(I(n)), else: Average case | |
710 | O(1) (constant), worst case O(n). | |
711 | * [*Note:] Only provided when `unordered_set_of` is used and the other collection | |
712 | type is mutable. | |
713 | ||
714 | ||
715 | [#reference_unordered_set_of_at_key] | |
716 | ||
717 | template< class CompatibleKey > | |
718 | mapped_type & at(const CompatibleKey & k); | |
719 | ||
720 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
721 | * [*Effects: ] Returns the `mapped_type` reference that is associated with `k`, or | |
722 | throws `std::out_of_range` if such key does not exist. | |
723 | * [*Complexity:] Average case O(1) (constant), worst case O(n). | |
724 | * [*Note:] Only provided when `unordered_set_of` is used and the other collection | |
725 | type is mutable. | |
726 | ||
727 | [/ | |
728 | ||
729 | The symmetry of bimap imposes some constraints to the `operator[]` that are not | |
730 | found in `std::maps`. | |
731 | If other views are unique, `bimap::duplicate_value` is thrown whenever an assignment is | |
732 | attempted to a value that is already a key in this views. | |
733 | As for bimap::value_not_found, this exception is thrown while trying to access | |
734 | a non-existent key: this behavior differs from that of std::map, which automatically | |
735 | assigns a default value to non-existent keys referred to by `operator[]`. | |
736 | ||
737 | const mapped_type & operator[](const typename key_type & k) const; | |
738 | ||
739 | * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or | |
740 | throws `bimap::value_not_found` if such an element does not exist. | |
741 | * [*Complexity:] O(log(n)). | |
742 | ||
743 | ||
744 | ``['-unspecified mapped_type proxy-]`` operator[](const typename key_type & k); | |
745 | ||
746 | * [*Effects:] Returns a proxy to a `mapped_type` associated with `k` and the | |
747 | bimap. The proxy behaves as a reference to the `mapped_type` object. If this | |
748 | proxy is read and `k` was not in the bimap, the bimap::value_not_found is | |
749 | thrown. If it is written then `bimap::duplicate_value` is thrown if the | |
750 | assignment is not allowed by one of the other views of the `bimap`. | |
751 | * [link unordered_set_of_complexity_signature | |
752 | [*Complexity:]] If the assignment operator of the proxy is not used, then | |
753 | the order is O(log(n)). If it is used, the order is O(I(n)) if `k` was not | |
754 | in the bimap and O(R(n)) if it existed in the bimap. | |
755 | ||
756 | ] | |
757 | ||
758 | [#reference_unordered_set_of_info_at_key] | |
759 | ||
760 | template< class CompatibleKey > | |
761 | info_type & info_at(const CompatibleKey & k); | |
762 | ||
763 | template< class CompatibleKey > | |
764 | const info_type & info_at(const CompatibleKey & k) const; | |
765 | ||
766 | * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`. | |
767 | * [*Effects:] Returns the `info_type` reference that is associated with `k`, or | |
768 | throws `std::out_of_range` if such key does not exist. | |
769 | * [*Complexity:] Average case O(1) (constant), worst case O(n). | |
770 | * [*Note:] Only provided when `unordered_set_of` and `info_hook` are used | |
771 | ||
772 | ||
773 | [endsect] | |
774 | ||
775 | [section Hash policy] | |
776 | ||
777 | ||
778 | [#reference_unordered_set_of_rehash_size] | |
779 | ||
780 | void rehash(size_type n); | |
781 | ||
782 | * [*Effects:] Increases if necessary the number of internal buckets so that | |
783 | `size()/bucket_count()` does not exceed the maximum load factor, and | |
784 | `bucket_count()>=n`. | |
785 | * [*Postconditions:] Validity of iterators and references to the elements | |
786 | contained is preserved. | |
787 | * [*Complexity:] Average case O(size()), worst case O(size(n)2). | |
788 | * [*Exception safety:] Strong. | |
789 | ||
790 | ||
791 | [endsect] | |
792 | ||
793 | [section Serialization] | |
794 | ||
795 | Views cannot be serialized on their own, but only as part of the | |
796 | `bimap` into which they are embedded. In describing the | |
797 | additional preconditions and guarantees associated to `unordered_[multi]set_of` views | |
798 | with respect to serialization of their embedding containers, we use | |
799 | the concepts defined in the `bimap` serialization section. | |
800 | ||
801 | [blurb [*Operation:] saving of a `bimap` b to an output archive | |
802 | (XML archive) ar.] | |
803 | ||
804 | * [*Requires:] No additional requirements to those imposed by the container. | |
805 | ||
806 | ||
807 | [blurb [*Operation:] loading of a `bimap` b' from an input | |
808 | archive (XML archive) ar.] | |
809 | ||
810 | * [*Requires:] Additionally to the general requirements, `key_eq()` must | |
811 | be serialization-compatible with `m.get<i>().key_eq()`, where i is the | |
812 | position of the `unordered_[multi]set_of` view in the container. | |
813 | * [*Postconditions:] On successful loading, the range `[begin(), end())` | |
814 | contains restored copies of every element in | |
815 | `[m.get<i>().begin(), m.get<i>().end())`, though not necessarily in | |
816 | the same order. | |
817 | ||
818 | ||
819 | [blurb [*Operation:] saving of an `iterator` or `const_iterator` `it` to an output | |
820 | archive (XML archive) ar.] | |
821 | ||
822 | * [*Requires: ] `it` is a valid `iterator` of the view. The associated | |
823 | `bimap` has been previously saved. | |
824 | ||
825 | ||
826 | [blurb [*Operation:] loading of an iterator or `const_iterator it`' from an | |
827 | input archive (XML archive) ar.] | |
828 | ||
829 | * [*Postconditions:] On successful loading, if `it` was dereferenceable then | |
830 | `*it`' is the restored copy of `*it`, otherwise `it`'` == end()`. | |
831 | * [*Note:] It is allowed that `it` be a `const_iterator` and the restored | |
832 | `it`' an `iterator`, or viceversa. | |
833 | ||
834 | ||
835 | [blurb [*Operation:] saving of a local_iterator or const_local_iterator it | |
836 | to an output archive (XML archive) ar.] | |
837 | ||
838 | * [*Requires: ] `it` is a valid local iterator of the view. The associated | |
839 | `bimap` has been previously saved. | |
840 | ||
841 | ||
842 | [blurb [*Operation:] loading of a `local_iterator` or `const_local_iterator` | |
843 | `it`' from an input archive (XML archive) ar.] | |
844 | ||
845 | * [*Postconditions:] On successful loading, if `it` was dereferenceable then | |
846 | `*it`' is the restored copy of `*it`; if `it` was `m.get<i>().end(n)` for some n, | |
847 | then `it`'` == m`'`.get<i>().end(n)` (where `b` is the original `bimap`, | |
848 | `b`' its restored copy and `i` is the ordinal of the index.) | |
849 | * [*Note:] It is allowed that `it` be a `const_local_iterator` and the restored | |
850 | `it`' a `local_iterator`, or viceversa. | |
851 | ||
852 | ||
853 | [endsect] | |
854 | [endsect] | |
855 | ||
856 | [endsect] |