13.33 <list>

The <list> header is one of the standard container template headers. It declares the list class template and a few global function templates that operate on list objects.

A list is a sequence container that has constant performance when adding to or removing from any point in the container. It supports bidirectional iterators, but not random access. Although the standard does not mandate any particular implementation, the obvious choice is to use a doubly-linked list to implement the list class template.

See Chapter 10 for information about containers.

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( ).

You must call the sort member function to sort a list. The generic sort algorithm requires a random access iterator, but list provides only a bidirectional iterator.

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).

13.33 <list>

See Also

See Also

See Also

See Also