13.7　适配器

前面简要提到了适配器的概念，适配器相当于提供了一个接口，使得某些不适用于特定对象的方法可以被该对象所用，适配器形象的功能图解如图13.2所示。图中容器或函数对象无法直接应用于算法，因此，必须有一种中间过渡机制来实现两者的匹配，这就是适配器。从本质上而言适配器是使一种事物的行为类似于另一种事物的行为的一种机制。

STL定义了3种形式的适配器，即容器适配器、迭代器适配器和函数适配器。

图　13.2　适配器作用图

❑容器适配器：包括栈（stack）、队列（queue）及优先（priority_queue）。可以把stack看做是某种特殊的vector、deque或者list容器，只是其操作仍然受到stack本身属性的限制。queue和priority_queue与之类似。容器适配器的接口更为简单，只是受限比一般容器要多。

❑迭代器适配器：修改为某些基本容器定义的迭代器的接口的一种STL组件。反向迭代器和插入迭代器都属于迭代器适配器，迭代器适配器扩展了迭代器的功能。

❑函数适配器：通过转换或者修改其他函数对象使其功能得到扩展。这一类适配器有否定器（Negator，相当于“非”操作）、绑定器（Binder）和成员函数适配器。

13.7.1　容器适配器

容器适配器可以看做对容器的封装，使其具有某些特殊的功能。容器适配器以一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现，只是发生了接口转换而已。标准库提供了3种序列容器适配器，即queue、priority_queue和stack。

所有适配器都定义了两个构造函数：默认构造函数用于创建空对象；带一个容器参数的构造函数将参数容器的副本作为其基础值。

默认的stack和queue都基于deque容器实现，而priority_queue则在vector容器上实现。在创建适配器时，通过将一个顺序容器指定为适配器的第2个类型参数，可覆盖其关联的基础容器类型。例如，下述代码创建的ob栈是基于vector实现的。

对于给定的适配器，其关联的容器必须满足一定的约束条件。stack适配器所关联的基本容器可以是任意一种序列容器类型，因为这些容器类型都提供了push_back、pop_back和back操作；queue适配器要求其关联的基础容器必须提供pop_front操作，因此其不能建立在vector容器上；priority_queue适配器要求提供随机访问功能，因此不能建立在list容器上。

1.stack

比起普通的序列式容器stack的限制更多，其不允许随机访问栈内元素，甚至不允许对栈内元素进行遍历访问，其使用机制遵循FILO原则，支持的操作为压元素入栈、弹元素出栈、查看栈顶、查看元素数目和测试栈是否为空等，如表13.13所示。

2.queue

使用queue和priority_queue必须包含头文件＜queue＞，与stack不同的是，queue使用了先进先出（FIFO）的存储和检索策略，进入队列的元素放置在尾部，下一个被取出的元素则取自队列的首部。

queue模板的限制比deque或list更多，同stack一样，queue不允许随机访问队列元素，也不允许遍历访问队列内的元素，支持的操作为压元素入队尾、从队首弹出元素、参看队首和队尾的值、查看元素数目和测试队列是否为空等，表13.14列出了这些操作。

3.priority_queue

priority_queue支持的操作与queue相同，默认使用元素类型的＜操作符来确定其之间的优先级关系，用户也可以定义自己的优先级关系。在优先级队列中，新元素被放置在比其优先级低的元素的前面。

priority_queue默认的底层容器是vector，但用户也可以用deque对其进行覆盖，并指定优先级排列方式，如下所示。

在上述定义的pq中，较小的元素具有高优先级。

相比queue,priority_queue增加了一个top操作，返回具有最高优先级的元素，但不删除该元素，如表13.14所示。

注意

对3种容器迭代器来说，pop方法只会将队首或栈顶的元素从队列或栈中删除，并不返回该值，要检索该值，应使用front（）或top（）操作。