【C++篇】STL适配器（下篇）：优先级队列与反向迭代器的底层奥秘

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对C++感兴趣的朋友

---

---

前言

话接上篇，本文将对优先级队列和迭代器进行详细讲解并模拟实现，其中优先级队列的实现涉及了仿函数等新的知识，因此本文难度会有所提升。

【本文目标】

• 知道优先级队列是什么？
• 能够正确使用优先级队列
• 了解并会使用仿函数
• 了解反向迭代器的功能原理
• 能够模拟实现priority_queue和reverse_iterator
• 能够将反向迭代器适配到vector和list中

---

一、priority_queue的介绍和使用

优先级队列其实就是我们先前学过的一个数据结构——堆
如有遗忘，一定要及时复习
【初探数据结构】二叉树的顺序结构——堆的实现详解（上下调整算法的时间复杂度分析）
【初探数据结构】堆的应用实例（堆排序与TopK问题）

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的场景，都可以考虑使用priority_queue。

使用时需要包头文件：#include <queue>

注意：默认情况下priority_queue是大堆。

那么如何控制成小堆呢？
这里就需要仿函数的功效了，这里先不解释，知道这是仿函数就行：
priority_queue有3个模板参数：
数据类型+容器+仿函数

template<T, vector<T>, less<T>>

这里仿函数有两个：

• less：默认仿函数，大堆
• greater：小堆

控制小堆示例：

#include <vector>
#include <queue>
// greater算法的头文件
#include <functional>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;
}

运行结果：

堆顶为：9
堆顶为：0

常用接口：

函数声明	接口说明
priority_queue()	构造一个空的优先级队列
priority_queue(first,last)	迭代构造一个优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

特别注意：如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

因为这里的仿函数是基于>和<操作符来实现的，如果没有，就会报错。

---

二、模拟实现priority_queue

首先，不难确定，成员变量只有一个：

Container _con;

1. pop()实现（向下调整算法）

核心思路：

1. 将堆顶元素与堆尾元素交换
2. 尾删（效率高）
3. 向下调整

void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//向下调整AdjustDown(0);
}

重难点在于向下调整算法的实现

核心思路：

1. 父节点与较大的那个孩子节点比较
2. 父节点小于（这里实现大堆，若要小堆就用大于）孩子节点就交换位置，如此循环
3. 直到孩子节点下标为_con.size()，循环结束。

大堆代码实现

void AdjustDown(int parent)
{//假设左孩子更大int child = parent * 2 + 1;while (child < _con.size()){//右孩子存在且比左孩子大，就指向右孩子if (child + 1 < _con.size() && _con[child] < _con[child + 1]){++child;}//父节点小于孩子节点就交换if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);}else{break;}//更新下标，为下一轮循环做准备parent = child;child = parent * 2 + 1;}
}

那么，如果我们要实现小堆，又要写一份几乎一样的代码吗？我们来看看仿函数是怎么解决的！

---

2. 仿函数控制大小堆

什么是仿函数？

在 C++ 中，仿函数（Functor） 是一种行为类似函数的对象（也称为函数对象，Function Object）。它通过重载函数调用运算符 operator() 实现，使得类的实例可以像普通函数一样被调用。

1. 本质：仿函数是类/结构体对象，但能通过 对象(参数) 语法调用
2. 实现：在类中重载 operator()

class MyFunctor {
public:// 重载函数调用运算符return_type operator()(参数列表) const { // 实现逻辑}
};

控制大小堆的本质：就是控制父子节点的比较方式。

代码实现：

//仿函数
//控制实例化大小堆//大堆
template<class T>
class Less
{
public:bool operator()(const T& a, const T& b){return a < b;}
};//小堆
template<class T>
class Greater
{
public:bool operator()(const T& a, const T& b){return a > b;}
};

这样一来，只要我们利用模板控制调用函数，就可以实现复用功能了：

namespace zhh
{
template <class T, class Container = vector<T>, class Compare = Less<T> >//设定默认大堆
class priority_queue
{
private:void AdjustDown(int parent){Compare _com;int 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])){swap(_con[parent], _con[child]);}else{break;}parent = child;child = parent * 2 + 1;}}private:Container _con;};

有没有发现，仿函数和C语言中的函数指针功能十分相似。取其精华去其糟粕，优化了函数指针的复杂性，加强了可用性。

仿函数 vs 函数指针

---

3. push()实现（向上调整算法）

这个很简单
核心思路：

1. 尾插
2. 向上调整

void push(const T& x)
{_con.push_back(x);//向上调整AdjustUp(_con.size() - 1);
}

向上调整算法

核心思路：

1. 将孩子节点与父节点比较大小
2. 孩子节点大于（小于）父节点就交换，如此循环
3. 直到孩子节点下标为0，循环终止。

代码实现：

 void AdjustUp(int child){Compare _com;int parent = (child - 1) / 2;while (child > 0){if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);}else{break;}child = parent;parent = (child - 1) / 2;}}

---

4. 构造函数实现

这里无参构造、拷贝构造、析构函数、迭代器均无需实现，因为内置类型无需这些，而自定义类型调用自己的构造函数和析构函数以及迭代器。

需要实现的是，迭代构造，这其实就是一个建堆的过程：

//[first, last)
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last):_con(first, last)
{//(_con.size() - 1 - 1)/2计算父亲节点的下标for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i){AdjustDown(i);}
}

需要注意的是，向下调整的时间复杂度（N）是比向上调整的时间复杂度（NlogN）要低的，因此向下调整建堆的效率更高。

---

源码

这是我模拟实现的源码

---

三、反向迭代器介绍和使用

初见反向迭代器，你可能会觉得很简单：
不就是把++重载为--，--重载为++，begin与end交换一下位置不就好了嘛？

确实思想很简单，但是看你如何实现了。
没错，可以利用适配器，很好的复用iterator的代码，让代码简短无比，我们一起来看看吧！

在 C++ 中，反向迭代器（Reverse Iterator） 是一种适配器，它允许以相反的顺序遍历容器（从容器的末尾向开头移动）。它是标准库的重要组成部分，定义在 <iterator> 头文件中，为所有支持双向迭代器的容器（如 vector, deque, list, set, map 等）提供反向遍历能力。

核心特性

1. 反向移动：

   • ++ 操作：向容器开头移动（相当于普通迭代器的 --）

   • -- 操作：向容器末尾移动（相当于普通迭代器的 ++）

2. 适配器模式：基于普通迭代器实现，不修改底层容器

3. 标准接口：与普通迭代器相同的操作（解引用、比较等）

反向迭代器与正向迭代器具有对称关系，以此来确定rbegin和rend指向的位置：

vector：

list：

用法和正向迭代器差不多：

#include <iostream>
#include <vector>
#include <iterator> // 包含 reverse_iteratorint main() {std::vector<int> vec = {1, 2, 3, 4, 5};// 获取反向迭代器auto rbegin = vec.rbegin(); // 指向最后一个元素auto rend = vec.rend();     // 指向第一个元素之前的位置// 反向遍历for (auto rit = rbegin; rit != rend; ++rit) {std::cout << *rit << " ";}// 输出：5 4 3 2 1return 0;
}

---

四、模拟实现reverse_iterator

1. 代码梳理与实现

成员变量：正向迭代器
配置接口与正向相同

核心思想：复用

解引用*和->重载：

注意：解引用的是rit所指向的前一个位置
因为rit是从rbegin开始的，rbegin指向的位置是最后一个元素的后一个位置。

T& operator*()
{Iterator tmp = _it;return *--tmp;
}

operator->()直接对解引用后的值取地址即可

T* operator->()
{return &(operator*());
}

完整代码：

#pragma oncenamespace zhh
{// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Iterator _it;Reverse_iterator(const Iterator& it):_it(it){ }Ref operator*(){Iterator tmp = _it;return *--tmp;}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self operator++(int){Iterator tmp = _it;--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){Iterator tmp = _it;++_it;return tmp;}bool operator==(const Self& s){return _it == s._it;}bool operator!=(const Self& s){return _it != s._it;}};
}

---

2. vector和list反向迭代器实现

我们一起来给我们之前实现的list和vector配置一下吧！

list配置

老样子，带上模板的名字太长了，我们了typedef一下：

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

rbegin()和rend()接口实现：

由我们之前提到的正反迭代器镜像对称关系：
rbegin就是end，rend就是begin
可以复用：

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());
}

这样就配置好了，非常简单

vector配置

这个可以自己试试哦

没错，和list一模一样。

配置后的源码：
- vector
- list