【C++基础】第五十五课:[顺序容器]容器适配器

stack,queue,priority_queue

Posted by x-jeff on November 10, 2022

【C++基础】系列博客为参考《C++ Primer中文版(第5版)》C++11标准)一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.容器适配器

除了顺序容器外,标准库还定义了三个顺序容器适配器:stack、queue和priority_queue。适配器(adaptor)是标准库中的一个通用概念。容器、迭代器和函数都有适配器。本质上,一个适配器是一种机制,能使某种事物的行为看起来像一种不同的类型。例如,stack适配器接受一个顺序容器(除array或forward_list外),并使其操作起来像一个stack一样。表9.17列出了所有容器适配器都支持的操作和类型。

1.1.定义一个适配器

每个适配器都定义两个构造函数:默认构造函数创建一个空对象,接受一个容器的构造函数拷贝该容器来初始化适配器。例如,假定dep是一个deque,我们可以用dep来初始化一个新的stack,如下所示:

1
stack<int> stk(deq); //从deq拷贝元素到stk

默认情况下,stack和queue是基于deque实现的,priority_queue是在vector之上实现的。我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数,来重载默认容器类型。

C++中deque和queue都是队列,但两者的用法有所不同:

  • deque是一种顺序容器,是双端队列,在头部尾部都可以进行快速插入/删除。
  • queue是一种适配器,设计模式为FIFO,简单来说,元素只能从队尾插入队首删除,queue更像是传统意义上的队列。
1
2
3
4
//在vector上实现的空栈
stack<string, vector<string>> str_stk; //个人理解:这个栈的元素类型为string,基于的顺序容器类型是vector<string>
//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构造。

以上提及的有关顺序容器的操作请见:【C++基础】第五十二课:[顺序容器]顺序容器操作

1.2.栈适配器

stack类型定义在stack头文件中。表9.18列出了stack所支持的操作。下面的程序展示了如何使用stack:

1
2
3
4
5
6
7
8
9
10
stack<int> intStack; //空栈
//填满栈
for(size_t ix = 0; ix != 10; ++ix)
	intStack.push(ix); //intStack保存0到9十个数
while(!intStack.empty()) //intStack中有值就继续循环
{
	int value = intStack.top();
	//使用栈顶值的代码
	intStack.pop(); //弹出栈顶元素,继续循环
}

每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作。我们只可以使用适配器操作,而不能使用底层容器类型的操作。例如,

1
intStack.push(ix); //intStack保存0到9十个数

此语句试图在intStack的底层deque对象上调用push_back。虽然stack是基于deque实现的,但我们不能直接使用deque操作。不能在一个stack上调用push_back,而必须使用stack自己的操作—push。

1.3.队列适配器

queue和priority_queue适配器定义在queue头文件中。表9.19列出了它们所支持的操作。

标准库queue使用一种先进先出(first-in,first-out,FIFO)的存储和访问策略。进入队列的对象被放置到队尾,而离开队列的对象则从队首删除。

priority_queue允许我们为队列中的元素建立优先级。新加入的元素会排在所有优先级比它低的已有元素之前。默认情况下,标准库在元素类型上使用<运算符来确定相对优先级。

表9.19中的pop()操作应该是写错了,其应该和之前stack中的pop()操作一样,是会删除首元素的,在本地测试了下,确实如此:

1
2
3
4
5
6
queue<int> q;
for(int ix = 0; ix != 10; ix++)
{
    q.push(ix); //q的元素为0~9
}
q.pop(); //首元素弹出,q的元素变为1~9