Standard C++ Library User Guide and Tutorial

Type Definitions
The class list includes a number of type definitions. The most common use for these is in declaration
statements. For example, an iterator for a list of integers can be declared as follows:
list<int>::iterator location;
In addition to iterator, the following types are defined:
value_type The type associated with the elements the list maintains.
const_iterator An iterator that does not allow modification of the underlying sequence.
reverse_iterator An iterator that moves in a backward direction.
const_reverse_iterator A combination constant and reverse iterator.
reference A reference to an underlying element.
const_reference A reference to an underlying element that will not permit the element to be
modified.
size_type An unsigned integer type, used to refer to the size of containers.
difference_type A signed integer type, used to describe distances between iterators.
Placing Elements into a List
Values can be inserted into a list in a variety of ways. Elements are most commonly added to the
front or back of a list. These tasks are provided by the push_front() and push_back() operations,
respectively. These operations are efficient (constant time) for both types of containers.
list_seven.push_front(1.2);
list_eleven.push_back (Widget(6));
In a previous discussion (Declaration and Initialization of Lists) we noted how, with the aid of an
insert iterator and the copy() or generate() generic algorithm, values can be placed into a list at a
location denoted by an iterator. There is also a member function, named insert(), that avoids the need
to construct the inserter. As we will describe shortly, the values returned by the iterator generating
functions begin() and end() denote the beginning and end of a list, respectively. An insert using one
of these is equivalent to push_front() or push_back(), respectively. If we specify only one iterator, the
default element value is inserted.
// insert default type at beginning of list
list_eleven.insert(list_eleven.begin());
// insert widget 8 at end of list
list_eleven.insert(list_eleven.end(), Widget(8));
Iteration Invalidation
An iterator can denote a location in the middle of a list. There are several ways to produce this
iterator. For example, we can use the result of any of the searching operations described in Chapter
13 (Searching Opertations), such as an invocation of the find() generic algorithm. The new value is
inserted immediately prior to the location denoted by the iterator. The insert() operation itself returns