Category: containers | Component type: type |
template <typename T, class A>An implementation of flist::merge that uses two different forms of splice:
void flist<T,A>::resize( size_type n, const value_type &v ) {
size_type s( size() );
if( s < n ) {
flist temp( n-s, v );
splice( end(), temp );
}
else if( s > n ) {
iterator e( end() );
e.reverse();
std::advance( e, s-n );
e.reverse();
erase( e, end() );
}
}
template <typename T, class A>An implementation of flist::remove_if that is wary of invalidated iterators. In addition to the usual care taken with invalidation on erase, note that the end() value is not cached:
template <typename Comp>
void flist<T,A>::merge( flist &that, Comp comp ) {
if( this == &that )
return;
iterator first1 = begin();
iterator first2 = that.begin();
while( first1 != end() && first2 != that.end() ) {
if( comp( *first2, *first1 ) ) {
iterator i = first2;
while( ++i != that.end() && comp( *i, *first1 ) ) {}
splice_return_type r = splice_before( first1, that, first2, i );
first1 = r.first.second;
first2 = r.second;
}
else
++first1;
}
if( first2 != that.end() )
splice( end(), that, first2, that.end() );
}
template <typename T, class A>
template <typename Pred>
void flist<T,A>::remove_if( Pred pred ) {
iterator first = begin();
while( first != end() ) {
if( pred( *first ) )
first = erase( first );
else
++first;
}
}
Parameter | Description | Default | |
---|---|---|---|
T | The flist's value type: the type of object that is stored in the flist. | ||
Alloc | The flist's allocator, used for all internal memory management. | std::allocator |
Member | Where defined | Description |
---|---|---|
value_type | Container | The type of object, T, stored in the list. |
pointer | Container | Pointer to T. |
reference | Container | Reference to T |
const_reference | Container | Const reference to T |
size_type | Container | An unsigned integral type. |
difference_type | Container | A signed integral type. |
iterator | Container | Iterator used to iterate through an flist. |
const_iterator | Container | Const iterator used to iterate through an flist. |
reverse_iterator | Reversible Container | Iterator used to iterate backwards through an flist. |
const_reverse_iterator | Reversible Container | Const iterator used to iterate backwards through an flist. |
iterator begin() | Container | Returns an iterator pointing to the beginning of the flist. |
iterator end() | Container | Returns an iterator pointing to the end of the flist. |
const_iterator begin() const | Container | Returns a const_iterator pointing to the beginning of the flist. |
const_iterator end() const | Container | Returns a const_iterator pointing to the end of the flist. |
reverse_iterator rbegin() | Reversible Container | Returns a reverse_iterator pointing to the beginning of the reversed flist. |
reverse_iterator rend() | Reversible Container | Returns a reverse_iterator pointing to the end of the reversed flist. |
const_reverse_iterator rbegin() const | Reversible Container | Returns a const_reverse_iterator pointing to the beginning of the reversed flist. |
const_reverse_iterator rend() const | Reversible Container | Returns a const_reverse_iterator pointing to the end of the reversed flist. |
size_type size() const | Container | Returns the size of the flist. Note: you should not assume that this function is constant time. It is permitted to be O(N), where N is the number of elements in the flist. If you wish to test whether an flist is empty, you should write L.empty() rather than L.size() == 0. |
size_type max_size() const | Container | Returns the largest possible size of the flist. |
bool empty() const | Container | true if the flist's size is 0. |
flist() | Container | Creates an empty flist. |
flist(size_type n) | Sequence | Creates an flist with n elements, each of which is a copy of T(). |
flist(size_type n, const T& t) | Sequence | Creates an flist with n copies of t. |
flist(const flist&) | Container | The copy constructor. |
template <class InputIterator> |
Sequence | Creates an flist with a copy of a range. |
~flist() | Container | The destructor. |
flist& operator=(const flist&) | Container | The assignment operator. |
reference front() | Front Insertion Sequence | Returns the first element. |
const_reference front() const | Front Insertion Sequence | Returns the first element. |
reference back() | Sequence | Returns the last element. |
const_reference back() const | Back Insertion Sequence | Returns the last element. |
void push_front(const T&) | Front Insertion Sequence | Inserts a new element at the beginning.
Invalidates iterators that std::list
does not (see below). |
void push_back(const T&) | Back Insertion Sequence | Inserts a new element at the end. Invalidates iterators that std::list does not (see below). |
void pop_front() | Front Insertion Sequence | Removes the first element. Invalidates iterators that std::list does not (see below). |
void pop_back() | Back Insertion Sequence | Removes the last element. Invalidates iterators that std::list does not (see below). |
void swap(flist&) | Container | Swaps the contents of two flists. Invalidates iterators that std::list does not (see below). |
iterator insert(iterator pos, const T& x) |
Sequence | Inserts x before pos. Invalidates iterators that std::list does not (see below). |
template <class InputIterator> |
Sequence | Inserts the range [f, l) before pos. Invalidates iterators that std::list does not (see below). |
void insert(iterator pos, |
Sequence | Inserts n copies of x before pos. Invalidates iterators that std::list does not (see below). |
iterator erase(iterator pos) | Sequence | Erases the element at position pos. Invalidates iterators that std::list does not (see below). |
iterator erase(iterator first, iterator last) |
Sequence | Erases the range [first, last) Invalidates iterators that std::list does not (see below). |
void clear() | Sequence | Erases all of the elements. |
void resize(n, t = T()) | Sequence | Inserts or erases elements at the end such that the size becomes n. Invalidates iterators that std::list does not (see below). |
bool operator==(const flist&) |
Forward Container | Tests two flists
for equality. Note that this may be a member or non-member.
This implementation defines ==
as a member, and provides an implementation of !=. |
bool operator<(const flist&) |
Forward Container | Lexicographical comparison of two flists. Note that this
may be a member or non-member. This implementation defines < as a member, and also
provides the other relational operators. |
Function | Description |
---|---|
void splice(iterator position, |
position must be a valid iterator in *this, and x must be an flist that is distinct from *this. (That is, it is required that &x != this.) All of the elements of x are inserted before position and removed from x. Invalidates iterators that std::list does not (see below). This function is constant time. |
|
position must be a valid iterator in *this, and i must be a dereferenceable iterator in x. Splice moves the element pointed to by i from x to *this, inserting it before position. Invalidates iterators that std::list does not (see below). If position == i or position == ++i, this function is a null operation. This function is constant time. |
|
position must be a valid iterator in *this, and [first, last) must be a valid range in x. position may not be an iterator in the range [first, last). Splice moves the elements in [first, last) from x to *this, inserting them before position. Invalidates iterators that std::list does not (see below). This function is constant time. |
void remove(const T& val); | Removes all elements that compare equal to val. The relative order of elements that are not removed is unchanged. Invalidates iterators that std::list does not (see below).. This function is linear time: it performs exactly size() comparisons for equality. |
template<class Predicate> |
Removes all elements *i such that p(*i) is true. The relative order of elements that are not removed is unchanged. Invalidates iterators that std::list does not (see below). This function is linear time: it performs exactly size() applications of p. |
void unique(); | Removes all but the first element in every consecutive group of equal elements. The relative order of elements that are not removed is unchanged. Invalidates iterators that std::list does not (see below). This function is linear time: it performs exactly size() - 1 comparisons for equality. |
template<class BinaryPredicate> |
Removes all but the first element in every consecutive group of equivalent elements, where two elements *i and *j are considered equivalent if p(*i, *j) is true. The relative order of elements that are not removed is unchanged. Invalidates iterators that std::list does not (see below). This function is linear time: it performs exactly size() - 1 comparisons for equality. |
void merge(flist& x); | Both *this and x must be sorted according to operator<, and they must be distinct. (That is, it is required that &x != this.) This function removes all of x's elements and inserts them in order into *this. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x. Invalidates iterators that std::list does not (see below). This function is linear time: it performs at most size() + x.size() - 1 comparisons. |
template<class BinaryPredicate> |
Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements) on objects of type T, and both *this and x must be sorted according to that ordering. The lists x and *this must be distinct. (That is, it is required that &x != this.) This function removes all of x's elements and inserts them in order into *this. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x. Invalidates iterators that std::list does not (see below). This function is linear time: it performs at most size() + x.size() - 1 applications of Comp. |
void reverse(); | Reverses the order of elements in the flist. Iterators are not invalidated (but see below under iterators). This function is constant time. |
void sort(); | Sorts *this according to operator<. The sort is stable, that is, the relative order of equivalent elements is preserved. Invalidates iterators that std::list does not (see below). The number of comparisons is approximately N log N, where N is the flist's size. |
template<class BinaryPredicate> |
Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements on objects of type T. This function sorts the list *this according to Comp. The sort is stable, that is, the relative order of equivalent elements is preserved. Invalidates iterators that std::list does not (see below). The number of comparisons is approximately N log N, where N is the flist's size. |
Function | Description |
---|---|
iterator previous(iterator pos) | pos must be a valid iterator in *this. The return value is an iterator prev such that ++prev == pos. Complexity: linear in the number of iterators in the range [begin(), pos). |
const_iterator previous(const_iterator pos) | pos must be a valid iterator in *this. The return value is an iterator prev such that ++prev == pos. Complexity: linear in the number of iterators in the range [begin(), pos). |
iterator insert_after(iterator pos) | pos must be a dereferenceable iterator in *this. (That is, pos may not be end().) Inserts a copy of T() immediately following pos. The return value is an iterator that points to the new element. Complexity: constant time. Invalidates iterators that slist does not (see below). |
iterator insert_after(iterator pos, |
pos must be a dereferenceable iterator in *this. (That is, pos may not be end().) Inserts a copy of x immediately following pos. The return value is an iterator that points to the new element. Complexity: constant time. Invalidates iterators that slist does not (see below). |
template<class InputIterator> |
Inserts elements from the range [f, l) immediately following pos. Complexity: linear in last - first. Invalidates iterators that slist does not (see below). |
void insert_after(iterator pos, |
Inserts n copies of x immediately following pos. Complexity: linear in n. Invalidates iterators that slist does not (see below). |
iterator erase_after(iterator pos) | Erases the element pointed to by the iterator following pos. If pos is end(), begin() is erased. pos may not refer to the element preceding end(). Complexity: constant time. The return value is a new iterator that refers to the element pos referred to before the erase (since pos may be invalid). Invalidates iterators that slist does not (see below). |
iterator erase_after(iterator
before_first, iterator last) |
Erases all elements in the range [before_first + 1, last). Complexity: linear in last - (before_first + 1). The return value is a new iterator that refers to the element pos referred to before the erase (since pos may be invalid). Invalidates iterators that slist does not (see below). |
splice_return_type
splice_after(iterator pos, flist &x ) |
pos must be a valid
iterator in *this, or pos must be equal to end(). If pos == end(), the splice will
take place before begin().
x must be an flist
that is distinct from *this.
(That is, it is required that &x != this.) All of
the
elements of x are inserted after pos and
removed from x. Invalidates iterators that slist does not (see
below).
This function is constant time. Note that the signature and
return type of this splice_after
differ from that of slist::splice_after. |
splice_return_type splice_after(iterator pos, flist &x, iterator prev) |
pos must be a valid iterator in *this, or pos must be equal to end(). If pos == end(), the splice will take place before begin(). x must be an flist that is distinct from *this. (That is, it is required that &x != this.) Moves the element following prev to *this, inserting it immediately after pos. Invalidates iterators that slist does not (see below). This function is constant time. Note that the signature and return type of this splice_after differ from that of slist::splice_after. |
splice_return_type splice_after(iterator pos, |
pos must be a valid iterator in *this, or pos must be equal to end(). If pos == end(), the splice will take place before begin(). x must be an flist that is distinct from *this. (That is, it is required that &x != this.) Moves the elements in the range [before_first + 1, before_last + 1) to *this, inserting them immediately after pos. Invalidates iterators that slist does not (see below). This function is constant time. Note that the signature and return type of this splice_after differ from that of slist::splice_after. |
Function | Description |
---|---|
splice_return_type splice_before(iterator position, |
Behaves like the corresponding splice member, but returns splice_return_type rather than void. |
|
Behaves like the corresponding splice member, but returns splice_return_type rather than void. |
|
Behaves like the corresponding splice member, but returns splice_return_type rather than void. |
iterator Function | Description |
---|---|
iterator reverse() | The iterator will still refer to the same flist element as before, but the effect of ++ and -- will be reversed. The return value is a copy of the (now reversed) *this. This is a constant time operation. |
const_iterator reverse() const | The iterator will still refer to the same flist element as before, but the effect of ++ and -- will be reversed. The return value is a copy of the (now reversed) *this. This is a constant time operation. |