三、priority_queue的介绍及使用
💦 priority_queue的介绍
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素 (优先队列中位于顶部的元素)。
- 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的 “ 尾部 ” 弹出，其称为优先队列的顶部。
- 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
➡ empty()：检测容器是否为空。
➡ size()：返回容器中有效元素个数。
➡ front()：返回容器中第一个元素的引用。
➡ push_back()：在容器尾部插入元素。
➡ pop_back()：删除容器尾部元素。 - 标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用 vector。
- 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和pop_heap 来自动完成此操作。
注意这里的优先级队列不符合队列的先进先出特性，它的 push 没有要求，pop/top 是取优先级最高的，优先级指的是大小，这里默认是大的优先级高，如果要让小的优先级高，就需要仿函数来控制。但要注意并不一定是大的优先级高，小的优先级低，因为对于用数字来评分 (大的高) 是一种场景，对于用字母来评分 (小的高) 又是一种场景。
💦 priority_queue的使用
优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下 priority_queue 是大堆。
| 函数声明 | 接口说明 |
| priority_queue()/priority_queue(first,last) | 构造一个空的优先级队列 |
| empty() | 检测优先级队列是否为空，是返回 true，否则返回 false |
| top() | 返回优先级队列中最大 (最小) 元素，即堆顶元素 |
| push(x) | 在优先级队列中插入元素 x |
| pop() | 删除优先级队列中最大 (最小) 元素，即堆顶元素 |
#include<iostream> #include<queue> #include<functional> //greater的头 using namespace std; void test_priority_queue() { //priority_queue<int> pq;//默认是大堆,大的优先级高 priority_queue<int,vector<int>, greater<int>> pq;//默认是小堆,小的优先级高。控制大小堆的是第3个参数,你要传第3个参数,必须先传第2个参数,因为它也是缺省的 pq.push(1); pq.push(10); pq.push(11); pq.push(3); pq.push(5); pq.push(8); while(!pq.empty()) { //取堆顶的数据 cout << pq.top() << " "; //出堆顶(与最后元素交换,再删除它),向下调整 pq.pop(); } cout << endl; } int main() { test_priority_queue(); return 0; }
💦 priority_queue的OJ
1、数组中的第K个最大元素＜难度系数⭐⭐＞
📝 题述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
💨示例1：
输入：[3,2,1,5,6,4] 和 k = 2
输出：5
💨示例2：
输入：[3,2,3,1,2,4,5,5,6] 和 k = 4
输出：4
⚠ 提示：
- 1 <= k <= nums.length <= 104
- -104 <= nums[i] <= 104
🧷 平台：Visual studio 2017 && windows
🔑 核心思想：这道题是一道 top-k 的变形问题。这里用 C++ 来做就非常简单，有如下方案：
- 先调用 <algorithm> 中的 sort 对数组排升序，随后算倒数第 k 大就是正数的 nums.size() - k 为下标的位置。当然直接排降序也可以，其底层是快排。时间复杂度为 O(N*logN)。无空间复杂度。
- 用 priority_queue 建一个大堆，然后pop k - 1 个，再 top() 就是第 k 大的。把 nums 的数据往 maxHeap 里放有 2 种方式。时间复杂度为 O(N + K * logN)，N 是向下调整建堆，K * logN 是 pop。空间复杂度 O(N)。
➡ 遍历nums，一个个 push。
➡ 构造函数里提供迭代器区间初始化。 - 建一个 k 个数的小堆，其它数依次比较，它比堆顶的数要大，那么就 pop 堆顶，再 push 这个数，最后堆顶的数据就是第 k 大的。时间复杂度是 O(K + (N - K) * logK)，空间复杂度是 O(K)。就目前的数据量来说，其实第二种方案和第三种方案的效率差不多，但是当 N 远大于 K 时，尤其是大到内存存不下 (方案一、二都不能适用)，第三种方案更适用，此时可以认为它的时间复杂度是 O(N - K) ➡ O(N)。
🧿 方案一
class Solution { public: int findKthLargest(vector<int>& nums, int k) { // //RandAccessIterator,sort默认是升序 // sort(nums.begin(), nums.end()); // //此时倒数第k大就是正数的nums.size()-k为下标的位置。 // return nums[nums.size() - k]; //sort排降序 //greater<int> g; //sort(nums.begin(), nums.end(), g); sort(nums.begin(), nums.end(), greater<int>());//同上,匿名对象 //此时k-1作为下标就是第k大的 return nums[k - 1]; } };
🧿 方案二
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> maxHeap(nums.begin(), nums.end()); while(k-=1)//同k-=1 { maxHeap.pop(); } //此时堆顶既是第k大 return maxHeap.top(); } };
🧿 方案三
class Solution { public: int findKthLargest(vector<int>& nums, int k) { //建k个数的小堆 priority_queue<int, vector<int>, greater<int>> kMinHeap; for(size_t i = 0; i < k; ++i) { kMinHeap.push(nums[i]); } //再用剩余的数比较 for(size_t j = k; j < nums.size(); ++j) { if(kMinHeap.top() < nums[j]) { kMinHeap.pop(); kMinHeap.push(nums[j]); } } //此时的堆顶就是第k大的 return kMinHeap.top(); } };
💦 priority_queue的模拟实现
💨PriorityQueue.h
#pragma once #include<vector> #include<list> #include<iostream> using namespace std; namespace bit { //仿函数/函数对象——自定义类型,类型的对象可以像函数一样使用 template<class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> class Greater { public: bool operator()(const T& x, const T& y) { return x > y; } }; //模板参数->类型 //函数参数->对象 //less->大堆 greater->小堆,默认是Less template<class T, class Container = vector<T>, class Compare = Less<T>> class priority_queue { public: priority_queue() {} template<class InputIterator> priority_queue(InputIterator first, InputIterator last)//可以传任意类型的迭代器 { //插入数据 while(first != last) { _con.push_back(*first); ++first; } //建堆 for(int i = (_con.size() - 1 - 1) / 2; i >= 0; --i) { AdjustDown(i); } } void AdjustUp(size_t child) { Compare com; size_t parent = (child - 1) / 2; while (child > 0) { //if (_con[parent] < _con[child]) if (com(_con[parent], _con[child])) { swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else//父亲>=孩子 { break; } } } void AdjustDown(size_t parent) { Compare com; size_t child = parent * 2 + 1; while (child < _con.size()) { //if (child + 1 < _con.size() && _con[child] < _con[child + 1]) if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { ++child; } //if (_con[parent] < _con[child]) if (com(_con[parent], _con[child])) { swap(_con[parent], _con[child]); parent = child; child = parent * 2 + 1; } else { break; } } } void push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1); } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } const T& top() const { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con;//构造析构等可以不写,因为这是自定义类型 }; void test_priority_queue() { //priority_queue<int> pq; priority_queue<int, vector<int>, Greater<int>> pq; pq.push(1); pq.push(10); pq.push(11); pq.push(3); pq.push(5); pq.push(8); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; list<int> lt = { 2, 5, 1, 3, 4 }; priority_queue<int, vector<int>, greater<int>> pq1(lt.begin(), lt.end()); while (!pq1.empty()) { cout << pq1.top() << " "; pq1.pop(); } cout << endl; } }
💨test.cpp
int main() { bit::test_priority_queue(); return 0; }
📝说明
- List item
在以前我们要让大堆变小堆，都是直接去改符号，那如何能不改符号的情况下就能达到效果呢 ❓
C语言其实可以利用函数指针来解决。但是 C++ 放弃用函数指针的方式，且非常不建议用函数指针，因为比较复杂。可以说 C++ 里的仿函数/函数对象就是为了替代 C语言里的函数指针。
“ () ” 的功能可以提高优先级、强制类型转换、函数名 (形参表)，仿函数用的是函数名 (形参表)。我们实现两个类，分别重载 “ () ” 完成比较大小功能，然后用 priority_queue 这个类来实例化控制。
- List item
对比 priority_queue 的仿函数和 <algorithm> 中 sort 的仿函数 ❗
priority_queue 是一个类，最好通过模板参数来传递，传的是类型。
这里 less 中给的是 typename Container::value_type，并没有很特别的原因，less 里可以直接给 T，因为它是取 Container 中的 value_type，value_type 是被 typedef 的第一个模板参数，也就是 T。我们要去 Container 中取 value_type。Container 是一个模板，不知道它具体是啥，因为 vector 没有被实例化，所以去取可能会报错，所以加上 typename 是告诉编译器，后面是一个类型，当然报错与否，主要看编译器。这里后面遇到合适的场景会再谈。
sort 是一个函数，最好通过参数来传递。
类模板是显示实例化的，所以说我们可以显示的指定参数；但是函数模板一般是通过实参去推演的，所以说 sort 得写在函数参数里。所以 priority_queue 是传类型，sort 是传对象。
💦 仿函数的变异玩法
要求往优先级队列里放一个日期类，且取出最大的日期 ❓
🧿 方案一：
#include<queue> #include<iostream> using namespace std; class Date { public: Date(int year = 2022, int month = 5, int day = 1) : _year(year) , _month(month) , _day(day) {} bool operator<(const Date& d)const { return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day); } friend ostream& operator<<(ostream& _cout, const Date& d); private: int _year; int _month; int _day; }; ostream& operator<<(ostream& _cout, const Date& d) { _cout << d._year << "-" << d._month << "-" << d._day << endl; return _cout; } int main() { //我们可以放int,也可以放类 priority_queue<Date> pq; pq.push(Date(2021, 11, 24)); pq.push(Date(2021, 10, 24)); pq.push(Date(2021, 12, 24)); pq.push(Date(2022, 1, 24)); //pq是自定义类型,所以上面需要重载<<,要取最大的日期,需要重载< cout << pq.top() << endl; pq.pop(); return 0; }
🧿 方案二：
假设极端情况，如果存的是日期类指针呢，如果再用上面的方式，取不出来，因为它比的是地址。解决方案就是我们自己实现仿函数来控制。
#include<queue> #include<iostream> using namespace std; class Date { public: Date(int year = 2022, int month = 5, int day = 1) : _year(year) , _month(month) , _day(day) {} bool operator<(const Date& d)const { return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day); } friend ostream& operator<<(ostream& _cout, const Date& d); friend class PDateLess; private: int _year; int _month; int _day; }; ostream& operator<<(ostream& _cout, const Date& d) { _cout << d._year << "-" << d._month << "-" << d._day << endl; return _cout; } class PDateLess { public: bool operator()(const Date* p1, const Date* p2) { /*if(p1->_year < p2->_year) || (p1->_year == p2->_year && p1->_month < p2->_month) || (p1->_year == p2->_year && p1->_month == p2->_month && p1->_day < p2->_day) { return true; } else { return false; }*/ //同上,重载了<的情况 return *p1 < *p2; } }; int main() { priority_queue<Date*, vector<Date*>, PDateLess> pq; pq.push(new Date(2023, 11, 24)); pq.push(new Date(2021, 10, 24)); pq.push(new Date(2021, 12, 24)); pq.push(new Date(2022, 1, 24)); cout << (*pq.top()) << endl; pq.pop(); return 0; }
最后这里想说明的是我们可以通过仿函数来控制比较方式。
四、容器适配器
💦 什么是适配器
适配器是一种设计模式 (设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
💦 STL标准库中stack和queue的底层结构
虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和队列只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque，比如：
💦 deque的简单介绍(了解)
这里我们只是了解了解，想更深入可以去配合着源码看候捷老师的《STL源码剖析》。
1、deque的简单使用
void test_deque() { deque<int> dq; dq.push_back(1); dq.push_back(2); dq.push_front(3); dq.push_front(4); //dq.insert(); //dq.erase(); dq.pop_back(); dq.pop_front() for(size_t i = 0; i < dq.size(); ++i) { cout << dq[i] << " "; } cout << endl; }
📝说明
通过以上操作我们可以看出 deque 融合了 vector and list 的优点，并且从使用的角度避开了 vector and list 各自的缺点。
- vector 的缺点是需要扩容，且头部和中间的插入删除。
- list 的缺点是 “ [ ] ”，它不支持任意位置的随机访问。
那就目前来看 deque 可以认为是最完美的线性表。那我们直接学 deque 就行了，还学啥 vector and list 呢 ？ 实际 deque 并没有崭露头角，想要了解从使用方面 deque 这么牛逼，却没有把 vector and list 替换掉，就需要了解 deque 的底层实现(这里我们也只是了解，不会模拟实现)。
2、deque的原理介绍
deque(双端队列)：但是记住，它与实际队列的先进先出的性质没有关联，也就是说 deque 并不要求先进先出。它是一种双开口的 " 连续 " 空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)，与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。
我们要继续分析 deque 就要先分析 vector and list，因为开发者肯定是从它们俩上受启发的。
- vector 是连续的物理空间，它的优点是 a)尾插、尾删效率很高，最重要的是它支持随机访问 b)cpu高速缓存命中率很高。它的缺点是 a)空间不够，就需要增容，增容代价大，还存在一定的空间浪费。 b)头部和中间的插入删除是 O(N)，效率低。
- list 是非连续的物理空间，它的优点是 a)按需申请释放空间。b)任意位置插入删除都是 O(1)，效率高。它的缺点是 a)不支持随机访问。b)cpu高速缓存命中率低。
可以看到 vector and list 的优缺点是互补的，vector 的优点大概就是 list 的缺点，vector 的缺点大概是 list 的优点，list 的优点大概就是 vector 的缺点，list 的缺点大概是 vector 的优点。
结合 vector and list 的优缺点，开发者就设计了 deque(但这似乎在很多场景下是一个相对比较无用的设计)。
deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组，其底层结构如下图所示：
deque 设计的真正复杂的是它的迭代器，这也是它的核心。我们碰到的迭代器要么是原生指针，要么是类封装的指针。而 deque 的迭代器封装了 4 个指针。
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其 “ 整体连续 ” 以及随机访问的假象，任务就落在了 deque 的迭代器身上，因此 deque 的迭代器设计就比较复杂，如下图所示：
📝说明：
- 它的迭代器有 4 个指针，其中 first and last 分别指向一段 buff 的开始和结束，cur 指向当前迭代器所访问的位置，node 指向中控数组。
- 遍历：begin() 给了第一个 buff 里面，*cur 就是第一个数据，++cur 就指向第二个数据，cur == last 时，第一个 buff 走完，随后 node = *node++，把 first and last 定位到下一个 buff 的对应位置，然后接着遍历即可。
以上内容在时间有富余的情况下可以在深挖。不过有人也遇到过相关面试题。
【面试题】
结合 vector and list 的优缺点，有没有什么改进的方案 ❓
这里呢，不要一上嘴就谈 deque 迭代器的 4 个指针啥的，你可以先不需要谈细节的实现。就谈可以实现固定数组的 buff，头插、尾插，再通过中控数组也就是指针数组来管理 buff，如果中控满了，扩容中控。在没有良好功底的情况下，面试官不问迭代器的实现就不谈，避免踩坑，因为往下会把这个问题扯的很深。
2、deque的缺陷及优点
咦，上面 deque 不是挺牛逼的吗 ？
deque 叫双端队列，说明它很适合头插头删，尾插尾删，也说明 deque 很适合 (比 vector and list 都适合) 去做 stack and queue 的默认适配容器，它尾插数据相比 vector 没有扩容，相比 list 它的缓存利用率很高。所以说 deque 最大的优点是做 stack and queue 的默认适配容器。
deque 的一大缺陷就是中间插入、删除，效率很低，比如要删除一个数据，这里有两种实现方案：
- 可以头往前挪，可以尾往前挪，也可以哪一端少就挪哪一端，这又回到 vector 的问题了。
- 只挪当前 buff 的数据，记录当前 buff 的 size(可以定义结构体，它里面放中控数组及 size)，少一个就缩容，多一个就增容，但它始终都要挪动数据。且当 buff 的大小不是固定后，“ [ ] ” 就不好计算了。
整体而言，第一种，中间插入删除的效率就和 vector 一样了，而 " [ ] " 的效率好歹高点；第二种，中间插入删除的效率变高了，而 " [ ] " 的效率变低了。所以对于 deque 中间插入删除操作类似于一碗水端不平的问题。大家可以去瞅下 SGI 版本的 deque 是怎么实现中间插入删除的。
deque 的另一个缺陷是不够极致， deque 是一种折中的方案设计。随机访问效率不及 vector，任意位置插入删除不及 list，它真正的优点是头尾插入删除。你可以理解 vector 是一面很锋利的刀，list 也是一面很锋利的刀，所以铁匠就设计铸造出一把两面都很锋利的刀，这就导致了两面都不够锋利，它是一种不够极致，折中的设计。所以严格来说 deque 是一个挺失败的设计。
使用场景 ❓
- 数据排序，使用 vector。
- 任意位置插入、删除，使用 list。
- 头尾插入删除 (stack and queue) 用 deque。
💦 为什么选择deque作为stack和queue的底层默认容器
也就是说 stack 为啥不用 vector 作为默认容器；queue 为啥不用 list 做为默认容器 ❓
stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back and pop_back 操作的线性结构，都可以作为 stack 的底层容器，比如 vector and list 都可以；queue 是先进先出的特殊线性数据结构，只要具有 push_back and pop_front 操作的线性结构，都可以作为 queue 的底层容器，比如 list。但是 STL 中对 stack and queue 默认选择 deque 作为其底层容器，主要是因为：
- stack 和 queue 不需要遍历 (因此 stack and queue没有迭代器)，只需要在固定的一端或者两端进行操作。
- 在 stack 中空间增长时，deque 比 vector 的效率高 (扩容时不需要搬移大量数据)；queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。
结合了 deque 的优点，而完美的避开了其缺陷。
💦 STL标准库中对于stack和queue的模拟实现
1、stack的模拟实现
#include<vector> #include<list> #include<deque> #include<iostream> using namespace std; namespace bit { //stack是一个Container适配(封装转换)出来的,且它是一个缺省参数,deque容器,但是它的功能是不变的,所以叫做容器适配器 template<class T, class Container = deque<T>> class stack { //Container的尾认定是栈顶 public: void push(const T& x)//先进 { _con.push_back(x); } void pop()//后出 { _con.pop_back(); } const T& top() { //不能用[],因为如果是list就不支持了,back更为通用 return _con.back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; }; void test_stack() { //stack<int, std::vector<int>> st; //stack<int, std::list<int>> st; stack<int> st; st.push(1); st.push(2); st.push(3); while(!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } } int main() { bit::test_stack(); return 0; }
2、queue的模拟实现
#include<vector> #include<list> #include<deque> #include<iostream> using namespace std; namespace bit { //stack是一个Container适配(封装转换)出来的,且它是一个缺省参数,deque容器 template<class T, class Container = deque<T>> class queue { //Container的尾认定是队尾,头是队头 public: void push(const T& x)//先进 { _con.push_back(x); } void pop()//先出 { _con.pop_front(); } const T& front() { return _con.front(); } const T& back() { return _con.back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; }; void test_queue() { //queue<int, std::vector<int>> qu;//err,因为vector不支持头删接口,所以不能适配 //queue<int, std::list<int>> qu; queue<int> qu; qu.push(1); qu.push(2); qu.push(3); while(!qu.empty()) { cout << qu.front() << " "; qu.pop(); } cout << endl; } } int main() { bit::test_queue(); return 0; }
