In this section, each of the member functions provided by the list datatype are described in more detail. These member functions provide the basic operations for lists. They can be greatly extended through the generic algorithms described in Chapter 13.
A list may contain elements of a primitive language type, such as an int or double, a pointer type, or a user-defined type. A user-defined type must implement a copy constructor, as this constructor is used to initialize newly created elements.
There are a variety of ways to declare a list. In the simplest form, a list is declared by simply stating the type of element the list will maintain. A list declared in this fashion initially contains no elements:
std::list<int> list_one; std::list<Widget*> list_two; std::list<Widget> list_three;
NOTE -- If you declare a container as holding pointers, you are responsible for managing the memory for the objects pointed to. The container classes will not automatically free memory for these objects when an item is erased from the container.
An alternative form of declaration creates a collection that initially contains some number of equal elements. The constructor takes two arguments, a size and an initial value. The second argument is optional if the contained type has a default constructor. If only the number of initial elements to be created is given, these values are initialized with the default constructor; otherwise the elements are initialized with the value of the second argument:
std::list<int> list_four (5); // five elements,
// each initialized to zero
std::list<double> list_five (4, 3.14); // 4 values,
// each initially 3.14
std::list<Widget> list_six (4); // 4 elements, each created using
// default constructor for Widget
std::list<Widget> list_six (3, Widget(7)); // 3 elements, each a
// copy of Widget(7)
lists can also be initialized using elements from another collection, with a beginning and ending iterator pair. The arguments can be any form of iterator; thus collections can be initialized with values drawn from any of the container classes in the C++ Standard Library that support iterators.
std::list<double> list_seven(aVector.begin(), aVector.end());
The insert() operation can also be used to place values denoted by an iterator into a list (Section 6.2.3). Insert iterators can be used to initialize a list with a sequence of values produced by a generator (Section 13.2.3). This is illustrated by the following:
std::list<int> list_nine;
// initialize list 1 2 3 ... 7
std::generate_n(std::inserter(list_nine, list_nine.begin()),
7, iotaGen(1));
A copy constructor can be used to initialize a list with values drawn from another list. The assignment operator performs the same actions. In both cases the assignment operator for the element type is used to copy each new value.
std::list<int> list_ten (list_nine); // copy constructor std::list<Widget> list_eleven; std::list_eleven = list_six; // values copied by assignment
The assign() member function is similar to the assignment operator, but is more versatile and, in some cases, requires more arguments. Like an assignment, the existing values in the container are deleted, and replaced with the values specified by the arguments. If a destructor is provided for the container element type, it is invoked for the elements being removed. There are two forms of assign():
The first form takes two iterator arguments that specify a sub-sequence of an existing container. The values from this sub-sequence then become the new elements in the receiver.
The second form takes a count and an optional value of the container element type. After the call the container holds the number of elements specified by the count, which is equal to either the default value for the container type or the initial value specified. The initial value must be specified if the contained type does not have a default constructor.
list_six.assign(list_ten.begin(), list_ten.end()); list_four.assign(3, 7); // three copies of value seven list_five.assign(12); // twelve copies of value zero
Finally, two lists can exchange their entire contents by means of the operation swap(). The argument container takes on the values of the receiver, while the receiver assumes those of the argument. A swap is very efficient, and should be used in preference to an explicit element-by-element transfer where appropriate.
list_ten.swap(list_nine); // exchange lists nine and ten
The class list includes a number of type definitions, most commonly used in declaration statements. For example, an iterator for a list of integers can be declared as follows:
std::list<int>::iterator location;
In addition to iterator, list defines the following types:
| Type | Definition |
value_type | The type of the elements maintained by the list. |
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. |
pointer | A pointer to an underlying element |
const_pointer | A constant pointer to an underlying element. |
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. |
allocator_type | The allocator type used for all storage management by the 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 Section 6.2.1 we noted how values can be placed into a list at a location denoted by an iterator with the aid of an insert iterator and the std::copy() or std::generate() generic algorithm. 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));
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 Section 13.3, such as an invocation of the find() generic algorithm:
// find the location of the first occurrence of the // value 5 in list std::list<int>::iterator location = std::find(list_nine.begin(), list_nine.end(), 5); // and insert an 11 immediately before it location = list_nine.insert(location, 11);
Here the new value is inserted immediately prior to the location denoted by the iterator. The insert() operation itself returns an iterator denoting the location of the inserted value. This result value was ignored in the invocations shown above.
NOTE -- Unlike a vector or deque, insertions or removals from the middle of a list will not invalidate references or pointers to other elements in the container. This property can be important if two or more iterators are being used to refer to the same container.
It is also possible to insert a fixed number of copies of an argument value. This form of insert() does not yield the location of the values:
line_nine.insert(location, 5, 12); // insert five twelves
Finally, an entire sequence denoted by an iterator pair can be inserted into a list. Again, no value is returned as a result of the insert().
// insert entire contents of list_ten into list_nine list_nine.insert(location, list_ten.begin(), list_ten.end());
There are several ways to splice one list into another. A splice differs from an insertion in that the item is simultaneously added to the receiver list and removed from the source list. For this reason, a splice can be performed efficiently, and should be used whenever appropriate. As with an insertion, the member function splice() uses an iterator to indicate the location in the receiver list where the splice should be made. The argument is either an entire list, a single element in a list (denoted by an iterator), or a sub-sequence of a list (denoted by a pair of iterators).
// splice the last element of list ten
list_nine.splice(location, list_ten, list_ten.end());
// splice all of list ten
list_nine.splice(location, list_ten);
// splice list 9 back into list 10
list_ten.splice(list_ten.begin(), list_nine,
list_nine.begin(), location);
Two ordered lists can be combined into one using the merge() operation. Values from the argument list are merged into the ordered list, leaving the argument list empty. The merge is stable; that is, elements retain their relative ordering from the original lists. As with the generic algorithm of the same name (Section 14.5), two forms are supported. The first form uses the operator<() defined for the contained type. The second form uses the binary function supplied as argument to order values, but not all compilers suppor the second form. If the second form is desired and not supported, the more general generic algorithm can be used, although this is slightly less efficient:
// merge with explicit compare function
list_eleven.merge(list_six, widgetCompare);
// similar merge using the generic algorithm
std::list<Widget> list_twelve;
std::merge (list_eleven.begin(), list_eleven.end(),
list_six.begin(), list_six.end(),
inserter(list_twelve, list_twelve.begin()),
widgetCompare);
list_eleven.swap(list_twelve);
Just as there are a number of different ways to insert an element into a list, there are a variety of ways to remove values from a list. The most common operations used to remove a value are pop_front() or pop_back(), which delete the single element from the front or the back of the list, respectively. If a destructor is defined for the element type, it is invoked as the element is removed. These member functions simply remove the given element, and do not themselves yield a result. To retrieve the values before deletion, use the member functions front() or back().
The erase() operation can be used to remove a value denoted by an iterator. For a list, the argument iterator and any other iterators that denote the same location become invalid after the removal, but iterators denoting other locations are unaffected. We can also use erase() to remove an entire sub-sequence denoted by a pair of iterators. The values beginning at the initial iterator and up to, but not including, the final iterator are removed from the list. Erasing elements from the middle of a list is an efficient operation, unlike erasing elements from the middle of a vector or a deque:
list_nine.erase (location);
// erase values between the first occurrence of 5
// and the following occurrence of 7
std::list<int>::iterator location =
find(list_nine.begin(), list_nine.end(), 5);
std::list<int>::iterator location2 =
find(location, list_nine.end(), 7);
list_nine.erase(location, location2);
The remove() member function removes all occurrences of a given value from a list. A variation, remove_if(), removes all values that satisfy a given predicate. An alternative to either of these are the remove() or remove_if() generic algorithms (Section 13.5.1). The generic algorithms do not reduce the size of the list; instead they move the elements to be retained to the front of the list, leave the remainder of the list unchanged, and return an iterator denoting the location of the first unmodified element. This value can be used in conjunction with the erase() member function to remove the remaining values.
list_nine.remove(4); // remove all fours
list_nine.remove_if(divisibleByThree); // remove any div by 3
// the following is equivalent to the above
std::list<int>::iterator location3 =
std::remove_if(list_nine.begin(), list_nine.end(),
divisibleByThree);
list_nine.erase(location3, list_nine.end());
The member function unique() erases duplicate elements from a list. To do this, the function iterates over the list and removes every element that is equal to the preceeding element. An alternative version takes a binary function and compares adjacent elements using the function, removing the second value in those situations where the function yields a true value. The more general unique() generic algorithm can also be used (Section 13.5.2). In the following example, the binary function is the greater-than operator, which removes all elements smaller than a preceding element:
// remove first from consecutive equal elements
list_nine.unique();
// explicitly give comparison function
list_nine.unique(greater<int>());
// the following is equivalent to the above, using the
// generic algorithm unique() rather than the list member
// function
std::list<int>::iterator location3 =
std::unique(list_nine.begin(),
list_nine.end(), greater<int>());
list_nine.erase(location3, list_nine.end());
The member function size() returns the number of elements being held by a container. The member function empty() returns true if the container is empty, and is more efficient than comparing the size() against 0.
std::cout << "Number of elements: "
<< list_nine.size () << std::endl;
if ( list_nine.empty() )
std::cout << "list is empty " << std::endl;
else
std::cout << "list is not empty " << std::endl;
The member function resize() changes the size of the list to the value specified by the argument. Values are either added or erased from the end of the collection as necessary. An optional second argument can be used to provide the initial value for any new elements added to the collection:
// become size 12, adding values of 17 if necessary list_nine.resize(12, 17);
The member functions front() and back() return, but do not remove, the first and last items in the container, respectively. A list does not provide random access. Access to elements other than the first and last elements is possible only by removing elements until the desired element becomes the front or back element, or by using iterators.
There are three types of iterators that can be constructed for lists. The functions begin() and end() construct iterators that traverse the list in forward order. For the list datatype, begin() and end() create bidirectional iterators. The alternative functions rbegin() and rend() construct iterators that traverse in reverse order, moving from the end of the list to the front.
The list datatypes do not directly provide any method that can be used to determine if a specific value is contained in the collection. However, either of the generic algorithms std::find() or std::count() can be used for this purpose (Section 13.3.1 and Section 13.6.1). For example, to test whether an integer list contains the element 17:
find(vec_five.begin(), vec_five.end(), 17);
If your compiler does not support partial specialization, then you must use the following interface instead:
// test for inclusion using count
int num = 0;
std::count(list_five.begin(), list_five.end(), 17, num);
if (num > 0)
std::cout << "contains a 17" << std::endl;
else
std::cout << "does not contain a 17" << std::endl;
// test for inclusion using find
if (std::find(list_five.begin(), list_five.end(), 17) !=
list_five.end())
std::cout << "contains a 17" << std::endl;
else
std::cout << "does not contain a 17" << std::endl;
The member function sort() places elements into ascending order. If a comparison operator other than < is desired, it can be supplied as an argument.
list_ten.sort(); // order elements
list_twelve.sort(widgetCompare); // sort with widget compare
// function
Once a list has been sorted, a number of the generic algorithms for ordered collections can be used with lists (Chapter 14).
The various forms of searching functions described in Chapter 13.3, namely std::find(), std::find_if(), std::adjacent_find(), std::mismatch(), std::max_element(), std::min_element(), or std::search(), can be applied to list. In all cases the result is an iterator, which can be dereferenced to discover the denoted element, or used as an argument in a subsequent operation.
NOTE -- The searching algorithms in the C++ Standard Library always return the end of range iterator if no element matching the search condition is found. Unless the result is guaranteed to be valid, it is a good idea to check for the end of range condition.
A number of operations can be applied to lists in order to transform them in place. Some of these are provided as member functions. Others make use of some of the generic functions described in Chapter 13.
For a list, the member function reverse() reverses the order of elements in the list:
list_ten.reverse(); // elements are now reversed
The generic algorithm std::transform() can be used to modify every value in a container by simply using the same container as both input and result for the operation (Section 13.7.1). For example, the following code increments each element of a list by one:
std::transform(list_ten.begin(), list_ten.end(), list_ten.begin(),
std::bind1st(std::plus<int>(), 1));
To construct the necessary unary function, the first argument of the binary integer addition function is bound to the value 1 using the bind1st function adapter (Section 3.5). The version of std::transform() that manipulates two parallel sequences can also be used this way.
Similarly, the functions std::replace() and std::replace_if() can be used to replace elements of a list with specific values (Section 13.4.2). Rotations and partitions can also be performed with lists (Section 13.4.3 and Section 13.4.4):
// find the location of the value 5, and rotate around it
std::list<int>::iterator location =
std::find(list_ten.begin(), list_ten.end(), 5);
std::rotate(list_ten.begin(), location, list_ten.end());
// now partition using values greater than 7 std::partition(list_ten.begin(), list_ten.end(),
std::bind2nd(std::greater<int>(), 7));
The functions std::next_permutation() and std::prev_permutation() can be used to generate the next permutation (or previous permutation) of a collection of values (Section 13.4.5):
std::next_permutation(list_ten.begin(), list_ten.end());
The algorithm std::for_each() applies a function to every element of a collection (Section 13.8). An illustration of this use is given in the radix sort example program in the section on the deque data structure (Section 7.3).
The std::accumulate() generic algorithm reduces a collection to a scalar value (Chapter 13.6.2). This can be used, for example, to compute the sum of a list of numbers. A more unusual use of std::accumulate() is illustrated in the radix sort example from Section 7.3:
std::cout << "Sum of list is: "
<< std::accumulate(list_ten.begin(),list_ten.end(),0)
<< std::endl;
Two lists can be compared against each other using the std::lexicographical_compare() algorithm (Section 13.6.5). The lists are equal if they are the same size and all corresponding elements are equal. A list is less than another list if it is lexicographically smaller.