![]() |
Home | Libraries | People | FAQ | More |
namespace boost { namespace bimaps { template< class KeyType > struct list_of; struct list_of_relation; } // namespace bimap } // namespace boost
A list_of set view is a std::list signature compatible interface to the
underlying heap of elements contained in a bimap
.
If you look the bimap by a side, you will use a map view and if you looked it as a whole you will be using a set view.
Elements in a list_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 list_of view. Additionally, the view allows for free
reordering of elements in the same vein as std::list
does. Validity of iterators and references to elements is preserved in
all operations.
There are a number of differences with respect to std::lists
:
std::list
, insertions into a list_of view
may fail due to clashings with other views. This alters the semantics
of the operations provided with respect to their analogues in std::list
.
replace
and modify
member functions.
Having these restrictions into account, list_of views are models of Reversible Container, Front Insertion Sequence and Back Insertion Sequence. We only provide descriptions of 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=(const 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; void resize(size_type n, const value_type & x = value_type()); // access 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 n, 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- mapped_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< class Compare > void merge(this_type & x,Compare comp); void sort(); template< class 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< list_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 list_of
views, we adopt the scheme outlined in the complexity
signature section. The complexity signature of a list_of
view is:
c(n) = n * log(n)
,
i(n) = 1
(constant),
h(n) = 1
(constant),
d(n) = 1
(constant),
r(n) = 1
(constant),
m(n) = 1
(constant).
list_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 list_of
,
Allocator
from bimap
,
As explained in the view 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 views 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);
void resize(size_type n,const value_type& x=value_type());
if( n > size() ) insert(end(),
n -
size(),
x);
else if( n < size() ) {
iterator
it =
begin();
std::advance(it, n);
erase(it, end());
}
std::pair<iterator,bool> push_front(const value_type& x);
x
at the beginning of the sequence if no other views 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> push_back(const value_type & x);
x
at the end of the sequence if no other views 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 n, const value_type & x);
position
is a valid iterator
of the view.
for(size_type
i =
0;
i <
n;
++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
.
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)
.
last
.
[first,last)
.
bool replace(iterator position,const value_type& x);
position
is a valid dereferenceable iterator of the view.
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
.
position
is preserved in all cases.
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.
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
.
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
.
x.size()
*I(n+x.size()
)
+ x.size()
*D(x.size()
)).
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
,
constant; otherwise O(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
,
constant; otherwise O(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);
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
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.
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);
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.
std::less<value_type>
does not throw; otherwise, basic.
template< typename Compare > void sort(Compare comp);
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 list_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 list_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()
.
it
be a const_iterator
and the restored it
'
an iterator, or viceversa.