Deitel & Associates, Inc. Logo

Back to www.deitel.com
digg.png delicious.png blinkit.png furl.png
C++ How to Program, 5/e

ISBN:
0-13-185757-6
© 2005
pages: 1500
Buy the Book!
Amazon logo
InformIT logo

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.

[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.

Page 1 | 2

Tutorial Index