 

Category: containers   Component type: type 
Description
A list
is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. List
s have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list<T>iterator
might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit. [1]
Note that singly linked lists, which only support forward traversal, are also sometimes useful. If you do not need backward traversal, then Slist
may be more efficient than list
.
Definition
Defined in the standard header list, and in the nonstandard backwardcompatibility header list.h.
Example
list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(), 2);
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
Template parameters
Parameter  Description  Default 
T  The list 's value type: the type of object that is stored in the list.  
Alloc  The list 's allocator, used for all internal memory management.  Allocators 
Model of
ReversibleContainer, FrontInsertionSequence, BackInsertionSequence.
Type requirements
None, except for those imposed by the requirements of ReversibleContainer, FrontInsertionSequence, and BackInsertionSequence.
Public base classes
None.
Members
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 a list . 
const_iterator  Container  Const iterator used to iterate through a list . 
reverse_iterator  ReversibleContainer  Iterator used to iterate backwards through a list . 
const_reverse_iterator  ReversibleContainer  Const iterator used to iterate backwards through a list . 
iterator begin()  Container  Returns an iterator pointing to the beginning of the list . 
iterator end()  Container  Returns an iterator pointing to the end of the list . 
const_iterator begin() const  Container  Returns a const_iterator pointing to the beginning of the list . 
const_iterator end() const  Container  Returns a const_iterator pointing to the end of the list . 
reverse_iterator rbegin()  ReversibleContainer  Returns a reverse_iterator pointing to the beginning of the reversed list. 
reverse_iterator rend()  ReversibleContainer  Returns a reverse_iterator pointing to the end of the reversed list. 
const_reverse_iterator rbegin() const  ReversibleContainer  Returns a const_reverse_iterator pointing to the beginning of the reversed list. 
const_reverse_iterator rend() const  ReversibleContainer  Returns a const_reverse_iterator pointing to the end of the reversed list. 
size_type size() const  Container  Returns the size of the list . 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 list . If you wish to test whether a list 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 list . 
bool empty() const  Container  true if the list 's size is 0 . 
list()  Container  Creates an empty list. 
list(size_type n)  Sequence  Creates a list with n elements, each of which is a copy of T() . 
list(size_type n, const T& t)  Sequence  Creates a list with n copies of t . 
list(const list&)  Container  The copy constructor. 
template <class InputIterator>
list(InputIterator f, InputIterator l)
[2]  Sequence  Creates a list with a copy of a range. 
~list()  Container  The destructor. 
list& operator=(const list&)  Container  The assignment operator 
reference front()  FrontInsertionSequence  Returns the first element. 
const_reference front() const  FrontInsertionSequence  Returns the first element. 
reference back()  Sequence  Returns the last element. 
const_reference back() const  BackInsertionSequence  Returns the last element. 
void push_front(const T&)  FrontInsertionSequence  Inserts a new element at the beginning. 
void push_back(const T&)  BackInsertionSequence  Inserts a new element at the end. 
void pop_front()  FrontInsertionSequence  Removes the first element. 
void pop_back()  BackInsertionSequence  Removes the last element. 
void swap(list&)  Container  Swaps the contents of two lists. 
iterator insert(iterator pos, const T& x)  Sequence  Inserts x before pos . 
template <class InputIterator>
void insert(iterator pos,
InputIterator f,
InputIterator l)
[2]  Sequence  Inserts the range [f, l) before pos . 
void insert(iterator pos,
size_type n, const T& x)
 Sequence  Inserts n copies of x before pos . 
iterator erase(iterator pos)  Sequence  Erases the element at position pos . 
iterator erase(iterator first, iterator last)  Sequence  Erases the range [first, last) 
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 . 
void splice(iterator pos, list& L)  list  See below. 
void splice(iterator pos,
list& L,
iterator i)
 list  See below. 
void splice(iterator pos,
list& L,
iterator f, iterator l)
 list  See below. 
void remove(const T& value)  list  See below. 
void unique()  list  See below. 
void merge(list& L)  list  See below. 
void sort()  list  See below. 
bool operator==(const list&,
const list&)
 ForwardContainer  Tests two lists for equality. This is a global function, not a member function. 
bool operator<(const list&,
const list&)
 ForwardContainer  Lexicographical comparison. This is a global function, not a member function. 
New members
These members are not defined in the ReversibleContainer, FrontInsertionSequence, and BackInsertionSequence requirements, but are specific to list
.
Function  Description 
void splice(iterator position,
list<T, Alloc>& x);
 position must be a valid iterator in *this , and x must be a list 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 . All iterators remain valid, including iterators that point to elements of x . [3] This function is constant time. 
void splice(iterator position,
list<T, Alloc>& x,
iterator i);
 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 . All iterators remain valid, including iterators that point to elements of x . [3] If position == i or position == ++i , this function is a null operation. This function is constant time. 
void splice(iterator position,
list<T, Alloc>& x,
iterator f, iterator l);
 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 . All iterators remain valid, including iterators that point to elements of x . [3] 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, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() comparisons for equality. 
template<class Predicate>
void remove_if(Predicate p);
[4]  Removes all elements *i such that p(*i) is true. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. 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, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size()  1 comparisons for equality. 
template<class BinaryPredicate>
void unique(BinaryPredicate p);
[4]  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, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size()  1 comparisons for equality. 
void merge(list<T, Alloc>& 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 . All iterators to elements in *this and x remain valid. This function is linear time: it performs at most size() + x.size()  1 comparisons. 
template<class BinaryPredicate>
void merge(list<T, Alloc>& x,
BinaryPredicate Comp);
[4]  Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThanComparable 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 . All iterators to elements in *this and x remain valid. 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 list. All iterators remain valid and continue to point to the same elements. [5] This function is linear time. 
void sort();  Sorts *this according to operator< . The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [6] The number of comparisons is approximately N log N , where N is the list 's size. 
template<class BinaryPredicate>
void sort(BinaryPredicate comp);
[4]  Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThanComparable 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. All iterators remain valid and continue to point to the same elements. [6] The number of comparisons is approximately N log N , where N is the list 's size. 
Notes
[1] A comparison with Vector
is instructive. Suppose that i
is a valid Vector<T>iterator
. If an element is inserted or removed in a position that precedes i
, then this operation will either result in i
pointing to a different element than it did before, or else it will invalidate i
entirely. (A Vector<T>iterator
will be invalidated, for example, if an insertion requires a reallocation.) However, suppose that i
and j
are both iterators into a Vector, and there exists some integer n
such that i == j + n
. In that case, even if elements are inserted into the vector and i
and j
point to different elements, the relation between the two iterators will still hold. A list
is exactly the opposite: iterators will not be invalidated, and will not be made to point to different elements, but, for list
iterators, the predecessor/successor relationship is not invariant.
[2] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of InputIterator. If your compiler does not yet support member templates, though, then the arguments must either be of type const value_type*
or of type list::const_iterator
.
[3] A similar property holds for all versions of insert()
and erase()
. List<T, Alloc>insert()
never invalidates any iterators, and list<T, Alloc>erase()
only invalidates iterators pointing to the elements that are actually being erased.
[4] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. You can only use this member function if your compiler supports member templates.
[5] If L
is a list, note that L.reverse()
and reverse(L.begin(), L.end())
are both correct ways of reversing the list. They differ in that L.reverse()
will preserve the value that each iterator into L
points to but will not preserve the iterators' predecessor/successor relationships, while reverse(L.begin(), L.end())
will not preserve the value that each iterator points to but will preserve the iterators' predecessor/successor relationships. Note also that the algorithm reverse(L.begin(), L.end())
will use T
's assignment operator, while the member function L.reverse()
will not.
[6] The sort
algorithm works only for RandomAccessIterator. In principle, however, it would be possible to write a sort algorithm that also accepted BidirectionalIterator. Even if there were such a version of sort
, it would still be useful for list
to have a sort
member function. That is, sort
is provided as a member function not only for the sake of efficiency, but also because of the property that it preserves the values that list iterators point to.
See also
BidirectionalIterator, ReversibleContainer, Sequence, Slist
, Vector
.