C++效率掌握之STL库：优先级队列priority_queue && 双端队列deque
C++效率掌握之STL库：优先级队列priority_queue && 双端队列deque
本篇是 STL 库专题之 priority_queue 和 deque，书接上文
1.priority_queue
priority_queue 的主要特征可总结为：
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的，简单来说就是
取出元素的顺序默认是从大到小的 - 此上下文
类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素) - 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，
queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部 - 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过
随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空size()：返回容器中有效元素个数front()：返回容器中第一个元素的引用push_back()：在容器尾部插入元素pop_back()：删除容器尾部元素
- 标准容器类
vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector - 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数
make_heap、push_heap和pop_heap来自动完成此操作
1.1 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;
}⌨️代码输出示例：
1.2 priority_queue常见OJ
1.2.1 数组中的第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();
}
};1.3 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，可用于构建小顶堆
2.deque
2.1 deque原理
🤔什么是deque？
deque也叫做双端队列，虽然叫做队列，但是并不是队列，不符合先进先出的原理deque是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高
deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组，其底层结构如下面的简单分析所示：
首先对两种存储方式进行对比：
- 通常使用
vector数组时，通常是连续存储，但是最麻烦的就是扩容和部分位置的插入删除问题 deque使用的是把存储空间碎片化的方式进行存储
🤔那么是如何实现的呢？
deque 中有一个中控数组，存储每个碎片化数组的地址，每个碎片化数组的大小通常是相等的，所以实际操作都是在碎片化数组上实现的
如何扩容： 直接在中控数组上扩容即可，这就有人问了那和之前的扩容有啥区别，不都是扩容吗？这区别可大了，别忘了中控数组是个指针数组，扩容的代价很小，如果是扩容传统的数组，内置类型的数据还好，但是自定义数据就麻烦了，扩容后的数据迁移涉及实际数据和数据间的连接，特别麻烦，因此 deque 大大降低了扩容的麻烦
如何头部尾部处理数据： deque 是从中间开始插入的，从中间往两侧打开，比如尾插，如图就是从左到右，先插入 10，再插入 20
以上是简单对 deque 的底层进行了解，实际的 deque 底层借助其迭代器维护其假想连续的结构相当复杂：
2.2 deque缺陷
- 相比
vector，极大的缓解了扩容/头插头删问题，头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的
但是对于像 [] 的访问，是数组必须的，像for循环这样大量访问数组的情景很常见，如图分析，显然在这种场景下 deque 的效率就不如 vector 的直接访问数组
- 与
list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段
总的来说： deque 的致命缺陷就是不适合遍历，因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构
2.3 为什么选择deque作为stack和queue的底层默认容器
stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以
queue 是先进先出的特殊线性数据结构，只要具有push_back 和 pop_front 操作的线性结构，都可以作为queue 的底层容器，比如list
但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：
stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。- 在
stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷
2.4 STL标准库中对于stack和queue的模拟实现
2.4.1 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;
};
}2.4.2 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;
};
}希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
腾讯云开发者
