...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
namespace boost { namespace bimaps { template< class KeyType > struct vector_of; struct vector_of_relation; } // namespace bimap } // namespace boost
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:
Having these restrictions into account, vector of views are models of Random Access Container and Back Insertion Sequence. Although these views do not model 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 assign(InputIterator first, InputIterator last); void 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 capacity() const; void reserve(size_type m); void 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> push_front(const value_type & x); void pop_front(); std::pair<iterator,bool> push_back(const value_type & x); void pop_back(); std::pair<iterator,bool> insert(iterator position, const value_type & x); void insert(iterator position, size_type m, const value_type & x); template< class InputIterator> void insert(iterator position, InputIterator first, InputIterator last); iterator erase(iterator position); iterator erase(iterator first, iterator last); bool 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 replace_key(iterator position, const CompatibleKey & x); template< class CompatibleData > bool replace_data(iterator position, const CompatibleData & x); template< class KeyModifier > bool modify_key(iterator position, KeyModifier mod); template< class DataModifier > bool modify_data(iterator position, DataModifier mod); // } void clear(); // list operations void splice(iterator position, this_type & x); void splice(iterator position, this_type & x, iterator i); void splice( iterator position, this_type & x, iterator first, iterator last); void remove(const value_type & value); template< class Predicate > void remove_if(Predicate pred); void unique(); template< class BinaryPredicate > void unique(BinaryPredicate binary_pred); void merge(this_type & x); template< typename Compare > void merge(this_type & x, Compare comp); void sort(); template< typename Compare > void sort(Compare comp); void reverse(); // rearrange operations void relocate(iterator position, iterator i); void 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;
Here and in the descriptions of operations of vector_of
views, we adopt the scheme outlined in the complexity
signature section. The complexity signature of vector_of
view is:
c(n) = n * log(n)
,
i(n) = 1
(amortized constant),
h(n) = 1
(amortized constant),
d(n) = m
,
where m is the distance from the deleted element to the end of the
sequence,
r(n) = 1
(constant),
m(n) = 1
(constant).
The following expressions are also used as a convenience for writing down some of the complexity formulas:
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.)
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
,
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);
a=b;
where a and b are the bimap
objects to which *this
and x
belong, respectively.
*this
.
template< class InputIterator > void assign(InputIterator first, InputIterator last);
InputIterator
is a model of 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
.
clear(); insert(end(),first,last);
void assign(size_type n, const value_type & value);
clear(); for(size_type
i =
0;
i <
n;
++n) push_back(v);
size_type capacity() const;
c
such that, when
size()
< c
,
back insertions happen in constant time (the general case as described
by i(n) is amortized constant time.)
void reserve(size_type m);
capacity()
was greater than or equal to m
,
nothing is done; otherwise, the internal capacity is changed so that
capacity()>=m
.
void resize(size_type n, const value_type & x = value_type());
if( n > size() ) insert(end(),
n-size(),
x);
else if( n<size() ) erase(begin()+n,end());
std::pair<iterator,bool> push_front(const value_type & x);
bimap
bans the insertion.
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.
std::pair<iterator,bool> push_back(const value_type & x);
x
at the end of the sequence if no other view of the bimap
bans the insertion.
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.
std::pair<iterator,bool> insert(iterator position, const value_type & x);
position
is a valid iterator of the view.
x
before position if insertion is allowed by all other views of the
bimap
.
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.
void insert(iterator position, size_type m, const value_type & x);
position
is a valid iterator of the view.
for(size_type
i =
0;
i <
m;
++i) insert(position, x);
template< class InputIterator > void insert(iterator position, InputIterator first, InputIterator last);
position
is a valid iterator of the view. InputIterator
is a model of 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
.
while(first!=last)insert(position,*first++);
[first,last)
.
iterator erase(iterator position);
position
is a valid dereferenceable iterator of the view.
position
.
end()
if no such element exists.
iterator erase(iterator first, iterator last);
[first,last)
is a valid range of the view.
[first,last)
.
[first,last)
.
bool replace(iterator position, const value_type & x);
position
is a valid dereferenceable iterator of the view.
bimap
to which the view belongs if replacing is allowed by all other views
of the bimap
.
true
if the replacement took place, false
otherwise.
bimap
to which the view belongs
remains in its original state.
template< class CompatibleKey > bool replace_key(iterator position, const CompatibleKey & x);
position
is a valid dereferenceable iterator of the set view. CompatibleKey
can be assigned to
key_type
.
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
.
true
if the replacement took place, false
otherwise.
bimap
to which the set view belongs
remains in its original state.
template< class CompatibleData > bool replace_data(iterator position, const CompatibleData & x);
position
is a valid dereferenceable iterator of the set view. CompatibleKey
can be assigned to
mapped_type
.
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
.
true
if the replacement took place, false
otherwise.
bimap
to which the set view belongs
remains in its original state.
template< class KeyModifier > bool modify_key(iterator position, KeyModifier mod);
KeyModifier
is a model of Unary
Function accepting arguments of type: key_type&
; position
is a valid dereferenceable iterator of the view.
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
.
position
is preserved if the operation
succeeds.
true
if the operation succeeded, false
otherwise.
template< class DataModifier > bool modify_data(iterator position, DataModifier mod);
DataModifier
is a model of Unary
Function accepting arguments of type: mapped_type&
; position
is a valid dereferenceable iterator of the view.
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
.
position
is preserved if the operation
succeeds.
true
if the operation succeeded, false
otherwise.
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.
void splice(iterator position, this_type & x);
position
is a valid iterator of the view. &x!=this
.
x
before position,
in the same order as they were in x
.
Those elements successfully inserted are erased from x
.
void splice(iterator position, this_type & x,iterator i);
position
is a valid iterator of the view. i
is a valid dereferenceable iterator x
.
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.
&x==this
,
no iterator or reference is invalidated.
&x==this
,
O(rel(position,i,i+1)); otherwise O(shl(end()-position,1) + I(n)
+ D(n)).
&x==this
,
nothrow; otherwise, strong.
void splice(iterator position, this_type & x, iterator first, iterator last);
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)
.
[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.
&x==this
,
no iterator or reference is invalidated.
&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)
.
&x==this
,
nothrow; otherwise, basic.
void remove(const value_type & value);
value
.
template< class Predicate > void remove_if(Predicate pred);
x
of the view for which pred(x)
holds.
void unique();
i
in the range [first+1,last)
for which *i==*(i-1)
.
template< class BinaryPredicate > void unique(BinaryPredicate binary_pred);
[first+1,last)
for which binary_pred(*i, *(i-1))
holds.
void merge(this_type & x);
std::less<value_type>
is a Strict
Weak Ordering over value_type
.
Both the view and x
are sorted according to std::less<value_type>
.
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.
x
are sorted. Validity of iterators to the view and of non-erased elements
of x
references is
preserved.
&x==this
,
constant; otherwise O(n + x.size()*I(n+x.size()) + x.size()*D(x.size())).
&x==this
,
nothrow; otherwise, basic.
template< class Compare > void merge(this_type & x, Compare comp);
Compare
is a Strict
Weak Ordering over value_type
.
Both the view and x
are sorted according to comp.
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.
x
are sorted according to comp
.
Validity of iterators to the view and of non-erased elements of
x
references is preserved.
&x==this
,
constant; otherwise O(n + x.size()*I(n+x.size()) + x.size()*D(x.size())).
&x==this
,
nothrow; otherwise, basic.
void sort();
std::less<value_type>
is a Strict
Weak Ordering over value_type
.
std::less<value_type>
.
The sorting is stable, i.e. equivalent elements preserve their relative
position.
template< class Compare > void sort(Compare comp);
value_type
.
comp
. The sorting
is stable, i.e. equivalent elements preserve their relative position.
void reverse();
These operations, without counterpart in std::list
(although splice provides partially overlapping functionality), perform
individual and global repositioning of elements inside the index.
void relocate(iterator position, iterator i);
position
is a valid iterator of the view. i
is a valid dereferenceable iterator of the view.
i
before position
. If position==i
,
no operation is performed.
void relocate(iterator position, iterator first, iterator last);
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)
.
[first,last)
is repositioned just before position
.
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.
Operation: saving of a bimap
b to an output archive (XML archive)
ar.
Operation: loading of a bimap
b' from an input archive (XML
archive) ar.
[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.
Operation: saving of an iterator
or const_iterator
it
to an output archive
(XML archive) ar.
it
is a valid iterator of the view. The associated bimap
has been previously saved.
Operation: loading of an iterator
or const_iterator
it
' from an input archive
(XML archive) ar.
*it
' is the restored copy of *it
,
otherwise it
'==end()
.
const_iterator
and
the restored it
'
an iterator
, or viceversa.