|
|
In addition to the sequential containers, the library defines three sequential container adaptors: stack, queue, and priority_queue. 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 type. For example, the stack adaptor takes a sequential container (other than array or forward_list) and makes it operate as if it were a stack. Table 9.17 lists the operations and types that are common to all the container adaptors.
Table 9.17. Operations and Types Common to the Container Adaptors
Exercises Section 9.5.5
Exercise 9.50: Write a program to process a
vector<string>s whose elements represent integral values. Produce the sum of all the elements in thatvector. Change the program so that it sums ofstrings that represent floating-point values.Exercise 9.51: Write a class that has three
unsignedmembers representing year, month, and day. Write a constructor that takes astringrepresenting a date. Your constructor should handle a variety of date formats, such as January 1, 1900, 1/1/1900, Jan 1, 1900, and so on.
Each adaptor defines two constructors: the default constructor that creates an empty object, and a constructor that takes a container and initializes the adaptor by copying the given container. For example, assuming that deq is a deque<int>, we can 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 we create the adaptor:
// empty stack implemented on top of vector
stack<string, vector<string>> str_stk;
// str_stk2 is implemented on top of vector and initially holds a copy of svec
stack<string, vector<string>> str_stk2(svec);
There are constraints on which containers can be used for a given adaptor. All of the adaptors require the ability to add and remove elements. As a result, they cannot be built on an array. Similarly, we cannot use forward_list, because all of the adaptors require operations that add, remove, or access the last element in the container. A stack requires only push_back, pop_back, and back operations, so we can use any of the remaining container types for a stack. The queue adaptor requires back, push_back, front, and push_front, so it can be built on a list or deque but not on a vector. A priority_queue requires random access in addition to the front, push_back, and pop_back operations; it can be built on a vector or a deque but not on a list.
The stack type is defined in the stack header. The operations provided by a stack are listed in Table 9.18. The following program illustrates the use of stack:
stack<int> intStack; // empty stack
// fill up the stack
for (size_t ix = 0; ix != 10; ++ix)
intStack.push(ix); // intStackholds 0 ... 9 inclusive
while (!intStack.empty()) { // while there are still values in intStack
int value = intStack.top();
// code that uses value
intStack.pop(); // pop the top element, and repeat
}
Table 9.18. Stack Operations in Addition to Those in Table 9.17
The declaration
stack<int> intStack; // empty stack
defines intStack to be an empty stack that holds integer elements. The for loop adds ten 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. We can use only the adaptor operations and cannot use the operations of the underlying container type. For example,
intStack.push(ix); // intStackholds 0 ... 9 inclusive
calls push_back on 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 queue and priority_queue adaptors are defined in the queue header. Table 9.19 lists the operations supported by these types.
Table 9.19. queue, priority_queue Operations in Addition to Table 9.17
The library queue uses a first-in, first-out (FIFO) storage and retrieval policy. Objects entering the queue are placed in the back and objects leaving the queue are removed from the front. A restaurant that seats people in the order in which they arrive is an example of a FIFO queue.
A priority_queue lets us establish a priority among the elements held in the queue. Newly added elements are placed ahead of all the elements with a lower priority. A restaurant that seats people according to their reservation time, regardless of when they arrive, is an example of a priority queue. By default, the library uses the < operator on the element type to determine relative priorities. We’ll learn how to override this default in § 11.2.2 (p. 425).
Exercises Section 9.6
Exercise 9.52: Use a
stackto process parenthesized expressions. When you see an open parenthesis, note that it was seen. When you see a close parenthesis after an open parenthesis,popelements down to and including the open parenthesis off thestack.pusha value onto thestackto indicate that a parenthesized expression was replaced.
|
|