C++ Reference Material
The STL list Container

The list class implements a sequential container with fast insertions and deletions anywhere, but without random access to its components values.

Constructors and destructor

Default Constructor

list<T> lst;
Construct an empty list lst which can hold values of type T.

Copy Constructor

There is, of course, only one copy constructor, but there are two syntactic forms that invoke it, and both are shown.

list<T> lst(otherList);
Construct lst as a copy of otherList, whose component type must be T.
list<T> lst = otherList;
Copy constructor (alternate usage syntax).

Other Constructors

list<T> lst(num);
Construct a list lst of size num containing num values, each equal to the default value of type T.
list<T> lst(num, val);
Construct a list lst of size num containing num values, each equal to val, which must be of type T, and which may be supplied by a variable, a literal or named constant, or a function call.
list<T> lst(inIterBegin, inIterEnd);
Construct lst containing values from the range [inIterBegin,inIterEnd) in another (not necessarily list) container, but whose component type is the same as the component type of lst.

Destructor

lst.~list<T>()
Destroy all components of lst and free the associated memory.

Overloaded operators

Assignment operator

lst1 = lst2
Assign lst2 to lst1, and return the common value. The list on the left of an assignment receives the values and size of the one on the right.

Relational operators

Lists are compared in the "lexicographic ordering" sense. This essentially means that the two lists are compared by comparing their values pairwise, starting at the beginning, with each comparison looking at two values in corresponding positions, until a determination of the relationship between the two lists can be made. Only lists of the same component type can be compared of course, and the == and < operators must be defined for the component type.

lst1 == lst2
Return true if lst1 and lst2 have the same component type and the same size, and the components in each pair of corresponding locations have the same value; otherwise return false.
lst1 != lst2
Return true if lst1==lst2 returns false; otherwise return false.
lst1 < lst2
Return true if, in the pairwise comparison of values from lst1 and lst2, in the first pair in which the two values differ, the one from lst1 is less than the one from lst2; otherwise return false.
lst1 <= lst2
Return true if either lst1<lst2 or lst1==lst2 is true; otherwise return false.
lst1 > lst2
Return true if lst2<lst1 is true; otherwise return false.
lst1 >= lst2
Return true if either lst1>lst2 or lst1==lst2 is true, otherwise return false.

Member functions for accessing values

Each of the member functions in this section has both a const and a non-const version.

lst.front()
Return a reference (or const_reference) to the first component of lst.
lst.back()
Return a reference (or const_reference) to the last component of lst.
lst.begin()
Return an iterator (or const_iterator) pointing to the first component of lst.
lst.end()
Return an iterator (or const_iterator) pointing to one-past-the-last component of lst.
lst.rbegin()
Return a reverse_iterator (or const_reverse_iterator) pointing to the last component of lst.
lst.rend()
Return a reverse_iterator (or const_reverse_iterator) pointing to one-before-the-first component of lst.

Member functions for reporting status

lst.max_size()
Return a value of type size_type giving the maximum possible size of lst, which will depend on the size of the component type T of the list object, and the amount of available memory.
lst.size()
Return a value of type size_type giving the number of values currently in lst.
lst.empty()
Return true if lst is empty (contains zero values); otherwise return false.

Member functions for inserting one or more values

lst.assign(num, val)
Assign num copies of val to lst, overwriting the entire previous contents of lst.
lst.assign(inIterBegin, inIterEnd)
Assign to lst the values from the range [inIterBegin,inIterEnd) in another (not necessarily list) container, but whose values are also of type T, overwriting the entire previous contents of lst.
lst.insert(iter, val)
Insert val into lst immediately before the value pointed to by iter, and return an iterator pointing at the new component with value val.
lst.insert(iter, num, val)
Insert num copies of val into lst, immediately before the value pointed to by iter.
lst.insert(iter, inIterBegin, inIterEnd)
Insert into lst, immediately before the value pointed to by iter, values from the range [inIterBegin,inIterEnd) in another (not necessarily list) container, but whose values must be of the same type as the values of lst.
lst.push_back(val)
Add val to the end of lst, increasing the size of lst by one.
lst.push_front(val)
Add val to the front of lst, increasing the size of lst by one.

Member functions for deleting one or more values

lst.clear()
Delete all values of lst. The size of lst is reduced to zero.
lst.erase(iter)
Delete the value of lst pointed to by iter and return an iterator pointing at the following value, or to one-past-the-last if the value deleted was the last one. The size of lst is reduced by one.
lst.erase(iterBegin, iterEnd)
Delete all values of lst from the range [iterBegin,iterEnd) and return iterEnd. The size of lst is reduced by iterEnd-iterBegin (a value of type difference_type).
lst.pop_back()
Delete the last value of lst. The size of lst is reduced by one.
lst.pop_front()
Delete the first value of lst. The size of lst is reduced by one.
lst.remove(val)
Remove all components with value val.
lst.remove_if(unPred)
Remove all values for which the unary predicate function unPred returns true.
lst.unique()
Remove all but one of any group of consecutive components containing duplicate items.
lst.unique(binPred)
Same as preceding unique() but uses binPred to determine when two component values are duplicates.

Member functions for merging and splicing

lst.merge(otherList)
Merge the list contained in otherList with the invoking list and clear otherList. (Both lists are assumed to be ordered and the result is also ordered.)
lst.merge(otherList, binPred)
Same as preceding merge(), except that in this version a comparitor (comparison function) binPred is provided to determine when one component value precedes another.
lst.splice(iter, otherList)
Remove all values from otherList and insert them just before location iter.
lst.splice(iter, otherList, otherIter)
Remove value pointed to by otherIter from otherList and insert it just before location iter.
lst.splice(iter, otherList, otherIterBegin, otherIterEnd)
Remove values from range [otherIterBegin,otherIterEnd) in otherList and insert them just before location iter.

Miscellaneous member functions

lst.resize(num)
Change size of lst to num. (If lst must be lengthened, default values of its component type are added to the end of lst. If lst is shortened, values at the end are lost.)
lst.resize(num, val)
Change size of lst to num. (If lst must be lengthened, copies of val are added to the end of lst. If lst is shortened, values at the end are lost, and the value of val is not used.)
lst.reverse()
Reverse the order of all components of a list.
lst.sort()
Sort the components of a list into ascending order.
lst.sort(binPred)
Sort the components of a list using the comparitor binPred to determine when one component value precedes another.
lst.swap(otherList)
Exchange values in lst with those in otherList. The sizes and capacities are swapped as well.
lst.getallocator()
Return the allocator of lst. (This is possibly the most infrequently used of all member functions of the list class.)

Miscellaneous notes

Implementation
Standard C++ does not say how the STL containers and algorithms must be implemented. It does, however, state certain constraints, such as complexity constraints, to which each implementation must adhere. Thus it is much better to base your programs on the STL's performance guarantees, rather than upon any assumption about how a particular feature, like the list class, may be implemented.
Some performance and usage issues
The following STL "best practice" applies to use of the list container: For those operations whose names are identical to the names of general STL algorithms (merge, remove, remove_if, reverse, sort, swap, and unique), the list-specific versions are to be preferred when working with lists. And, by the way, similar advice applies as well to other STL containers when a choice can be made between using a member function and using an algorithm.

The list<T>::iterator and list<T>::reverse_iterator iterators are bidirectional access iterators, the second-most powerful kind of STL iterator. The member function begin() returns an iterator pointing at the first element of the list, while end() is a member function returning an iterator pointing at the position "one past the end" of the list. Analogously, rbegin() and rend() return iterators pointing at the last and "one before the first" positions, respectively.

Note that the at() member function and index access via [ ] are not supported, but the bidirectional iterators supported by the list container do permit a different kind of access to any element in a list.

Neither inserting components into a list, nor deleting components from the list, will invalidate pointers, references or iterators to other components of that list.

A list is useful when the order of the components and fast insertion and deletion at arbitrary locations are important. If insertion and deletion only take place at the ends, lists are not as efficient as deques.

The list class is one of the three "sequential" container classes in the STL (the vector and the deque are the other two). Lists provide many of the same operations as vectors and deques. However, the list class also provides a number of "high-powered" list operations like splice and merge that are not found in the other sequence containers.

Sample programs

There are two groups of sample programs. The first group involves only STL lists and generic C++, while the second group involves other STL features in addition to lists. The programs should be studied in the sequence given, since the description of each new sample program in the sequence mentions only the new features illustrated for the first time in that particular program, and features seen in earlier sample programs will continue to reappear in later programs.

All of the programs have been compiled and run successfully under Microsoft Visual Studio .NET 2005, unless otherwise noted.

Programs involving only lists (and generic C++)

list01.cpp | Windows_executable | program_output (text)
Illustrates list constructors, list<T>::iterator, and the member functions begin() and end(). Also illustrates how ordinary array pointers can be used, in certain situations, in the same way that STL iterators are used.
list02.cpp | Windows_executable | program_output (text)
Illustrates member functions size() and empty().
list03.cpp | Windows_executable | program_output (text)
Illustrates member function max_size(), and how the maximum size for a list object depends on the size of its component type.
list04.cpp | Windows_executable | program_output (text)
Illustrates push_back() and push_front().
list05.cpp | Windows_executable | program_output (text)
Illustrates typical uses of the default (bidirectional) iterator for the list class, shows additional uses of member functions begin() and end(), and also shows the use of operators =, ++, --, != and * with list class iterators.
list06.cpp | Windows_executable | program_output (text)
Illustrates the default (bidirectional) list class iterator in additional situations, and shows the use of operators ->, and == with list class iterators.
list07.cpp | Windows_executable | program_output (text)
Illustrates reverse iterators for the list class, as well as member functions rbegin() and rend().
list08.cpp | Windows_executable | program_output (text)
Illustrates a typical use of a const iterator.
list09.cpp | Windows_executable | program_output (text)
Illustrates member functions front() and back().
list10.cpp | Windows_executable | program_output (text)
Illustrates the overloaded assignment operator = and the assign() member function.
list11.cpp | Windows_executable | program_output (text)
Illustrates the insert() member function.
list12.cpp | Windows_executable | program_output (text)
Illustrates the clear(), erase(), pop_back() and pop_front() member functions.
list13.cpp | Windows_executable | program_output (text)
Illustrates the resize() member function.
list14.cpp | Windows_executable | program_output (text)
Illustrates the swap() member function.
list15.cpp | Windows_executable | program_output (text)
Illustrates the remove() and remove_if() member functions.
list16.cpp | Windows_executable | program_output (text)
Illustrates the unique() member function.
list17.cpp | Windows_executable | program_output (text)
Illustrates the reverse() and sort() member functions.
list18.cpp | Windows_executable | program_output (text)
Illustrates the merge() member function.
list19.cpp | Windows_executable | program_output (text)
Illustrates the splice() member function.

Programs involving additional list features and lists in combination with other STL features

list_a.cpp | Windows_executable | program_output (text)
Illustrates the use of stream iterators and the copy algorithm for I/O of list values.
list_b.cpp | Windows_executable | program_output (text)
Illustrates how to display the name of the underlying type represented by each typedef defined by a list class.
list_c.cpp | Windows_executable | program_output (text)
Illustrates initialization of a list with values from non-list containers (in this case, a vector and a deque).

Member function prototypes

For enhanced readability in each of the prototypes given below, each parameter in each parameter list appears on a separate line. Also, some formatting liberties are taken, in the interest of greater readability. For example, rather than aligning all prototypes at the left margin, const and non-const versions of a member function are aligned in such a way as to allow the reader to more easily compare the two visually.

Template specification for the list class

template<class T,
         class Allocator = allocator<T> >
class list { ... }

Constructors

explicit list(const Allocator& a = Allocator());

explicit list(size_type num,
              const T& val = T(),
              const Allocator& a = Allocator());
                

template<class InIterator>
list(InIterator inIterBegin,
     InIterator inIterEnd,
     const Allocator& a = Allocator());

Copy Constructor

list(const list<T, Allocator>& otherList);

Destructor

~list();

assign

void assign(size_type num,
            const T& val);

template<class InIterator>
void assign(InIterator inIterBegin,
            InIterator inIterEnd);

back

      reference back();
const_reference back() const;

begin

      iterator begin();
const_iterator begin() const;

clear

void clear();

empty

bool empty() const;

end

      iterator end();
const_iterator end() const;

erase

iterator erase(iterator iter);
iterator erase(iterator iterBegin,
               iterator iterEnd);

front

      reference front();
const_reference front() const;

get_allocator

allocator_type get_allocator() const;

insert

iterator insert(iterator iter,
                const T& val);

void insert(iterator iter,
            size_type num,
            const T& val);

template<class InIterator>
void insert(iterator iter,
            InIterator inIterBegin,
            InIterator inIterEnd);

max_size

size_type max_size() const;

merge

void merge(list<T, Allocator>& otherList)

template<typename BinaryPred>
void merge(list<T, Allocator>& otherList,
           BinaryPred binPred)

pop_back

void pop_back();

pop_front

void pop_front();

push_back

void push_back(const T& val);

push_front

void push_front(const T& val);

rbegin

      reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

remove

void remove(const T& val);

remove_if

template<typename UnaryPred>
void remove_if(UnaryPred unPred);

rend

      reverse_iterator rend();
const_reverse_iterator rend() const;

resize

void resize(size_type num,
            T val = T());

reverse

void reverse();

size

size_type size() const;

sort

void sort();

template<typename BinaryPred>
void sort(BinaryPred binPred);

splice

void splice(iterator iter,
            list<T, Allocator>& otherList);

void splice(iterator iter,
            list<T, Allocator>& otherList,
            iterator otherIter);

void splice(iterator iter,
            list<T, Allocator>& otherList,
            iterator otherIterBegin,
            iterator otherIterEnd);

swap

void swap(list<T, Allocator>& otherList);

unique

void unique();

template<typename BinaryPred>
void unique(BinaryPred binPred);