迭代器五大类别
# 37.迭代器五大类别
# 目录介绍
- 1. 案例引入
- 2. 架构概览
- 3. Input / Output 迭代器
- 4. Forward 迭代器
- 5. Bidirectional 与 Random Access 迭代器
- 6. Tag Dispatch 的分派机制
- 7. 迭代器萃取 iterator_traits
- 8. C++20 Ranges 对迭代器的重构
- 9. 迭代器失效全族谱
- 10. 综合案例串讲
# 1. 案例引入
# 1.1 std::sort 拒绝 list::iterator 的编译灾难
某新手看到 std::sort——把它用在 std::list 上。GCC 爆出 400 行错误：
// ====== 事故代码 V1：sort 不接受双向迭代器 ======
std::list<int> lst = {3, 1, 4, 1, 5};
std::sort(lst.begin(), lst.end()); // ❌ 编译错误！400 行模板错误信息
// 根本原因：std::sort 需要 Random Access Iterator
// list::iterator 只是 Bidirectional Iterator——缺少 +n、-n、<、> 等操作
1
2
3
4
5
6
2
3
4
5
6
std::sort 内部需要 last - first（计算元素数）和 first + n（随机访问 pivot）——双向迭代器提供不了这些。
修复：lst.sort()——list 的成员函数用归并排序，只要求双向迭代。
# 1.2 自定义迭代器的 tag 错误
某个项目自己实现了一个环形缓冲区的迭代器——但却标了 random_access_iterator_tag：
// ====== 事故代码 V2：虚假的 random_access_tag ======
class RingIterator {
int* buf_; size_t pos_; size_t cap_;
public:
using iterator_category = std::random_access_iterator_tag; // ← 撒谎！
RingIterator& operator++() { pos_ = (pos_ + 1) % cap_; return *this; }
// ❌ 没有定义 operator+=(n) —— random_access 要求 O(1) 的 +=n
// ❌ 也没有定义 operator-(iterator) —— random_access 要求
};
// std::sort 尝试用 +=N 跳转到 pivot
// → 编译通过（tag 是 random_access）→ 找不到 operator+= → 编译期报错
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
教训：tag 不是自己说了算的——必须实现对应的操作集。
# 1.3 七个待解疑问
① 五大类别的层级关系是什么? 谁继承自谁? → 第 2 / 第 6 章
② input/output 迭代器为什么是「一次性」的? → 第 3 章
③ tag dispatch 怎么做到零运行时开销? 汇编层怎么验证? → 第 6 章
④ iterator_traits 是什么? 为什么裸指针也是迭代器? → 第 7 章
⑤ C++20 ranges 为什么用 sentinel 替代 end iterator? → 第 8 章
⑥ 各类容器的迭代器分别是什么类别? 什么时候会失效? → 第 5.3 / 第 9 章
⑦ 怎么给自己写的容器配上正规的迭代器? → 第 7.3 / 第 10 章
1
2
3
4
5
6
7
2
3
4
5
6
7
# 2. 架构概览
# 2.1 五大类别的层级与演进
┌──────────────────────────────┐
│ Random Access (随机访问) │ ← 最强大：+n、<、[]、O(1)
│ vector::iterator, deque::it │
├──────────────────────────────┤
│ Bidirectional (双向) │ ← 额外：+--it
│ list::iterator, map::it │
├──────────────────────────────┤
│ Forward (前向) │ ← 额外：可重复遍历
│ forward_list::iterator │
├────────────┬─────────────────┤
│ Input │ Output │ ← 单次消费 / 单次写入
│ istream │ ostream │
└────────────┴─────────────────┘
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
每一层在前一层的基础上增加能力：
| 类别 | 标签 | 支持的操作 | 可多遍? |
|---|---|---|---|
| Input | input_iterator_tag | ++, *, ==, != | ❌ |
| Output | output_iterator_tag | ++, *（写入） | ❌ |
| Forward | forward_iterator_tag | ++, *, ==, != | ✅ |
| Bidirectional | bidirectional_iterator_tag | ++, --, *, ==, != | ✅ |
| Random Access | random_access_iterator_tag | ++, --, +n, -n, <, >, [], ==, != | ✅ |
# 2.2 为何这么切
疑惑：为什么不把所有迭代器都做成 Random Access？这样所有算法都能用最有效的版本？
论证：
- 物理限制——链表无法在 O(1) 内跳到第 N 个元素。如果强制链表实现
operator+=n——那就得遍历 N 步——O(N) 冒充 O(1)——std::sort会多次使用它，导致 O(N² log N) 的灾难。 - 类型系统是安全网——算法设计要求 Random Access 就用 tag 声明——编译器在模板实例化时检查。这避免了「算法认为迭代器能做到 O(1) 随机访问，但实际是 O(N) 遍历」的潜在灾难。
- tag dispatch 比虚函数更快——零运行时开销。编译期就决定了走哪条代码路径（第 6.3 节）。
结论：迭代器的层级不是为了限制——是为了「算法的复杂度承诺」通过类型系统自动选择正确的实现。 Random Access 的算法可以回退到 Forward 的实现（O(N)），但反之不然。
# 3. Input / Output 迭代器
# 3.1 单次消费的不可逆模型
Input 迭代器的核心约束：同一个位置只能被读取一次——++it 之后，前一个位置的值不再保证有效。
// istream_iterator 是典型的 Input 迭代器
std::istringstream iss("1 2 3");
std::istream_iterator<int> it(iss), end;
// it 在底层是「当前读取到的 int」——++it 触发下一次 >> 读
// 没有「回退」能力——流不会为了你保留历史字符
1
2
3
4
5
2
3
4
5
Output 迭代器同理——写入不可逆：
std::ostream_iterator<int> out(std::cout, " ");
*out = 42; ++out; // 输出 "42 "——不能撤销
1
2
2
# 3.2 istream_iterator 与 ostream_iterator 的汇编
std::istream_iterator<int> it(std::cin), end;
int x = *it; // 触发 cin >> x
1
2
2
GCC 13.2 -O2：
; *it → cin >> x
mov rdi, QWORD PTR std::cin[rip]
call std::istream::operator>>(int&)
; 没有缓存——每次 *it 都是一次流操作
1
2
3
4
2
3
4
# 3.3 为什么 input 迭代器不能用于多遍算法
std::vector<int> v;
std::copy(std::istream_iterator<int>(std::cin),
std::istream_iterator<int>(),
std::back_inserter(v));
// ✅ 一遍遍历——Input 迭代器可以
// ❌ 不能这样：
std::sort(std::istream_iterator<int>(std::cin),
std::istream_iterator<int>());
// sort 需要多次访问元素、需要随机跳转——Input 做不到
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 4. Forward 迭代器
# 4.1 可重复遍历的最小保证
Forward 迭代器的核心承诺：同一个范围可以被遍历多遍：
std::forward_list<int> fl = {1, 2, 3};
auto it = fl.begin();
auto saved = it; // ✅ 保存迭代器——可以回来
++it; ++it; // 现在 it → 3
// saved 仍然 → 1 —— 前向迭代器 <=> 多遍能力
1
2
3
4
5
2
3
4
5
# 4.2 forward_list 的迭代器剖析
// forward_list::iterator 只存一个指针（指向当前节点）
struct _Fwd_list_iterator {
_Fwd_list_node* _M_node; // 仅一个指针——8 字节
auto& operator++() { _M_node = _M_node->_M_next; return *this; }
// ⚠️ 没有 operator-- ——单向链表的物理约束
};
1
2
3
4
5
6
7
2
3
4
5
6
7
# 4.3 为什么 forward 迭代器不需要 size()
forward 迭代器不承诺「知道终点」。它只承诺「可以到达终点」。std::count 和 std::find 对 Forward 迭代器的下限就是「我可以一直 ++ 直到 == end」——不需要终点提前已知。
# 5. Bidirectional 与 Random Access 迭代器
# 5.1 双向的额外能力与代价
std::list<int> lst = {1, 2, 3};
auto it = lst.end();
--it; // ✅ 双向迭代器——回到最后一个元素
// 要求：每个节点必须存储 prev 指针
// list 节点 = next(8B) + prev(8B) + data
// forward_list 节点 = next(8B) + data（省 8 字节）
1
2
3
4
5
6
7
2
3
4
5
6
7
# 5.2 随机访问的五项全能
std::vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin();
it + 3; // ✅ O(1) —— 指针加法
it[2]; // ✅ O(1) —— 等价于 *(it+2)
it2 - it1; // ✅ O(1) —— 指针差
it1 < it2; // ✅ O(1) —— 地址比较
it += 3; // ✅ O(1)
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 5.3 各容器迭代器的类别对照表
| 容器 | 迭代器类别 | 裸指针? | 迭代器失效（insert/erase） |
|---|---|---|---|
| vector | Random Access | ✅ T* | 扩容全失效 / 删除点之后 |
| deque | Random Access | ❌ (4 成员) | 中间操作全失效 / 两端安全 |
| list | Bidirectional | ❌ | 仅被删除者 |
| forward_list | Forward | ❌ | 仅被删除者 |
| map/set | Bidirectional | ❌ | 仅被删除者 |
| unordered_map | Forward | ❌ | rehash 全失效 / erase 仅被删者 |
| 数组 (T[]) | Random Access | ✅ T* | N/A |
# 6. Tag Dispatch 的分派机制
# 6.1 五个 tag 的结构与继承链
// libstdc++ 的实际定义
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
1
2
3
4
5
6
2
3
4
5
6
继承链的存在让「最匹配版本」的分派成为可能：
random_access_tag → bidirectional_tag → forward_tag → input_tag
如果一个算法有「random_access 版」和「input 版」两个重载：
传入 random_access_tag → 两个都匹配 → 选更特化的 random_access 版
传入 bidirectional_tag → 只匹配 input 版（bidirectional 不是 random_access）
1
2
3
4
5
2
3
4
5
# 6.2 算法如何根据 tag 分派实现
以 std::advance 为例：
// ① 接口层——提取 tag
template <typename It>
void advance(It& it, int n) {
advance_impl(it, n, typename std::iterator_traits<It>::iterator_category{});
}
// ② Random Access 版——最快的实现
template <typename It>
void advance_impl(It& it, int n, std::random_access_iterator_tag) {
it += n; // 直接跳——O(1)
}
// ③ Bidirectional / Forward / Input 版——退化的实现
template <typename It>
void advance_impl(It& it, int n, std::bidirectional_iterator_tag) {
if (n >= 0) while (n--) ++it; else while (n++) --it; // 逐次移动
}
// 如果 n=1000000：
// random_access → 1 条指令
// bidirectional → 1000000 条指令——但正确
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 6.3 汇编层的零开销证据
std::vector<int> v = {1,2,3};
auto it = v.begin();
std::advance(it, 2);
1
2
3
2
3
GCC 13.2 -O2：
; std::advance —— 编译后的汇编（Random Access）
add rax, 8 ; 直接 += 2*sizeof(int)
; 没有函数调用、没有虚表查表、没有分支——完全内联
1
2
3
2
3
tag dispatch 的所有分支在编译期全部消去——最终二进制里只留下「具体迭代器类别的最优路径」。
# 6.4 std::distance 和 std::advance 的 tag 分派实例
// distance —— 用 tag 选择 O(1) 还是 O(N)
template <typename It>
int distance_impl(It first, It last, std::random_access_iterator_tag) {
return last - first; // O(1)
}
template <typename It>
int distance_impl(It first, It last, std::input_iterator_tag) {
int n = 0;
while (first != last) { ++first; ++n; }
return n; // O(N)
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 7. 迭代器萃取 iterator_traits
# 7.1 五类关联类型的自动推导
template <typename It>
struct iterator_traits {
using iterator_category = typename It::iterator_category;
using value_type = typename It::value_type;
using difference_type = typename It::difference_type;
using pointer = typename It::pointer;
using reference = typename It::reference;
};
// 使用：提取迭代器的类型以确定算法策略
template <typename It>
auto sum(It first, It last) ->
typename std::iterator_traits<It>::value_type { ... }
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 7.2 裸指针的迭代器身份
std::iterator_traits 对裸指针有偏特化——这让裸指针也是合法的迭代器：
// 偏特化——T* 的 traits
template <typename T>
struct iterator_traits<T*> {
using iterator_category = std::random_access_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
};
// 所以你可以这样做：
int arr[] = {1, 2, 3};
std::sort(arr, arr + 3); // ✅ T* 被识别为 Random Access Iterator
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 7.3 自定义迭代器的最小实现
class MyIterator {
int* ptr_;
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; }
MyIterator operator+(difference_type n) const { return {ptr_ + n}; }
difference_type operator-(const MyIterator& o) const { return ptr_ - o.ptr_; }
bool operator==(const MyIterator& o) const { return ptr_ == o.ptr_; }
bool operator!=(const MyIterator& o) const { return !(*this == o); }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 8. C++20 Ranges 对迭代器的重构
# 8.1 sentinel 替代 end iterator
C++20 引入 sentinel——一个可以和 begin iterator 不同类型的「结束标记」：
// ❌ C++17：必须提供两个相同类型的迭代器
std::istream_iterator<int> begin(std::cin), end;
// ✅ C++20：sentinel 可以是不同类型
auto sv = "1 2 3 4"sv;
auto words = std::ranges::split_view(sv, ' ');
// end sentinel 不需要是迭代器——可以是一个谓词
1
2
3
4
5
6
7
2
3
4
5
6
7
好处：流终止、以 '\0' 结尾的 C string——这些场景不需要「构造一个假的 end iterator」。sentinel 是一个更轻的抽象。
# 8.2 从 iterator_traits 到 iter_value_t
C++20 用 concepts + alias 简化了萃取：
// C++17
typename std::iterator_traits<It>::value_type
// C++20
std::iter_value_t<It> // 更简洁
std::iter_reference_t<It>
std::iter_difference_t<It>
1
2
3
4
5
6
7
2
3
4
5
6
7
# 8.3 视图管道的迭代器组合
auto v = std::views::iota(1)
| std::views::filter([](int x) { return x % 2 == 0; })
| std::views::take(5);
// 每层视图都产生一个新的迭代器类型——链式组合
// filter 的迭代器是「跳过不满足条件的元素」的 input/forward 迭代器
// take 的迭代器是「计数到 N 后终止」的迭代器
1
2
3
4
5
6
7
2
3
4
5
6
7
# 9. 迭代器失效全族谱
# 9.1 各容器失效规则汇总
| 容器 | insert | erase | push_back (扩容) | push_back (有容量) | rehash |
|---|---|---|---|---|---|
| vector | 插入点及之后全失效 | 删除点及之后全失效 | 全失效 | ❌ | — |
| deque | 全失效 | 全失效 | ❌ | ❌ | — |
| list | ❌ | 仅被删除者 | ❌ | — | — |
| forward_list | ❌ (insert_after) | 仅被删除者 | ❌ | — | — |
| map/set | ❌ | 仅被删除者 | — | — | — |
| unordered_map | ❌ (不 rehash) | 仅被删除者 | — | — | 全失效 |
# 9.2 「修改而不遍历」的危险模式
// ❌ 遍历 list 时删除——没问题（list 不失效其他迭代器）
for (auto it = lst.begin(); it != lst.end(); ) {
if (bad(*it)) it = lst.erase(it); else ++it;
}
// ❌ 遍历 vector 时删除——灾难（erase 使后续迭代器全部失效）
for (auto it = v.begin(); it != v.end(); ++it) {
if (bad(*it)) v.erase(it); // it 失效——++it 访问已失效迭代器
}
// ✅ C++20 —— std::erase_if 替你处理
std::erase_if(v, bad);
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 9.3 ranges 如何部分解决失效问题
// ranges 生成的是视图（view）——惰性求值——不修改原容器
auto good = std::views::filter(v, [](int x) { return !bad(x); });
// good 是一个视图——原 v 不变——迭代器不会失效
// 但要小心：原 v 如果被修改，视图的迭代器仍然是失效的
1
2
3
4
2
3
4
# 10. 综合案例串讲
# 10.1 案例真相揭晓
| # | 疑问 | 答案 |
|---|---|---|
| ① | 五大类别的层级? | 第 2/6 章：input → forward → bidirectional → random_access（继承链） |
| ② | input 为什么是一次性? | 第 3 章：底层是流——不可回退；++it 后前一个位置的缓存不可靠 |
| ③ | tag dispatch 零开销? | 第 6 章：编译期全内联——汇编里看不到任何 tag 痕迹 |
| ④ | iterator_traits? | 第 7 章：萃取 5 类类型——裸指针偏特化让 T* 也是迭代器 |
| ⑤ | sentinel vs end? | 第 8 章：C++20 允许 begin 和 sentinel 不同类型——泛化 find 的终止条件 |
| ⑥ | 各类容器迭代器? | 第 5.3/9 章：vector=RA、deque=RA、list=Bidi、fwd_list=Fwd、umap=Fwd |
| ⑦ | 自定义迭代器? | 第 7.3 章：实现 5 类型别名 + 对应操作集 |
# 10.2 STL 算法的分派决策树
STL 算法如何选择实现？
① 读 iterator_traits → iterator_category
② 根据 tag 选择实现版本：
├─ random_access → 最优路径（O(1) 跳转、二分等）
├─ bidirectional → 双向路径（可用 --）
├─ forward → 多遍路径（可用多遍遍历）
└─ input → 单遍路径（最慢但最通用）
③ 编译期全内联——无运行时开销
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 10.3 设计哲学回扣
哲学 1：迭代器是算法和数据结构的胶水——二者通过 tag 互选
数据结构暴露自己的迭代器 tag，算法通过 tag dispatch 选择实现。二者不需要互相了解——只需要通过迭代器类型系统交流。 这是 STL 的最核心设计：算法 + 迭代器 + 容器——三分天下。这个设计让「通用算法」成为可能——std::sort 不需要知道 vector 或 deque 的内部实现，只需要知道迭代器的能力。同样的算法代码、不同的迭代器类型、编译器自动选不同的实现路径。
哲学 2：编译期的分支是零开销的——tag dispatch 就是证明
五个 tag 类型的继承链让算法在编译期就选好了路径。最终二进制里没有 if/else、没有 switch、没有虚函数——只有「对具体迭代器类型最有优化」的代码。 汇编证据：std::advance(it, n) 对 vector<int>::iterator 生成 add rax, n*4——一条指令；对 list<int>::iterator 生成一个 while 循环。同一个函数名、完全不同的指令——由 tag 在编译期驱动。
哲学 3：裸指针是 C++ 迭代器系统的基石——不是缺陷是设计
T* 通过 iterator_traits 偏特化获得 random_access_iterator_tag——这让所有 C 数组都可以直接参与 STL 算法。STL 的设计不是 C++ 强加给 C 的——是 C 的指针被 STL 自然地吸纳为一等公民。 这也让 std::sort(arr, arr+N) 和 std::sort(v.begin(), v.end()) 共享同一份算法代码——只是迭代器类型（T* vs __gnu_cxx::__normal_iterator<T*>）不同，在编译期分派到同一份优化代码。
哲学 4：复杂度承诺是迭代器 tag 的最高法则——tag 就是说「我能做到 O(1)」
Random Access Iterator 承诺 +=n 是 O(1)。如果实现成 O(N)——算法会因你的谎言而产生错误的性能行为。tag 不是随便选的——它是一个复杂度契约。 std::sort 要求 Random Access——它用 last-first 算元素个数、用 first + N/2 选 pivot、用 < 比较迭代器。如果双向迭代器谎称自己是 Random Access——所有随机操作都会变成 O(N)——sort 从 O(NlogN) 退化为 O(N²logN)。类型系统在这里不是累赘——是复杂度安全的护城河。
哲学 5：C++20 sentinel 把「结束条件」从「类型相同」解放出来
传统的迭代器模型要求 begin 和 end 是同一类型——但 C string 以 \0 结束、流以 EOF 结束——不需要构造一个假的 end iterator。sentinel 把「范围」的定义从「两个相同类型的迭代器」泛化为「一个迭代器和一个可比较的哨兵」。 这让 ranges 能覆盖之前迭代器无法表达的边界情况。这是迭代器概念自从 STL 诞生以来最重要的泛化。
# 10.4 速查表合集
五大迭代器能力速查：
| 能力 | Input | Fwd | Bidi | RA |
|---|---|---|---|---|
| ++ | ✅ | ✅ | ✅ | ✅ |
| * (读) | ✅ | ✅ | ✅ | ✅ |
| * (写) | Output | ✅ | ✅ | ✅ |
| == / != | ✅ | ✅ | ✅ | ✅ |
| 可多遍遍历 | ❌ | ✅ | ✅ | ✅ |
| -- | ❌ | ❌ | ✅ | ✅ |
| +n / -n | ❌ | ❌ | ❌ | ✅ |
| [] | ❌ | ❌ | ❌ | ✅ |
| < / > | ❌ | ❌ | ❌ | ✅ |
STL 算法最低迭代器要求：
| 算法 | 最低要求 | 原因 |
|---|---|---|
std::find | Input | 单次线性扫描 |
std::copy | Input + Output | 一遍读取+写入 |
std::reverse | Bidirectional | 需要从两端交换 |
std::sort | Random Access | 需要随机 pivot |
std::binary_search | Forward | 至少需要多遍 |
下一篇：迭代器的分派机制说清了。下一篇进入卷五收官篇 38.STL 算法设计哲学——算法+迭代器+容器三分天下的设计范型、introsort 的混合排序策略、stable_sort 的归并与 allocate 权衡、partition 三路分组的优雅。
上次更新: 2026/06/10, 11:13:41
