C++算法
C++ 反向迭代器：原理、实现与避坑
介绍 C++ STL 中 reverse_iterator 的原理与使用。其本质是普通迭代器的封装，通过反向映射实现遍历。rbegin() 对应 end()，rend() 对应 begin()。使用时需注意 base() 返回的是错位迭代器，不可直接解引用。仅支持双向或随机访问容器，如 vector、list 等。适用于反向查找和插入等场景。
介绍 C++ STL 中 reverse_iterator 的原理与使用。其本质是普通迭代器的封装，通过反向映射实现遍历。rbegin() 对应 end()，rend() 对应 begin()。使用时需注意 base() 返回的是错位迭代器，不可直接解引用。仅支持双向或随机访问容器，如 vector、list 等。适用于反向查找和插入等场景。
基础回顾：普通迭代器通过 ++ 操作从起始位置移动到尾后位置，实现正向遍历；
反向迭代器的核心定位：基于普通迭代器封装的'反向遍历工具'，无需修改容器本身，就能实现从容器末尾到起始位置的遍历，接口与普通迭代器保持一致（支持 ++、*、== 等操作），适配双向/随机访问容器。
最基础的使用示例（仅作快速关联，不展开讲解，重点看后续原理）：
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
// 反向遍历：从最后一个元素（5）到第一个元素（1）
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
cout << *it << " "; // 输出：5 4 3 2 1
}
return 0;
}
关键提醒：反向迭代器不是'全新迭代器'，也不是普通迭代器的'反向操作'，而是对普通迭代器的封装——这是理解其原理的核心前提。
很多开发者使用反向迭代器时，只知 rbegin() 和 rend() 的用法，却不懂其设计初衷，导致踩坑不断。这里从'为什么这么设计'切入，拆解核心思路。
STL 中不同容器（vector、list、map）的普通迭代器，已经实现了各自的遍历逻辑（适配底层存储结构）。
反向迭代器的设计目标，就是不重复造轮子：
用一个简单的 vector{1,2,3,4,5}，直观理解反向迭代器与普通迭代器的映射关系： 普通迭代器的区间：[begin(), end()) → 指向 1 → 逐步 ++ → 指向尾后位置（5 后面）； 反向迭代器的区间：[rbegin(), rend()) → 指向 5 → 逐步 ++ → 指向 1 前面的位置；
两者的核心映射关系（重中之重）：
为什么解引用要取'基迭代器前一个位置'？ 核心是适配 STL 统一的「左闭右开」区间规则——普通迭代器的 end() 是尾后位置（无效），反向迭代器的 rbegin() 对应 end()，解引用时必须向前移动一位，才能拿到有效元素（5）。
这是反向迭代器最容易踩坑的点，单独拆解，记牢这 2 句话，避开 90% 的边界错误：
rbegin()：反向起始迭代器，其基迭代器是普通迭代器的 end()（尾后位置），解引用时取 *(base()-1)，指向容器最后一个有效元素；rend()：反向终止迭代器，其基迭代器是普通迭代器的 begin()（起始位置），解引用会越界，仅作为遍历终止标志，不可使用 *it；示例验证（直观感受边界映射）：
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
auto r_it = vec.rbegin(); // 反向迭代器，指向 5
auto base_it = r_it.base(); // 基迭代器，指向 end()（5 后面，无效）
cout << *r_it << endl; // 正确：输出 5（底层是 *(base_it-1)）
// cout << *base_it << endl; // 错误：base_it 是 end()，解引用越界
return 0;
}
理解了设计思路，我们手动实现一个极简版反向迭代器（仅保留核心逻辑，不做 STL 兼容冗余代码），基于普通迭代器封装，看完就能懂 STL 反向迭代器的底层实现。
#include <iostream>
#include <iterator>
using namespace std;
// 复用普通迭代器（仅保留核心，不重复上一篇细节）
class IntRangeIterator {
public:
using iterator_category = forward_iterator_tag;
using value_type = int;
using pointer = int*;
using reference = int&;
using difference_type = ptrdiff_t;
IntRangeIterator(int current, int end) : current_(current), end_(end) {}
// 普通迭代器核心操作：++（正向移动）、--（反向移动，供反向迭代器使用）
IntRangeIterator& operator++() {
++current_;
return *this;
}
IntRangeIterator& operator--() {
--current_;
return *this;
}
int operator*() const {
return current_;
}
bool operator==(const IntRangeIterator& other) const {
return current_ == other.current_ && end_ == other.end_;
}
bool operator!=(const IntRangeIterator& other) const {
return !(*this == other);
}
// 提供 base() 方法，返回基迭代器（供反向迭代器获取）
IntRangeIterator base() const {
return *this;
}
private:
int current_; // 当前位置
int end_; // 终止位置（左闭右开）
};
// 自定义可迭代对象（极简版，仅支持正向/反向迭代器）
class IntRange {
public:
IntRange(int start, int end) : start_(start), end_(end) {}
// 普通迭代器的 begin/end（仅作支撑，不展开）
IntRangeIterator begin() const {
return IntRangeIterator(start_, end_);
}
IntRangeIterator end() const {
return IntRangeIterator(end_, end_);
}
private:
int start_;
int end_;
};
// 重点：手动实现反向迭代器（封装普通迭代器）
template<typename Iterator>
class MyReverseIterator {
public:
// 构造函数：接收普通迭代器，作为基迭代器
MyReverseIterator(Iterator it) : base_it(it) {}
// 1. 反向迭代器的 ++：等价于基迭代器的 --（核心映射）
MyReverseIterator& operator++() {
--base_it; // 基迭代器向后移动，反向迭代器向前移动
return *this;
}
// 2. 反向迭代器的 --：等价于基迭代器的 ++（补充操作）
MyReverseIterator& operator--() {
++base_it; // 基迭代器向前移动，反向迭代器向后移动
return *this;
}
// 3. 反向迭代器的解引用：返回基迭代器前一个位置的元素
typename Iterator::value_type operator*() const {
Iterator temp = base_it; // 保存当前基迭代器位置（避免修改原位置）
--temp; // 移动到前一个有效位置
return *temp; // 返回有效元素
}
// 4. 边界判断：复用基迭代器的判断逻辑
bool operator==(const MyReverseIterator& other) const {
return base_it == other.base_it;
}
bool operator!=(const MyReverseIterator& other) const {
return !(*this == other);
}
// 5. 获取基迭代器（供外部使用，注意错位问题）
Iterator base() const {
return base_it;
}
private:
Iterator base_it; // 底层核心：封装的普通迭代器（基迭代器）
};
// 为 IntRange 添加反向迭代器支持（rbegin/rend）
template<typename Iterator>
MyReverseIterator<Iterator> rbegin(const IntRange& range) {
return MyReverseIterator<Iterator>(range.end()); // rbegin() 对应 end()
}
template<typename Iterator>
MyReverseIterator<Iterator> rend(const IntRange& range) {
return MyReverseIterator<Iterator>(range.begin()); // rend() 对应 begin()
}
// 测试自定义反向迭代器（验证核心逻辑）
int main() {
IntRange range(1, 6); // 元素：1,2,3,4,5（左闭右开）
// 反向遍历（核心验证）
cout << "自定义反向迭代器遍历：";
for (auto it = rbegin<IntRangeIterator>(range); it != rend<IntRangeIterator>(range); ++it) {
cout << *it << " "; // 输出：5 4 3 2 1（符合预期）
}
cout << endl;
// 验证基迭代器错位映射
auto r_it = rbegin<IntRangeIterator>(range);
cout << "rbegin() 解引用：" << *r_it << endl; // 输出 5
cout << "rbegin() 的基迭代器 base()：" << *(r_it.base()) << endl; // 输出 6（end() 位置，无效）
cout << "基迭代器 base()-1 解引用：" << *(--r_it.base()) << endl; // 输出 5（有效）
return 0;
}
核心总结（手动实现关键点）：
我们实现的是极简版，STL 中的 std::reverse_iterator 更完善，但核心逻辑完全一致。以下 3 个细节，是日常开发中最容易踩坑的，结合 STL 实际使用场景拆解。
记住：反向迭代器的 base() 方法，返回的是'错位的普通迭代器'，不可直接解引用。 STL 设计 base() 的初衷，是为了让反向迭代器与普通迭代器相互转换，而非让开发者直接使用基迭代器取值。
错误示例（高频踩坑）：
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
auto r_it = vec.rbegin();
// 错误写法：直接解引用 base() 返回的基迭代器
cout << *(r_it.base()) << endl; // 未定义行为（base() 是 end()，无效）
// 正确写法：如需用基迭代器取值，先向前移动一位
cout << *(--r_it.base()) << endl; // 正确：输出 5
return 0;
}
反向迭代器依赖基迭代器的 -- 操作（向后移动），因此不是所有容器的普通迭代器，都能适配反向迭代器：
错误示例（编译失败）：
#include <forward_list>
using namespace std;
int main() {
forward_list<int> flist = {1, 2, 3};
// 错误：forward_list 的迭代器是前向迭代器，不支持 --，无法适配反向迭代器
for (auto it = flist.rbegin(); it != flist.rend(); ++it) {
// 编译失败
}
return 0;
}
无论正向还是反向迭代器，STL 都遵循'左闭右开'区间规则，反向迭代器也不例外：
it != rend()，不可写 it < rend()（仅随机访问迭代器支持 <，双向迭代器不支持）；正确示例（通用写法，适配所有支持的容器）：
#include <iostream>
#include <list>
// list 是双向迭代器，支持反向迭代器
using namespace std;
int main() {
list<int> lst = {1, 2, 3, 4, 5};
// 正确写法：it != rend()（通用，适配双向/随机访问迭代器）
for (auto it = lst.rbegin(); it != lst.rend(); ++it) {
cout << *it << " ";
}
return 0;
}
结合实际开发场景，补充 2 个反向迭代器的高频用法，帮你快速落地。
当需要从容器末尾查找目标元素时，用反向迭代器配合 find 算法，比正向查找更高效（尤其适合大概率在末尾的场景）。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8};
int target = 7;
// 反向查找：从末尾开始查找 7
auto r_it = find(vec.rbegin(), vec.rend(), target);
if (r_it != vec.rend()) {
// 转换为普通迭代器，获取正向索引（注意 base() 错位）
int index = r_it.base() - vec.begin() - 1;
cout << "找到目标元素" << target << "，索引：" << index << endl; // 输出 6
} else {
cout << "未找到目标元素" << target << endl;
}
return 0;
}
结合容器的 insert 方法，反向迭代器可实现'在指定元素前插入'（利用 base() 转换为普通迭代器）。
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
auto r_it = vec.rbegin() + 2; // 反向迭代器指向 3（从末尾数第 3 个元素）
// 插入元素 10：在 r_it 指向的元素（3）前插入（正向位置是索引 2）
vec.insert(r_it.base(), 10);
// 正向遍历验证
cout << "插入后正向遍历：";
for (auto num : vec) {
cout << num << " "; // 输出：1 2 10 3 4 5
}
return 0;
}
it != rend()；
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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