 |
ISBN: |
STL containers are data structures capable of storing objects of any type. There are three major categories of containers—sequence containers, associative containers and container adapters. The sequence containers represent linear data structures. The following article discusses the list sequence container. Also see the related articles that introduce sequence containers and discuss the vector sequence container and the deque sequence container.
- Before You Begin: Download the code examples for this tutorial
[Note: This tutorial is an excerpt (Sections 23.2) of Chapter 23, Standard Template Library (STL), from our textbook C++ How to Program, 5/e. These tutorials may refer to other chapters or sections of the book that are not included here. Permission Information: Deitel, Harvey M. and Paul J., C++ HOW TO PROGRAM, ©2005, pp.1124-1136. Electronically reproduced by permission of Pearson Education, Inc., Upper Saddle River, New Jersey.]
23.2.2 list Sequence Container
The list sequence container provides an efficient implementation for 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 23.2.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 of the list member functions manipulate the elements of the container as an ordered set of elements.
In addition to the member functions of all STL containers in Fig. 23.2 and the common member functions of all sequence containers discussed in Section 23.2, class template list provides nine other member functions—splice, push_front, pop_front, remove, remove_if, unique, merge, reverse and sort. Several of these member functions are list-optimized implementations of STL algorithms presented in Section 23.5. Figure 23.17 demonstrates several features of class list. Remember that many of the functions presented in Figs. 23.14–23.15 can be used with class list. Header file <list> must be included to use class list.
1 // Fig. 23.17: Fig23_17.cpp 2 // Standard library list class template test program. 3 #include <iostream> 4 using std::cout; 5 using std::endl; 6 7 #include <list> // list class-template definition 8 #include <algorithm> // copy algorithm 9 #include <iterator> // ostream_iterator 10 11 // prototype for function template printList 12 template < typename T > void printList( const std::list< T > &listRef ); 13 14 int main() 15 { 16 const int SIZE = 4; 17 int array[ SIZE ] = { 2, 6, 4, 8 }; 18 std::list< int > values; // create list of ints 19 std::list< int > otherValues; // create list of ints 20 21 // insert items in values 22 values.push_front( 1 ); 23 values.push_front( 2 ); 24 values.push_back( 4 ); 25 values.push_back( 3 ); 26 27 cout << "values contains: "; 28 printList( values ); 29 30 values.sort(); // sort values 31 cout << "\nvalues after sorting contains: "; 32 printList( values ); 33 34 // insert elements of array into otherValues 35 otherValues.insert( otherValues.begin(), array, array + SIZE ); 36 cout << "\nAfter insert, otherValues contains: "; 37 printList( otherValues ); 38 39 // remove otherValues elements and insert at end of values 40 values.splice( values.end(), otherValues ); 41 cout << "\nAfter splice, values contains: "; 42 printList( values ); 43 44 values.sort(); // sort values 45 cout << "\nAfter sort, values contains: "; 46 printList( values ); 47 48 // insert elements of array into otherValues 49 otherValues.insert( otherValues.begin(), array, array + SIZE ); 50 otherValues.sort(); 51 cout << "\nAfter insert, otherValues contains: "; 52 printList( otherValues ); 53 54 // remove otherValues elements and insert into values in sorted order 55 values.merge( otherValues ); 56 cout << "\nAfter merge:\n values contains: "; 57 printList( values ); 58 cout << "\n otherValues contains: "; 59 printList( otherValues ); 60 61 values.pop_front(); // remove element from front 62 values.pop_back(); // remove element from back 63 cout << "\nAfter pop_front and pop_back:\n values contains: " 64 printList( values ); 65 66 values.unique(); // remove duplicate elements 67 cout << "\nAfter unique, values contains: "; 68 printList( values ); 69 70 // swap elements of values and otherValues 71 values.swap( otherValues ); 72 cout << "\nAfter swap:\n values contains: "; 73 printList( values ); 74 cout << "\n otherValues contains: "; 75 printList( otherValues ); 76 77 // replace contents of values with elements of otherValues 78 values.assign( otherValues.begin(), otherValues.end() ); 79 cout << "\nAfter assign, values contains: "; 80 printList( values ); 81 82 // remove otherValues elements and insert into values in sorted order 83 values.merge( otherValues ); 84 cout << "\nAfter merge, values contains: "; 85 printList( values ); 86 87 values.remove( 4 ); // remove all 4s 88 cout << "\nAfter remove( 4 ), values contains: "; 89 printList( values ); 90 cout << endl; 91 return 0; 92 } // end main 93 94 // printList function template definition; uses 95 // ostream_iterator and copy algorithm to output list elements 96 template < typename T > void printList( const std::list< T > &listRef ) 97 { 98 if ( listRef.empty() ) // list is empty 99 cout << "List is empty"; 100 else 101 { 102 std::ostream_iterator< T > output( cout, " " ); 103 std::copy( listRef.begin(), listRef.end(), output ); 104 } // end else 105 } // 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, 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 8
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. 23.17 Standard Library list class template.