The list sequence container (from header <list>) allows insertion and deletion operations at any location in the container. If most of the insertions and deletions occur at the ends of the container, the deque
data structure (Section 15.5.3) provides a more efficient implementation. Class template list
is implemented as a doubly linked list—every node in the list
contains a pointer to the previous node in the list
and to the next node in the list
. This enables class template list
to support bidirectional iterators that allow the container to be traversed both forward and backward. Any algorithm that requires input, output, forward or bidirectional iterators can operate on a list
. Many list
member functions manipulate the elements of the container as an ordered set of elements.
C++11 now includes the new forward_list sequence container (header <forward_list>
), which is implemented as a singly linked list—every node in the list
contains a pointer to the next node in the list
. This enables class template list
to support forward iterators that allow the container to be traversed in the forward direction. Any algorithm that requires input, output or forward iterators can operate on a forward_list
.
In addition to the member functions in Fig. 15.2 and the common member functions of all sequence containers discussed in Section 15.5, class template list
provides other member functions, including splice
, push_front
, pop_front
, remove
, remove_if
, unique
, merge
, reverse
and sort
. Several of these member functions are list
-optimized implementations of the Standard Library algorithms presented in Chapter 16. Both push_front
and pop_front
are also supported by forward_list
and deque
. Figure 15.13 demonstrates several features of class list
. Remember that many of the functions presented in Figs. 15.10–15.11 can be used with class list
, so we focus on the new features in this example’s discussion.
1 // Fig. 15.13: fig15_13.cpp
2 // Standard library list class template.
3 #include <iostream>
4 #include <array>
5 #include <list> // list class-template definition
6 #include <algorithm> // copy algorithm
7 #include <iterator> // ostream_iterator
8 using namespace std;
9
10 // prototype for function template printList
11 template < typename T > void printList( const list< T > &listRef );
12
13 int main()
14 {
15 const size_t SIZE = 4;
16 array< int, SIZE > ints = { 2, 6, 4, 8 };
17 list< int > values; // create list of ints
18 list< int > otherValues; // create list of ints
19
20 // insert items in values
21 values.push_front( 1 );
22 values.push_front( 2 );
23 values.push_back( 4 );
24 values.push_back( 3 );
25
26 cout << "values contains: ";
27 printList( values );
28
29 values.sort(); // sort values
30 cout << "
values after sorting contains: ";
31 printList( values );
32
33 // insert elements of ints into otherValues
34 otherValues.insert( otherValues.cbegin(), ints.cbegin(), ints.cend() );
35 cout << "
After insert, otherValues contains: ";
36 printList( otherValues );
37
38 // remove otherValues elements and insert at end of values
39 values.splice( values.cend(), otherValues );
40 cout << "
After splice, values contains: ";
41 printList( values );
42
43 values.sort(); // sort values
44 cout << "
After sort, values contains: ";
45 printList( values );
46
47 // insert elements of ints into otherValues
48 otherValues.insert( otherValues.cbegin(), ints.cbegin(), ints.cend() );
49 otherValues.sort(); // sort the list
50 cout << "
After insert and sort, otherValues contains: ";
51 printList( otherValues );
52
53 // remove otherValues elements and insert into values in sorted order
54 values.merge( otherValues );
55 cout << "
After merge:
values contains: ";
56 printList( values );
57 cout << "
otherValues contains: ";
58 printList( otherValues );
59
60 values.pop_front(); // remove element from front
61 values.pop_back(); // remove element from back
62 cout << "
After pop_front and pop_back:
values contains: "
63 printList( values );
64
65 values.unique(); // remove duplicate elements
66 cout << "
After unique, values contains: ";
67 printList( values );
68
69 // swap elements of values and otherValues
70 values.swap( otherValues );
71 cout << "
After swap:
values contains: ";
72 printList( values );
73 cout << "
otherValues contains: ";
74 printList( otherValues );
75
76 // replace contents of values with elements of otherValues
77 values.assign( otherValues.cbegin(), otherValues.cend() );
78 cout << "
After assign, values contains: ";
79 printList( values );
80
81 // remove otherValues elements and insert into values in sorted order
82 values.merge( otherValues );
83 cout << "
After merge, values contains: ";
84 printList( values );
85
86 values.remove( 4 ); // remove all 4s
87 cout << "
After remove( 4 ), values contains: ";
88 printList( values );
89 cout << endl;
90 } // end main
91
92 // printList function template definition; uses
93 // ostream_iterator and copy algorithm to output list elements
94 template < typename T > void printList( const list< T > &listRef )
95 {
96 if ( listRef.empty() ) // list is empty
97 cout << "List is empty";
98 else
99 {
100 ostream_iterator< T > output( cout, " " );
101 copy( listRef.cbegin(), listRef.cend(), output );
102 } // end else
103 } // end function printList
values contains: 2 1 4 3
values after sorting contains: 1 2 3 4
After insert, otherValues contains: 2 6 4 8
After splice, values contains: 1 2 3 4 2 6 4 8
After sort, values contains: 1 2 2 3 4 4 6 8
After insert and sort, otherValues contains: 2 4 6 8
After merge:
values contains: 1 2 2 2 3 4 4 4 6 6 8 8
otherValues contains: List is empty
After pop_front and pop_back:
values contains: 2 2 2 3 4 4 4 6 6 8r
After unique, values contains: 2 3 4 6 8
After swap:
values contains: List is empty
otherValues contains: 2 3 4 6 8
After assign, values contains: 2 3 4 6 8
After merge, values contains: 2 2 3 3 4 4 6 6 8 8
After remove( 4 ), values contains: 2 2 3 3 6 6 8 8
Lines 17–18 instantiate two list
objects capable of storing int
s. Lines 21–22 use function push_front to insert integers at the beginning of values
. Function push_front
is specific to classes forward_list
, list
and deque
. Lines 23–24 use function push_back
to insert integers at the end of values
. Function push_back is common to all sequence containers, except array
and forward_list
.
Line 29 uses list
member function sort to arrange the elements in the list
in ascending order. [Note: This is different from the sort
in the Standard Library algorithms.] A second version of function sort
allows you to supply a binary predicate function that takes two arguments (values in the list), performs a comparison and returns a bool
value indicating whether the first argument should come before the second in the sorted contents. This function determines the order in which the elements of the list
are sorted. This version could be particularly useful for a list
that stores pointers rather than values. [Note: We demonstrate a unary predicate function in Fig. 16.3. A unary predicate function takes a single argument, performs a comparison using that argument and returns a bool
value indicating the result.]
Line 39 uses list
function splice to remove the elements in otherValues
and insert them into values
before the iterator position specified as the first argument. There are two other versions of this function. Function splice
with three arguments allows one element to be removed from the container specified as the second argument from the location specified by the iterator in the third argument. Function splice
with four arguments uses the last two arguments to specify a range of locations that should be removed from the container in the second argument and placed at the location specified in the first argument. Class template forward_list
provides a similar member function named splice_after
.
After inserting more elements in otherValues
and sorting both values
and otherValues
, line 54 uses list
member function merge to remove all elements of otherValues
and insert them in sorted order into values
. Both list
s must be sorted in the same order before this operation is performed. A second version of merge
enables you to supply a binary predicate function that takes two arguments (values in the list) and returns a bool
value. The predicate function specifies the sorting order used by merge
.
Line 60 uses list
function pop_front to remove the first element in the list
. Line 60 uses function pop_back (available for sequence containers other than array
and forward_list
) to remove the last element in the list
.
Line 65 uses list
function unique to remove duplicate elements in the list
. The list
should be in sorted order (so that all duplicates are side by side) before this operation is performed, to guarantee that all duplicates are eliminated. A second version of unique
enables you to supply a predicate function that takes two arguments (values in the list) and returns a bool
value specifying whether two elements are equal.
Line 70 uses function swap (available to all first-class containers) to exchange the contents of values
with the contents of otherValues
.
Line 77 uses list
function assign (available to all sequence containers) to replace the contents of values
with the contents of otherValues
in the range specified by the two iterator arguments. A second version of assign
replaces the original contents with copies of the value specified in the second argument. The first argument of the function specifies the number of copies. Line 86 uses list
function remove to delete all copies of the value 4
from the list
.