15.5.2. list Sequence Container
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: forward_list Container
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.
list Member Functions
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
Fig. 15.13. Standard Library list class template.
Creating list Objects
Lines 17–18 instantiate two list objects capable of storing ints. 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.
list Member Function sort
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.]
list Member Function splice
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.
list Member Function merge
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 lists 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.
list Member Function pop_front
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.
list Member Function unique
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.
list Member Function swap
Line 70 uses function swap (available to all first-class containers) to exchange the contents of values with the contents of otherValues.
list Member Functions assign and remove
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.