Next : Deque, Previous : Vector,
Top : Table of Contents
List
list is a kind of sequence (See Sequences.)
that supports bidirectional iterators and allows constant time insert and
erase operations anywhere within the sequence, with storage management
handled automatically. Unlike vectors
and
deques,
fast random access to list elements is not supported,
but many algorithms only need sequential access anyway. See Reversible
Container.
template
class Allocator = allocator> class list {
public:
// typedefs:
typedef iterator
typedef const_iterator
typedef Allocator::pointer pointer
typedef Allocator::reference reference
typedef Allocator::const_reference const_reference
typedef size_type
typedef difference_type
typedef T value_type
typedef reverse_iterator
typedef const_reverse_iterator;
// allocation/deallocation:
list()
list(size_type n, const T& value = T())
template
list(InputIterator first, InputIterator last)
list(const list& x)
~list()
list& operator=(const list& x)
void swap(list& x);
// accessors:
iterator begin()
const_iterator begin() const
iterator end()
const_iterator end() const
reverse_iterator rbegin()
const_reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rend();
bool empty() const;
size_type size() const;
size_type max_size() const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// insert/erase:
void push_front(const T& x);
void push_back(const T& x);
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template
void insert(iterator position, InputIterator first, InputIterator last);
void pop_front();
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
// special mutative operations on list:
void splice(iterator position, list& x);
void splice(iterator position, list& x, iterator i);
void splice(iterator position, list& x,
iterator first, iterator last);
void remove(const T& value);
template void remove_if(Predicate pred);
void unique();
template void unique(BinaryPredicate binary_pred);
void merge(list& x);
template void merge(list& x, Compare comp);
void reverse();
void sort();
template void sort(Compare comp);
};
template
bool operator==(const list& x, const list& y);
template
bool operator<(const list& x, const list& y);
iterator is a bidirectional iterator referring to T. The exact type is implementation dependent and determined
by Allocator.
| const_iterator |
Typedef on list |
const_iterator is a constant bidirectional iterator referring to const T. The exact type is implementation
dependent and determined by Allocator. It is guaranteed that
there is a constructor for const_iterator out of
iterator.
| size_type |
Typedef on list |
size_type is an unsigned integral type. The exact type is
implementation dependent and determined by Allocator.
| difference_type |
Typedef on list |
difference_type is a signed integral type. The exact type
is implementation dependent and determined by Allocator.
| insert (iterator position, const T& x = T());
|
Method on list |
| insert (iterator position, size_type n, const
T& x); |
Method on list |
| insert (iterator position, InputIterator first,
InputIterator last); |
Method on list |
insert does not affect the validity of iterators and
references. Insertion of a single element into a list takes constant time
and exactly one call to the copy constructor of T. Insertion
of multiple elements into a list is linear in the number of elements
inserted, and the number of calls to the copy constructor of T is exactly equal to the number of elements inserted.
| erase (iterator position); |
Method on list |
| erase (iterator first, iterator last); |
Method on list |
erase invalidates only the iterators and references to
the erased elements. Erasing a single element is a constant time operation
with a single call to the destructor of T. Erasing a range in
a list is linear time in the size of the range and the number of calls to
the destructor of type T is exactly equal to the size of the range.
Since lists allow fast insertion and erasing from the middle of a list,
certain operations are provided specifically for them:
list provides three splice operations that destructively move
elements from one list to another:
| void splice (iterator position,
list& x) |
Method on list |
inserts the contents of x before position and x becomes empty. It takes constant time. The result is
undefined if &x == this.
| void splice (iterator position, list& x, iterator i) |
Method on list |
| void splice (iterator position, list& x, iterator first, iterator last) |
Method on list |
inserts elements in the range [first, last) before position and removes the elements from x. It takes constant time if &x == this; otherwise, it takes linear time. [first, last) is a valid range in x. The result is undefined if position is an iterator in the range [first, last).
| remove (const T& value); |
Method on list |
remove erases all the elements in the list referred by
the list iterator i for which the following conditions hold: *i == value, pred(*i) == true. remove is stable,
that is, the relative order of the elements that are not removed is the
same as their relative order in the original list. Exactly size() applications of the corresponding predicate are done.
unique erases all but the first element from every
consecutive group of equal elements in the list. Exactly size() -
1 applications of the corresponding binary predicate are done.
| merge (list& x); |
Method on list |
| merge (list& x, Compare comp); |
Method on list |
merge merges the argument list into the list (both are
assumed to be sorted). The merge is stable, that is, for equal elements in
the two lists, the elements from the list always precede the elements from
the argument list. x is empty after the merge. At most size() + x.size() - 1 comparisons are done.
reverse reverses the order of the elements in the list.
It is linear time.
sort sorts the list according to the
operator< or a compare function object. `size().
