C++STL复习（13）容器适配器

STL 提供了 3 种容器适配器&＃xff0c;分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。

不同场景下&＃xff0c;由于不同的序列式容器其底层采用的数据结构不同&＃xff0c;因此容器适配器的执行效率也不尽相同。

1 stack

stack 栈适配器是一种单端开口的容器&＃xff0c;实际上该容器模拟的就是栈存储结构&＃xff0c;即无论是向里存数据还是从中取数据&＃xff0c;都只能从这一个开口实现操作。

stack 适配器的开头端通常称为栈顶。由于数据的存和取只能从栈顶处进行操作&＃xff0c;因此对于存取数据&＃xff0c;stack 适配器有这样的特性&＃xff0c;即每次只能访问适配器中位于最顶端的元素&＃xff0c;也只有移除 stack 顶部的元素之后&＃xff0c;才能访问位于栈中的元素。
栈中存储的元素满足“后进先出&＃xff08;简称LIFO&＃xff09;”的准则&＃xff0c;stack 适配器也同样遵循这一准则。

1 stack容器适配器的创建

由于 stack 适配器以模板类 stack&＃xff08;其中 T 为存储元素的类型&＃xff0c;Container 表示底层容器的类型&＃xff09;的形式位于头文件中&＃xff0c;并定义在 std 命名空间里。因此&＃xff0c;在创建该容器之前&＃xff0c;程序中应包含以下 2 行代码&＃xff1a;

#include
using namespace std;


1

创建一个不包含任何元素的 stack 适配器&＃xff0c;并采用默认的 deque 基础容器&＃xff1a;

std::stack<int> values;


上面这行代码&＃xff0c;就成功创建了一个可存储 int 类型元素&＃xff0c;底层采用 deque 基础容器的 stack 适配器。

2

上面提到&＃xff0c;stack 模板类提供了 2 个参数&＃xff0c;通过指定第二个模板类型参数&＃xff0c;我们可以使用出 deque 容器外的其它序列式容器&＃xff0c;只要该容器支持 empty()、size()、back()、push_back()、pop_back() 这 5 个成员函数即可。
在介绍适配器时提到&＃xff0c;序列式容器中同时包含这 5 个成员函数的&＃xff0c;有 vector、deque 和 list 这 3 个容器。因此&＃xff0c;stack 适配器的基础容器可以是它们 3 个中任何一个。例如&＃xff0c;下面展示了如何定义一个使用 list 基础容器的 stack 适配器&＃xff1a;

std::stack<std::string, std::list<int>> values;


3

可以用一个基础容器来初始化 stack 适配器&＃xff0c;只要该容器的类型和 stack 底层使用的基础容器类型相同即可。例如&＃xff1a;

std::list<int> values {1, 2, 3};
std::stack<int,std::list<int>> my_stack(values);


注意&＃xff0c;初始化后的 my_stack 适配器中&＃xff0c;栈顶元素为 3&＃xff0c;而不是 1。另外在第 2 行代码中&＃xff0c;stack 第 2 个模板参数必须显式指定为 list&＃xff08;必须为 int 类型&＃xff0c;和存储类型保持一致&＃xff09;&＃xff0c;否则 stack 底层将默认使用 deque 容器&＃xff0c;也就无法用 lsit 容器的内容来初始化 stack 适配器。

4

还可以用一个 stack 适配器来初始化另一个 stack 适配器&＃xff0c;只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如&＃xff1a;

std::list<int> values{ 1, 2, 3 };
std::stack<int, std::list<int>> my_stack1(values);
std::stack<int, std::list<int>> my_stack &＃61; my_stack1;
//std::stack> my_stack(my_stack1);


可以看到&＃xff0c;和使用基础容器不同&＃xff0c;使用 stack 适配器给另一个 stack 进行初始化时&＃xff0c;有 2 种方式&＃xff0c;使用哪一种都可以。

stack容器适配器支持的成员函数

对上面的成员函数&＃xff0c;举个例子&＃xff1a;

#include
#include
#include using namespace std;int main()
{//构建 stack 容器适配器list<int> values{ 1, 2, 3 };stack<string, list<int>> my_stack(values);//查看 my_stack 存储元素的个数cout << "size of my_stack: " << my_stack.size() << endl;//将 my_stack 中存储的元素依次弹栈&＃xff0c;直到其为空while (!my_stack.empty()){ cout << my_stack.top() << endl;//将栈顶元素弹栈my_stack.pop();}return 0;
}


输出结果&＃xff1a;

size of my_stack: 3
3
2
1


2 deque

和 stack 栈容器适配器不同&＃xff0c;queue 容器适配器有 2 个开口&＃xff0c;其中一个开口专门用来输入数据&＃xff0c;另一个专门用来输出数据。

这种存储结构最大的特点是&＃xff0c;最先进入 queue 的元素&＃xff0c;也可以最先从 queue 中出来&＃xff0c;即用此容器适配器存储数据具有“先进先出&＃xff08;简称 “FIFO” &＃xff09;”的特点&＃xff0c;因此 queue 又称为队列适配器。

1 queue容器适配器的创建

queue 容器适配器以模板类 queue&＃xff08;其中 T 为存储元素的类型&＃xff0c;Container 表示底层容器的类型&＃xff09;的形式位于头文件中&＃xff0c;并定义在 std 命名空间里。因此&＃xff0c;在创建该容器之前&＃xff0c;程序中应包含以下 2 行代码&＃xff1a;

#include
using namespace std;


1

创建一个空的 queue 容器适配器&＃xff0c;其底层使用的基础容器选择默认的 deque 容器&＃xff1a;

std::queue<int> values;


通过此行代码&＃xff0c;就可以成功创建一个可存储 int 类型元素&＃xff0c;底层采用 deque 容器的 queue 容器适配器。

2

也可以手动指定 queue 容器适配器底层采用的基础容器类型。
例如&＃xff0c;下面创建了一个使用 list 容器作为基础容器的空 queue 容器适配器&＃xff1a;

std::queue<int, std::list<int>> values;


注意&＃xff0c;在手动指定基础容器的类型时&＃xff0c;其存储的数据类型必须和 queue 容器适配器存储的元素类型保持一致。

3

可以用基础容器来初始化 queue 容器适配器&＃xff0c;只要该容器类型和 queue 底层使用的基础容器类型相同即可。例如&＃xff1a;

std::deque<int> values{1,2,3};
std::queue<int> my_queue(values);


由于 my_queue 底层采用的是 deque 容器&＃xff0c;和 values 类型一致&＃xff0c;且存储的也都是 int 类型元素&＃xff0c;因此可以用 values 对 my_queue 进行初始化。

4

还可以直接通过 queue 容器适配器来初始化另一个 queue 容器适配器&＃xff0c;只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如&＃xff1a;

std::deque<int> values{1,2,3};
std::queue<int> my_queue1(values);
std::queue<int> my_queue(my_queue1);
//或者使用
//std::queue my_queue &＃61; my_queue1;


queue容器适配器支持的成员函数

和 stack 一样&＃xff0c;queue 也没有迭代器&＃xff0c;因此访问元素的唯一方式是遍历容器&＃xff0c;通过不断移除访问过的元素&＃xff0c;去访问下一个元素。

上个例子&＃xff1a;

#include
#include
#include using namespace std;int main()
{//构建 queue 容器适配器std::deque<int> values{ 1,2,3 };std::queue<int> my_queue(values);//{1,2,3}//查看 my_queue 存储元素的个数cout << "size of my_queue: " << my_queue.size() << endl;//访问 my_queue 中的元素while (!my_queue.empty()){cout << my_queue.front() << endl;//访问过的元素出队列my_queue.pop();}return 0;
}


输出结果;

size of my_queue: 3
1
2
3


3 priority_queue

priority_queue 容器适配器模拟的也是队列这种存储结构&＃xff0c;即使用此容器适配器存储元素只能“从一端进&＃xff08;称为队尾&＃xff09;&＃xff0c;从另一端出&＃xff08;称为队头&＃xff09;”&＃xff0c;且每次只能访问 priority_queue 中位于队头的元素。
但是&＃xff0c;priority_queue 容器适配器中元素的存和取&＃xff0c;遵循的并不是 “First in,First out”&＃xff08;先入先出&＃xff09;原则&＃xff0c;而是优先级最大的元素最先出队列。

那么&＃xff0c;priority_queue 容器适配器中存储的元素&＃xff0c;优先级是如何评定的呢&＃xff1f;很简单&＃xff0c;每个 priority_queue 容器适配器在创建时&＃xff0c;都制定了一种排序规则。根据此规则&＃xff0c;该容器适配器中存储的元素就有了优先级高低之分。

举个例子&＃xff0c;假设当前有一个 priority_queue 容器适配器&＃xff0c;其制定的排序规则是按照元素值从大到小进行排序。根据此规则&＃xff0c;自然是 priority_queue 中值最大的元素的优先级最高。

priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素&＃xff0c;每当有新元素进入&＃xff0c;它都会根据既定的排序规则找到优先级最高的元素&＃xff0c;并将其移动到队列的队头&＃xff1b;同样&＃xff0c;当 priority_queue 从队头移除出一个元素之后&＃xff0c;它也会再找到当前优先级最高的元素&＃xff0c;并将其移动到队头。

基于 priority_queue 的这种特性&＃xff0c;因此该容器适配器有被称为优先级队列。
priority_queue 容器适配器的定义如下&＃xff1a;

template <typename T,typename Container&＃61;std::vector<T>,typename Compare&＃61;std::less<T> >
class priority_queue{//......
}


可以看到&＃xff0c;priority_queue 容器适配器模板类最多可以传入 3 个参数&＃xff0c;它们各自的含义如下&＃xff1a;

• typename T&＃xff1a;指定存储元素的具体类型&＃xff1b;
• typename Container&＃xff1a;指定 priority_queue 底层使用的基础容器&＃xff0c;默认使用 vector 容器;
• typename Compare&＃xff1a;指定容器中评定元素优先级所遵循的排序规则&＃xff0c;默认使用std::less按照元素值从大到小进行排序&＃xff0c;还可以使用std::greater按照元素值从小到大排序&＃xff0c;但更多情况下是使用自定义的排序规则。

1 创建priority_queue

由于 priority_queue 容器适配器模板位于头文件中&＃xff0c;并定义在 std 命名空间里&＃xff0c;因此在试图创建该类型容器之前&＃xff0c;程序中需包含以下 2 行代码&＃xff1a;

#include
using namespace std;


1

创建一个空的 priority_queue 容器适配器&＃xff0c;第底层采用默认的 vector 容器&＃xff0c;排序方式也采用默认的 std::less 方法&＃xff1a;

std::priority_queue<int> values;


2

可以使用普通数组或其它容器中指定范围内的数据&＃xff0c;对 priority_queue 容器适配器进行初始化&＃xff1a;

//使用普通数组
int values[]{4,1,3,2};
std::priority_queue<int> copy_values(values,values&＃43;4);//{4,3,2,1}
//使用序列式容器
std::array<int,4> values{ 4,1,3,2 };
std::priority_queue<int> copy_values(values.begin(),values.end());//{4,3,2,1}


注意&＃xff0c;以上 2 种方式必须保证数组或容器中存储的元素类型和 priority_queue 指定的存储类型相同。另外&＃xff0c;用来初始化的数组或容器中的数据不需要有序&＃xff0c;priority_queue 会自动对它们进行排序。

3

还可以手动指定 priority_queue 使用的底层容器以及排序规则&＃xff0c;比如&＃xff1a;

int values[]{ 4,1,2,3 };
std::priority_queue<int, std::deque<int>, std::greater<int>> copy_values(values, values&＃43;4);//{1,2,3,4}


priority_queue提供的成员函数

举个例子&＃xff1a;

#include
#include
#include
#include using namespace std;int main()
{//创建一个空的priority_queue容器适配器std::priority_queue<int>values;//使用 push() 成员函数向适配器中添加元素values.push(3);//{3}values.push(1);//{3,1}values.push(4);//{4,3,1}values.push(2);//{4,3,2,1}//遍历整个容器适配器while (!values.empty()){//输出第一个元素并移除。std::cout << values.top()<<" ";values.pop();//移除队头元素的同时&＃xff0c;将剩余元素中优先级最大的移至队头}return 0;
}


输出结果&＃xff1a;

4 3 2 1 %