unordered_set_of.qbk

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

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  ...   data_type;

    typedef signature-compatible with std::pair< const Left, ... > value_type;

In the right map view:

    typedef  ...  key_type;
    typedef  Left data_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 `data_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: `data_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