123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856 |
- [/license
- Boost.Bimap
- Copyright (c) 2006-2007 Matias Capeletto
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- ]
- [/ QuickBook Document version 1.4 ]
- [section unordered_set_of Reference]
- [section Header "boost/bimap/unordered_set_of.hpp" synopsis]
- namespace boost {
- namespace bimaps {
- template
- <
- class KeyType,
- class HashFunctor = hash< KeyType >,
- class EqualKey = std::equal_to< KeyType >
- >
- struct unordered_set_of;
- template
- <
- class HashFunctor = hash< _relation >,
- class EqualKey = std::equal_to< _relation >
- >
- struct unordered_set_of_relation;
- } // namespace bimap
- } // namespace boost
- [endsect]
- [section Header "boost/bimap/unordered_multiset_of.hpp" synopsis]
- namespace boost {
- namespace bimaps {
- template
- <
- class KeyType,
- class HashFunctor = hash< KeyType >,
- class EqualKey = std::equal_to< KeyType >
- >
- struct unordered_multiset_of;
- template
- <
- class HashFunctor = hash< _relation >,
- class EqualKey = std::equal_to< _relation >
- >
- struct unordered_multiset_of_relation;
- } // namespace bimap
- } // namespace boost
- [endsect]
- [section Collection type specifiers unordered_set_of and unordered_multiset_of]
- These collection types specifiers allow for set views without and
- with allowance of duplicate elements, respectively. The syntax of
- `set_of` and `multiset_of` coincide, thus we describe them
- in a grouped manner.
- [endsect]
- [section unordered_\[multi\]set_of Views]
- An unordered_\[multi\]set_of set view is a tr1::unordered\[multi\]set signature compatible
- interface to the underlying heap of elements contained in a `bimap`.
- The interface and semantics of `unordered_[multi]set_of` views are
- modeled according to the proposal for unordered associative containers given
- in the __CPP_STANDARD_LIBRARY_TECHNICAL_REPORT__, also known as TR1.
- An `unordered_[multi]set_of` view is particularized according to a given
- `Hash` function object which returns hash values for the keys and a
- binary predicate `Pred` acting as an equivalence relation on values of Key.
- There are two variants: unordered_set_of, which do not allow duplicate elements
- (with respect to its associated comparison predicate) and unordered_multiset_of,
- which accept those duplicates. The interface of these two variants is the same
- to a great extent, so they are documented together with their differences
- explicitly noted when they exist.
- If you look the bimap by a side, you will use a map view and if you looked
- it as a whole you will be using a set view.
- Except where noted, `unordered_[multi]set_of` views (both unique and non-unique) are models
- of [^Unordered Associative Container].
- Validity of iterators and references to elements is preserved in all cases.
- Occasionally, the exception safety guarantees provided are actually stronger
- than required by the extension draft. We only provide descriptions of those
- types and operations that are either not present in the concepts modeled or
- do not exactly conform to the requirements for unordered associative containers.
- namespace boost {
- namespace bimap {
- namespace views {
- template< ``['-implementation defined parameter list-]`` >
- class ``['-implementation defined view name-]``
- {
- public:
- // types
- typedef ``['-unspecified-]`` key_type;
- typedef ``['-unspecified-]`` value_type;
- typedef ``['-unspecified-]`` key_compare;
- typedef ``['-unspecified-]`` value_compare;
- typedef ``['-unspecified-]`` hasher;
- typedef ``['-unspecified-]`` key_equal;
- typedef ``['-unspecified-]`` allocator_type;
- typedef ``['-unspecified-]`` reference;
- typedef ``['-unspecified-]`` const_reference;
- typedef ``['-unspecified-]`` iterator;
- typedef ``['-unspecified-]`` const_iterator;
- typedef ``['-unspecified-]`` size_type;
- typedef ``['-unspecified-]`` difference_type;
- typedef ``['-unspecified-]`` pointer;
- typedef ``['-unspecified-]`` const_pointer;
- typedef ``['-unspecified-]`` local_iterator;
- typedef ``['-unspecified-]`` const_local_iterator;
- typedef ``['-unspecified-]`` info_type;
- // construct/destroy/copy:
- this_type & operator=(const this_type & x);
- allocator_type get_allocator() const;
- // size and capacity
- bool empty() const;
- size_type size() const;
- size_type max_size() const;
- // iterators
- iterator begin();
- const_iterator begin() const;
- iterator end();
- const_iterator end() const;
- // modifiers
- std::pair< iterator, bool > ``[link reference_unordered_set_of_insert_value insert]``(const value_type & x);
- iterator ``[link reference_unordered_set_of_insert_iterator_value insert]``(iterator position, const value_type & x);
- template< class InputIterator >
- void ``[link reference_unordered_set_of_insert_iterator_iterator insert]``(InputIterator first, InputIterator last);
- iterator ``[link reference_unordered_set_of_erase_iterator erase]``(iterator position);
- template< class CompatibleKey >
- size_type ``[link reference_unordered_set_of_erase_key erase]``(const CompatibleKey & x);
- iterator ``[link reference_unordered_set_of_erase_iterator_iterator erase]``(iterator first, iterator last);
- bool ``[link reference_unordered_set_of_replace_iterator_value replace]``(iterator position, const value_type & x);
- // Only in map views
- // {
- typedef ``['-unspecified-]`` mapped_type;
- typedef ``['-unspecified-]`` data_type; // Equal to mapped_type
- template< class CompatibleKey >
- bool ``[link reference_unordered_set_of_replace_key_iterator_key replace_key]``(iterator position, const CompatibleKey & x);
- template< class CompatibleData >
- bool ``[link reference_unordered_set_of_replace_data_iterator_data replace_data]``(iterator position, const CompatibleData & x);
- template< class KeyModifier >
- bool ``[link reference_unordered_set_of_modify_key_iterator_modifier modify_key]``(iterator position, KeyModifier mod);
- template< class DataModifier >
- bool ``[link reference_unordered_set_of_modify_data_iterator_modifier modify_data]``(iterator position, DataModifier mod);
- // }
- void clear();
- // observers
- key_from_value key_extractor() const;
- hasher hash_function() const;
- key_equal key_eq() const;
- // lookup
- template< class CompatibleKey >
- iterator ``[link reference_unordered_set_of_find_key find]``(const CompatibleKey & x);
- template< class CompatibleKey >
- const_iterator ``[link reference_unordered_set_of_find_key find]``(const CompatibleKey & x) const;
- template< class CompatibleKey >
- size_type ``[link reference_unordered_set_of_count_key count]``(const CompatibleKey & x) const;
- template< class CompatibleKey >
- std::pair<iterator,iterator>
- ``[link reference_unordered_set_of_equal_range_key equal_range]``(const CompatibleKey & x);
- template< class CompatibleKey >
- std::pair<const_iterator,const_iterator>
- ``[link reference_unordered_set_of_equal_range_key equal_range]``(const CompatibleKey & x) const;
- // bucket interface
- size_type bucket_count() const;
- size_type max_bucket_count() const;
- size_type bucket_size(size_type n) const;
- size_type bucket(const key_type & k) const;
- local_iterator begin(size_type n);
- const_local_iterator begin(size_type n) const;
- local_iterator end(size_type n);
- const_local_iterator end(size_type n) const;
- // hash policy
- float load_factor() const;
- float max_load_factor() const;
- void max_load_factor(float z);
- void ``[link reference_unordered_set_of_rehash_size rehash]``(size_type n);
- // Only in maps views
- // {
- typedef ``['-unspecified-]`` mapped_type;
- // Only in for `unordered_set_of` collection type
- // {
- template<class CompatibleKey>
- const mapped_type & ``[link reference_unordered_set_of_at_key_const at]``(const CompatibleKey & k) const;
- // Only if the other collection type is mutable
- // {
- template<class CompatibleKey>
- mapped_type & ``[link reference_unordered_set_of_operator_bracket_key operator\[\]]``(const CompatibleKey & k);
- template<class CompatibleKey>
- mapped_type & ``[link reference_unordered_set_of_at_key at]``(const CompatibleKey & k);
- // }
- // Only if info_hook is used
- // {
- template< class CompatibleKey >
- info_type & ``[link reference_unordered_set_of_info_at_key info_at]``(const CompatibleKey & k);
- template< class CompatibleKey >
- const info_type & ``[link reference_unordered_set_of_info_at_key info_at]``(const CompatibleKey & k) const;
- // }
- // }
- };
- } // namespace views
- } // namespace bimap
- } // namespace boost
- In the case of a `bimap< unordered_{multi}set_of<Left>, ... >`
- In the set view:
- typedef signature-compatible with relation< Left, ... > key_type;
- typedef signature-compatible with relation< const Left, ... > value_type;
- In the left map view:
- typedef Left key_type;
- typedef ... mapped_type;
- typedef signature-compatible with std::pair< const Left, ... > value_type;
- In the right map view:
- typedef ... key_type;
- typedef Left mapped_type;
- typedef signature-compatible with std::pair< ... ,const Left > value_type;
- [#unordered_set_of_complexity_signature]
- [section Complexity signature]
- Here and in the descriptions of operations of `unordered_[multi]set_of` views,
- we adopt the scheme outlined in the
- [link complexity_signature_explanation complexity signature section].
- The complexity signature of `unordered_[multi]set_of` view is:
- * copying: `c(n) = n * log(n)`,
- * insertion: average case `i(n) = 1` (constant), worst case `i(n) = n`,
- * hinted insertion: average case `h(n) = 1` (constant), worst case `h(n) = n`,
- * deletion: average case `d(n) = 1` (constant), worst case `d(n) = n`,
- * replacement:
- * if the new element key is equivalent to the original, `r(n) = 1` (constant),
- * otherwise, average case `r(n) = 1` (constant), worst case `r(n) = n`,
- * modifying: average case `m(n) = 1` (constant), worst case `m(n) = n`.
- [endsect]
- [section Instantiation types]
- `unordered_[multi]set_of` views are instantiated internally to `bimap`
- specified by means of the collection type specifiers and the `bimap` itself.
- Instantiations are dependent on the following types:
- * `Value` from `bimap`,
- * `Allocator` from `bimap`,
- * `Hash` from the collection type specifier,
- * `Pred` from the collection type specifier.
- `Hash` is a __SGI_UNARY_FUNCTION__ taking a single argument of type
- `key_type` and returning a value of type `std::size_t` in the range
- `[0, std::numeric_limits<std::size_t>::max())`.
- Pred is a __SGI_BINARY_PREDICATE__ inducing an equivalence relation on elements of
- `key_type`. It is required that the `Hash` object return the same value for
- keys equivalent under `Pred`.
- [endsect]
- [section Nested types]
- iterator
- const_iterator
- local_iterator
- const_local_iterator
- [: These types are models of __SGI_FORWARD_ITERATOR__.
- ]
- [endsect]
- [section Constructors, copy and assignment]
- As explained in the concepts section,
- views do not have public constructors or destructors. Assignment, on the other
- hand, is provided.
- Upon construction, `max_load_factor()` is 1.0.
- this_type & operator=(const this_type & x);
- * [*Effects: ] `a = b`;
- where a and b are the `bimap` objects to which `*this`
- and x belong, respectively.
- * [*Returns: ] `*this.`
- [endsect]
- [section Modifiers]
- [#reference_unordered_set_of_insert_value]
- std::pair<iterator,bool> insert(const value_type & x);
- * [*Effects:] Inserts `x` into the `bimap` to which the view belongs if
- * the view is non-unique OR no other element with equivalent key exists,
- * AND insertion is allowed by all other views of the `bimap`.
- * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only if
- insertion took place. On successful insertion, `p.first` points to the element
- inserted; otherwise, `p.first` points to an element that caused the insertion to
- be banned. Note that more than one element can be causing insertion not to be
- allowed.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(I(n)).
- * [*Exception safety:] Strong.
- [#reference_unordered_set_of_insert_iterator_value]
- iterator insert(iterator position, const value_type & x);
- * [*Requires: ] `position` is a valid iterator of the view.
- * [*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
- * the view is non-unique OR no other element with equivalent key exists,
- * AND insertion is allowed by all other views of the `bimap`.
- * [*Returns:] On successful insertion, an iterator to the newly inserted element.
- Otherwise, an iterator to an element that caused the insertion to be banned.
- Note that more than one element can be causing insertion not to be allowed.
- * [link unordered_set_of_complexity_signature [*Complexity:]] O(H(n)).
- * [*Exception safety:] Strong.
- [#reference_unordered_set_of_insert_iterator_iterator]
- template< class InputIterator>
- void insert(InputIterator first, InputIterator last);
- * [*Requires: ] `InputIterator` is a model of __SGI_INPUT_ITERATOR__ over elements of type
- `value_type`. `first` and `last` are not iterators into any views of the
- `bimap` to which this view belongs. `last` is reachable from first.
- * [*Effects: ]
- `iterator hint = end();`
- `while(first != last) hint = insert(hint, *first++);`
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(m*H(n+m)), where m is the number of elements in `[first, last)`.
- * [*Exception safety:] Basic.
- [#reference_unordered_set_of_erase_iterator]
- iterator erase(iterator position);
- * [*Requires: ] `position` is a valid dereferenceable `iterator` of the view.
- * [*Effects:] Deletes the element pointed to by `position`.
- * [*Returns:] An `iterator` pointing to the element immediately following the one
- that was deleted, or `end()` if no such element exists.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(D(n)).
- * [*Exception safety:] nothrow.
- [#reference_unordered_set_of_erase_key]
- template< class CompatibleKey >
- size_type erase(const CompatibleKey & x);
- * [*Effects:] Deletes the elements with key equivalent to `x`.
- * [*Returns:] Number of elements deleted.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] Average case, O(1 + m*D(n)), worst case O(n + m*D(n)),
- where m is the number of elements deleted.
- * [*Exception safety:] Basic.
- [#reference_unordered_set_of_erase_iterator_iterator]
- iterator erase(iterator first, iterator last);
- * [*Requires: ] `[first,last)` is a valid range of the view.
- * [*Effects:] Deletes the elements in `[first,last)`.
- * [*Returns: ] `last`.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(m*D(n)), where m is the number of elements in `[first,last)`.
- * [*Exception safety:] nothrow.
- [#reference_unordered_set_of_replace_iterator_value]
- bool replace(iterator position, const value_type & x);
- * [*Requires: ] `position` is a valid dereferenceable `iterator` of the view.
- * [*Effects:] Assigns the value `x` to the element pointed to by `position` into
- the `bimap` to which the view belongs if, for the value `x`
- * the view is non-unique OR no other element with equivalent key exists
- (except possibly `*position`),
- * AND replacing is allowed by all other views of the `bimap`.
- * [*Postconditions:] Validity of position is preserved in all cases.
- * [*Returns: ] `true` if the replacement took place, `false` otherwise.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(R(n)).
- * [*Exception safety:] Strong. If an exception is thrown by some user-provided
- operation the `bimap` to which the view belongs remains in its original state.
- [#reference_unordered_set_of_replace_key_iterator_key]
- template< class CompatibleKey >
- bool replace_key(iterator position, const CompatibleKey & x);
- * [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
- `CompatibleKey` can be assigned to `key_type`.
- * [*Effects:] Assigns the value `x` to `e.first`, where `e` is the element pointed
- to by `position` into the `bimap` to which the set view belongs if,
- * the map view is non-unique OR no other element with equivalent key exists
- (except possibly `*position`),
- * AND replacing is allowed by all other views of the `bimap`.
- * [*Postconditions:] Validity of position is preserved in all cases.
- * [*Returns: ] `true` if the replacement took place, `false` otherwise.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(R(n)).
- * [*Exception safety:] Strong. If an exception is thrown by some user-provided
- operation, the `bimap` to which the set view belongs remains in
- its original state.
- [#reference_unordered_set_of_replace_data_iterator_data]
- template< class CompatibleData >
- bool replace_data(iterator position, const CompatibleData & x);
- * [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
- `CompatibleKey` can be assigned to `mapped_type`.
- * [*Effects:] Assigns the value `x` to `e.second`, where `e` is the element pointed
- to by `position` into the `bimap` to which the set view belongs if,
- * the map view is non-unique OR no other element with equivalent key exists
- (except possibly `*position`),
- * AND replacing is allowed by all other views of the `bimap`.
- * [*Postconditions:] Validity of position is preserved in all cases.
- * [*Returns: ] `true` if the replacement took place, `false` otherwise.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(R(n)).
- * [*Exception safety:] Strong. If an exception is thrown by some user-provided
- operation, the `bimap` to which the set view belongs remains in
- its original state.
- [#reference_unordered_set_of_modify_key_iterator_modifier]
- template< class KeyModifier >
- bool modify_key(iterator position, KeyModifier mod);
- * [*Requires: ] `KeyModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of
- type: `key_type&`; `position` is a valid dereferenceable iterator of the view.
- * [*Effects:] Calls `mod(e.first)` where e is the element pointed to by position and
- rearranges `*position` into all the views of the `bimap`.
- If the rearrangement fails, the element is erased.
- Rearrangement is successful if
- * the map view is non-unique OR no other element with equivalent key exists,
- * AND rearrangement is allowed by all other views of the `bimap`.
- * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
- * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(M(n)).
- * [*Exception safety:] Basic. If an exception is thrown by some user-provided
- operation (except possibly mod), then the element pointed to by position is erased.
- * [*Note:] Only provided for map views.
- [#reference_unordered_set_of_modify_data_iterator_modifier]
- template< class DataModifier >
- bool modify_data(iterator position, DataModifier mod);
- * [*Requires: ] `DataModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of
- type: `mapped_type&`; `position` is a valid dereferenceable iterator of the view.
- * [*Effects:] Calls `mod(e.second)` where e is the element pointed to by position and
- rearranges `*position` into all the views of the `bimap`.
- If the rearrangement fails, the element is erased.
- Rearrangement is successful if
- * the oppositte map view is non-unique OR no other element with equivalent key in that
- view exists,
- * AND rearrangement is allowed by all other views of the `bimap`.
- * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
- * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(M(n)).
- * [*Exception safety:] Basic. If an exception is thrown by some user-provided
- operation (except possibly mod), then the element pointed to by position is erased.
- * [*Note:] Only provided for map views.
- [/
- [#reference_unordered_set_of_modify_iterator_modifier]
- template< class Modifier>
- bool modify(iterator position, Modifier mod);
- * [*Requires: ] `Modifier` is a model of __SGI_BINARY_FUNCTION__ accepting arguments of
- type: `first_type&` and `second_type&` for ['Map View] or `left_type&` and `right_type&`
- for ['Set View]; `position` is a valid dereferenceable iterator of the view.
- * [*Effects:] Calls `mod(e.first,e.second)` for ['Map View:] or calls `mod(e.left,e.right)`
- for ['Set View] where `e` is the element pointed to by `position` and
- rearranges `*position` into all the views of the `bimap`.
- If the rearrangement fails, the element is erased.
- Rearrangement is successful if
- * the view is non-unique OR no other element with equivalent key exists,
- * AND rearrangement is allowed by all other views of the `bimap`.
- * [*Postconditions:] Validity of position is preserved if the operation succeeds.
- * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] O(M(n)).
- * [*Exception safety:] Basic. If an exception is thrown by some user-provided
- operation (except possibly `mod`), then the element pointed to by `position` is erased.
- /]
- [endsect]
- [section Lookup]
- `unordered_[multi]set_of` views provide the full lookup functionality required by unordered
- associative containers, namely `find`, `count`, and `equal_range`. Additionally,
- these member functions are templatized to allow for non-standard arguments,
- so extending the types of search operations allowed. The kind of arguments
- permissible when invoking the lookup member functions is defined by the
- following concept.
- [/
- Consider a pair `(Hash, Pred)` where `Hash` is a hash functor over values of type
- `Key` and `Pred` is a __SGI_BINARY_PREDICATE__ inducing an equivalence relation on `Key`,
- with the additional constraint that equivalent keys have the same hash value.
- A triplet of types `(CompatibleKey, CompatibleHash, CompatiblePred)` is said to
- be a ['compatible extension] of `(Hash, Pred)` if
- * `CompatibleHash` is a hash functor on values of type `CompatibleKey`,
- * `CompatiblePred` is a __SGI_BINARY_PREDICATE__ over `(Key, CompatibleKey)`,
- * `CompatiblePred` is a __SGI_BINARY_PREDICATE__ over `(CompatibleKey, Key)`,
- * if `c_eq(ck,k1)` then `c_eq(k1,ck)`,
- * if `c_eq(ck,k1)` and `eq(k1,k2)` then `c_eq(ck,k2)`,
- * if `c_eq(ck,k1)` and `c_eq(ck,k2)` then `eq(k1,k2)`,
- * if `c_eq(ck,k1)` then `c_hash(ck)==hash(k1)`,
- for every `c_hash` of type `CompatibleHash`, `c_eq` of type `CompatiblePred`, hash of
- type `Hash`, `eq` of type `Pred`, `ck` of type `CompatibleKey` and `k1`, `k2` of type `Key`.
- ]
- A type `CompatibleKey` is said to be a ['compatible key] of `(Hash, Pred)`
- if `(CompatibleKey, Hash, Pred)` is a compatible extension of `(Hash, Pred)`. This
- implies that `Hash` and `Pred` accept arguments of type `CompatibleKey`, which usually
- means they have several overloads of their corresponding `operator()` member
- functions.
- [/
- In the context of a compatible extension or a compatible key, the expression
- "equivalent key" takes on its obvious interpretation.
- ]
- [#reference_unordered_set_of_find_key]
- template< class CompatibleKey >
- iterator find(const CompatibleKey & x);
- template< class CompatibleKey >
- const_iterator find(const CompatibleKey & x) const;
- * [*Effects:] Returns a pointer to an element whose key is equivalent to `x`,
- or `end()` if such an element does not exist.
- * [*Complexity:] Average case O(1) (constant), worst case O(n).
- [#reference_unordered_set_of_count_key]
- template< class CompatibleKey >
- size_type count(const CompatibleKey & x) const;
- * [*Effects:] Returns the number of elements with key equivalent to `x`.
- * [*Complexity:] Average case O(count(x)), worst case O(n).
- [#reference_unordered_set_of_equal_range_key]
- template< class CompatibleKey >
- std::pair<iterator,iterator>
- equal_range(const CompatibleKey & x);
- template< class CompatibleKey >
- std::pair<const_iterator,const_iterator>
- equal_range(const CompatibleKey & x) const;
- * [*Effects:] Returns a range containing all elements with keys equivalent
- to `x` (and only those).
- * [*Complexity:] Average case O(count(x)), worst case O(n).
- [endsect]
- [section at(), info_at() and operator\[\] - set_of only]
- [#reference_unordered_set_of_at_key_const]
- template< class CompatibleKey >
- const mapped_type & at(const CompatibleKey & k) const;
- * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
- * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or
- throws `std::out_of_range` if such key does not exist.
- * [*Complexity:] Average case O(1) (constant), worst case O(n).
- * [*Note:] Only provided when `unordered_set_of` is used.
- The symmetry of bimap imposes some constraints on `operator[]` and the
- non constant version of at() that are not found in `std::maps`.
- Tey are only provided if the other collection type is mutable
- (`list_of`, `vector_of` and `unconstrained_set_of`).
- [#reference_unordered_set_of_operator_bracket_key]
- template< class CompatibleKey >
- mapped_type & operator[](const CompatibleKey & k);
- * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
- * [*Effects: ] `return insert(value_type(k,mapped_type()))->second;`
- * [*Complexity:] If the insertion is performed O(I(n)), else: Average case
- O(1) (constant), worst case O(n).
- * [*Note:] Only provided when `unordered_set_of` is used and the other collection
- type is mutable.
- [#reference_unordered_set_of_at_key]
- template< class CompatibleKey >
- mapped_type & at(const CompatibleKey & k);
- * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
- * [*Effects: ] Returns the `mapped_type` reference that is associated with `k`, or
- throws `std::out_of_range` if such key does not exist.
- * [*Complexity:] Average case O(1) (constant), worst case O(n).
- * [*Note:] Only provided when `unordered_set_of` is used and the other collection
- type is mutable.
- [/
- The symmetry of bimap imposes some constraints to the `operator[]` that are not
- found in `std::maps`.
- If other views are unique, `bimap::duplicate_value` is thrown whenever an assignment is
- attempted to a value that is already a key in this views.
- As for bimap::value_not_found, this exception is thrown while trying to access
- a non-existent key: this behavior differs from that of std::map, which automatically
- assigns a default value to non-existent keys referred to by `operator[]`.
- const mapped_type & operator[](const typename key_type & k) const;
- * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or
- throws `bimap::value_not_found` if such an element does not exist.
- * [*Complexity:] O(log(n)).
- ``['-unspecified mapped_type proxy-]`` operator[](const typename key_type & k);
- * [*Effects:] Returns a proxy to a `mapped_type` associated with `k` and the
- bimap. The proxy behaves as a reference to the `mapped_type` object. If this
- proxy is read and `k` was not in the bimap, the bimap::value_not_found is
- thrown. If it is written then `bimap::duplicate_value` is thrown if the
- assignment is not allowed by one of the other views of the `bimap`.
- * [link unordered_set_of_complexity_signature
- [*Complexity:]] If the assignment operator of the proxy is not used, then
- the order is O(log(n)). If it is used, the order is O(I(n)) if `k` was not
- in the bimap and O(R(n)) if it existed in the bimap.
- ]
- [#reference_unordered_set_of_info_at_key]
- template< class CompatibleKey >
- info_type & info_at(const CompatibleKey & k);
- template< class CompatibleKey >
- const info_type & info_at(const CompatibleKey & k) const;
- * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
- * [*Effects:] Returns the `info_type` reference that is associated with `k`, or
- throws `std::out_of_range` if such key does not exist.
- * [*Complexity:] Average case O(1) (constant), worst case O(n).
- * [*Note:] Only provided when `unordered_set_of` and `info_hook` are used
- [endsect]
- [section Hash policy]
- [#reference_unordered_set_of_rehash_size]
- void rehash(size_type n);
- * [*Effects:] Increases if necessary the number of internal buckets so that
- `size()/bucket_count()` does not exceed the maximum load factor, and
- `bucket_count()>=n`.
- * [*Postconditions:] Validity of iterators and references to the elements
- contained is preserved.
- * [*Complexity:] Average case O(size()), worst case O(size(n)2).
- * [*Exception safety:] Strong.
- [endsect]
- [section Serialization]
- Views cannot be serialized on their own, but only as part of the
- `bimap` into which they are embedded. In describing the
- additional preconditions and guarantees associated to `unordered_[multi]set_of` views
- with respect to serialization of their embedding containers, we use
- the concepts defined in the `bimap` serialization section.
- [blurb [*Operation:] saving of a `bimap` b to an output archive
- (XML archive) ar.]
- * [*Requires:] No additional requirements to those imposed by the container.
- [blurb [*Operation:] loading of a `bimap` b' from an input
- archive (XML archive) ar.]
- * [*Requires:] Additionally to the general requirements, `key_eq()` must
- be serialization-compatible with `m.get<i>().key_eq()`, where i is the
- position of the `unordered_[multi]set_of` view in the container.
- * [*Postconditions:] On successful loading, the range `[begin(), end())`
- contains restored copies of every element in
- `[m.get<i>().begin(), m.get<i>().end())`, though not necessarily in
- the same order.
- [blurb [*Operation:] saving of an `iterator` or `const_iterator` `it` to an output
- archive (XML archive) ar.]
- * [*Requires: ] `it` is a valid `iterator` of the view. The associated
- `bimap` has been previously saved.
- [blurb [*Operation:] loading of an iterator or `const_iterator it`' from an
- input archive (XML archive) ar.]
- * [*Postconditions:] On successful loading, if `it` was dereferenceable then
- `*it`' is the restored copy of `*it`, otherwise `it`'` == end()`.
- * [*Note:] It is allowed that `it` be a `const_iterator` and the restored
- `it`' an `iterator`, or viceversa.
- [blurb [*Operation:] saving of a local_iterator or const_local_iterator it
- to an output archive (XML archive) ar.]
- * [*Requires: ] `it` is a valid local iterator of the view. The associated
- `bimap` has been previously saved.
- [blurb [*Operation:] loading of a `local_iterator` or `const_local_iterator`
- `it`' from an input archive (XML archive) ar.]
- * [*Postconditions:] On successful loading, if `it` was dereferenceable then
- `*it`' is the restored copy of `*it`; if `it` was `m.get<i>().end(n)` for some n,
- then `it`'` == m`'`.get<i>().end(n)` (where `b` is the original `bimap`,
- `b`' its restored copy and `i` is the ordinal of the index.)
- * [*Note:] It is allowed that `it` be a `const_local_iterator` and the restored
- `it`' a `local_iterator`, or viceversa.
- [endsect]
- [endsect]
- [endsect]
|