一、迭代器是什么：一个"像指针的东西"

先用一句话说清：

容器 ──[ begin()/end() ]──► 迭代器 ◄──[ 算法只认这个 ]── 算法
                                │
                        长得像指针：*it 取值、++it 前进

看一个最能说明问题的例子：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // ── 同一段内存，两种"看法" ────────────
    int a[] = {7, 3, 9, 1};

    int *p = a;                       // ← 指针
    vector<int> v = {7, 3, 9, 1};
    vector<int>::iterator it = v.begin();   // ← 迭代器

    // 它们的用法一模一样：
    cout << "*p = " << *p << "，*it = " << *it << endl;
    ++p; ++it;
    cout << "++ 之后：*p = " << *p << "，*it = " << *it << endl;

    // ── 关键：算法对两者一视同仁 ──────────
    sort(a, a + 4);                            // 排数组
    sort(v.begin(), v.end());                  // 排 vector
    cout << "a: ";
    for (int i = 0; i < 4; i++) cout << a[i] << " ";
    cout << "   v: ";
    for (int x : v) cout << x << " ";
    cout << endl;

    cout << "（sort 只有一份代码，却服务了数组和 vector —— 因为两者都是随机访问迭代器）" << endl;
    return 0;
}

看到什么算成功：

*p = 7，*it = 7
++ 之后：*p = 3，*it = 3
a: 1 3 7 9    v: 1 3 7 9 
（sort 只有一份代码，却服务了数组和 vector —— 因为两者都是随机访问迭代器）

这就是迭代器的全部秘密：指针是迭代器的一个特例（数组的迭代器就是指针）；vector 的迭代器是"包装过的指针"；list 的迭代器是"包装过的节点指针"。算法只要求"像指针那样能用"，不关心它内部是什么。

所以"迭代器"不是一个类，而是一个"约定"：只要一个类型支持 *、++（以及别的），它就能当迭代器用。 这是 C++ 里"用概念（concept）解耦"的早期形态——12.1 的模板提供了语法基础（template <typename Iter>），迭代器提供了语义约定。

二、五个等级：一张"能力阶梯"

不是所有迭代器都一样能打。 标准把它们分成五类，能力从弱到强：

① 输出迭代器（只写）        ← 独立的一支（只有"写"的能力）
② 输入迭代器（只读）        ┐
③ 前向迭代器（++）          │ 这一支能力逐步递增
④ 双向迭代器（++ / --）     │
⑤ 随机访问迭代器（+n / -n） ┘

准确地说，迭代器不是"一条直线"：输入→前向→双向→随机访问构成一条"读能力递增"的链；输出迭代器是独立的一支（只有写能力）。但教材按"从弱到强"的顺序讲五类，本节也按这个顺序——你只要记住"能力越强，能用的算法越多"。

五个等级的完整对照表（先扫一遍，不要求背）：

"能力递增"的含义就是"上面每一行的算法，下面每一行都能用，反之不行"： - sort 要 ⑤ → list / set（只有 ④）用不了； - reverse 要 ④ → list 能用（13.3.2 说过），forward_list 用不了； - find / count 只要 ② → 所有容器都能用。

这就是 13.3.3 那句"sort 要求随机访问迭代器，所以 list 用不了它"的完整答案。

三、动手 Demo：看迭代器的"等级差"怎么变成报错

任务：用同一个算法分别作用在"能力不同"的容器上，看哪些能编过、哪些不能。

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5};
    list<int>   l = {3, 1, 4, 1, 5};
    set<int>    s = {3, 1, 4, 5};

    // ── ① count 只要"能 ++"（输入迭代器以上）→ 全都能用 ──
    cout << "count 在 vector 上：" << count(v.begin(), v.end(), 1) << endl;
    cout << "count 在 list   上：" << count(l.begin(), l.end(), 1) << endl;
    cout << "count 在 set    上：" << count(s.begin(), s.end(), 1) << endl;

    // ── ② accumulate 只要"能 ++" → 都能用 ──
    cout << "accumulate(vector)：" << accumulate(v.begin(), v.end(), 0) << endl;
    cout << "accumulate(list)  ：" << accumulate(l.begin(), l.end(), 0) << endl;

    // ── ③ reverse 要"能 --"（双向以上）→ vector / list 都能，set 是"只读"不能 ──
    reverse(v.begin(), v.end());
    cout << "reverse(vector) 之后：";
    for (int x : v) cout << x << " ";
    cout << endl;

    reverse(l.begin(), l.end());
    cout << "reverse(list)   之后：";
    for (int x : l) cout << x << " ";
    cout << endl;

    // reverse(s.begin(), s.end());   // ❌ 编译不过：set 的元素是 const，不能写

    // ── ④ sort 要"+n / -n"（随机访问）→ 只有 vector 能 ──
    sort(v.begin(), v.end());
    cout << "sort(vector) 之后：";
    for (int x : v) cout << x << " ";
    cout << endl;

    // sort(l.begin(), l.end());      // ❌ 编译不过：list 的迭代器不支持 -
    l.sort();                          // ★ list 只能用成员版
    cout << "list 用成员 l.sort()：";
    for (int x : l) cout << x << " ";
    cout << endl;

    // sort(s.begin(), s.end());      // ❌ 编译不过（而且根本没必要）
    return 0;
}

看到什么算成功：

count 在 vector 上：2
count 在 list   上：2
count 在 set    上：1
accumulate(vector)：14
accumulate(list)  ：14
reverse(vector) 之后：5 1 4 1 3 
reverse(list)   之后：5 1 4 1 3 
sort(vector) 之后：1 1 3 4 5 
list 用成员 l.sort()：1 1 3 4 5 

这张表的"规律"就是全部答案：

注意 set 那一列：set 的迭代器是双向的（等级够），但它的元素是 const（13.2.1 讲过，是排序依据）——"等级够"和"能不能用"是两件事：改元素的算法在 set 上都会被 const 拦下。 reverse 在 list 上能编过，但 list 有自己的 l.reverse()（13.1.3）——成员版更懂自己的结构，通常更快。 这是"能编过"和"该用哪个"的区别。

30 秒实验

1. list 用 sort 的报错长什么样：把 // sort(l.begin(), l.end()); 取消注释，编译 → 报错信息里会出现 no match for 'operator-'（sort 内部要算 last - first）。认一下这个报错脸。
2. set 用 reverse：把 // reverse(s.begin(), s.end()); 取消注释 → 报 assignment of read-only location（元素 const）。和 set 不能改元素是同一条。
3. 等级测试：写 cout << (v.begin() < v.end()); → 能编过（随机访问支持 <）；写 cout << (l.begin() < l.end()); → 编译不过（双向迭代器只能 == / !=）。这个"能不能比大小"是 ④ 和 ⑤ 的分水岭。
4. 数组是 ⑤：int a[5]; sort(a, a+5); 能跑——说明裸指针完全达到了随机访问迭代器的级别。

常见误区

1. "迭代器就是指针"——指针是一种迭代器，但迭代器不都是指针。list / set 的迭代器是包装过的节点指针（类对象）——所以它们能"知道容器、能维护遍历状态"。"像指针"是接口相似，不是本质相同。
2. "所有迭代器都一样"——差得远。能不能 --、能不能 +n、能不能 []、能不能比大小，决定了它能用哪些算法。 这一节的全部内容就是这个。
3. "end() 指向最后一个元素"——指向"最后一个的下一个位置"（左闭右开的收尾）。所以 *v.end() 是错的（未定义行为）。
4. "迭代器可以一直用"——要留意"失效"：vector 扩容/中间增删、deque 中间增删、几乎所有容器的 erase（除了被删的那个）都可能让迭代器作废。删元素时接住返回值最稳：it = v.erase(it);
5. "it++ 和 ++it 一样"——结果一样（都能前进），但 ++it 通常更快：it++ 需要"存一份旧值再前进、返回旧值"（多做一次拷贝和构造）。对 int 无所谓，对 list 的迭代器就有成本。 写习惯了以后一律用 ++it。
6. "set / map 的迭代器是随机的"——是双向（13.4.4）。所以 s.begin() + 3 编译不过，要移动得用 advance(it, 3)（O(n) 的代价）。
7. "迭代器能存下来下次再用"——存可以，但要清楚"什么操作会让它失效"。跨容器比较或使用另一个容器的迭代器是未定义行为（v1.begin() == v2.begin() 没有意义）。

• ☐ 下一节（13.4.1 输出迭代器）

相关笔记

• 输出迭代器（含实例09） —— 下一节：只能写的那一支
• 双向迭代器 —— list / set / map 的等级
• 随机访问迭代器 —— vector 的等级，也是 sort 的门槛
• 排序算法（含实例07） —— "sort 要求随机访问"的出处
• 链表类模板 —— list 为什么没有 []
• 指针 —— 指针：迭代器的原型
• 🔷 C++基础 · 索引 —— 全课路线图