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 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 4 using std::cout; 5 using std::endl; 6 7 #include // stack adapter definition 8 #include // vector class-template definition 9 #include // 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 << " Pushing onto intVectorStack: "; 32 pushElements( intVectorStack ); 33 cout << " Pushing 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 << " Popping from intVectorStack: "; 41 popElements( intVectorStack ); 42 cout << " Popping 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
|
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.
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.
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).
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 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 4 using std::cout; 5 using std::endl; 6 7 #include // 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
|
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).
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 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 4 using std::cout; 5 using std::endl; 6 7 #include // 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
|
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).