C++ Notes: STL: list class

The list template class is based on a doubly-linked list, and has all the functions of vector except capacity, reserve, at, and operator[].

Assume that T is some type (eg, int). Assume the following declarations:

   T e;
list<T> v, lst2;
list<T>::iterator iter, iter2, beg, end;
int i, , n, size;

Common constructors, functions, operators, etc

Result Method
Description
Constructors and destructors
  list<T> lst;
Creates an empty list for elements of type T.
  list<T> lst(n, e);
Creates list of n copies of e.
  list<T> lst(beg, end);
Creates list with copies from range beg..end.
  lst.~list<T>();
Destroys all elems and frees memory.
Entire list
i =  lst.size(); V
Number of elements.
b =  lst.empty(); V
True if empty. Use instead of lst.size()==0, which may traverse entire list in some implementations.
lst =  lst2; V
Assigns lst2 to lst.
  lst.clear(); V
Removes all elements.
  lst.assign(n, e); V
Replaces existing elements with n copies of e.
  lst.sort(); a
Sorts list (stable) with <.
  lst.unique(); a
Assumes lst is sorted. Removes subsequent consecutive equal values.
  lst.reverse(); a
Reverses lst.
  lst.merge(lst2);
Assumes lst and lst2 are sorted. Merges lst2 into lst to remain sorted.
Front and back - no random access
e =  lst.front(); V
First element.
e =  lst.back(); V
Last element.
  lst.push_front(e);
Adds e to front of lst.
  lst.pop_front();
Removes first element of lst.
  lst.push_back(e); V
Adds e to end of lst.
  lst.pop_back(); V
Removes last element of lst.
Iteration based
iter2 =  lst.assign(beg, end); V
Sets list to copies from range beg..end.
iter2 =  lst.insert(iter, e); V
Inserts copy of e at iter position, returns its position.
  lst.insert(iter, n, e); V
Inserts n copies of e starting at iter position.
  lst.insert(iter, beg, end); V
Inserts copies in range beg..end, starting at iter.
iter2 =  lst.erase(iter); V
Removes element at iter, returns position of next.
iter2 =  lst.erase(beg, end); V
Removes beg...end, returns position of next.
  lst.splice(iter, lst2);
Inserts copies of lst2 elements before iter.
  lst.splice(iter, lst2, beg);
Inserts before iter copies from lst2, beginning at beg.
  lst.splice(iter, lst2, beg, end);
Inserts before iter copies from beg...end of lst2.
Iterators
beg =  lst.begin(); V
Returns iterator to first element.
end =  lst.end(); V
Returns iterator to after last element.
beg =  lst.rbegin(); V
Returns iterator to first (in reverse order) element.
end =  lst.rend(); V
Returns iterator to after last (in reverse order) element.
Value based
  lst.remove(e);
Removes all elements from lst with value e.

Iterators

Lists support bidirectional iterators, but not random-access iterators as vectors do.