Team LiB
Previous Section Next Section

9.7. Container Adaptors

9.7. 容器适配器

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.

除了顺序容器,标准库还提供了三种顺序容器适配器:queuepriority_queuestack适配器(adaptor)是标准库中通用的概念,包括容器适配器、迭代器适配器和函数适配器。本质上,适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。例如,stack(栈)适配器可使任何一种顺序容器以栈的方式工作。表 9.22 列出了所有容器适配器通用的操作和类型。

Table 9.22. Common Adaptor Operations and Types
表 9.22. 适配器通用的操作和类型


Type large enough to hold size of largest object of this type.



Element type.



Type of the underlying container on which the adaptor is implemented.


A a;

Create a new empty adaptor named a.

创建一个新空适配器,命名为 a

A a(c);

Create a new adaptor named a with a copy of the container c.

创建一个名为 a 的新适配器,初始化为容器 c 的副本

Relational Operators


Each adaptor supports all the relational operators: ==, !=, <, <=, >, >=.

所有适配器都支持全部关系操作符:==、 !=、 <、 <=、 >、 >=

To use an adaptor, we must include its associated header:


     #include <stack>    // stack adaptor
     #include <queue>    // both queue and priority_queue adaptors

Initializing an Adapator


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:

所有适配器都定义了两个构造函数:默认构造函数用于创建空对象,而带一个容器参数的构造函数将参数容器的副本作为其基础值。例如,假设 deqdeque<int> 类型的容器,则可用 deq 初始化一个新的栈,如下所示:

     stack<int> stk(deq);      // copies elements from deq into stk

Overriding the Underlying Container Type


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:

默认的 stackqueue 都基于 deque 容器实现,而 priority_queue 则在 vector 容器上实现。在创建适配器时,通过将一个顺序容器指定为适配器的第二个类型实参,可覆盖其关联的基础容器类型:

     // 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.

对于给定的适配器,其关联的容器必须满足一定的约束条件。stack 适配器所关联的基础容器可以是任意一种顺序容器类型。因此,stack 栈可以建立在 vector、list 或者 deque 容器之上。而 queue 适配器要求其关联的基础容器必须提供 push_front 运算,因此只能建立在 list 容器上,而不能建立在 vector 容器上。priority_queue 适配器要求提供随机访问功能,因此可建立在 vectordeque 容器上,但不能建立在 list 容器上。

Relational Operations on Adaptors


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.


9.7.1. Stack Adaptor

9.7.1. 栈适配器

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:

表 9.23 列出了栈提供的所有操作。

Table 9.23. Operations Supported by the Stack Container Adaptor
表 9.23. 栈容器适配器支持的操作


Returns true if the stack is empty; false otherwise.

如果栈为空,则返回 true,否则返回 stack


Returns a count of the number of elements on the stack.



Removes, but does not return, the top element from the stack.


Returns, but does not remove, the top element on the stack.



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 =;
         // 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.

intStack 定义为一个存储整型元素的空栈。第一个 while 循环在该栈中添加了 stk_size 个元素,元素初值是从 0 开始依次递增 1 的整数。第二个 while 循环迭代遍历整个栈,检查其栈顶(top)的元素值,然后栈顶元素出栈,直到栈变空为止。

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

所有容器适配器都根据其基础容器类型所支持的操作来定义自己的操作。默认情况下,栈适配器建立在 deque 容器上,因此采用 deque 提供的操作来实现栈功能。例如,执行下面的语句:

     // 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.

这个操作通过调用 push_back 操作实现,而该 intStack 所基于的 deque 对象提供。尽管栈是以 deque 容器为基础实现的,但是程序员不能直接访问 deque 所提供的操作。例如,不能在栈上调用 push_back 函数,而是必须使用栈所提供的名为 push 的操作。

9.7.2. Queue and Priority Queue

9.7.2. 队列和优先级队列

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.

标准库队列使用了先进先出(FIFO)的存储和检索策略。进入队列的对象被放置在尾部,下一个被取出的元素则取自队列的首部。标准库提供了两种风格的队列:FIFO 队列(FIFO queue,简称 queue),以及优先级队列(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.

priority_queue 允许用户为队列中存储的元素设置优先级。这种队列不是直接将新元素放置在队列尾部,而是放在比它优先级低的元素前面。标准库默认使用元素类型的 < 操作符来确定它们之间的优先级关系。

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.

优先级队列的一个实例是机场行李检查队列。30 分钟后即将离港的航班的乘客通常会被移到队列前面,以便他们能在飞机起飞前完成检查过程。使用优先级队列的程序示例是操作系统的调试表,它决定在大量等待进程中下一个要执行的进程。

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.

要使用这两种队列,必须包含 queue 头文件。表 9.24 列出了队列和优先级队列所提供的所有操作。

Table 9.24. Operations Supported by Queues and Priority Queues
表 9.24. 队列和优先级队列支持的操作


Returns true if the queue is empty; false otherwise.

如果队列为空,则返回 true,否则返回 false


Returns a count of the number of elements on the queue.



Removes, but does not return, the front element from the queue.



Returns, but does not remove, the front element on the queue.


This operation can be applied only to a queue.



Returns, but does not remove, the back element on the queue.


This operation can be applied only to a queue.


Returns, but does not remove, the highest-priority element.


This operation can be applied only to a priority_queue.



Places a new element at the end of the queue or at its appropriate position based on priority in a priority_queue.

对于 queue,在队尾压入一个新元素,对于 priority_quue,在基于优先级的适当位置插入新元素

Exercises Section 9.7.2

Exercise 9.42:

Write a program to read a series of words into a stack.

编写程序读入一系列单词,并将它们存储在 stack 对象中。

Exercise 9.43:

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.

使用 stack 对象处理带圆括号的表达式。遇到左圆括号时,将其标记下来。然后在遇到右加括号时,弹出 stack 对象中这两边括号之间的相关元素(包括左圆括号)。接着在 stack 对象中压入一个值,用以表明这个用一对圆括号括起来的表达式已经被替换。

Team LiB
Previous Section Next Section