list_of.qbk

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

* [*Returns:] An iterator pointing to the element immediately following the
one that was deleted, or `end()` if no such element exists.
* [link list_of_complexity_signature 
[*Complexity:]] O(D(n)).
* [*Exception safety:] nothrow.


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


[#reference_list_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 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 list_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_list_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 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 list_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_list_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 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 list_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_list_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.
It is successful if the 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 list_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_list_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.
It is successful if the 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 list_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_list_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] and `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`.
Rearrangement on `list_of` views does not change the position of the element
with respect to the view; rearrangement on other views may or might not suceed.
If the rearrangement fails, the element is erased.
* [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
* [*Returns: ] `true` if the operation succeeded, `false` otherwise.
* [link list_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 List operations]

`list_of` views provide the full set of list operations found in `std::list`;
the semantics of these member functions, however, differ from that of `std::list`
in some cases as insertions might not succeed due to banning by other views.
Similarly, the complexity of the operations may depend on the other views
belonging to the same `bimap`.


[#reference_list_of_splice_iterator_this]

    void splice(iterator position, this_type & x);

* [*Requires: ] `position` is a valid iterator of the view. `&x!=this`.
* [*Effects:] Inserts the contents of `x` before position, in the same order as
they were in `x`. Those elements successfully inserted are erased from `x`.
* [link list_of_complexity_signature 
[*Complexity:]] O(`x.size()`*I(n+`x.size()`) + `x.size()`*D(`x.size()`)).
* [*Exception safety:] Basic.


[#reference_list_of_splice_iterator_this_iterator]

    void splice(iterator position, this_type & x,iterator i);

* [*Requires: ] `position` is a valid iterator of the view. `i` is a valid
dereferenceable iterator `x`.
* [*Effects:] Inserts the element pointed to by `i` before position: if insertion
is successful, the element is erased from `x`. In the special case `&x==this`,
no copy or deletion is performed, and the operation is always successful. If
`position==i`, no operation is performed.
* [*Postconditions:] If `&x==this`, no iterator or reference is invalidated.
* [link list_of_complexity_signature 
[*Complexity:]] If `&x==this`, constant; otherwise O(I(n) + D(n)).
* [*Exception safety:] If `&x==this`, nothrow; otherwise, strong.


[#reference_list_of_splice_iterator_this_iterator_iterator]

    void splice(iterator position, this_type & x, iterator first, iterator last);

* [*Requires: ] `position` is a valid iterator of the view. `first` and `last` are
valid iterators of `x`. last is reachable from `first`. position is not in the
range `[first,last)`.
* [*Effects:] For each element in the range `[first,last)`, insertion is tried
before position; if the operation is successful, the element is erased from x.
In the special case `&x==this`, no copy or deletion is performed, and insertions
are always successful.
* [*Postconditions:] If `&x==this`, no iterator or reference is invalidated.
* [link list_of_complexity_signature 
[*Complexity:]] If `&x==this`, constant; otherwise O(m*I(n+m) + m*D(x.size()))
where m is the number of elements in `[first,last)`.
* [*Exception safety:] If `&x==this`, nothrow; otherwise, basic.


[#reference_list_of_remove_value]

    void remove(const value_type & value);

* [*Effects:] Erases all elements of the view which compare equal to `value`.
* [link list_of_complexity_signature 
[*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
* [*Exception safety:] Basic.


[#reference_list_of_remove_if_predicate]

    template< class Predicate >
    void remove_if(Predicate pred);

* [*Effects:] Erases all elements `x` of the view for which `pred(x)` holds.
* [link list_of_complexity_signature 
[*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
* [*Exception safety:] Basic.


[#reference_list_of_unique]

    void unique();

* [*Effects:] Eliminates all but the first element from every consecutive
group of equal elements referred to by the iterator `i` in the range
`[first+1,last)` for which `*i==*(i-1)`.
* [link list_of_complexity_signature 
[*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
* [*Exception safety:] Basic.


[#reference_list_of_unique_predicate]

    template< class BinaryPredicate >
    void unique(BinaryPredicate binary_pred);

* [*Effects:] Eliminates all but the first element from every consecutive
group of elements referred to by the iterator i in the range \[first+1,last)
for which `binary_pred(*i,*(i-1))` holds.
* [link list_of_complexity_signature 
[*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
* [*Exception safety:] Basic.


[#reference_list_of_merge_this]

    void merge(this_type & x);

* [*Requires: ] `std::less<value_type>` is a __SGI_STRICT_WEAK_ORDERING__ over `value_type`.
Both the view and `x` are sorted according to `std::less<value_type>`.
* [*Effects:] Attempts to insert every element of `x` into the corresponding
position of the view (according to the order). Elements successfully inserted
are erased from `x`. The resulting sequence is stable, i.e. equivalent elements
of either container preserve their relative position. In the special case
`&x==this`, no operation is performed.
* [*Postconditions:] Elements in the view and remaining elements in `x` are sorted.
Validity of iterators to the view and of non-erased elements of `x` references
is preserved.
* [link list_of_complexity_signature 
[*Complexity:]] If `&x==this`, constant; otherwise
O(n + `x.size()`*I(n+`x.size()`) + `x.size()`*D(`x.size()`)).
* [*Exception safety:] If `&x==this`, nothrow; otherwise, basic.


[#reference_list_of_merge_this_compare]

    template< class Compare >
    void merge(this_type & x, Compare comp);

* [*Requires:] Compare is a __SGI_STRICT_WEAK_ORDERING__ over `value_type`. Both the view
and `x` are sorted according to `comp`.
* [*Effects:] Attempts to insert every element of `x` into the corresponding position
of the view (according to `comp`). Elements successfully inserted are erased from `x`.
The resulting sequence is stable, i.e. equivalent elements of either container preserve
their relative position. In the special case `&x==this`, no operation is performed.
* [*Postconditions:] Elements in the view and remaining elements in `x` are sorted
according to `comp`. Validity of iterators to the view and of non-erased elements
of `x` references is preserved.
* [link list_of_complexity_signature 
[*Complexity:]] If `&x==this`, constant;
otherwise O(n + `x.size()`*I(n+`x.size()`) + `x.size()`*D(`x.size()`)).
* [*Exception safety:] If `&x==this`, nothrow; otherwise, basic.


[#reference_list_of_sort]

    void sort();

* [*Requires: ] `std::less<value_type>` is a __SGI_STRICT_WEAK_ORDERING__ over value_type.
* [*Effects:] Sorts the view according to `std::less<value_type>`. The sorting is stable,
i.e. equivalent elements preserve their relative position.
* [*Postconditions:] Validity of iterators and references is preserved.
* [*Complexity:] O(n*log(n)).
* [*Exception safety:] nothrow if `std::less<value_type>` does not throw; otherwise, basic.


[#reference_list_of_sort_compare]

    template< typename Compare >
    void sort(Compare comp);

* [*Requires:] Compare is a __SGI_STRICT_WEAK_ORDERING__ over value_type.
* [*Effects:] Sorts the view according to comp. The sorting is stable, i.e. equivalent
elements preserve their relative position.
* [*Postconditions:] Validity of iterators and references is preserved.
* [*Complexity:] O(n*log(n)).
* [*Exception safety:] nothrow if comp does not throw; otherwise, basic.


[#reference_list_of_reverse]

    void reverse();

* [*Effects:] Reverses the order of the elements in the view.
* [*Postconditions:] Validity of iterators and references is preserved.
* [*Complexity:] O(n).
* [*Exception safety:] nothrow.


[endsect]

[section Rearrange operations]

These operations, without counterpart in `std::list` (although splice provides
partially overlapping functionality), perform individual and global repositioning
of elements inside the index.


[#reference_list_of_relocate_iterator_iterator]

    void relocate(iterator position, iterator i);

* [*Requires: ] `position` is a valid iterator of the view. `i` is a valid
dereferenceable iterator of the view.
* [*Effects:] Inserts the element pointed to by `i` before `position`.
If `position==i`, no operation is performed.
* [*Postconditions:] No iterator or reference is invalidated.
* [*Complexity:] Constant.
* [*Exception safety:] nothrow.


[#reference_list_of_relocate_iterator_iterator_iterator]

    void relocate(iterator position, iterator first, iterator last);

* [*Requires: ] `position` is a valid iterator of the view. `first` and `last` are
valid iterators of the view. `last` is reachable from `first`. `position` is not
in the range `[first,last)`.
* [*Effects:] The range of elements `[first,last)` is repositioned just before
`position`.
* [*Postconditions:] No iterator or reference is invalidated.
* [*Complexity:] Constant.
* [*Exception safety:] nothrow.


[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 `list_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:] No additional requirements to those imposed by the container.
[*Postconditions:] On successful loading, each of the elements of
`[begin(), end())`
is a restored copy of the corresponding element in
`[m.get<i>().begin(), m.get<i>().end())`,
where `i` is the position of the `list_of` view in the container.


[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.


[endsect]
[endsect]


[endsect]