unordered_set_of.qbk

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

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 data_type & at(const CompatibleKey & k) const;

* [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
* [*Effects:] Returns the `data_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 >
    data_type & operator[](const CompatibleKey & k);

* [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
* [*Effects: ] `return insert(value_type(k,data_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 >
    data_type & at(const CompatibleKey & k);

* [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
* [*Effects: ] Returns the `data_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 data_type & operator[](const typename key_type & k) const;

* [*Effects:] Returns the `data_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 data_type proxy-]`` operator[](const typename key_type & k);

* [*Effects:] Returns a proxy to a `data_type` associated with `k` and the
bimap. The proxy behaves as a reference to the `data_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]