Section 9.7. Container Adaptors
9.7. Container AdaptorsIn 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.
To use an adaptor, we must include its associated header: #include <stack> // stack adaptor #include <queue> // both queue and priority_queue adaptors Initializing an AdapatorEach 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 Overriding the Underlying Container TypeBy 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. Relational Operations on AdaptorsTwo 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. 9.7.1. Stack AdaptorThe 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:
// 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; The declaration 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. 9.7.2. Queue and Priority QueueThe 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.
|
EAN: 2147483647
Pages: 223