C++效率掌握之STL库：优先级队列priority_queue && 双端队列deque

本篇是 STL 库专题之 priority_queue 和 deque，书接上文

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 是大堆

函数名	功能说明
empty	检测优先级队列是否为空，是返回 true，否则返回 false
size	返回 stack 中元素的个数
top	返回优先级队列中最大(最小元素)，即堆顶元素
push	在优先级队列中插入元素 x
pop	删除优先级队列中最大(最小)元素，即堆顶元素

💻代码测试示例：

#include <queue>
#include <iostream>
using namespace std;

int main()
{
	vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int> q1;
	for (auto& e : v)
		q1.push(e);
	cout << q1.top() << endl;

	q1.pop();
	cout << q1.top() << endl;

	cout << "empty:" << q1.empty() << endl;
	cout << "size:" << q1.size() << endl;

	return 0;
}

⌨️代码输出示例：

priority_queue常见OJ

数组中的第K个最大元素

✏️题目描述：

✏️示例：

传送门： 数组中的第K个最大元素

题解:

因为优先级队列的本质是堆，所以每次删除都会把堆的最大元素放到堆顶，删除 k 次，第 k 个元素就在栈顶

关于堆的详细介绍：

传送门：【初阶数据结构】森林里的树影 “堆” 光：堆

💻代码实现：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int> p(nums.begin(), nums.end());
        for(int i= 0; i < k-1; ++i)
        {
            p.pop();
        }
        return p.top();
    }
};

priority_queue模拟实现

通过对 priority_queue 的底层结构就是堆，因此此处只需对对进行通用的封装即可

#include <iostream>
using namespace std;

#include <vector>
// priority_queue--->堆
namespace bite
{
	template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		// 创造空的优先级队列
		priority_queue() : c() {}

		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last)
		{
			// 将c中的元素调整成堆的结构
			int count = c.size();
			int root = ((count - 2) >> 1);
			for (; root >= 0; root--)
				AdjustDown(root);
		}

		void push(const T& data)
		{
			c.push_back(data);
			AdjustUP(c.size() - 1);
		}

		void pop()
		{
			if (empty())
				return;

			swap(c.front(), c.back());
			c.pop_back();
			AdjustDown(0);
		}

		size_t size()const
		{
			return c.size();
		}

		bool empty()const
		{
			return c.empty();
		}

		// 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性
		const T& top()const
		{
			return c.front();
		}
	private:
		// 向上调整
		void AdjustUP(int child)
		{
			int parent = ((child - 1) >> 1);
			while (child)
			{
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					child = parent;
					parent = ((child - 1) >> 1);
				}
				else
				{
					return;
				}
			}
		}

		// 向下调整
		void AdjustDown(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < c.size())
			{
				// 找以parent为根的较大的孩子
				if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
					child += 1;

				// 检测双亲是否满足情况
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					return;
			}
		}
	private:
		Container c;
	};
}

Compare 比较器：这里涉及仿函数的应用，后面会专门讲解

• less 结构体：重载了 () 运算符，用于比较两个元素，当 left 小于 right 时返回 true，可用于构建大顶堆
• greater 结构体：同样重载了 () 运算符，当 left 大于 right 时返回 true，可用于构建小顶堆

deque

deque原理

🤔什么是deque？

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

deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组，其底层结构如下面的简单分析所示：

首先对两种存储方式进行对比：

• 通常使用 vector 数组时，通常是连续存储，但是最麻烦的就是扩容和部分位置的插入删除问题
• deque 使用的是把存储空间碎片化的方式进行存储

🤔那么是如何实现的呢？

deque 中有一个中控数组，存储每个碎片化数组的地址，每个碎片化数组的大小通常是相等的，所以实际操作都是在碎片化数组上实现的

如何扩容： 直接在中控数组上扩容即可，这就有人问了那和之前的扩容有啥区别，不都是扩容吗？这区别可大了，别忘了中控数组是个指针数组，扩容的代价很小，如果是扩容传统的数组，内置类型的数据还好，但是自定义数据就麻烦了，扩容后的数据迁移涉及实际数据和数据间的连接，特别麻烦，因此 deque 大大降低了扩容的麻烦

如何头部尾部处理数据： deque 是从中间开始插入的，从中间往两侧打开，比如尾插，如图就是从左到右，先插入 10，再插入 20

以上是简单对 deque 的底层进行了解，实际的 deque 底层借助其迭代器维护其假想连续的结构相当复杂：

deque缺陷

• 相比 vector ，极大的缓解了扩容/头插头删问题，头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必 vector 高的

但是对于像 [] 的访问，是数组必须的，像for循环这样大量访问数组的情景很常见，如图分析，显然在这种场景下 deque 的效率就不如 vector 的直接访问数组

• 与 list 比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段

总的来说： deque 的致命缺陷就是不适合遍历，因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构

为什么选择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 的优点，而完美的避开了其缺陷

STL标准库中对于stack和queue的模拟实现

stack

#include<deque>
namespace bite
{
	template<class T, class Con = deque<T>>
	//template<class T, class Con = vector<T>>
	//template<class T, class Con = list<T>>
	class stack
	{
	public:
		stack() {}
		void push(const T& x) { _c.push_back(x); }
		void pop() { _c.pop_back(); }
		T& top() { return _c.back(); }
		const T& top()const { return _c.back(); }
		size_t size()const { return _c.size(); }
		bool empty()const { return _c.empty(); }
	private:
		Con _c;
	};
}

queue

#include<deque>
#include <list>
namespace bite
{
	template<class T, class Con = deque<T>>
	//template<class T, class Con = list<T>>
	class queue
	{
	public:
		queue() {}
		void push(const T& x) { _c.push_back(x); }
		void pop() { _c.pop_front(); }
		T& back() { return _c.back(); }
		const T& back()const { return _c.back(); }
		T& front() { return _c.front(); }
		const T& front()const { return _c.front(); }
		size_t size()const { return _c.size(); }
		bool empty()const { return _c.empty(); }
	private:
		Con _c;
	};
}

---

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！