C++算法
C++ 容器适配器：优先级队列与反向迭代器实现原理
C++ 容器适配器中的反向迭代器通过包装正向迭代器并反转 ++/-- 操作实现反向遍历。优先级队列基于堆结构，默认大顶堆，支持自定义比较规则。文章详细讲解了反向迭代器的模板参数、运算符重载及优先级队列的 AdjustDown/Up 调整算法、构造函数及核心成员函数实现。
C++ 容器适配器中的反向迭代器通过包装正向迭代器并反转 ++/-- 操作实现反向遍历。优先级队列基于堆结构，默认大顶堆，支持自定义比较规则。文章详细讲解了反向迭代器的模板参数、运算符重载及优先级队列的 AdjustDown/Up 调整算法、构造函数及核心成员函数实现。
要实现反向迭代器，就不得不提到适配器模式。
在之前的学习中，stack 和 queue 是典型的容器适配器；而反向迭代器则是一种迭代器适配器。
反向迭代器是一个迭代器适配器，它包装了一个正向迭代器，把 ++ 操作映射成原迭代器的 --，把 -- 操作映射成原迭代器的 ++，从而实现反向遍历的效果。
反向迭代器在容器中的指向：
namespace ljh {
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++(int) { Self tmp(*this); --_it;//正向迭代器--，反向迭代器++ return tmp; }
Self& operator--() { ++_it; return *this; }
Self operator--(int) { Self tmp(*this); ++_it; return tmp; }
bool operator!=(const Self& s) const { return _it != s._it; }
};
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 reverse_iterator(end()); }
const_reverse_iterator rend() const { return reverse_iterator(begin()); }
}
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
**Iterator：**被适配的正向迭代器类型（比如 vector::iterator）
**Ref：**迭代器取值（*it）时返回的引用类型（比如 T& 或 const T&）
**Ptr：**迭代器箭头访问（it->）时返回的指针类型（比如 T* 或 const T*）
typedef ReverseIterator<Iterator, Ref, Ptr> Self;
Iterator _it;
**Self：**简化自身类型的书写，避免重复写长模板名
**_it：**内部持有的正向迭代器，是反向迭代器的'核心数据'
ReverseIterator(Iterator it) : _it(it) {}
用一个正向迭代器来初始化反向迭代器，把传入的迭代器保存到 _it 中。
operator*Ref operator*() { Iterator tmp = _it; return *(--tmp); }
这是反向迭代器的核心适配逻辑。
它先拷贝一份内部迭代器 _it，对拷贝做 -- 移动到前一个位置，再取值返回。
这样保证了 rbegin() 能正确指向容器的最后一个元素。
operator->Ptr operator->() { return &(operator*()); }
复用 operator* 的结果，取其地址返回，支持 it->member 这样的指针访问语法。
operator++Self& operator++() { --_it; return *this; }
反向迭代器的 ++ 对应内部正向迭代器的 --，实现'向后移动'（在反向遍历中是向前走）。
operator++(int)Self operator++(int) { Self tmp(*this); --_it; return tmp; }
先创建一个当前对象的副本，再移动内部迭代器，最后返回副本。
这是后置 ++ 的标准实现，保证返回的是'移动前'的迭代器。
operator--Self& operator--() { ++_it; return *this; }
反向迭代器的 -- 对应内部正向迭代器的 ++，实现'向前移动'（在反向遍历中是向后退）。
operator--(int)Self operator--(int) { Self tmp(*this); ++_it; return tmp; }
逻辑同后置 ++，先拷贝再移动，返回移动前的迭代器。
operator!=bool operator!=(const Self& s) const { return _it != s._it; }
bool operator==(const Self& s) const { return _it == s._it; }
直接比较两个反向迭代器内部持有的正向迭代器，判断它们是否指向不同位置。
// 先定义反向迭代器的类型别名（依赖之前的 ReverseIterator 适配器）
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
// 1. 普通版 rbegin()：可读写反向迭代器起点
reverse_iterator rbegin() {
// 核心：用正向迭代器的 end() 初始化反向迭代器，指向容器最后一个元素
return reverse_iterator(end());
}
// 2. 普通版 rend()：可读写反向迭代器终点
reverse_iterator rend() {
// 核心：用正向迭代器的 begin() 初始化反向迭代器，指向第一个元素之前
return reverse_iterator(begin());
}
// 3. const 版 rbegin() const：只读反向迭代器起点
const_reverse_iterator rbegin() const {
// 核心：逻辑同普通版，但返回 const 版本，仅支持读操作
return const_reverse_iterator(end());
}
// 4. const 版 rend() const：只读反向迭代器终点
const_reverse_iterator rend() const {
// 核心：逻辑同普通版，但返回 const 版本，仅支持读操作
return const_reverse_iterator(begin());
}
仿函数（Functor）是 C++ 中一种特殊的类对象，核心特点是重载了 operator() 运算符，使得对象可以像函数一样被调用（用 对象名 (参数) 的形式）。
简单说：仿函数是'像函数的对象'，本质是带 operator() 的类实例。
template<class T>
class small {
public:
bool operator()(const T& x,const T& y) { return x < y; }
};
template<class T>
class big {
public:
bool operator()(const T& x,const T& y) { return x > y; }
};
int main() {
small<int> s;
big<int> b;
cout << s(1,2) << endl;
cout << b(1, 2) << endl;
return 0;
}
priority_queue 是 C++ 标准库中的一个容器适配器，底层默认用 vector 存储数据，内部维护一个堆结构，确保队首元素始终是优先级最高的（默认是最大值）。
核心特点：
只能访问队首的最大元素，不能遍历或随机访问其他元素。
插入新元素时，会自动调整堆结构以维持优先级顺序。
弹出队首元素后，剩余元素也会自动重新调整。
底层原理：通过调用 make_heap、push_heap、pop_heap 等算法函数来维护堆的特性。
默认行为：默认是大顶堆（最大元素优先），可以通过传入仿函数（如 greater<T>）改为小顶堆。
namespace ljh {
// 仿函数/函数对象
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; }
};
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])) //if (child + 1 < _con.size() && _con[child] < _con[child + 1])
{ ++child; }
if (com(_con[parent], _con[child])) {
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
} else { break; }
}
}
//向上调整算法
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]);
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++;
}
//建堆 - 向下调整建堆（默认建立大堆）
//N
for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
//向下调整算法
AdjustDown(i);
}
}
void pop() {
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
const T& top() { return _con[0]; }
bool empty() { return _con.empty(); }
size_t size() { return _con.size(); }
private:
Container _con;
};
}
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
这是整个优先级队列的模板定义，有三个模板参数：
**T：**队列中存储的元素类型。
**Container：**底层存储数据的容器，默认用 vector，也可以换成 deque 等支持随机访问的容器。
**Compare：**比较规则的仿函数，默认是 Less<T>（大顶堆），可以换成 Greater<T> 实现小顶堆。
AdjustDown 向下调整算法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[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
} else { break; }
}
}
这是维护堆结构的核心函数，用来在堆顶元素被移除后，把新的堆顶向下调整到正确位置：
先创建一个比较规则的仿函数对象 com。
从 parent 的左孩子 child = parent*2+1 开始。
先在左右孩子中，用 com 比较出优先级更高的那个，作为真正要交换的 child。
然后用 com 比较父节点和这个孩子节点，如果父节点优先级更低，就交换它们，并继续向下调整。
如果父节点优先级已经更高，说明调整完成，直接跳出循环。
AdjustUp 向上调整算法void AdjustUp(int child) {
Compare com;
int parent = (child - 1) / 2;
while (child > 0) {
if (com(_con[parent], _con[child])) {
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
} else { break; }
}
}
这个函数用来在新元素插入堆尾后，把它向上调整到正确位置：
创建比较规则的仿函数对象 com。
计算当前 child 节点的父节点 parent = (child-1)/2。
用 com 比较父节点和孩子节点，如果父节点优先级更低，就交换它们，并继续向上调整。
如果父节点优先级已经更高，说明调整完成，跳出循环。
priority_queue() {}
空的默认构造函数，底层容器 _con 会自己调用默认构造，不需要额外操作。
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last) {
while (first != last) {
_con.push_back(*first);
first++;
}
for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
AdjustDown(i);
}
}
这个构造函数可以用一段迭代器区间来初始化队列：
先把区间里的所有元素都插入到底层容器 _con 中。
然后从最后一个非叶子节点开始，依次调用 AdjustDown，把整个容器调整成一个合法的堆结构。
pop 弹出堆顶元素void pop() {
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
弹出堆顶元素的步骤：
先把堆顶元素（_con[0]）和堆尾元素交换。
然后删除堆尾元素（也就是原来的堆顶）。
最后对新的堆顶元素调用 AdjustDown，重新维护堆的结构。
push 插入新元素void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
插入新元素的步骤：
先把新元素插入到底层容器的尾部。
然后对这个新插入的元素调用 AdjustUp，把它向上调整到正确的位置，以维持堆的性质。
top 获取堆顶元素const T& top() { return _con[0]; }
直接返回底层容器的第一个元素，也就是堆顶元素。因为堆顶始终是优先级最高的元素。
empty 判断队列是否为空bool empty() { return _con.empty(); }
直接调用底层容器的 empty() 方法，判断队列是否为空。
size 获取队列元素个数size_t size() { return _con.size(); }
直接返回底层容器的大小，也就是队列中元素的个数。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online