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.

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

Table 9.22. Common Adaptor Operations and Types

表 9.22. 适配器通用的操作和类型

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:

所有适配器都定义了两个构造函数：默认构造函数用于创建空对象，而带一个容器参数的构造函数将参数容器的副本作为其基础值。例如，假设 deq 是 deque<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:

默认的 stack 和 queue 都基于 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 适配器要求提供随机访问功能，因此可建立在 vector 或 deque 容器上，但不能建立在 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. 栈容器适配器支持的操作

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

将 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. 队列和优先级队列支持的操作