www.gibmonks.com

Main Page




Previous Page
Next Page

[Page 1147 (continued)]

23.4. Container Adapters

The STL provides three container adaptersstack, queue and priority_queue. Adapters are not first-class containers, because they do not provide the actual data-structure implementation in which elements can be stored and because adapters do not support iterators. The benefit of an adapter class is that the programmer can choose an appropriate underlying data structure. All three adapter classes provide member functions push and pop that properly insert an element into each adapter data structure and properly remove an element from each adapter data structure. The next several subsections provide examples of the adapter classes.

23.4.1. stack Adapter

Class stack enables insertions into and deletions from the underlying data structure at one end (commonly referred to as a last-in, first-out data structure). A stack can be implemented with any of the sequence containers: vector, list and deque. This example creates three integer stacks, using each of the sequence containers of the Standard Library as the underlying data structure to represent the stack. By default, a stack is implemented with a deque. The stack operations are push to insert an element at the top of the stack (implemented by calling function push_back of the underlying container), pop to remove the top element of the stack (implemented by calling function pop_back of the underlying container), top to get a reference to the top element of the stack (implemented by calling function back of the underlying container), empty to determine whether the stack is empty (implemented by calling function empty of the underlying container) and size to get the number of elements in the stack (implemented by calling function size of the underlying container).

Performance Tip 23.16

Each of the common operations of a stack is implemented as an inline function that calls the appropriate function of the underlying container. This avoids the overhead of a second function call.


Performance Tip 23.17

For the best performance, use class deque or vector as the underlying container for a stack.


Figure 23.23 demonstrates the stack adapter class. Header file <stack> must be included to use class stack.

Figure 23.23. Standard Library stack adapter class.
(This item is displayed on pages 1148 - 1149 in the print version)

 1  // Fig. 23.23: Fig23_23.cpp
 2  // Standard Library adapter stack test program.
 3  #include <iostream>
 4  using std::cout;
 5  using std::endl;
 6
 7  #include <stack> // stack adapter definition
 8  #include <vector> // vector class-template definition
 9  #include <list> // list class-template definition
10
11  // pushElements function-template prototype
12  template< typename T > void pushElements( T &stackRef );
13
14  // popElements function-template prototype
15  template< typename T > void popElements( T &stackRef );
16
17  int main()
18  {
19     // stack with default underlying deque
20     std::stack< int > intDequeStack;      
21
22     // stack with underlying vector                      
23     std::stack< int, std::vector< int > > intVectorStack;
24
25     // stack with underlying list                    
26     std::stack< int, std::list< int > > intListStack;
27
28     // push the values 0-9 onto each stack
29     cout << "Pushing onto intDequeStack: ";
30     pushElements( intDequeStack );
31     cout << "\nPushing onto intVectorStack: ";
32     pushElements( intVectorStack );
33     cout << "\nPushing onto intListStack: ";
34     pushElements( intListStack );
35     cout << endl << endl;
36
37     // display and remove elements from each stack
38     cout << "Popping from intDequeStack: ";
39     popElements( intDequeStack );
40     cout << "\nPopping from intVectorStack: ";
41     popElements( intVectorStack );
42     cout << "\nPopping from intListStack: ";
43     popElements( intListStack );
44     cout << endl;
45     return 0;
46  } // end main
47
48  // push elements onto stack object to which stackRef refers
49  template< typename T > void pushElements( T &stackRef )
50  {
51     for ( int i = 0; i < 10; i++ )
52     {
53        stackRef.push( i ); // push element onto stack                   
54        cout << stackRef.top() << ' '; // view (and display ) top element
55     } // end for
56  } // end function pushElements
57
58  // pop elements from stack object to which stackRef refers
59  template< typename T > void popElements( T &stackRef )
60  {
61     while ( !stackRef.empty() )
62     {
63        cout << stackRef.top() << ' '; // view (and display) top element
64        stackRef.pop(); // remove top element                           
65     } // end while
66  } // end function popElements

 Pushing onto intDequeStack: 0 1 2 3 4 5 6 7 8 9
 Pushing onto intVectorStack: 0 1 2 3 4 5 6 7 8 9
 Pushing onto intListStack: 0 1 2 3 4 5 6 7 8 9

 Popping from intDequeStack: 9 8 7 6 5 4 3 2 1 0
 Popping from intVectorStack: 9 8 7 6 5 4 3 2 1 0
 Popping from intListStack: 9 8 7 6 5 4 3 2 1 0


Lines 20, 23 and 26 instantiate three integer stacks. Line 20 specifies a stack of integers that uses the default deque container as its underlying data structure. Line 23 specifies a stack of integers that uses a vector of integers as its underlying data structure. Line 26 specifies a stack of integers that uses a list of integers as its underlying data structure.


[Page 1148]

Function pushElements (lines 4956) pushes the elements onto each stack. Line 53 uses function push (available in each adapter class) to place an integer on top of the stack. Line 54 uses stack function top to retrieve the top element of the stack for output. Function top does not remove the top element.

Function popElements (lines 5966) pops the elements off each stack. Line 63 uses stack function top to retrieve the top element of the stack for output. Line 64 uses function pop (available in each adapter class) to remove the top element of the stack. Function pop does not return a value.


[Page 1149]

23.4.2. queue Adapter

Class queue enables insertions at the back of the underlying data structure and deletions from the front (commonly referred to as a first-in, first-out data structure). A queue can be implemented with STL data structure list or deque. By default, a queue is implemented with a deque. The common queue operations are push to insert an element at the back of the queue (implemented by calling function push_back of the underlying container), pop to remove the element at the front of the queue (implemented by calling function pop_front of the underlying container), front to get a reference to the first element in the queue (implemented by calling function front of the underlying container), back to get a reference to the last element in the queue (implemented by calling function back of the underlying container), empty to determine whether the queue is empty (implemented by calling function empty of the underlying container) and size to get the number of elements in the queue (implemented by calling function size of the underlying container).


[Page 1150]

Performance Tip 23.18

Each of the common operations of a queue is implemented as an inline function that calls the appropriate function of the underlying container. This avoids the overhead of a second function call.


Performance Tip 23.19

For the best performance, use class deque or list as the underlying container for a queue.


Figure 23.24 demonstrates the queue adapter class. Header file <queue> must be included to use a queue.

Figure 23.24. Standard Library queue adapter class templates.

 1  // Fig. 23.24: Fig23_24.cpp
 2  // Standard Library adapter queue test program.
 3  #include <iostream>
 4  using std::cout;
 5  using std::endl;
 6
 7  #include <queue> // queue adapter definition
 8
 9  int main()
10  {
11     std::queue< double > values; // queue with doubles
12
13     // push elements onto queue values
14     values.push( 3.2 );               
15     values.push( 9.8 );               
16     values.push( 5.4 );               
17
18     cout << "Popping from values: ";
19
20     // pop elements from queue
21     while ( !values.empty() )
22     {
23        cout << values.front() << ' '; // view front element
24        values.pop(); // remove element                     
25     } // end while
26
27     cout << endl;
28     return 0;
29  } // end main

 Popping from values: 3.2 9.8 5.4


Line 11 instantiates a queue that stores double values. Lines 1416 use function push to add elements to the queue. The while statement at lines 2125 uses function empty (available in all containers) to determine whether the queue is empty (line 21). While there are more elements in the queue, line 23 uses queue function front to read (but not remove) the first element in the queue for output. Line 24 removes the first element in the queue with function pop (available in all adapter classes).


[Page 1151]

23.4.3. priority_queue Adapter

Class priority_queue provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure. A priority_queue can be implemented with STL sequence containers vector or deque. By default, a priority_queue is implemented with a vector as the underlying container. When elements are added to a priority_queue, they are inserted in priority order, such that the highest-priority element (i.e., the largest value) will be the first element removed from the priority_queue. This is usually accomplished via a sorting technique called heapsort that always maintains the largest value (i.e., highest-priority element) at the front of the data structuresuch a data structure is called a heap. The comparison of elements is performed with comparator function object less< T > by default, but the programmer can supply a different comparator.

The common priority_queue operations are push to insert an element at the appropriate location based on priority order of the priority_queue (implemented by calling function push_back of the underlying container, then reordering the elements using heapsort), pop to remove the highest-priority element of the priority_queue (implemented by calling function pop_back of the underlying container after removing the top element of the heap), top to get a reference to the top element of the priority_queue (implemented by calling function front of the underlying container), empty to determine whether the priority_queue is empty (implemented by calling function empty of the underlying container) and size to get the number of elements in the priority_queue (implemented by calling function size of the underlying container).

Performance Tip 23.20

Each of the common operations of a priority_queue is implemented as an inline function that calls the appropriate function of the underlying container. This avoids the overhead of a second function call.


Performance Tip 23.21

For the best performance, use class vector or deque as the underlying container for a priority_queue.


Figure 23.25 demonstrates the priority_queue adapter class. Header file <queue> must be included to use class priority_queue.

Figure 23.25. Standard Library priority_queue adapter class.
(This item is displayed on pages 1151 - 1152 in the print version)

 1  // Fig. 23.25: Fig23_25.cpp
 2  // Standard Library adapter priority_queue test program.
 3  #include <iostream>
 4  using std::cout;
 5  using std::endl;
 6
 7  #include <queue> // priority_queue adapter definition
 8
 9  int main()
10  {
11     std::priority_queue< double > priorities; // create priority_queue
12
13     // push elements onto priorities
14     priorities.push( 3.2 );         
15     priorities.push( 9.8 );         
16     priorities.push( 5.4 );         
17
18     cout << "Popping from priorities: ";
19
20     // pop element from priority_queue
21     while ( !priorities.empty() )
22     {
23        cout << priorities.top() << ' '; // view top element
24        priorities.pop(); // remove top element             
25     } // end while
26
27     cout << endl;
28     return 0;
29  } // end main

 Popping from priorities: 9.8 5.4 3.2



[Page 1152]

Line 11 instantiates a priority_queue that stores double values and uses a vector as the underlying data structure. Lines 1416 use function push to add elements to the priority_queue. The while statement at lines 2125 uses function empty (available in all containers) to determine whether the priority_queue is empty (line 21). While there are more elements, line 23 uses priority_queue function top to retrieve the highest-priority element in the priority_queue for output. Line 24 removes the highest-priority element in the priority_queue with function pop (available in all adapter classes).


Previous Page
Next Page