【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

一、容器适配器

1、什么是容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

例如我们常见的充电器就是一种适配器，它将我们常用的220V交流电压转化为4，5V (或者其他更高的电压) 的直流电压来给我们的电子设备进行充电。

2、STL标准库中的容器适配器

虽然stack和queue priority_queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配

器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，priority_queue默认使用了vector。

二、stack的模拟实现

1、stack的简单介绍

相关文档
stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，但这些容器类应该支持以下操作：

• empty：判空操作
• back：获取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部删除元素操作

标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

2、栈的模拟实现

为了栈的通用性，这里我们使用模板来进行模拟栈，关于栈的底层容器这里我们选择vector来进行模拟实现。

template<class T, class Container = vector<T>>
class stack
{
public://栈的插入void push(const T& val){//使用底层容器中尾插函数进行插入,栈只能进行栈顶插入和删除_con.push_back(val);}//栈的删除void pop(){//使用底层容器中尾删函数进行插入,栈只能进行栈顶插入和删除_con.pop_back();}//获取栈顶元素T& top(){//返回底层容器中最后一个数据return _con.back();}//const 版本const T& top() const{return _con.back();}//获取数据个数size_t size() const{//返回底层容器中数据的个数return _con.size();}//判空函数bool empty() const{//对底层容器进行判空return _con.empty();}
private://成员变量是一个容器创建的对象Container _con;
};

三、queue的模拟实现

1、queue的简单介绍

相关文档
queue底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

• empty：检测队列是否为空
• size：返回队列中有效元素的个数
• front：返回队头元素的引用
• back：返回队尾元素的引用
• push_back：在队列尾部入队列
• pop_front：在队列头部出队列

标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2、queue的模拟实现

为了queue的通用性，这里我们使用模板来进行模拟queue，关于queue的底层容器这里我们选择list来进行模拟实现。

template<class T, class Container = list<T>>
class queue
{
public://队列的插入void push(const T& val){//使用底层容器中尾插函数进行插入,队列只能进行队尾插入_com.push_back(val);}//队列的删除void pop(){//使用底层容器中头删函数进行删除,队列只能进行队头删除_com.pop_front();}//获取队头数据T& front(){//返回底层容器中第一个数据return _com.front();}//const版本const T& front() const{return _com.front();}//获取队尾数据T& back(){//返回底层容器中最后一个数据return _com.back();}//const版本const T& back() const{return _com.back();}//获取数据个数size_t size() const{//返回底层容器中数据的个数return _com.size();}//判空函数bool empty() const{//对底层容器进行判空return _com.empty();}
private://成员变量是一个容器创建的对象Container _com;
};

四、priority_queue的模拟实现

1、priority_queue的简单介绍

相关文档
优先队列是一种容器适配器，它其实就是我们数据结构中的堆,默认情况下priority_queue是大堆。

priority_queue底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

• empty：检测容器是否为空
• size：返回容器中有效元素个数
• front：返回容器中第一个元素的引用
• push_back：在容器尾部插入元素
• pop_back：删除容器尾部元素

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

2、priority_queue的模拟实现

与前面的栈与队列一样priority_queue前两个模板参数都类似,但是priority_queue要有第三个模板参数，这个参数表示按照什么方式进行比较，即建立大堆还是小堆。

//第三个参数是比较方式，需要传递一个仿函数来确定比较方式,默认传递的是less<T>,表示建大堆
template<class T, class Container = vector<T>, class Comper = less<T>>
class priority_queue
{
public://获取堆顶数据const T& top() const{//返回底层容器的第一个数据return _con.front();}//获取数据个数size_t size() const{//返回底层容器的数据个数return _con.size();}//判空函数bool empty() const{//判断底层容器是否为空return _con.empty();}//堆的插入void push(const T& val){//从尾部插入_con.push_back(val);int child = _con.size() - 1;//向上调整重新建堆AdjustUp(child);}//堆的删除void pop(){//检查堆是否为空assert(!_con.empty());//交换堆顶与最后一个数据swap(_con.front(), _con.back());//删除最后一个数据_con.pop_back();//从堆顶进行向下调整，重新建堆AdjustDown(0);}private://向上调整算法void AdjustUp(int child){Comper com;int parent = (child - 1) / 2;while (child > 0){//这里使用了仿函数来判断建立什么堆//比较的位置（_con[parent], _con[child]）是不能换的！！！if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下调整算法void AdjustDown(int parent){Comper com;//默认左孩子更符合建堆的要求int child = parent *2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && Comper()(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//成员变量是一个容器创建的对象Container _con;
};