014 容器适配器
除了顺序容器外,标准库还定义了三个顺序容器适配器:stack、queue 和 priority_queue。适配器 是标准库中的一个通用概念。容器、迭代器和函数都有适配器。本质上,一个适配器是一种机制,能使某种事物的行为看起来像另外一种事物一样。一个容器适配器接受一种已有的容器类型,使其行为看起来像一种不同的类型。例如,stack 适配器接受一个顺序容器(除 array 或 forward_list 外),并使其操作像一个 stack 一样。
下面列出了所有容器适配器都支持的操作和类型:
操作和类型 | 说明 |
---|---|
size_type | 一种类型,足以保存当前类型的最大对象的大小 |
value_type | 元素类型 |
container_type | 实现适配器的底层容器类型 |
A a; | 创建一个名为 a 的空适配器 |
A a(c); | 创建一个名为 a 的适配器,带有容器 c 的一个拷贝 |
关系运算符 | 每个适配器都支持所有关系运算符:==、!=、<、<=、> 和 >= 这些运算符返回底层容器的比较结果 |
a.empty() | 若 a 包含任何元素,返回 false,否则返回 true |
a.size() | 返回 a 中的元素数目 |
swap(a,b) a.swap(b) |
交换 a 和 b 的内容,a 和 b 必须有相同类型,包括底层容器类型也必须相同 |
定义一个适配器
每个适配器都定义两个构造函数:默认构造函数创建一个空对象,接受一个容器的构造函数拷贝该容器来初始化适配器。例如,假定deq是一个 deque<int>,我们可以用 deq 来初始化一个新的 stack,如下所示:
stack<int> stk(deq); // 从 deq 拷贝元素到 stk
默认情况下,stack 和 queue 是基于 deque 实现的, priority_queue 是在 vector 之上实现的。我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数来重载默认容器类型:
// 在 vector上实现的空栈
stack<string, vector<string>> str_stk;
// str_stk2 在 vector 上实现,初始化时保存 svec 的拷贝
stack<string, vector<string>> str_stk2(svec);
对于一个给定的适配器,可以使用哪些容器是有限制的。所有适配器都要求容器具有添加和删除元素的能力。因此,适配器不能构造在 array 之上。类似的,我们也不能用 forward_list 来构造适配器,因为所有适配器都要求容器具有添加、删除以及访问尾元素的能力。 stack 只要求 push_back、 pop_back 和 back 操作,因此可以使用除 array 和 forward_list 之外的任何容器类来构造 stack。 queue 适配器要求 back、push_back、 front 和 push_front,因此它可以构造于 list 或 deque 之上,但不能基于 vector 构造。 priority_queue 除了 front、 push_back 和 pop_back 操作之外还要求随机访问能力,因此它可以构造于 vector 或 deque 之上,但不能基于 list 构造。