priority_queue的使用和模拟
(一) priority_queue的使用
priority_queue的文档介绍
它是优先级队列，其底层是堆，也是容器适配器。若忘记数据结构的堆可以去查看一下——堆。
又上图可知：它基于vector作为底层容器，第三个参数是仿函数(后面讲)
为什么底层容器是vector不是deque了？
priority_queue选择vector作为默认底层容器，是因为堆操作对 “随机访问效率” 的强依赖 ——vector的连续内存布局能提供最高效的[]访问，而deque的分段内存虽然也能满足功能需求，但在高频随机访问场景下效率更低，且其优势无法被priority_queue利用。因此，vector是更 “划算” 的选择。
当然，标准也允许通过模板参数指定deque作为底层容器（如std::priority_queue<int, std::deque<int>>），但实际中几乎不会这么做，因为性能不如vector。
操作：（重要的接口解释在图片中）
使用：
注意： 默认情况下priority_queue是大堆
void test1()
{vector<int> v{ 3,5,7,1,2,8,9,4,6,0 };priority_queue<int> q1;for (auto& e : v){q1.push(e);}while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;
}//测试结果：9 8 7 6 5 4 3 2 1 0那如果想建立小堆怎么办？
使用仿函数控制，如下：
void test1()
{vector<int> v{ 3,5,7,1,2,8,9,4,6,0 };priority_queue<int,vector<int>,greater<int>> q2;for (auto& e : v){q2.push(e);}while (!q2.empty()){cout << q2.top() << " ";q2.pop();}cout << endl;
}//运行结果：0 1 2 3 4 5 6 7 8 9使用基本还是跟之前也有，也是很容易上手的。
仿函数
它是一种通过重载operator()运算符，使对象能够像函数一样被调用的特殊类对象。
它替代了C语言的函数指针——函数指针可读性差，且易错，故出现了仿函数。
它常常被用在排序中
class Greater { public:bool operator()(int a, int b) const {return a > b;} };class Less { public:bool operator()(int a, int b) const {return a < b;} };void test2() {vector<int> numbers = { 5, 2, 9, 1, 5, 6 };sort(numbers.begin(), numbers.end(), Greater());cout << "降序排序结果: ";for (int num : numbers) {cout << num << " ";}cout << endl;sort(numbers.begin(), numbers.end(), Less());cout << "升序排序结果: ";for (int num : numbers){cout << num << " ";}cout << endl; }//运行结果： //降序排序结果: 9 6 5 5 2 1 //升序排序结果: 1 2 5 5 6 9发现可以改变其升序还是降序
Greater x1; x1(1, 2)； Less x2; x2(1, 2)；也可以这样我们能发现它就像函数一样被调用了。
注意：C++11 引入的Lambda 表达式本质上是匿名仿函数（这里博主没学到，后面在讲解吧）
(二) priority_queue的模拟
#pragma oncetemplate <class T>
class Less
{
public:bool operator()(const T& x, const T& y) const {return x < y;}
};template <class T>
class Greater
{
public:bool operator()(const T& x, const T& y) const {return x > y;}
};namespace Yu
{template <class T, class Container = std::vector<T>, class Compare = Less<T> >class priority_queue{private:// 向下调整（用于删除堆顶元素后）void Adjustdown(size_t parent){Compare com;size_t child = parent * 2 + 1; // 左孩子while (child < _con.size()){// 找较大的孩子（根据比较器）if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child; // 右孩子更大，选右孩子}// 父节点小于孩子，交换并继续向下调整if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break; }}}// 向上调整（用于插入新元素后）void AdjustUp(size_t child){Compare com;int parent = (child - 1) / 2; while (child > 0){if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}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) // 用int避免无符号下溢，i >= 0确保根节点被调整{Adjustdown(i);}}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}const T& top() const{return _con[0];}// 插入元素后向上调整void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1); }// 删除堆顶元素后向下调整void pop(){std::swap(_con[0], _con[_con.size() - 1]); // 交换堆顶和最后一个元素_con.pop_back(); // 移除最后一个元素（原堆顶）if (!_con.empty()){Adjustdown(0); // 对新堆顶向下调整}}private:Container _con; };
}小细节：
若向上调整和向下调整忘记了可以看——博主之前的博客堆
template <class T, class Container = std::vector<T>, class Compare = Less<T> >
第一个参数：class T
- 含义：指定优先队列中存储的元素类型。
- 作用：决定了队列能存放什么类型的数据。
第二个参数：class Container = std::vector<T>
- 含义：指定优先队列的底层容器类型
第三个参数：class Compare = Less<T>
含义：指定优先级比较规则（仿函数类型），默认使用自定义的Less<T>仿函数。
作用：决定堆的类型（大顶堆 / 小顶堆）：
- Less<T>（默认）：比较规则为x < y，构造大顶堆（每次弹出最大元素）。
- Greater<T>：比较规则为x > y，构造小顶堆（每次弹出最小元素）。
通过修改 Compare 所指定的仿函数类型，无需修改堆的核心调整逻辑，就能快速切换堆的类型
调用如下：
// 大顶堆（默认，使用 Less<T>）
Yu::priority_queue<int> pq1;
// 底层为大顶堆，弹出最大元素// 小顶堆（显式指定 Greater<T>）
Yu::priority_queue<int, std::vector<int>, Greater<int>> pq2;
// 底层为小顶堆，弹出最小元素for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
(size() - 1 - 1)/2：为最后一个非叶子节点
因为最后一个节点索引是size-1，其父节点是(size-1-1)/2）
注意：
如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。
如：日期类的比较大小，如下：
Yu::priority_queue<Date> q1; q1.push(Date(2025, 8, 7)); q1.push(Date(2025, 1, 25)); q1.push(Date(2025, 11, 22)); cout << q1.top() << endl;就得增加自定义类型的operator>>和operator<<
class Date { public:Date(int year = 2025, int month = 8, int day = 7): _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);}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){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;} private:int _year;int _month;int _day; };
priority_queue的完整代码——gitee
(三) 反向迭代器
允许从容器的最后一个元素开始，依次访问到第一个元素。（博主懒所以花了个简单点的）
由上图可知
正向迭代器：
- begin ：指向容器第一个元素（ list 因是链表，图示中 begin 与 end 初始位置关联 ）
- end ：指向容器尾后位置（不存储元素，标记遍历结束 ）
反向迭代器：
- rbegin ：指向容器最后一个有效元素（反向遍历的“起始” ）
- rend ：指向容器第一个元素的前一个位置（反向遍历的“结束” ）
而库中的反向rbegin为正向end位置，rend为中序begin位置，为什么这样设计了？
- 接口统一：保持正向与反向迭代器遍历代码结构一致，如正向用 while (it != end) ，反向用 while (it != rend) ，方便使用。
- 算法兼容：利于标准库通用算法，能在正向和反向遍历容器时正常工作，避免为反向遍历单独设计算法。
- 实现便利：为不同容器实现反向迭代器提供统一规则，降低实现和维护难度，如 list 用前驱指针、 vector 通过偏移量计算来实现。
总之，他们是镜像对称——反向迭代器和正向迭代器为对称关系
模拟
反向迭代器不直接操作容器，而是通过封装一个正向迭代器 _it 实现功能
#pragma oncenamespace Yu
{template<class Iterator, class Ref, class Ptr>struct ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;Iterator _it;ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s) const{return _it != s._it;}};
}小细节：
template<class Iterator, class Ref, class Ptr>
第一个参数：class Iterator
- 底层依赖的正向迭代器类型，反向迭代器通过操作这个正向迭代器实现功能。
第二个参数：class Ref
- 反向迭代器解引用（operator*）返回的引用类型（如 int& 或 const int&），用于控制元素是否可修改。
第三个参数：class Ptr
- 反向迭代器箭头操作（operator->）返回的指针类型（如 int* 或 const int*），配合指针访问元素成员。
Ref operator*() {Iterator tmp = _it; return *(--tmp); }
其底层正向迭代器_it存储的是 “目标元素的下一个位置”（如rbegin()的_it对应正向end()）。通过--tmp让临时迭代器回退一位，才能正确指向反向遍历的当前有效元素。
operator++()和operator--()
反向迭代器的++就是正向迭代器的--，而反向迭代器的--就是正向迭代器的++。
Ptr operator->() {return &(operator*()); }
- 功能：当迭代器指向的元素是自定义类型时，通过 -> 访问其成员（如 (*it).name 等价于 it->name）。
- 逻辑：通过解引用操作（operator*）获取元素引用，再取地址得到指针。
调用
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;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());
}小细节：
由上面的图片可知：
rbegin()：返回反向遍历的 “起始点”，指向容器最后一个有效元素。
- 实现上用容器的正向迭代器end()（尾后位置）初始化，配合ReverseIterator内部的--操作，刚好指向最后一个元素。
rend()：返回反向遍历的 “终止点”（第一个元素的前一个位置）。
- 实现上用正向迭代器begin()（第一个元素位置）初始化，作为反向遍历结束的标志（类似正向遍历的end()）。
完整代码——博主的gitee
以上就是priority_queue，仿函数和反向迭代器的知识点了，后续的完善工作我们将留待日后进行。希望这些知识能为你带来帮助！如果觉得内容实用，欢迎点赞支持~ 若发现任何问题或有改进建议，也请随时与我交流。感谢你的阅读