去感受一棵草、一缕风、一场日落，去重新触摸真正的生活。
——高盛元
目录
1、优先级队列
1.1什么是优先级队列
1.2 priority_queue 的使用
1.3 仿函数
2、priority_queue 的模拟实现
2.1整体框架接口
2.2插入&&向上调整
2.2删除&&向下调整
2.3其他接口
2.4优先级队列的应用
3、反向迭代器
3.1重载运算符
3.2容器的反向迭代器使用
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; //更新下一个孩子}elsebreak;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; //更新下一个左孩子}elsebreak;}
}删除
//删除
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(); // 这里是根据传过去的正向迭代器，我们将其封装到一个类（反向迭代器）通过复用实现功能 可以调试理解}
其他模板容器均可以通过这样的方式实现反向迭代器，是一种封装的思想
大家可以在实际中继续体会。
