In addition to the sequential containers, the library provides three sequential container adaptors: queue, priority_queue, and stack. An adaptor is a general concept in the library. There are container, iterator, and function adaptors. Essentially, an adaptor is a mechanism for making one thing act like another. A container adaptor takes an existing container type and makes it act like a different abstract type. For example, the stack adaptor takes any of the sequential containers and makes it operate as if it were a stack. Table 9.22 (p. 350) lists the operations and types that are common to all the container adaptors.
size_type
Type large enough to hold size of largest object of this type.
value_type
Element type.
container_type
Type of the underlying container on which the adaptor is implemented.
A a;
Create a new empty adaptor named a.
A a(c);
Create a new adaptor named a with a copy of the container c.
Relational Operators
Each adaptor supports all the relational operators: ==, !=, <, <=, >, >=.
Write a program that accepts the following two strings:
string q1("When lilacs last in the dooryard bloom'd");
string q2("The child is father of the man");
Using the assign and append operations, create the string
string sentence("The child is in the dooryard");
Write a program that, given the strings
string generic1("Dear Ms Daisy:");
string generic2("MrsMsMissPeople");
implements the function
string greet(string form, string lastname, string title, string::size_type pos, int length);
using the replace operations, where lastname replaces Daisy and pos indexes into generic2 of length characters replacing Ms. For example, the following
string lastName("AnnaP");
string salute = greet(generic1, lastName, generic2, 5, 4);
returns the string
Dear Miss AnnaP:
To use an adaptor, we must include its associated header:
#include <stack> // stack adaptor #include <queue> // both queue and priority_queue adaptors
Each adaptor defines two constructors: the default constructor that creates an empty object and a constructor that takes a container and makes a copy of that container as its underlying value. For example, assuming that deq is a deque<int>, we could use deq to initialize a new stack as follows:
stack<int> stk(deq); // copies elements from deq into stk
By default both stack and queue are implemented in terms of deque, and a priority_queue is implemented on a vector. We can override the default container type by naming a sequential container as a second type argument when creating the adaptor:
// empty stack implemented on top of vector stack< string, vector<string> > str_stk; // str_stk2 is implemented on top of vector and holds a copy of svec stack<string, vector<string> > str_stk2(svec);
There are constraints on which containers can be used for a given adapator. We can use any of the sequential containers as the underlying container for a stack. Thus, a stack can be built on a vector, list, or deque. The queue adapator requires push_front in its underlying container, and so could be built on a list but not on a vector. A priority_queue requires random access and so can be built on a vector or a deque but not on a list.
Two adaptors of the same type can be compared for equality, inequality, less-than, greater-than, less-than-equal, and greater-than-equal relationships, provided that the underlying element type supports the equality and less-than operators. For these operations, the elements are compared in turn. The first pair of unequal elements determines the less-than or greater-than relationship.
The operations provided by a stack are listed in Table 9.23 on the facing page. The following program exercises this set of five stack operations:
s.empty()
Returns TRue if the stack is empty; false otherwise.
s.size()
Returns a count of the number of elements on the stack.
s.pop()
Removes, but does not return, the top element from the stack.
s.top()
Returns, but does not remove, the top element on the stack.
s.push(item)
Places a new top element on the stack.
// number of elements we'll put in our stack
const stack<int>::size_type stk_size = 10;
stack<int> intStack; // empty stack
// fill up the stack
int ix = 0;
while (intStack.size() != stk_size)
// use postfix increment; want to push old value onto intStack
intStack.push(ix++); // intStack holds 0...9 inclusive
int error_cnt = 0;
// look at each value and pop it off the stack
while (intStack.empty() == false) {
int value = intStack.top();
// read the top element of the stack
if (value != --ix) {
cerr << "oops! expected " << ix
<< " received " << value << endl;
++error_cnt; }
intStack.pop(); // pop the top element, and repeat
}
cout << "Our program ran with "
<< error_cnt << " errors!" << endl;
stack<int> intStack; // empty stack
defines intStack to be an empty stack that holds integer elements. The for loop adds stk_size elements initializing each to the next integer in sequence starting from zero. The while loop iterates through the entire stack, examining the top value and popping it from the stack until the stack is empty.
Each container adaptor defines its own operations in terms of operations provided by the underlying container type. By default, this stack is implemented using a deque and uses deque operations to implement the operations of a stack. For example, when we execute
// use postfix increment; want to push old value onto intStack intStack.push(ix++); // intStack holds 0...9 inclusive
this operation executes by calling the push_back operation of the deque object on which intStack is based. Although stack is implemented by using a deque, we have no direct access to the deque operations. We cannot call push_back on a stack; instead, we must use the stack operation named push.
The library queue uses a first-in, first-out (FIFO) storage and retrieval policy. Objects entering the queue are placed in the back. The next object retrieved is taken from the front of the queue. There are two kinds of queues: the FIFO queue, which we will speak of simply as a queue, and a priority queue.
A priority_queue lets us establish a priority among the elements held in the queue. Rather than place a newly entered item at the back of the queue, the item is placed ahead of all those items with a lower priority. By default, the library uses the < operator on the element type to determine relative priorities.
A real-world example of a priority queue is the line to check luggage at an airport. Those whose flight is going to leave within the next 30 minutes are generally moved to the front of the line so that they can finish the check-in process before their plane takes off. A programming example of a priority queue is the scheduler of an operating system determining which, of a number of waiting processes, should execute next.
To use either queue or priority_queue, we must include the queue header. Table 9.24 lists the operations supported by queue and priority_queue.
q.empty()
Returns TRue if the queue is empty; false otherwise.
q.size()
Returns a count of the number of elements on the queue.
q.pop()
Removes, but does not return, the front element from the queue.
q.front()
Returns, but does not remove, the front element on the queue.
This operation can be applied only to a queue.
q.back()
Returns, but does not remove, the back element on the queue.
This operation can be applied only to a queue.
q.top()
Returns, but does not remove, the highest-priority element.
This operation can be applied only to a priority_queue.
q.push(item)
Places a new element at the end of the queue or at its appropriate position based on priority in a priority_queue.
Write a program to read a series of words into a stack.
Use a stack to process parenthesized expressions. When you see an open parenthesis, note that it was seen. When you see a close parenthesis after an open parenthesis, pop elements down to and including the open parenthesis off the stack. push a value onto the stack to indicate that a parenthesized expression was replaced.