🍑个人主页：Jupiter. 🚀 所属专栏：C++学习笔记 欢迎大家点赞收藏评论😊

---

容器适配器

什么是容器适配器

容器适配器是一种设计模式，它通过封装现有的序列容器类，并重定义其成员函数，以提供不同的功能或满足特定的需求。这种适配器类似于电源适配器，它将不兼容的电源（如不同国家的电压标准）转换可用的电源（即适合电器使用的电压），以便用户能够方便地使用各种电器。

在计算机编程中，容器适配器允许程序员使用已经存在的序列容器类（如vector、deque、list等），同时获得预定义的特定功能，如stack实现后进先出（LIFO）存储、queue实现先进先出（FIFO）存储、以及priority_queue实现基于优先级的存储。

容器适配器本质上是容器的一种变体，它利用了其他基础容器模板类中已经实现的成员函数，并在必要时添加或创新自己的成员函数。

如图：

STL中stack，queue在底层中的结构

STL中stack与queue不属于容器，而是容器适配器，他们是基于已经存在的类（容器）上面，对该类（容器）的接口进行了包装，STL中stack和queue默认使用deque；

可以通过文档发现：

相关适配器的介绍及实现

简单的说，这里的适配器的实现，就是在一个类里面，定义一个其他容器的对象A（能支持该适配器B的功能），然后在实现 B 所需要的函数的时候，在函数里面调用 A 的成员函数 来实现 B的函数 或则 B函数 的某部分，然而实现B；

可以结合下面的例子看看：

stack

stack的介绍

• stack的文档 link

• stack是一种容器适配器，具有 后进先出 的特点，是只允许在一端进行删除，插入，提取操作的容器适配器；

• stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

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

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

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

后进先出特点

stack相关函数

实现

    //这里的Cintainer不确定是什么，默认不传我们给的是deque<int>，和库里面一致
	template<class T, class Container=deque<int>>  //模板参数是传类型
	class stack
	{
	public:
		stack()         //初始化，会去调用对象_con的构造函数
			:_con()     //这里_con默认是deque
		{ }
		void push(const T& x)    //这里成员函数名可以自己随便修改，这里是为了和库里面的一致
		{
			_con.push_back(x);    //这里调用的函数必须是对象_con的成员函数，并且名字必须相同
		}
		void pop()         
		{
			_con.pop_back();   //下面的调用和上面的都类似
		}
		T& top()
		{
			return _con.back();   //调用_con的取头数据函数
		}
		bool empty()
		{
			return _con.empty();    //调用_con的判空函数
		}
		size_t size()
		{
			return _con.size();    //调用_con的size()函数
		}
	private:     
		Container _con;       //声明一个Container对象
	};

stack的实现完全就是自己什么都不做，全去调用Contaoner的成员函数就可以实现的，下面的queue也是一样；

queue

queue的介绍

• 文档链接: link

• 队列是一种容器适配器，专门用于在先进先出（比如现实中取号排队的问题，越早取号的先）中操作，其中从容器一端插入元素，另一端提取元素；

• 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

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

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

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

先进先出 特点

函数使用

实现

与stack的实现一样

template<class T,class Container=deque<int>>   //库里面一致，默认是deque<int>
class quque
{
public:
	quque()
		:_con()
	{}
	void push(const T& x)
	{
		_con.push_back(x);    //调用_con的成员函数
	}
	void pop()
	{
		_con.pop_front();
	}
	T& top()
	{
		return _con.front();
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};

priority_queue

priority_queue的介绍

• priority_queue文档链接: link

• 优先队列是一种容器适配器，类似于堆，默认情况下是大堆，即堆顶的元素总是它所包含的元素中最大的；

• 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

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

• 需要支持随机访问迭代器，以便始终在内部保持堆结构；支持以下操作：

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

函数使用

实现

仿函数的简单介绍

• 仿函数，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个perator()，这个类就有了类似函数的行为，就是一个仿函数类了；

• 有了仿函数类过后，再结合模板使用，就可以使一些需要重复使用的代码独立出来，以便下次复用，这样有利于资源的管理（这点可能是它相对于函数最显著的优点了）。

• 就比如下面我们所需要实现的优先队列，默认的是大堆（如图，库里面是反着的，less是大堆，greater是小堆），当我们想要小堆的时候，就需要用仿函数，这样只需要我们再使用优先级队列时改变传的模板参数即可；
  

向上调整与向下调整思想及图解链接: link

template<class T>
class lesser              
{
public:
	bool operator()(const T& x, const T& y)   //重载operator()
	{
		return x < y;                  //小于的比较逻辑
	}
};

template<class T>                 
class greater
{
public:
	bool operator()(const T& x, const T& y)     //重载operator()
	{
		return x > y;              //大于的比较逻辑
	}
};

namespace P
{                         
	template<class T, class Container=vector<int>,class Compare= less<int> >
	class priority_quque
	{
	public:
		priority_quque()
			:_con()
		{}
		void AdjustUp(int child){
			Compare _com;
			int parent = (child - 1) / 2;
			while (parent >= 0){
				if(_com(_con[child],_con[parent])){
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}
		void AdjustDown(int parent)
		{
			Compare _com;
			int child = parent * 2 + 1;

			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _com(_con[child+1] , _con[child]))
					++child;
				//如果父亲比孩子小，交换
				if(_com(_con[child],_con[parent]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;                           //向下走
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);    //尾插一个数据
			AdjustUp(size() - 1);  //然后向上调整
		}
		void pop()
		{
			std::swap(_con[0], _con[size() - 1]);   //堆顶与最后一个元素交换，然后删除最后一个元素，然后从堆顶开始，向下调整
			_con.pop_back();
			AdjustDown(0);     //向下调整
		}
		T& top()
		{
			return _con.front();
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

}

deque的介绍

deque(双端队列)：是一种双开口的 “连续” 空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

所说的来连续，并不是说都是连续的，在底层，deque是一段一段的数组，数组中存储的数据，然后有一个指针数组存储每一个数组的地址，这样，与vector比较，头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是有一个致命的缺陷是：中间插入和删除效率与下标随机访问的效率不高，这个缺陷是底层物理结构所导致的；

为什么选择deque作为stack和queue的底层默认容器？

• stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；
• queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。
  但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。

---