【C++】详细介绍：priority_queue的使用、适配器、deque介绍、仿函数

目录

一、介绍

二、使用

三、函数模版和类模板的区别

四、适配器

1、适配器适配栈

扩展：

2、deque（双端队列）

缺省模版

五、仿函数

一、介绍

（1）、priority_queue称为优先级队列，是一种容器适配器，不是队列也不是容器。

（2）、该结构的底层是堆结构，默认是大堆，用模版参数来区分是大堆还是小堆。

（3）、具体信息可查看官网手册：https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue

二、使用

注意： 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

（1）、大堆使用：

//默认是大堆
priority_queue<int, vector<int>> big_heap;
big_heap.push(1);
big_heap.push(10);
big_heap.push(2);
big_heap.push(4);
big_heap.push(2);
big_heap.push(4);
while (!big_heap.empty())
{
	cout << big_heap.top() << " ";
	big_heap.pop();
}
cout << endl;

（2）、小堆使用,第三个参数模版传大于

//小堆，第三个模版参数用大于
priority_queue<int, vector<int>, greater<int>> small_heap;
small_heap.push(1);
small_heap.push(10);
small_heap.push(2);
small_heap.push(4);
small_heap.push(2);
small_heap.push(4);
while (!small_heap.empty())
{
	cout << small_heap.top() << " ";
	small_heap.pop();
}

三、函数模版和类模板的区别

如下：

sort(s1.begin(), s1.end(), greater<int>());
priority_queue<int, vector<int>, greater<int>>;

看这两段代码的，第一个是sort函数的传参，第二个是类的传参，看第三个参数，看似好像没区别，但实则有个括号的差异，一个传递的是对象，一个传递的是类型

四、适配器

priority_queue的实现是通过适配器实现的，那么什么是适配器呐？

  适配器是一种设计模式，该种模式是将一个类的接口转换成客户希望的另外一个接口。

也就是说，是通过复用对应容器的接口来构成自己想要的结构。适配器的核心是大量复用。  

1、适配器适配栈

先看源代码：

namespace HF
{
	template<class T ,class Container>
	class stack
	{
	private:
		Container _con;
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	};
}

HF::stack<int,vector<int>> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
while (!pq.empty())
{
	cout << pq.top() << " ";
	pq.pop();
}

看代码我们更容易理解适配器的概念，首先用一个类模版，第一个参数T是数据类型，第二个参数Container是具体的容器，为了实现我们需要的结构，必须确保我们所传入的容器有对应的接口：

如上我们实现栈，而栈的核心接口就是插入（push_back），删除（pop_back），取栈顶元素（top），判空（empty），而我们传入的模版是vector类型：

很显然vector都具备这些接口，所以可以用vector适配出一个栈，其步骤就是在栈的相应接口下调用vector对应的接口：

我们知道，因为我们模版传入的是vector，所以成员变量_con就是vector对象，所以就复用相应接口。

扩展：

根据上面内容我们可以思考一个问题：

​​​​​​vector底层是连续的空间，所以适配出的栈就是数组栈，那么当我们传的模版是list，自然而然适配出的就是链式栈。

2、deque（双端队列）

（1）、手册官网： https://legacy.cplusplus.com/reference/deque/deque/?kw=deque

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

（3）、注意：deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维 数组。

（4）、也就是说deque是包含头插头删尾插尾删等一系列接口的东西，相当于把vector和list的优点结合在一起。（但要注意，并不能取代vector和list）

由此我们引出以下内容：