C++ 迭代器 (Iterator) 完全指南
1. 迭代器概述
迭代器是一种用于遍历容器（如 vector、list、map 等）中元素的对象，它提供了类似指针的操作（如 ++、*），但行为更通用，是泛型编程的核心。
核心思想：将算法与容器解耦。算法通过迭代器操作数据，无需关心容器的具体类型。
迭代器 是行为像指针的对象，但比指针更安全、更抽象。
核心价值：统一所有容器的遍历接口，让同一套算法能适配任意容器。
2. 迭代器的分类与能力
迭代器按操作能力分为五类，层次递进：
| 类别 |
支持操作 |
特点 |
示例容器 |
| 输入迭代器 |
++, ==, !=, * (只读) |
单遍扫描，只读，不可重复遍历 |
istream_iterator |
| 输出迭代器 |
++, * (只写) |
单遍扫描，只写，不可重复遍历 |
ostream_iterator |
| 前向迭代器 |
输入迭代器 + 多遍扫描 |
可多次读写，只能向前移动 |
forward_list, unordered_map |
| 双向迭代器 |
前向迭代器 + -- |
可前后移动 |
list, map, set |
| 随机访问迭代器** |
|
|
|
| 注意**：原生指针可视为最高级的随机访问迭代器。 |
双向迭代器 + +, -, [], <, > |
支持跳跃式访问，时间复杂度O(1) |
vector, deque, array, 原生指针 |
| 重要：算法对迭代器有最低要求，使用算法前必须确保传入的迭代器满足其所需的最低类别。 |
|
|
|
例：std::sort 要求随机访问迭代器，不能用于 list/map。 |
|
|
|
4. 迭代器的基本操作
以下操作适用于所有迭代器（具体支持程度取决于分类）：
| 操作 |
说明 |
适用迭代器类型 |
*iter |
解引用，返回元素引用 |
所有（输出迭代器只能赋值） |
iter->member |
访问元素成员（等价于 (*iter).member） |
前向及以上 |
++iter / iter++ |
前进到下一个元素 |
所有 |
--iter / iter-- |
回退到上一个元素 |
双向及以上 |
iter1 == iter2 |
判断是否相等 |
输入及以上 |
iter1 != iter2 |
判断是否不等 |
输入及以上 |
iter + n / iter - n |
前进 / 回退 n 个位置 |
随机访问 |
iter1 - iter2 |
计算两个迭代器间的距离 |
随机访问 |
iter[n] |
访问第 n 个元素（等价于 *(iter + n)） |
随机访问 |
<, >, <=, >= |
比较位置前后 |
随机访问 |
最佳实践：优先使用前置自增 ++it，效率高于后置 it++（避免临时对象拷贝）。
5. 迭代器失效
易错点：迭代器失效是 C++ 中最常见的陷阱之一。容器在修改结构时（插入、删除、重分配）可能导致已有迭代器无效，继续使用会导致未定义行为（崩溃或数据错误）。
常见容器的失效场景
| 容器 |
操作 |
失效情况 |
vector / string |
insert() / push_back() |
如果导致内存重分配：所有迭代器、指针、引用失效。 |
| 如果未重分配：插入点之后的迭代器失效。 |
|
|
|
erase() |
被删除元素及之后的所有迭代器失效。 |
|
reserve() / resize() |
若容量改变，所有迭代器失效。 |
deque |
insert() 在首尾 |
可能使所有迭代器失效。 |
|
erase() 在首尾 |
被删除元素及对端迭代器可能失效。 |
|
push_front() / push_back() |
插入点对面的迭代器可能失效。 |
list / forward_list |
insert() / erase() |
仅被删除的迭代器失效，其他迭代器、引用、指针保持有效。 |
map / set |
insert() / erase() |
仅被删除的迭代器失效，其他迭代器保持有效。 |
unordered_map / unordered_set |
insert() / erase() |
若发生 rehash：所有迭代器失效。 |
| 若未 rehash：仅被删除的迭代器失效。 |
|
|
最佳实践：在对容器进行修改（特别是 vector）后，应重新获取迭代器，或使用返回新迭代器的 erase() / insert() 函数。
// 正确遍历并删除 vector 中的元素
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ) {
if (*it % 2 == 0) {
it = vec.erase(it); // erase 返回被删除元素的下一个有效迭代器
} else {
++it;
}
}
补充易错点：range-for 循环底层依赖迭代器，循环内修改容器（增删）会直接导致迭代器失效！
6. 迭代器适配器
标准库提供了一些迭代器适配器，用于生成特殊行为的迭代器：
| 适配器 |
作用 |
头文件 |
| 反向迭代器 |
使遍历方向相反（rbegin()/rend() 返回） |
<iterator> |
| 插入迭代器 |
将赋值转换为插入操作（back_inserter、front_inserter、inserter） |
<iterator> |
| 流迭代器 |
将输入 / 输出流视为容器（istream_iterator、ostream_iterator） |
<iterator> |
| 移动迭代器 |
解引用时返回右值引用（用于移动语义，make_move_iterator） |
<iterator> |
| 边界迭代器 |
C++20 std::views 迭代器，适配范围适配器 |
<ranges> |
举例：std::copy 结合 back_inserter 可向容器末尾安全添加元素。
#include <iterator>
#include <vector>
#include <algorithm>
std::vector<int> src = {1, 2, 3};
std::vector<int> dest;
std::copy(src.begin(), src.end(), std::back_inserter(dest)); // dest: [1, 2, 3]
7. 迭代器相关的辅助函数与技巧
| 函数 / 技巧 |
说明 |
std::advance(it, n) |
将迭代器 it 前进 n 步。复杂度：随机访问为 O(1)，否则 O(n)。 |
std::distance(first, last) |
计算 first 到 last 的元素个数。非随机访问迭代器必须保证 last 可达 first。 |
std::next(it, n=1) / std::prev(it, n=1) |
返回 it 前进 / 回退 n 步后的迭代器，不改变原迭代器（C++11）。 |
std::begin(arr) / std::end(arr) |
获取数组的起始和尾后迭代器，通用化获取容器的 begin()/end()。 |
std::empty / std::size |
C++17 通用容器 / 数组判空、取大小。 |
using iterator_category |
自定义迭代器必须定义嵌套类型，用于 traits 机制。 |
高危警告：distance 用于非随机访问迭代器时，若 last 在 first 前面，会触发无限循环 / 未定义行为！
8. 常量迭代器与非常量迭代器
易错点：若容器本身是 const，则只能获得 const_iterator。若希望通过 const 引用修改元素，必须非常谨慎，应使用 const_cast，但通常不推荐。
C++17 新特性：auto 自动推导 + 非成员 cbegin()/cend()，可强制获取常量迭代器。
void print(const std::vector<int>& vec) {
// vec 是 const，只能使用 const_iterator
for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
// *it = 0; // 错误！不能通过 const_iterator 修改
std::cout << *it << " ";
}
}
9. C++20 范围迭代器（Ranges）
C++20 核心扩展：std::ranges 迭代器，支持视图、惰性求值、管道操作，是现代 C++ 迭代器的升级。
#include <ranges>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1,2,3,4,5};
// 管道式迭代：过滤偶数 + 翻倍
auto even_double = v | std::views::filter([](int x){return x%2==0;})
| std::views::transform([](int x){return x*2;});
for (auto x : even_double) std::cout << x << " "; // 输出：4 8
}
10. 自定义迭代器
当编写自定义容器时，需要为其提供迭代器。实现一个随机访问迭代器通常需要满足以下要求：
定义五个嵌套类型（value_type, difference_type, pointer, reference, iterator_category）。
实现所有必要的操作符：++, --, *, ->, ==, !=, +, -, [], <, > 等。
可以从 std::iterator_traits 获取特性，C++17 后不再推荐继承 std::iterator。
// 简化示例：一个简单的自定义迭代器骨架（C++17 风格）
class MyIterator {
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = int;
using difference_type = std::ptrdiff_t;
using pointer = int*;
using reference = int&;
// 实现必要操作符...
reference operator*() const { return *ptr; }
MyIterator& operator++() { ++ptr; return *this; }
bool operator==(const MyIterator& other) const = default; // C++20 默认比较
// ... 其他操作符
private:
int* ptr;
};
提示：为了简化，可以使用 Boost.Iterator 库，它提供了迭代器构建模板。
补充要求：自定义迭代器必须满足迭代器概念，否则无法适配标准算法。
11. 迭代器安全与最佳实践
绝不解引用尾后迭代器：end()/rend() 不能 * / ->。
循环内不修改容器：range-for 和普通循环中增删会失效。
优先使用 cbegin/cend：只读场景用常量迭代器更安全。
失效后重新获取：增删操作后不要复用旧迭代器。
算法匹配迭代器类型：sort 只用随机访问，list 用成员函数 sort。
相关函数列表
| 函数 |
参数 |
功能描述 |
std::advance |
InputIt& it |
|
Difference n |
将迭代器 it 向前移动 n 步。若 n 为负，要求 it 是双向迭代器。 |
|
std::distance |
InputIt first |
|
InputIt last |
返回从 first 到 last 的元素个数。若迭代器不是随机访问，则复杂度为 O(N)。 |
|
std::next |
ForwardIt it |
|
typename iterator_traits<ForwardIt>::difference_type n = 1 |
返回 it 前进 n 步后的迭代器，不修改 it 本身。 |
|
std::prev |
BidirectionalIt it |
|
typename iterator_traits<BidirectionalIt>::difference_type n = 1 |
返回 it 后退 n 步后的迭代器，不修改 it 本身。 |
|
std::back_inserter |
Container& c |
创建一个 std::back_insert_iterator，对它的赋值操作会调用容器的 push_back。 |
std::front_inserter |
Container& c |
创建一个 std::front_insert_iterator，对它的赋值操作会调用容器的 push_front。 |
std::inserter |
Container& c |
|
Container::iterator pos |
创建一个 std::insert_iterator，对它的赋值操作会调用容器的 insert，在 pos 之前插入。 |
|
std::make_move_iterator |
Iterator it |
将给定的迭代器转换为移动迭代器，解引用时返回右值引用（value_type&&）。 |
std::begin |
Container& c |
|
const Container& c |
|
|
T (&arr)[N] |
返回指向容器或数组起始位置的迭代器。 |
|
std::end |
Container& c |
|
const Container& c |
|
|
T (&arr)[N] |
返回指向容器或数组尾后位置的迭代器。 |
|
std::cbegin |
Container& c |
|
const Container& c |
返回指向容器起始位置的常量迭代器（C++11）。 |
|
std::cend |
Container& c |
|
const Container& c |
返回指向容器尾后位置的常量迭代器（C++11）。 |
|
std::rbegin |
Container& c |
|
const Container& c |
|
|
T (&arr)[N] |
返回指向容器或数组最后一个元素的反向迭代器。 |
|
std::rend |
Container& c |
|
const Container& c |
|
|
T (&arr)[N] |
返回指向容器或数组第一个元素前一个位置的反向迭代器。 |
|
std::crbegin |
Container& c |
|
const Container& c |
返回指向容器最后一个元素的常量反向迭代器（C++14）。 |
|
std::crend |
Container& c |
|
const Container& c |
返回指向容器第一个元素前一个位置的常量反向迭代器（C++14）。 |
|
std::size/std::empty |
容器 / 数组 |
C++17 通用取大小、判空（适配迭代器体系）。 |
std::ranges::begin/end |
C++20 范围 |
适配范围视图的迭代器接口。 |
本次补充的核心遗漏点（清单）
- C++17/20 新特性
- 高危易错点
- 知识点补全
- 函数补全
- 边界场景
