【C++】—— priority_queue ：平衡效率与秩序的算法利器
去感受一棵草、一缕风、一场日落，去重新触摸真正的生活。
——高盛元
目录
1、优先级队列
1.1什么是优先级队列
优先队列也是一种容器适配器（容器适配器即将 特定容器类 （vector list 等等）封装作为其底层容器类 ），根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
严格弱序的三条要求：
1. 两个关键字不能同时“严格弱序”于对方
2. 如果a“严格弱序”于b，且b“严格弱序”于c，则a必须“严格弱序”于c
3. 如果存在两个关键字，任何一个都不“严格弱序”于另一个，则这两个关键字是相等的。
由此看来，优先级队列的性质类似于堆，可以在堆中随时插入元素，并且只能检索到当前所以元素的最大值或最小值（堆顶元素）。
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作:
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
- pop_back() : 删除容器尾部元素
注意到标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的 priority_queue类实例化指定容器类，则使用vector。需要支持随机访问迭代器，以便始终在内部保持堆结构，容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
1.2 priority_queue 的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
这里如何控制大堆小堆呢？？？
#include <vector> #include <queue> #include <functional> // greater算法的头文件 void TestPriorityQueue() { // 默认情况下，创建的是大堆，其底层按照小于号比较 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; // 如果要创建小堆，将第三个模板参数换成greater比较方式 priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end()); cout << q2.top() << endl; }如果在 priority_queue 中放自定义类型的数据，我们需要在自定义类型中提供 > 或者 < 的重载
学习一下优先级队列的模板参数：
- 模版参数 1 是 储存的数据类型
- 模版参数 2 是 底层结构，一般使用vector 或 deque
- 模版参数 3 是 仿函数，提供比较方式（建大堆，还是建小堆）
可以看到是通过仿函数逻辑来实现大堆小堆的，下面我们开始仿函数的学习使用。
1.3 仿函数
仿函数是什么？一看名字可能以为是函数，事实上仿函数（Functor） 是指一种重载了 operator() 运算符的类，可以像函数一样使用对象。这种设计使得对象可以具有类似于函数的行为，仿函数通常用于实现更复杂的函数逻辑。
先前我们C语言的qsort 函数：
void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*)); 其最后一个参数就是函数指针，说实话比较复杂，因为我们在实现函数功能时并不知道会是什么类型，所以就很复杂。而我们通过仿函数，可以使用模版类，然后就自然适配所有的类型：
//比较谁更小的的仿函数 template<class T> struct less { bool operator()(const T& a, const T& b) { return a < b; } }; //比较谁更大的的仿函数 template<class T> struct greater { bool operator()(const T& a, const T& b) { return a > b; } }; 通过这个仿函数可以轻松顶替复杂的函数指针。
仿函数的优点
- 灵活性：可以使用对象存储状态，而函数本身无法做到这一点。这允许在仿函数中存储更多的上下文信息。
- 可组合性：仿函数可以作为其他算法和函数模板的参数。
- 高效性：在一些STL算法中使用仿函数，可以提高代码执行效率，特别是在需要内联函数调用时。
2、priority_queue 的模拟实现
2.1整体框架接口
我们可以根据STL库里对应实现基本的接口
namespace qsy { template<class T> struct less { bool operator()(const T& a, const T& b) { return a < b; } }; template<class T> struct greater { bool operator()(const T& a, const T& b) { return a > b; } }; //默认是大堆 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) {} //插入新元素向上调整 void AdjustUp() {} //插入 void push(const T& x) {} //删除需要向下调整 void AdjustDown() {} //删除 void pop() {} //返回大小 size_t size() const {} //取堆顶元素 T& top() { } //判断是否为空 bool empty() {} private: //底层容器 实例化 Container _con; }; } 2.2插入&&向上调整
插入的操作很简单，容器调用 push_back 即可，但是我们需要位置优先级队列（堆）的结构就需要将元素进行向上调整
向上调整算法
//插入新元素向上调整 void AdjustUp(int size) //size 元素个数 { compare com; int child = size - 1;//插入元素的下标 int parent = (child - 1) / 2; while (child>0) { if (com(_con[parent], _con[child])) // < 就交换 com是 less 默认大堆 { swap(_con[parent], _con[child]); child = parent; //更新下一个孩子 } else break; parent = (child - 1) / 2; //更新下一个父亲 } }插入
//插入 void push(const T& x) { _con.push_back(x); AdjustUp(_con.size()); }
2.2删除&&向下调整
注意删除操作是对堆顶的删除，但是容器的删除操作一般都是尾删，所以要先将容器的首元素与结尾位置进行交换，交换后尾差即可。然后进行向下调整，维持优先队列（堆）的特性。
向下调整算法
//删除需要向下调整 void AdjustDown(int parent) //根据堆的删除思路 这个parent 应该是指向下标为0的元素 { compare com; int child = 2 * parent + 1; //找到左孩子 while (child < _con.size()) //不可以越界 { //在 com为less前提下 先求出两个孩子较大的一个 因为可能要与父亲节点交换维持大堆结构 if (child + 1 < _con.size() && com(_con[child], _con[child+1])) { child = child + 1; } //更新父子关系 com是less 默认大堆 这里因为置换了头尾元素所以 向下调整 //所以应该是父亲小于孩子进入 if 语句 if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); parent = child; //更新下一个父亲 child = 2 * parent + 1; //更新下一个左孩子 } else break; } }删除
//删除 void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); }
2.3其他接口
其他的功能接口直接复用底层容器接口即可
//返回大小 size_t size() const { return _con.size(); } //取堆顶元素 T& top() { return _con[0]; } //判断是否为空 bool empty() { return _con.empty(); }这里注意一下如何将一组无序数据建堆，对应的接口就是迭代器构造
// 创造空的优先级队列 priority_queue() : _con() {} template<class Iterator> priority_queue(Iterator first, Iterator last) : _con(first, last) { // 将_con 中的元素调整成堆的结构 int count = _con.size()-1; int root = ((count - 1)/ 2); //最后一个父个父亲节点开始从下往上建堆 for (; root >= 0; root--) AdjustDown(root); }
2.4优先级队列的应用
C++中的优先队列（priority_queue）是一种容器适配器，它提供了常数时间复杂度的元素插入操作和 logN时间复杂度的元素删除操作。由于它是基于堆实现的，所以非常适合用于需要频繁地找到最大或最小元素的应用场景。以下是一些典型的使用场景：
- 任务调度：在操作系统中，优先队列可以用来实现任务调度器（Linux下是使用优先队列），确保高优先级的任务先被执行。
- 图算法：
- Dijkstra算法：优先队列用于找出最短路径。
- Prim算法：在生成最小生成树时，优先队列用于选择最小的边。
- 数据流处理：在处理数据流时，如在线广告投放系统，可以使用优先队列来选择价值最高的广告进行展示。
- 事件模拟：在模拟系统中，优先队列可以用来按时间顺序处理事件，比如网络中的数据包传输。
- 霍夫曼编码：在构建霍夫曼树时，优先队列用来按照频率排序字符。
- 多路归并：在数据合并操作中，优先队列可以帮助实现多路归并算法，例如在数据库索引的构建中。
- 堆排序：优先队列可以作为堆排序算法的实现基础。
- 选择问题：例如，快速选择算法可以使用优先队列来找到第k大的元素。
- 资源分配：在网络路由算法中，优先队列可以用来决定数据包的传输路径。
- 游戏开发：在游戏AI中，优先队列可以用来确定下一步的行动，基于行动的优先级进行排序。
优先队列的使用非常灵活，它适合于任何需要动态调整元素优先级和快速访问最高（或最低）优先级元素的场景。在使用时，需要注意其插入和删除操作的时间复杂度，以及如何根据实际需求选择合适的仿函数。
3、反向迭代器
在复刻STL中的list容器时，首次采用了类封装的方式来构建迭代器，以此实现迭代器的递增、递减和元素访问功能。然而，当我们面临实现反向迭代器的需求时，是否需要重头开始，再次进行类的封装呢？
显然这种做法并非必要（不然就要手搓无数个反向迭代器了）。因为反向迭代器与正向迭代器在功能上存在高度一致性，唯一的区别在于它们在容器中的移动方向相反。因此，我们可以采用适配器设计模式，对现有的正向迭代器进行二次封装，以此满足反向迭代器的需求。
通过引入适配器，我们不仅可以避免重复造轮子的工作，还能够提升代码的复用性和简洁性。这种设计模式的应用，使得我们能够在保持代码高效和可维护性的同时，轻松实现反向迭代器的功能。
我们先学习一下STL源码是如何实现的
template <class RandomAccessIterator, class T, class Reference = T&, class Distance = ptrdiff_t> #else template <class RandomAccessIterator, class T, class Reference, class Distance> #endif class reverse_iterator { typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance> self; protected: RandomAccessIterator current; public: typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef Distance difference_type; typedef T* pointer; typedef Reference reference; } ； 这里我们选择三个模板参数复刻学习，事实上也可以一个模板参数通过迭代器萃取
其想要通过提供的正向迭代器实现所有容器的反向迭代器。
这是链表中的反向迭代器：
typedef reverse_bidirectional_iterator<const_iterator, value_type, const_reference, difference_type> const_reverse_iterator; typedef reverse_bidirectional_iterator<iterator, value_type, reference, difference_type> reverse_iterator; 如何实现我们自己的反向迭代器呢？
通过以往的理解，我们可以大致推出一个框架：
namespace qsy { // 适配器 -> 复用 //给谁的正向迭代器就产生谁的反向迭代器 template<class Iterator, class Ref, class Ptr> struct ReverseIterator { //简化书写 typedef ReverseIterator<Iterator, Ref, Ptr> Self; //构造函数 ReverseIterator(Iterator it) :_it(it) {} //实例化一个正向迭代器 Iterator _it; }; } 反向迭代器与正向迭代器在功能上相似，都用于遍历容器中的元素。然而，它们在操作方向上存在显著差异：
- 正向迭代器通过++运算符向前移动，而反向迭代器则通过–运算符向后移动。
实现反向迭代器的基本方法是通过编写一个类模板，该模板会被编译器用来生成具体容器对应的迭代器实例。在这个过程中，编译器负责实例化这些迭代器，从而提供一种便捷的方式来反向遍历容器中的元素。
3.1重载运算符
加减操作的重载
Self& operator++() { --_it; return *this; } //后置 Self& operator++(int) { Self tmp = _it; --_it; return tmp; } Self& operator--() { ++_it; return *this; } //后置 Self& operator--(int) { Self tmp = _it; ++_it; return tmp; }判断操作符重载
对于反向迭代器的 == !=操作实质上也就是其封装的正向迭代器的比较：
bool operator!=(const Self& s) { return _it != s._it; } bool operator==(const Self& s) { return _it == s._it; }访问操作
//// 不考虑与 begin end 对称的写法 //Ref operator*() //{ // return *_it; //} //Ptr operator->() //{ // return &(operator*()); //} // // 考虑与 begin end 对称的写法 Ref operator*() { //解引用前一个位置 这里需要注意 不能改变自身 _it 的属性 所以利用 tmp中间变量 Iterator tmp = _it; return *--tmp; } Ptr operator->() { return &(operator*()); }为什么这里的访问要有--操作？？？因为为了与正向迭代器对称，反向迭代器的开始位置并不是结尾，而是哨兵位。如图：
下面这种可以直接使用已有的end() , begin()函数进行复用，增加代码可读性。所以对应的访问方式就要减一再访问。效果其实两种区别不大，但是第二种的代码更加简洁。
3.2容器的反向迭代器使用
- Vector
这里需要 typedef 简化一下 然后提供 相应的 rbegin rend 就可以复用了
reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } constt_reverse_iterator rbegin()const { return constt_reverse_iterator(end()); } constt_reverse_iterator rend()const { return constt_reverse_iterator(begin()); } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; }就可以实现逆向访问了
int main() { qsy::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); qsy::vector<int>v(lt.begin(), lt.end()); auto rit = v.rbegin(); while(rit != v.rend()) { cout << *rit << ' '; ++rit; } cout << endl; //auto rit = lt.rbegin(); // 这里是根据传过去的正向迭代器，我们将其封装到一个类（反向迭代器）通过复用实现功能 可以调试理解 }
- List
List 思路是一样的
/*reverse_iterator rbegin() { return reverse_iterator(--end()); } reverse_iterator rend() { return reverse_iterator(end()); } const_reverse_iterator rbegin()const { return const_reverse_iterator(--end()); } const_reverse_iterator rend()const { return const_reverse_iterator(end()); }*/ // 对称优化写法 reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rbegin()const { return const_reverse_iterator(end()); } const_reverse_iterator rend()const { return const_reverse_iterator(begin()); } iterator begin()//第一个结点指针 { //iterator it(_head->_next);//构造函数 //return it; 优化一下 return _head->_next; //走的隐式类型转换 } // const 修饰begin 可以兼容拷贝构造 否则出现权限放大 这是不允许的 const_iterator begin()const //前面的const 迭代器是指向元素或引用不可以改变内容 后面的const是修饰this 对象不可以改变 { // 隐含的this指针由 list * const this 变为 const list* const this 前者是指针不可以更改指向 return _head->_next; } const_iterator cbegin()const { return _head->_next; } iterator end() { return _head; // 头节点 左闭右开 } const_iterator end()const { return _head; } const_iterator cend()const { return _head; }逆向复用正向迭代器访问
#define _CRT_SECURE_NO_WARNINGS #include"vector.h" #include"list.h" int main() { qsy::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); qsy::vector<int>v(lt.begin(), lt.end()); auto rit = v.rbegin(); auto rrit = lt.rbegin(); while(rrit != lt.rend()) { cout << *rrit << ' '; ++rrit; } cout << endl; //auto rit = lt.rbegin(); // 这里是根据传过去的正向迭代器，我们将其封装到一个类（反向迭代器）通过复用实现功能 可以调试理解 }
其他模板容器均可以通过这样的方式实现反向迭代器，是一种封装的思想
大家可以在实际中继续体会。
Thanks♪(･ω･)ﾉ谢谢阅读！！！
