list class template — List container
template <typename T, typename Alloc = allocator<T> > class list{ public: // Types typedef typename Alloc::reference reference; typedef typename Alloc::const_reference const_reference; typedef . . . iterator; typedef . . . const_iterator; typedef . . . size_type; typedef . . . difference_type; typedef T value_type; typedef Alloc allocator_type; typedef typename Alloc::pointer pointer; typedef typename Alloc::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; // Construct/copy/destroy explicit list(const Alloc& = Alloc( )); explicit list(size_type n, const T& value = T( ), const Alloc& = Alloc( )); template <class InputIterator> list(InputIterator first, InputIterator last, const Alloc& = Alloc( )); list(const list<T,Alloc>& x); ~list( ); list<T,Alloc>& operator=(const list<T,Alloc>& x); template <class InputIterator> void assign(InputIterator first, InputIterator last); void assign(size_type n, const T& t); 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 sz, T c = T( )); // Element access reference front( ); const_reference front( ) const; reference back( ); const_reference back( ) const; // Modifiers void push_front(const T& x); void pop_front( ); void push_back(const T& x); void pop_back( ); iterator insert(iterator position, const T& x); void insert(iterator position, size_type n, const T& x); template <class InputIterator> void insert(iterator position, InputIterator first, InputIterator last); iterator erase(iterator position); iterator erase(iterator position, iterator last); void swap(list<T,Alloc>&); void clear( ); // List operations void splice(iterator position, list<T,Alloc>& x); void splice(iterator position, list<T,Alloc>& x, iterator i); void splice(iterator position, list<T,Alloc>& x, iterator first, iterator last); void remove(const T& value); template <class Predicate> void remove_if(Predicate pred); void unique( ); template <class BinaryPredicate> void unique(BinaryPredicate binary_pred); void merge(list<T,Alloc>& x); template <class Compare> void merge(list<T,Alloc>& x, Compare comp); void sort( ); template <class Compare> void sort(Compare comp); void reverse( ); };
The list
class template is
one of the standard container types, like deque
and vector
. A list
stores a sequence of items such that
inserting or erasing an item at any position requires constant time.
The list
template supports all
the usual operations for a sequence container plus some functions
that are unique to list
.
When an item is erased from the list (by calling pop_back
, erase
, remove
, etc.), all iterators that point to
that item become invalid. All pointers and references to the item
become invalid. No other iterators, pointers, or references are
invalidated when inserting or erasing any items.
The size
function can have
constant or linear complexity. The standard encourages library
vendors to implement the list
class template so that size
has
constant complexity, but it permits worse performance (namely,
linear in the size of the list). If size
does not have constant complexity,
you should expect all versions of splice
to have constant complexity in all
cases. (The last constraint is not mandated by the standard, but by
common sense.)
The following are the member functions of list
:
explicit
list
(const Alloc& = Alloc(
))
Initializes an empty list that uses the given allocator.
explicit
list
(size_type n, const T& value = T(
), const Alloc& = Alloc( ))
Initializes a list that contains n
copies of value
.
template < typename
InputIterator>
, list
(InputIterator first, InputIterator last, const
Alloc& = Alloc( ))
Initializes the list with a copy of the items in the
range [first
, last
), unless InputIterator
is an integral type,
in which case the list is constructed as though the arguments
were cast:
list(static_cast<size_type>(first), static_cast<value_type>(last), alloc);
list
(const list<T,Alloc>&
x)
Constructs a copy of the contents and allocator of the
list x
.
list<T,Alloc>&
operator=
(const
list<T,Alloc>& x)
Replaces the list's contents with copies of the contents
of x
.
template <typename
InputIterator>
, void
assign
(InputIterator first,
InputIterator last)
Replaces the list's contents with the items in the range
[first
, last
), unless InputIterator
is an integral type,
in which case the arguments are interpreted as though they
were cast:
assign(static_cast<size_type>(first), static_cast<value_type>(last));
void
assign
(size_type n, const T&
value)
Replaces the list's contents with n
copies of value
.
reference
back
( )
, const_reference
back
( )
const
Returns the last item in the list. The behavior is undefined if the list is empty.
iterator
begin
( )
, const_iterator
begin
( )
const
Returns an iterator that points to the first item in the list.
void
clear
( )
Erases all the items in the list, invalidating all iterators that point to the list.
bool
empty
( )
const
Returns true
if the
list is empty. Note that empty(
)
has constant complexity even if size( )
does not.
iterator
end
( )
, const_iterator
end
( )
const
Returns an iterator that points one past the last item in the list.
iterator
erase
(iterator
position)
, iterator
erase
(iterator first, iterator
last)
Erases the item at position
or all the items in the
range [first
, last
).
reference
front
( )
, const_reference
front
( )
const
Returns the first item in the list. The behavior is undefined if the list is empty.
allocator_type
get_allocator
( )
const
Returns the list's allocator.
iterator
insert
(iterator position,
const T& x)
, void
insert
(iterator position,
size_type n, const T& x)
, template <typename
InputIterator>
, void
insert
(iterator position,
InputIterator first, InputIterator last)
Inserts one or more items before position
. The performance is linear
in the number of items inserted, and the T
copy constructor is invoked once
for each item inserted in the list. The first form inserts the
item x
; the second form
inserts n
copies of
x
; the third form copies
the items in the range [first
, last
), unless InputIterator
is an integral type,
in which case the arguments are interpreted as though they
were cast:
insert(position, static_cast<size_type>(first), static_cast<value_type>(last));
If an exception is thrown, such as bad_alloc
when there is insufficient
memory for a new element, the list is unchanged.
size_type
max_size
( )
const
Returns the size of the largest possible list.
void
merge
(list<T,Alloc>& x)
, template <class
Compare>
, void
merge
(list<T,Alloc>&
x, Compare comp)
Merges another sorted list, x
, into the current list, which must
also be sorted. Items are erased from x
, so after merge
returns, x
is empty. Items are compared using
the <
operator or
comp
. The same function
used to sort the items must be used to compare items. The
merge is stable, so the relative order of items is unchanged;
if the same item is already in the list and in x
, the item from x
is added after the item already in
the list.
The performance of the merge is linear: exactly size( )
+
x.size( )
-
1
comparisons
are performed.
void
pop_back
( )
Erases the last item from the list. The behavior is undefined if the list is empty.
void
pop_front
( )
Erases the first item from the list. The behavior is undefined if the list is empty.
void
push_back
(const T&
x)
Inserts x
at the end
of the list.
void
push_front
(const T&
x)
Inserts x
at the
beginning of the list.
reverse_iterator
rbegin
( )
, const_reverse_iterator
rbegin
( )
const
Returns a reverse iterator that points to the last item in the list.
void
remove
(const T&
value)
Erases all occurrences of value
from the list. The performance
is linear; exactly size( )
comparisons are performed.
template <typename
Predicate>
, void
remove_if
(Predicate
pred)
Erases all items for which pred(item)
returns true. The
performance is linear: pred
is called exactly size( )
times.
reverse_iterator
rend
( )
, const_reverse_iterator
rend
( )
const
Returns a reverse iterator that points to one position before the first item in the list.
void
resize
(size_type sz, T c = T(
))
Changes the size of the list to n
. If n
> size( )
, one or more copies of
c
are added to the end of
the list to reach the desired size. If the new size is smaller
than the current size, elements are erased from the end to
reach the new size.
void
reverse
( )
Reverses the order of the entire list. The performance is linear.
size_type
size
( )
const
Returns the number of elements in the list. The
complexity of size( )
can
be constant or linear, depending on the implementation.
void
sort
( )
, template <typename
Compare>
, void
sort
(Compare comp)
Sorts the items in the list, comparing items with the
<
operator or by calling
comp
. The sort is stable,
so the relative positions of the items do not change. The
performance is N
log
N
, in which N
is size(
)
.
void
splice
(iterator position,
list<T,Alloc>& x)
, void
splice
(iterator position,
list<T,Alloc>& x, iterator i)
, void
splice
(iterator position,
list<T,Alloc>& x, iterator first, iterator
last)
Moves one or more items from x
, inserting the items just before
position
. The first form
moves every item from x
to
the list. The second form moves the item at position i
. The third form moves all items in
the range [first
, last
); position
must not be in that range.
The third form requires no more than linear time when &x
!=
this
; all other cases work in
constant time. If size( )
has linear complexity, you should expect splice( )
to have constant
complexity in all cases.
void
swap
(list<T,Alloc>& x)
Swaps all the items in this list with all the items in
x
. The performance should
be constant.
void
unique
( )
, template <typename
BinaryPredicate>
, void
unique
(BinaryPredicate
pred)
Erases adjacent duplicate items from the list. Items are
compared with the ==
operator or by calling pred
. When adjacent equal items are
found in the list, the first one is retained, and the second
and subsequent items are erased. The performance is linear:
size( )
-
1
comparisons are performed (unless
the list is empty).