C++ STL 容器适配器
标准库提供了三种顺序容器适配器:queue、priority_queue、stack.适配器是标准库中通用的
概念,包括容器适配器、迭代器适配器和函数适配器。
本质上,适配器是使一事物的行为类似于另一类事物的行为的一种机制。容器适配器让一种已
存在的容器类型采用另一种不同的抽象类型的工作方式实现。例如,stack适配器可使任何一种顺
序容器以栈的方式工作。如下列出了所有容器适配器通用的操作和类型。
size_type 一种类型,足以存储此适配器类型最大对象的长度
value_type 元素类型
container_type 基础容器类型,适配器在此容器类型上实现
A a; 创建一个新的空适配器,命名为a
A a(c); 创建一个名为a的新适配器,初始化为容器c的副本
关系操作符 所有适配器都支持全部关系操作符:==、!=、<、<=、>、>=
使用适配器时,必须包含相关的头文件:
#include<stack> #include<queue>
适配器的初始化
deque<int> deq;
stack<int> stk(deq); //将deq中的元素复制到stk中
覆盖基础容器类型
默认的stack和queue都基于deque容器实现,而priority_queue则在vector容器上实现。在创建适
配器时,通过将一个顺序容器指定为适配器的第二个类型实参,可覆盖其关联的基础容器类型:
stack< string, vector<string> > str_stk;
stack< string, vector<string> > str_stk(svec);
对于给定的适配器,其关联的容器必须满足一定的约束条件。stack适配器所关联的基础容器可以是
任何一种顺序容器类型。因此,stack栈可以建立在vector、list、deque容器之上。而queue适配器
要求其关联的基础容器必须提供push_front运算,因此只能建立在list和deque容器上,而不能建立
在vector容器上。priority_queue适配器要求提供随机访问功能,因此可建立vector或deque容器上,
但不能建立在list容器上。
适配器的关系运算
两个相同类型的适配器可以做==、!=、<、<=、>、>= 关系比较,只要基础元素类型支持等于和小
于操作符即可。这些关系运算由元素依次比较来实现。第一对不相等的元素将决定两者之间的小于
或大于关系。
栈适配器
s.empty() 如果栈为空,返回true,否则返回false
s.size() 返回栈中元素的个数
s.pop() 删除栈顶元素,但不返回其值
s.top() 返回栈顶元素,但不删除其值
s.push(item) 在栈顶压入新元素
队列和优先级队列
q.empty() 如果对列为空,返回true,否则返回false
q.size() 返回队列中元素的个数
q.pop() 删除队列首元素,但不返回其值
q.front() 返回队列首元素的值,但不删除该元素 该操作适用于queue而非priority_queque
q.back() 返回队尾元素的值,而不删除该元素 该操作适用于queue而非priority_queque
q.top() 返回具有最高优先级的元素值,但不删除该元素 该操作适用于priority_queque
q.push(item) 对于queue,在队尾压入一个新元素
对于priority_queue,在基于优先级的适当位置插入新元素
注意:所有容器适配器都根据其基础容器类型所支持的操作来定义自己的操作。例如,默认情况下
栈适配器建立在deque容器上,因此采用deque提供的操作来实现栈功能。比如说,执行下面的语
句 intStack.push(ix++); 这个操作通过调用push_back操作来实现,而该push_back操作由intStack
所基于的deque对象提供。尽管栈是以deque容器为基础实现的,但是程序员不能直接访问deque
所提供的操作。不能在栈上调用push_back函数,而是必须使用栈所提供的名为push的操作。