STL ——priority_queue的模拟实现与基本使用 | 仿函数的介绍| 容器适配器的介绍

了解priority_queue

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特
   定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
   代器访问，并支持以下操作：

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

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆

priority_queue的定义方式

1.不指定底层容器和内部需要构造的堆结构。(默认大堆)

priority_queue<int> q1;
1

2.使用vector作为底层容器，内部构造小堆结构

priority_queue<int, vector<int>, greater<int>> q2;
1

3.使用vector作为底层容器，内部构造大堆结构(显示定义)

priority_queue<int, vector<int>, less<int>> q3;
1

其他的接口使用和STL的这些容器的方法都差不多，就不再赘述

priority_queue的模拟实现

向上调整算法和向下调整算法

在模拟实现之前，回顾一下堆的上调整算法和向下调整算法

在之前C语言实现的向下调整算法和向上调整算法

//用于pop堆顶，将堆顶的数据与堆尾交换，然后pop堆尾，再调整堆
void AdjustDown(HPDataType* a, int n, int parent)
{
	assert(a);
	int child = 2 * parent + 1;
	while (child<n)
	{
		if (a[child] < a[child + 1])
		{
			child++;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
//插入小堆的数向上调整
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)  不好
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

这里在c++中我们直接在类内实现成员函数，就不用传入这么多参数了

template<class T,class Container = std::vector<T>>
	class priority_queue {
	public:
		//向上调整 一个堆的末尾插入一个数据后，需要对堆进行调整，使其仍然是一个堆，这时需要用到堆的向上调整算法
		void Adjust_up(int child) {
			int parent = (child - 1) / 2;
			while (child>0) {
				if (_con[child] > _con[parent]) {
					swab(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}
		//向下调整 用于pop堆顶，将堆顶的数据与堆尾交换，然后pop堆尾，再调整堆
		void Adjust_down(int parent){
			int child = 2 * parent + 1;
			while (child < _con.size()) {
				if (child + 1 < _con.size() && _con[child + 1] > _con[child]) {
					++child;
				}
				if (_con[child] > _con[parent]) {
					swap(_con[parent], _con[child]);
					parent = child;
					child = 2 * parent + 1;
				}
				else {
					break;
				}
			}
		}
	private:
		Container_con;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

常用接口实现

void push(const T& x) {
			_con.push_back(x);
			Adjust_up(_con.size()-1);
		}
		void pop() {
			if (!_con.empty()) {
				swap(_con[0], _con[_con.size() - 1]);
				_con.pop_back();
				Adjust_down(0);
			}
		}
		bool empty() {
			return _con.empty();
		}
		const T& top() const {
			return _con[0];
		}
		size_t size() {
			return _con.size();
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

仿函数

在c++标准库中的介绍中，优先级队列的模板参数定义为
template , class Compare = less >
在上面的实现中，是大堆，打印出来是降序排列的，如果我们想要其是小堆怎么办呢？总不能再写一个小堆的向上调整和向下调整算法吧

所以这里就引入了仿函数，也就是这个模板的第三个参数class Compare = less

了解仿函数

在STL源码剖析中对仿函数给出了定义

光看定义肯定是看不懂的，我们直接用例子来说明：

struct lesscmp {
	bool operator()(int x, int y) {
		return x < y;
	}
};
int main() {
	int a = 10, b = 20;
	lesscmp cmp;
	cout << cmp(a, b);
}
1
2
3
4
5
6
7
8
9
10

当然这里的仿函数也可以使用模板，效果都是一样的

template<class T>
struct lesscmp {
	bool operator()(T x, T y) {
		return x < y;
	}
};
int main() {
	int a = 10, b = 20;
	lesscmp<int> cmp;
	cout << cmp(a, b);
}
1
2
3
4
5
6
7
8
9
10
11

引入仿函数的向上调整算法和向下调整算法

// less: 小于的比较
	template<class T>
	struct less {
		bool operator()(const T& x, const T& y) const {
			return x < y;
		}
	};
	// greater: 大于的比较
	template<class T>
	struct greater {
		bool operator()(const T& x, const T& y) const {
			return x > y;
		}
	};
	template<class T,class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue {
	public:
		//向上调整 一个堆的末尾插入一个数据后，需要对堆进行调整，使其仍然是一个堆，这时需要用到堆的向上调整算法
		void Adjust_up(int child) {
			size_t parent = (child - 1) / 2;
			while (child>0) {
				/*if (_con[child] > _con[parent])*/
				if (_cmp(_con[child],_con[parent]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}
		//向下调整 用于pop堆顶，将堆顶的数据与堆尾交换，然后pop堆尾，再调整堆
		void Adjust_down(int parent) {
			size_t child = 2 * parent + 1;
			while (child < _con.size()) {
				/*if (child + 1 < _con.size() && _con[child + 1] > _con[child]) */
				if (child + 1 < _con.size() && _cmp(_con[child + 1], _con[child]))
				{
					++child;
				}
				/*if (_con[child] > _con[parent])*/
				if (_cmp(_con[child],_con[parent]))
				{
					swap(_con[parent], _con[child]);
						parent = child;
						child = 2 * parent + 1;
				}
				else {
					break;
				}
			}
		}
private:
		Container _con;
		Compare _cmp;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

容器适配器

什么是适配器

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

容器适配器的作用

• 改变容器的接口
• 增加容器的功能
• 限制容器的功能

之前的栈，队列和这里的优先级队列就是用的容器适配器，将vector，deque等容器转换成了这些类型的容器

容器适配器的优点

封装性
容器适配器隐藏了底层容器的实现细节，只暴露出特定的接口，使得使用者可以方便地操作容器适配器，而不需要了解底层容器的具体实现。

灵活性
容器适配器可以根据不同的需求选择不同的底层容器来实现功能。例如，可以使用栈来实现适配器，也可以使用队列来实现适配器，这取决于具体的使用场景和要求。

功能拓展
容器适配器可以根据需要进行扩展，添加新的功能或修改现有功能。由于适配器与底层容器解耦，因此可以独立地对适配器进行修改，而不会影响到其他部分的代码。

与标准库兼容
容器适配器通常与标准库的容器接口兼容，这意味着可以通过容器适配器来替换标准容器的使用，而不需要修改其他代码。