5 Copyright (c) 2006-2007 Matias Capeletto
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)
13 [/ QuickBook Document version 1.4 ]
15 [section unordered_set_of Reference]
17 [section Header "boost/bimap/unordered_set_of.hpp" synopsis]
26 class HashFunctor = hash< KeyType >,
27 class EqualKey = std::equal_to< KeyType >
29 struct unordered_set_of;
34 class HashFunctor = hash< _relation >,
35 class EqualKey = std::equal_to< _relation >
37 struct unordered_set_of_relation;
46 [section Header "boost/bimap/unordered_multiset_of.hpp" synopsis]
55 class HashFunctor = hash< KeyType >,
56 class EqualKey = std::equal_to< KeyType >
58 struct unordered_multiset_of;
63 class HashFunctor = hash< _relation >,
64 class EqualKey = std::equal_to< _relation >
66 struct unordered_multiset_of_relation;
75 [section Collection type specifiers unordered_set_of and unordered_multiset_of]
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
84 [section unordered_\[multi\]set_of Views]
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`.
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.
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.
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.
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.
118 template< ``['-implementation defined parameter list-]`` >
119 class ``['-implementation defined view name-]``
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;
143 typedef ``['-unspecified-]`` info_type;
145 // construct/destroy/copy:
147 this_type & operator=(const this_type & x);
149 allocator_type get_allocator() const;
154 size_type size() const;
155 size_type max_size() const;
160 const_iterator begin() const;
162 const_iterator end() const;
166 std::pair< iterator, bool > ``[link reference_unordered_set_of_insert_value insert]``(const value_type & x);
168 iterator ``[link reference_unordered_set_of_insert_iterator_value insert]``(iterator position, const value_type & x);
170 template< class InputIterator >
171 void ``[link reference_unordered_set_of_insert_iterator_iterator insert]``(InputIterator first, InputIterator last);
173 iterator ``[link reference_unordered_set_of_erase_iterator erase]``(iterator position);
175 template< class CompatibleKey >
176 size_type ``[link reference_unordered_set_of_erase_key erase]``(const CompatibleKey & x);
178 iterator ``[link reference_unordered_set_of_erase_iterator_iterator erase]``(iterator first, iterator last);
180 bool ``[link reference_unordered_set_of_replace_iterator_value replace]``(iterator position, const value_type & x);
185 typedef ``['-unspecified-]`` mapped_type;
186 typedef ``['-unspecified-]`` data_type; // Equal to mapped_type
188 template< class CompatibleKey >
189 bool ``[link reference_unordered_set_of_replace_key_iterator_key replace_key]``(iterator position, const CompatibleKey & x);
191 template< class CompatibleData >
192 bool ``[link reference_unordered_set_of_replace_data_iterator_data replace_data]``(iterator position, const CompatibleData & x);
194 template< class KeyModifier >
195 bool ``[link reference_unordered_set_of_modify_key_iterator_modifier modify_key]``(iterator position, KeyModifier mod);
197 template< class DataModifier >
198 bool ``[link reference_unordered_set_of_modify_data_iterator_modifier modify_data]``(iterator position, DataModifier mod);
207 key_from_value key_extractor() const;
208 hasher hash_function() const;
209 key_equal key_eq() const;
213 template< class CompatibleKey >
214 iterator ``[link reference_unordered_set_of_find_key find]``(const CompatibleKey & x);
216 template< class CompatibleKey >
217 const_iterator ``[link reference_unordered_set_of_find_key find]``(const CompatibleKey & x) const;
219 template< class CompatibleKey >
220 size_type ``[link reference_unordered_set_of_count_key count]``(const CompatibleKey & x) const;
222 template< class CompatibleKey >
223 std::pair<iterator,iterator>
224 ``[link reference_unordered_set_of_equal_range_key equal_range]``(const CompatibleKey & x);
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;
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;
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;
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);
249 // Only in maps views
252 typedef ``['-unspecified-]`` mapped_type;
254 // Only in for `unordered_set_of` collection type
257 template<class CompatibleKey>
258 const mapped_type & ``[link reference_unordered_set_of_at_key_const at]``(const CompatibleKey & k) const;
260 // Only if the other collection type is mutable
263 template<class CompatibleKey>
264 mapped_type & ``[link reference_unordered_set_of_operator_bracket_key operator\[\]]``(const CompatibleKey & k);
266 template<class CompatibleKey>
267 mapped_type & ``[link reference_unordered_set_of_at_key at]``(const CompatibleKey & k);
271 // Only if info_hook is used
274 template< class CompatibleKey >
275 info_type & ``[link reference_unordered_set_of_info_at_key info_at]``(const CompatibleKey & k);
277 template< class CompatibleKey >
278 const info_type & ``[link reference_unordered_set_of_info_at_key info_at]``(const CompatibleKey & k) const;
292 In the case of a `bimap< unordered_{multi}set_of<Left>, ... >`
296 typedef signature-compatible with relation< Left, ... > key_type;
297 typedef signature-compatible with relation< const Left, ... > value_type;
299 In the left map view:
301 typedef Left key_type;
302 typedef ... mapped_type;
304 typedef signature-compatible with std::pair< const Left, ... > value_type;
306 In the right map view:
308 typedef ... key_type;
309 typedef Left mapped_type;
311 typedef signature-compatible with std::pair< ... ,const Left > value_type;
315 [#unordered_set_of_complexity_signature]
317 [section Complexity signature]
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:
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`,
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`.
336 [section Instantiation types]
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:
342 * `Value` from `bimap`,
343 * `Allocator` from `bimap`,
344 * `Hash` from the collection type specifier,
345 * `Pred` from the collection type specifier.
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`.
356 [section Nested types]
363 [: These types are models of __SGI_FORWARD_ITERATOR__.
369 [section Constructors, copy and assignment]
371 As explained in the concepts section,
372 views do not have public constructors or destructors. Assignment, on the other
374 Upon construction, `max_load_factor()` is 1.0.
376 this_type & operator=(const this_type & x);
378 * [*Effects: ] `a = b`;
379 where a and b are the `bimap` objects to which `*this`
380 and x belong, respectively.
381 * [*Returns: ] `*this.`
389 [#reference_unordered_set_of_insert_value]
391 std::pair<iterator,bool> insert(const value_type & x);
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
401 * [link unordered_set_of_complexity_signature
402 [*Complexity:]] O(I(n)).
403 * [*Exception safety:] Strong.
405 [#reference_unordered_set_of_insert_iterator_value]
407 iterator insert(iterator position, const value_type & x);
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.
420 [#reference_unordered_set_of_insert_iterator_iterator]
422 template< class InputIterator>
423 void insert(InputIterator first, InputIterator last);
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.
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.
435 [#reference_unordered_set_of_erase_iterator]
437 iterator erase(iterator position);
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.
448 [#reference_unordered_set_of_erase_key]
450 template< class CompatibleKey >
451 size_type erase(const CompatibleKey & x);
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.
461 [#reference_unordered_set_of_erase_iterator_iterator]
463 iterator erase(iterator first, iterator last);
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.
473 [#reference_unordered_set_of_replace_iterator_value]
475 bool replace(iterator position, const value_type & x);
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.
491 [#reference_unordered_set_of_replace_key_iterator_key]
493 template< class CompatibleKey >
494 bool replace_key(iterator position, const CompatibleKey & x);
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
512 [#reference_unordered_set_of_replace_data_iterator_data]
514 template< class CompatibleData >
515 bool replace_data(iterator position, const CompatibleData & x);
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
533 [#reference_unordered_set_of_modify_key_iterator_modifier]
535 template< class KeyModifier >
536 bool modify_key(iterator position, KeyModifier mod);
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.
555 [#reference_unordered_set_of_modify_data_iterator_modifier]
557 template< class DataModifier >
558 bool modify_data(iterator position, DataModifier mod);
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
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.
578 [#reference_unordered_set_of_modify_iterator_modifier]
580 template< class Modifier>
581 bool modify(iterator position, Modifier mod);
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.
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
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
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)`,
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`.
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
638 In the context of a compatible extension or a compatible key, the expression
639 "equivalent key" takes on its obvious interpretation.
642 [#reference_unordered_set_of_find_key]
644 template< class CompatibleKey >
645 iterator find(const CompatibleKey & x);
647 template< class CompatibleKey >
648 const_iterator find(const CompatibleKey & x) const;
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).
655 [#reference_unordered_set_of_count_key]
657 template< class CompatibleKey >
658 size_type count(const CompatibleKey & x) const;
660 * [*Effects:] Returns the number of elements with key equivalent to `x`.
661 * [*Complexity:] Average case O(count(x)), worst case O(n).
664 [#reference_unordered_set_of_equal_range_key]
666 template< class CompatibleKey >
667 std::pair<iterator,iterator>
668 equal_range(const CompatibleKey & x);
670 template< class CompatibleKey >
671 std::pair<const_iterator,const_iterator>
672 equal_range(const CompatibleKey & x) const;
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).
682 [section at(), info_at() and operator\[\] - set_of only]
685 [#reference_unordered_set_of_at_key_const]
687 template< class CompatibleKey >
688 const mapped_type & at(const CompatibleKey & k) const;
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.
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`).
702 [#reference_unordered_set_of_operator_bracket_key]
704 template< class CompatibleKey >
705 mapped_type & operator[](const CompatibleKey & k);
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
715 [#reference_unordered_set_of_at_key]
717 template< class CompatibleKey >
718 mapped_type & at(const CompatibleKey & k);
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
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[]`.
737 const mapped_type & operator[](const typename key_type & k) const;
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)).
744 ``['-unspecified mapped_type proxy-]`` operator[](const typename key_type & k);
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.
758 [#reference_unordered_set_of_info_at_key]
760 template< class CompatibleKey >
761 info_type & info_at(const CompatibleKey & k);
763 template< class CompatibleKey >
764 const info_type & info_at(const CompatibleKey & k) const;
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
775 [section Hash policy]
778 [#reference_unordered_set_of_rehash_size]
780 void rehash(size_type n);
782 * [*Effects:] Increases if necessary the number of internal buckets so that
783 `size()/bucket_count()` does not exceed the maximum load factor, and
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.
793 [section Serialization]
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.
801 [blurb [*Operation:] saving of a `bimap` b to an output archive
804 * [*Requires:] No additional requirements to those imposed by the container.
807 [blurb [*Operation:] loading of a `bimap` b' from an input
808 archive (XML archive) ar.]
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
819 [blurb [*Operation:] saving of an `iterator` or `const_iterator` `it` to an output
820 archive (XML archive) ar.]
822 * [*Requires: ] `it` is a valid `iterator` of the view. The associated
823 `bimap` has been previously saved.
826 [blurb [*Operation:] loading of an iterator or `const_iterator it`' from an
827 input archive (XML archive) ar.]
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.
835 [blurb [*Operation:] saving of a local_iterator or const_local_iterator it
836 to an output archive (XML archive) ar.]
838 * [*Requires: ] `it` is a valid local iterator of the view. The associated
839 `bimap` has been previously saved.
842 [blurb [*Operation:] loading of a `local_iterator` or `const_local_iterator`
843 `it`' from an input archive (XML archive) ar.]
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.