846 lines
31 KiB
Plaintext
846 lines
31 KiB
Plaintext
[/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 vector_of Reference]
|
|
|
|
[section Header "boost/bimap/vector_of.hpp" synopsis]
|
|
|
|
namespace boost {
|
|
namespace bimaps {
|
|
|
|
|
|
template< class KeyType >
|
|
struct vector_of;
|
|
|
|
struct vector_of_relation;
|
|
|
|
|
|
} // namespace bimap
|
|
} // namespace boost
|
|
|
|
|
|
[endsect]
|
|
|
|
[section vector_of views]
|
|
|
|
vector_of views are free-order sequences with constant time positional
|
|
access and random access iterators. Elements in a vector_of view are by
|
|
default sorted according to their order of insertion: this means that new elements
|
|
inserted through a different view of the `bimap` are appended to
|
|
the end of the vector_of view; additionally, facilities are provided for
|
|
further rearrangement of the elements. The public interface of vector_of views
|
|
includes that of list_of views, with differences in the complexity
|
|
of the operations, plus extra operations for positional access
|
|
(`operator[]` and `at()`) and for capacity handling. Validity of iterators and
|
|
references to elements is preserved in all operations, regardless of the
|
|
capacity status.
|
|
|
|
As is the case with list_of views, vector_of views have the following
|
|
limitations with respect to STL sequence containers:
|
|
|
|
* vector_of views
|
|
are not __SGI_ASSIGNABLE__ (like any other view.)
|
|
* Insertions into a vector_of view may fail due to clashings with other views.
|
|
This alters the semantics of the operations provided with respect to their analogues
|
|
in STL sequence containers.
|
|
* Elements in a vector_of view are not mutable, and can only be changed by
|
|
means of replace and modify member functions.
|
|
|
|
Having these restrictions into account, vector of views are models of
|
|
__SGI_RANDOM_ACCESS_CONTAINER__ and __SGI_BACK_INSERTION_SEQUENCE__. Although these views
|
|
do not model __SGI_FRONT_INSERTION_SEQUENCE__, because front insertion and deletion
|
|
take linear time, front operations are nonetheless provided to match the interface
|
|
of list_of views. We only describe those types and operations that are either
|
|
not present in the concepts modeled or do not exactly conform to the requirements
|
|
for these types of containers.
|
|
|
|
|
|
namespace boost {
|
|
namespace bimaps {
|
|
namespace views {
|
|
|
|
template< ``['-implementation defined parameter list-]`` >
|
|
class ``['-implementation defined view name-]``
|
|
{
|
|
public:
|
|
|
|
// types
|
|
|
|
typedef ``['-unspecified-]`` value_type;
|
|
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-]`` reverse_iterator;
|
|
typedef ``['-unspecified-]`` const_reverse_iterator;
|
|
|
|
typedef ``['-unspecified-]`` info_type;
|
|
|
|
// construct / copy / destroy
|
|
|
|
this_type & operator=(this_type & x);
|
|
|
|
template< class InputIterator >
|
|
void ``[link reference_vector_of_assign_iterator_iterator assign]``(InputIterator first, InputIterator last);
|
|
|
|
void ``[link reference_vector_of_assign_size_value assign]``(size_type n, const value_type & value);
|
|
|
|
allocator_type get_allocator() const;
|
|
|
|
// iterators
|
|
|
|
iterator begin();
|
|
const_iterator begin() const;
|
|
|
|
iterator end();
|
|
const_iterator end() const;
|
|
|
|
reverse_iterator rbegin();
|
|
const_reverse_iterator rbegin() const;
|
|
|
|
reverse_iterator rend();
|
|
const_reverse_iterator rend() const;
|
|
|
|
// capacity
|
|
|
|
bool empty() const;
|
|
|
|
size_type size() const;
|
|
|
|
size_type max_size() const;
|
|
|
|
size_type ``[link reference_vector_of_capacity capacity]``() const;
|
|
|
|
void ``[link reference_vector_of_reserve_size reserve]``(size_type m);
|
|
|
|
void ``[link reference_vector_of_resize_size_value resize]``(size_type n, const value_type & x = value_type());
|
|
|
|
// access
|
|
|
|
const_reference operator[](size_type n) const;
|
|
|
|
const_reference at(size_type n) const;
|
|
|
|
const_reference front() const;
|
|
|
|
const_reference back() const;
|
|
|
|
// modifiers
|
|
|
|
std::pair<iterator,bool> ``[link reference_vector_of_push_front_value push_front]``(const value_type & x);
|
|
void pop_front();
|
|
|
|
std::pair<iterator,bool> ``[link reference_vector_of_push_back_value push_back]``(const value_type & x);
|
|
void pop_back();
|
|
|
|
std::pair<iterator,bool> ``[link reference_vector_of_insert_iterator_value insert]``(iterator position, const value_type & x);
|
|
|
|
void ``[link reference_vector_of_insert_iterator_size_value insert]``(iterator position, size_type m, const value_type & x);
|
|
|
|
template< class InputIterator>
|
|
void ``[link reference_vector_of_insert_iterator_iterator_iterator insert]``(iterator position, InputIterator first, InputIterator last);
|
|
|
|
iterator ``[link reference_vector_of_erase_iterator erase]``(iterator position);
|
|
iterator ``[link reference_vector_of_erase_iterator_iterator erase]``(iterator first, iterator last);
|
|
|
|
bool ``[link reference_vector_of_replace_iterator_value replace]``(iterator position, const value_type & x);
|
|
|
|
// Only in map views
|
|
// {
|
|
typedef ``['-unspecified-]`` key_type;
|
|
typedef ``['-unspecified-]`` mapped_type;
|
|
typedef ``['-unspecified-]`` data_type; // Equal to mapped_type
|
|
|
|
template< class CompatibleKey >
|
|
bool ``[link reference_vector_of_replace_key_iterator_key replace_key]``(iterator position, const CompatibleKey & x);
|
|
|
|
template< class CompatibleData >
|
|
bool ``[link reference_vector_of_replace_data_iterator_data replace_data]``(iterator position, const CompatibleData & x);
|
|
|
|
template< class KeyModifier >
|
|
bool ``[link reference_vector_of_modify_key_iterator_modifier modify_key]``(iterator position, KeyModifier mod);
|
|
|
|
template< class DataModifier >
|
|
bool ``[link reference_vector_of_modify_data_iterator_modifier modify_data]``(iterator position, DataModifier mod);
|
|
|
|
// }
|
|
|
|
|
|
void clear();
|
|
|
|
// list operations
|
|
|
|
void ``[link reference_vector_of_splice_iterator_this splice]``(iterator position, this_type & x);
|
|
void ``[link reference_vector_of_splice_iterator_this_iterator splice]``(iterator position, this_type & x, iterator i);
|
|
void ``[link reference_vector_of_splice_iterator_this_iterator_iterator splice]``(
|
|
iterator position, this_type & x, iterator first, iterator last);
|
|
|
|
void ``[link reference_vector_of_remove_value remove]``(const value_type & value);
|
|
|
|
template< class Predicate >
|
|
void ``[link reference_vector_of_remove_if_predicate remove_if]``(Predicate pred);
|
|
|
|
void ``[link reference_vector_of_unique unique]``();
|
|
|
|
template< class BinaryPredicate >
|
|
void ``[link reference_vector_of_unique_predicate unique]``(BinaryPredicate binary_pred);
|
|
|
|
void ``[link reference_vector_of_merge_this merge]``(this_type & x);
|
|
|
|
template< typename Compare >
|
|
void ``[link reference_vector_of_merge_this_compare merge]``(this_type & x, Compare comp);
|
|
|
|
void ``[link reference_vector_of_sort sort]``();
|
|
|
|
template< typename Compare >
|
|
void ``[link reference_vector_of_sort_compare sort]``(Compare comp);
|
|
|
|
void ``[link reference_vector_of_reverse reverse]``();
|
|
|
|
// rearrange operations
|
|
|
|
void ``[link reference_vector_of_relocate_iterator_iterator relocate]``(iterator position, iterator i);
|
|
void ``[link reference_vector_of_relocate_iterator_iterator_iterator relocate]``(iterator position, iterator first, iterator last);
|
|
};
|
|
|
|
// view comparison
|
|
|
|
bool operator==(const this_type & v1, const this_type & v2 );
|
|
bool operator< (const this_type & v1, const this_type & v2 );
|
|
bool operator!=(const this_type & v1, const this_type & v2 );
|
|
bool operator> (const this_type & v1, const this_type & v2 );
|
|
bool operator>=(const this_type & v1, const this_type & v2 );
|
|
bool operator<=(const this_type & v1, const this_type & v2 );
|
|
|
|
} // namespace views
|
|
} // namespace bimap
|
|
} // namespace boost
|
|
|
|
|
|
|
|
In the case of a `bimap< vector_of<Left>, ... >`
|
|
|
|
In the set view:
|
|
|
|
typedef signature-compatible with relation< Left, ... > key_type;
|
|
typedef signature-compatible with relation< Left, ... > value_type;
|
|
|
|
In the left map view:
|
|
|
|
typedef Left key_type;
|
|
typedef ... mapped_type;
|
|
|
|
typedef signature-compatible with std::pair< Left, ... > value_type;
|
|
|
|
In the right map view:
|
|
|
|
typedef ... key_type;
|
|
typedef Left mapped_type;
|
|
|
|
typedef signature-compatible with std::pair< ... , Left > value_type;
|
|
|
|
|
|
[#vector_of_complexity_signature]
|
|
|
|
[section Complexity signature]
|
|
|
|
Here and in the descriptions of operations of `vector_of` views, we adopt
|
|
the scheme outlined in the
|
|
[link complexity_signature_explanation complexity signature section].
|
|
The complexity signature of `vector_of` view is:
|
|
|
|
* copying: `c(n) = n * log(n)`,
|
|
* insertion: `i(n) = 1` (amortized constant),
|
|
* hinted insertion: `h(n) = 1` (amortized constant),
|
|
* deletion: `d(n) = m`, where m is the distance from the deleted element to the
|
|
end of the sequence,
|
|
* replacement: `r(n) = 1` (constant),
|
|
* modifying: `m(n) = 1` (constant).
|
|
|
|
The following expressions are also used as a convenience for writing down some
|
|
of the complexity formulas:
|
|
|
|
[blurb
|
|
`shl(a,b) = a+b` if a is nonzero, 0 otherwise.
|
|
`rel(a,b,c) =` if `a<b`, `c-a`, else `a-b`,
|
|
]
|
|
|
|
(`shl` and `rel` stand for ['shift left] and ['relocate], respectively.)
|
|
|
|
[endsect]
|
|
|
|
[section Instantiation types]
|
|
|
|
`vector_of` views are instantiated internally to `bimap` and specified
|
|
by means of the collection type specifiers and the bimap itself.
|
|
Instantiations are dependent on the following types:
|
|
|
|
* `Value` from `vector_of`,
|
|
* `Allocator` from `bimap`,
|
|
|
|
[endsect]
|
|
|
|
[section Constructors, copy and assignment]
|
|
|
|
As explained in the views concepts section,
|
|
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`.
|
|
|
|
|
|
[#reference_vector_of_assign_iterator_iterator]
|
|
|
|
template< class InputIterator >
|
|
void assign(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
|
|
view belongs. `last` is reachable from `first`.
|
|
* [*Effects: ] `clear(); insert(end(),first,last);`
|
|
|
|
|
|
[#reference_vector_of_assign_size_value]
|
|
|
|
void assign(size_type n, const value_type & value);
|
|
|
|
* [*Effects: ] `clear(); for(size_type i = 0; i < n; ++n) push_back(v);`
|
|
|
|
[endsect]
|
|
|
|
[section Capacity operations]
|
|
|
|
[#reference_vector_of_capacity]
|
|
|
|
size_type capacity() const;
|
|
|
|
* [*Returns:] The total number of elements `c` such that, when `size() < c`,
|
|
back insertions happen in constant time (the general case as described by
|
|
i(n) is ['amortized] constant time.)
|
|
* [*Note:] Validity of iterators and references to elements is preserved
|
|
in all insertions, regardless of the capacity status.
|
|
|
|
|
|
[#reference_vector_of_reserve_size]
|
|
|
|
void reserve(size_type m);
|
|
|
|
* [*Effects:] If the previous value of `capacity()` was greater than or equal
|
|
to `m`, nothing is done; otherwise, the internal capacity is changed so that
|
|
`capacity()>=m`.
|
|
* [*Complexity:] If the capacity is not changed, constant; otherwise O(n).
|
|
* [*Exception safety:] If the capacity is not changed, nothrow; otherwise, strong.
|
|
|
|
|
|
[#reference_vector_of_resize_size_value]
|
|
|
|
void resize(size_type n, const value_type & x = value_type());
|
|
|
|
* [*Effects: ] `if( n > size() ) insert(end(), n-size(), x);`
|
|
`else if( n<size() ) erase(begin()+n,end());`
|
|
* [*Note:] If an expansion is requested, the size of the view is not guaranteed
|
|
to be n after this operation (other views may ban insertions.)
|
|
|
|
|
|
[endsect]
|
|
|
|
[section Modifiers]
|
|
|
|
[#reference_vector_of_push_front_value]
|
|
|
|
std::pair<iterator,bool> push_front(const value_type & x);
|
|
|
|
* [*Effects:] Inserts x at the beginning of the sequence if no other view
|
|
of the `bimap` bans the insertion.
|
|
* [*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 vector_of_complexity_signature [*Complexity:]] O(n+I(n)).
|
|
* [*Exception safety:] Strong.
|
|
|
|
|
|
[#reference_vector_of_push_back_value]
|
|
|
|
std::pair<iterator,bool> push_back(const value_type & x);
|
|
|
|
* [*Effects:] Inserts `x` at the end of the sequence if no other view of
|
|
the `bimap` bans the insertion.
|
|
* [*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 vector_of_complexity_signature [*Complexity:]] O(I(n)).
|
|
* [*Exception safety:] Strong.
|
|
|
|
|
|
[#reference_vector_of_insert_iterator_value]
|
|
|
|
std::pair<iterator,bool> insert(iterator position, const value_type & x);
|
|
|
|
* [*Requires: ] `position` is a valid iterator of the view.
|
|
* [*Effects:] Inserts `x` before position if 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 vector_of_complexity_signature [*Complexity:]] O(shl(end()-position,1) + I(n)).
|
|
* [*Exception safety:] Strong.
|
|
|
|
|
|
[#reference_vector_of_insert_iterator_size_value]
|
|
|
|
void insert(iterator position, size_type m, const value_type & x);
|
|
|
|
* [*Requires: ] `position` is a valid iterator of the view.
|
|
* [*Effects: ] `for(size_type i = 0; i < m; ++i) insert(position, x);`
|
|
* [link vector_of_complexity_signature
|
|
[*Complexity:]] O(shl(end()-position,m) + m*I(n+m)).
|
|
|
|
|
|
[#reference_vector_of_insert_iterator_iterator_iterator]
|
|
|
|
template< class InputIterator >
|
|
void insert(iterator position, InputIterator first, InputIterator last);
|
|
|
|
* [*Requires: ] `position` is a valid iterator of the view. `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 view belongs. `last` is reachable
|
|
from `first`.
|
|
* [*Effects: ] `while(first!=last)insert(position,*first++);`
|
|
* [link vector_of_complexity_signature
|
|
[*Complexity:]] O(shl(end()-position,m) + m*I(n+m)), where m is the number
|
|
of elements in `[first,last)`.
|
|
* [*Exception safety:] Basic.
|
|
|
|
|
|
[#reference_vector_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 vector_of_complexity_signature [*Complexity:]] O(D(n)).
|
|
* [*Exception safety:] nothrow.
|
|
|
|
|
|
[#reference_vector_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 vector_of_complexity_signature
|
|
[*Complexity:]] O(m*D(n)), where m is the number of elements in `[first,last)`.
|
|
* [*Exception safety:] nothrow.
|
|
|
|
|
|
[#reference_vector_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 vector_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_vector_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 vector_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_vector_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 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 vector_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_vector_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 vector_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_vector_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.
|
|
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 vector_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_vector_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`.
|
|
Rearrangement on `vector_of` views does not change the position of the
|
|
element with respect to the view; rearrangement on other views may or
|
|
might not succeed. 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 vector_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]
|
|
|
|
`vector_of` views replicate the interface of `list_of` views, which
|
|
in turn includes the list operations provided by `std::list`. The syntax and
|
|
behavior of these operations exactly matches those of `list_of` views, but
|
|
the associated complexity bounds differ in general.
|
|
|
|
|
|
[#reference_vector_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 vector_of_complexity_signature
|
|
[*Complexity:]] O(shl(end()-position,x.size()) + x.size()*I(n+x.size()) + x.size()*D(x.size())).
|
|
* [*Exception safety:] Basic.
|
|
|
|
|
|
[#reference_vector_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 vector_of_complexity_signature
|
|
[*Complexity:]] If `&x==this`, O(rel(position,i,i+1));
|
|
otherwise O(shl(end()-position,1) + I(n) + D(n)).
|
|
* [*Exception safety:] If `&x==this`, nothrow; otherwise, strong.
|
|
|
|
|
|
[#reference_vector_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 vector_of_complexity_signature
|
|
[*Complexity:]] If `&x==this`, O(rel(position,first,last));
|
|
otherwise O(shl(end()-position,m) + 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_vector_of_remove_value]
|
|
|
|
void remove(const value_type & value);
|
|
|
|
* [*Effects:] Erases all elements of the view which compare equal to `value`.
|
|
* [link vector_of_complexity_signature
|
|
[*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
|
|
* [*Exception safety:] Basic.
|
|
|
|
|
|
[#reference_vector_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 vector_of_complexity_signature
|
|
[*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
|
|
* [*Exception safety:] Basic.
|
|
|
|
|
|
[#reference_vector_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 vector_of_complexity_signature
|
|
[*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
|
|
* [*Exception safety:] Basic.
|
|
|
|
|
|
[#reference_vector_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 vector_of_complexity_signature
|
|
[*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
|
|
* [*Exception safety:] Basic.
|
|
|
|
|
|
[#reference_vector_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 vector_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_vector_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 vector_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_vector_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:] Basic.
|
|
|
|
|
|
[#reference_vector_of_sort_compare]
|
|
|
|
template< class 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:] Basic.
|
|
|
|
|
|
[#reference_vector_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_vector_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_vector_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 `vector_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 `vector_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] |