set_of.qbk

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

        template< class CompatibleKey, class CompatibleCompare >
        const_iterator lower_bound(const CompatibleKey & x,
                                   const CompatibleCompare & comp) const;

        template< class CompatibleKey, class CompatibleCompare >
        iterator upper_bound(const CompatibleKey & x,
                             const CompatibleCompare & comp);

        template< class CompatibleKey, class CompatibleCompare >
        const_iterator upper_bound(const CompatibleKey & x,
                                   const CompatibleCompare & comp) const;

        template< class CompatibleKey, class CompatibleCompare >
        std::pair<iterator,iterator> equal_range(
            const CompatibleKey & x, const CompatibleCompare & comp);

        template< class CompatibleKey, class CompatibleCompare >
        std::pair<const_iterator,const_iterator> equal_range(
            const CompatibleKey & x, const CompatibleCompare & comp) const;

]


In the case of a `bimap< {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;


[#set_of_complexity_signature]

[section Complexity signature]

Here and in the descriptions of operations of this view, we adopt the
scheme outlined in the [link complexity_signature_explanation complexity signature section].
The complexity signature of \[multi\]set_of view is:

* copying: `c(n) = n * log(n)`,
* insertion: `i(n) = log(n)`,
* hinted insertion: `h(n) = 1` (constant) if the hint element precedes the point of
insertion, `h(n) = log(n)` otherwise,
* deletion: `d(n) = 1` (amortized constant),
* replacement: `r(n) = 1` (constant) if the element position does not change,
`r(n) = log(n)` otherwise,
* modifying: `m(n) = 1` (constant) if the element position does not change,
`m(n) = log(n)` otherwise.

[endsect]

[section Instantiation types]

Set views are instantiated internally to a `bimap`.
Instantiations are dependent on the following types:

* `Value` from the set specifier,
* `Allocator` from `bimap`,
* `Compare` from the set specifier.

`Compare` is a __SGI_STRICT_WEAK_ORDERING__ on elements of `Value`.

[endsect]

[section Constructors, copy and assignment]

Set views do not have public constructors or destructors.
Assignment, on the other hand, is provided.

    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_set_of_insert_value]

    std::pair<iterator,bool> insert(const value_type & x);

* [*Effects:] Inserts `x` into the `bimap` to which the set view belongs if
    * the set view is non-unique OR no other element with equivalent key exists,
    * AND insertion is allowed by the other set specifications 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 set_of_complexity_signature
[*Complexity:]] O(I(n)).
* [*Exception safety:] Strong.


[#reference_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 set 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 set_of_complexity_signature
[*Complexity:]] O(H(n)).
* [*Exception safety:] Strong.


[#reference_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` or a type convertible to value_type. `first` and `last` are not
iterators into any view of the `bimap` to which this index
belongs. `last` is reachable from `first`.
* [*Effects: ]
`iterator hint = end()`;
`while( first != last ) hint = insert( hint, *first++ );`
* [link set_of_complexity_signature
[*Complexity:]] O(m*H(n+m)), where m is the number of elements in
`[first, last)`.
* [*Exception safety:] Basic.


[#reference_set_of_erase_iterator]

    iterator erase(iterator position);

* [*Requires: ] `position` is a valid dereferenceable iterator if the set 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 set_of_complexity_signature
[*Complexity:]] O(D(n)).
* [*Exception safety:] nothrow.


[#reference_set_of_erase_key]

    template< class CompatibleKey >
    size_type erase(const CompatibleKey & x);

* [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
* [*Effects:] Deletes the elements with key equivalent to `x`.
* [*Returns:] Number of elements deleted.
* [link set_of_complexity_signature
[*Complexity:]] O(log(n) + m*D(n)), where m is the number of elements deleted.
* [*Exception safety:] Basic.


[#reference_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 set_of_complexity_signature
[*Complexity:]] O(log(n) + m*D(n)), where m is the number of elements
in `[first,last)`.
* [*Exception safety:] nothrow.


[#reference_set_of_replace_iterator_value]

    bool replace(iterator position, const value_type& x);

* [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
* [*Effects:] Assigns the value `x` to the element pointed to by `position` into
the `bimap` to which the set view belongs if, for the value `x`
    * the set 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 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_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 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_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 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_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 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_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 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_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&`
['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 set_of_complexity_signature
[*Complexity:]] O(M(n)).
* [*Exception safety:] Basic. If an exception is thrown by some user-provided