流式的（单遍）              内存里的（多遍）
──────────────             ──────────────
输出（只写）  ←独立一支     前向（只 ++）
输入（只读） ─┐            双向（++ --）
             └───────────► 随机访问（+n -n [] <）

一、前向迭代器的"能力清单"

一句话：前向迭代器 = 输入迭代器 + 写能力 + 多遍。

"多遍"为什么这么重要：因为很多算法内部要"走两趟"： - remove 要先找到第一个要删的，再把后面的往前挪； - unique 要"比相邻的一对"（得同时持有两个位置）； - partition 要反复交换前后元素。

输入迭代器一个都做不了（走一遍就没了），前向迭代器就够用了（可以反反复复走）。

二、forward_list：最省的链表

先用一段代码看看它长什么样、和 list 差在哪：

#include <iostream>
#include <forward_list>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

int main() {
    // ── ① 基本操作 ────────────────────────
    forward_list<int> fl = {3, 1, 4, 1, 5};
    forward_list<int> fl2 = {9, 2};

    // 它只有 push_front / pop_front（没有 push_back！）
    fl.push_front(7);
    fl.pop_front();

    cout << "fl：";
    for (int x : fl) cout << x << " ";
    cout << endl;

    // ── ② 在"某位置之后"插入（注意：是"之后"）──
    forward_list<int>::iterator it = fl.begin();
    ++it;                                        // 走到第二个
    fl.insert_after(it, 99);                     // ★ 插在 it 之后
    cout << "insert_after 之后：";
    for (int x : fl) cout << x << " ";
    cout << endl;

    // ── ③ 删除"某位置之后"的那个 ────────────
    fl.erase_after(it);
    cout << "erase_after 之后： ";
    for (int x : fl) cout << x << " ";
    cout << endl;

    // ── ④ 它自带的"链表专属技能"（和 list 一样）──
    forward_list<int> f3 = {1, 2, 3, 2, 4, 2, 5};
    f3.remove(2);
    cout << "remove(2) 之后：  ";
    for (int x : f3) cout << x << " ";
    cout << endl;

    forward_list<int> f4 = {5, 2, 8, 1, 9, 3};
    f4.sort();
    cout << "sort() 之后：     ";
    for (int x : f4) cout << x << " ";
    cout << endl;

    // ── ⑤ 和 list 的关键差别：内存更省，但没有 -- 和双向遍历 ──
    cout << "-- forward_list vs list --" << endl;
    cout << "sizeof(forward_list<int>::iterator) 通常比 list 小（少一个前驱指针）" << endl;
    // cout << *(--fl.end());    // ❌ 编译不过：前向迭代器不能 --
    return 0;
}

看到什么算成功：

fl：3 1 4 1 5 
insert_after 之后：3 99 1 4 1 5 
erase_after 之后： 3 1 4 1 5 
remove(2) 之后：  1 3 4 5 
sort() 之后：     1 2 3 5 8 9 
-- forward_list vs list --
sizeof(forward_list<int>::iterator) 通常 < list（少一个"前驱"指针）

它和 list（13.1.3）的差别表：

forward_list 的两个"反直觉"设计值得单独说： 1. 没有 push_back、没有 size() —— 为了省那一个指针的空间，它愿意牺牲这些便利。这就是"极致省内存"的取舍（现实里它少用于一般业务，多用于内存紧张的场景）。 2. 插入删除都是 insert_after / erase_after —— 因为向前走容易、回头难，所以"给你一个位置，我只能在它后面动手"。这也解释了为什么 list 的 API 是 insert(it, x)（在 it 之前插入）而 forward_list 是 insert_after(it, x)。

三、unordered_set / unordered_map：哈希表的迭代器也是前向的

13.2.1 和 13.2.3 提过这两个名字（"只要快速去重/查找、不需要有序，用哈希表版更快"）。它们的迭代器等级就是前向的：

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <forward_list>
#include <list>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <algorithm>
using namespace std;

int main() {
    // ── ① unordered_set：去重，但"无序" ─────
    unordered_set<string> us = {"banana", "apple", "cherry", "apple"};
    cout << "unordered_set 里 " << us.size() << " 个（apple 重复被去掉）：";
    for (const string &s : us) cout << s << " ";
    cout << endl;
    cout << "（注意顺序：不是字母序，是哈希桶序 —— 和 set 比一眼就看出来）" << endl;

    // ── ② 和 set 对比 ─────────────────────
    set<string> s = {"banana", "apple", "cherry"};
    cout << "set 的顺序（有序）：";
    for (const string &x : s) cout << x << " ";
    cout << endl;

    // ── ③ unordered_map：计数（13.2.3 的写法照搬）──
    unordered_map<string, int> cnt;
    string text = "the quick brown fox the dog the cat";
    stringstream ss(text);
    string w;
    while (ss >> w) cnt[w]++;
    cout << "词频（unordered_map）：" << endl;
    for (const auto &p : cnt) cout << "  " << p.first << " -> " << p.second << endl;

    // ── ④ 它的迭代器只有"前向"：不能 -- ──────
    // auto it = us.end(); --it;               // ❌ 编译不过
    // sort(us.begin(), us.end());             // ❌ 编译不过（要随机访问，而且是只读的）
    cout << "（哈希表的迭代器是前向的：不能 --，也不能 sort）" << endl;

    // ── ⑤ 那它强在哪？—— 查找快 ────────────
    cout << "-- 查找 --" << endl;
    // set::find      → O(log n)（红黑树，一路比较下去）
    // unordered_set::find → 平均 O(1)（算哈希、直接跳过去）
    cout << "us.count(\"apple\") = " << us.count("apple") << endl;
    cout << "（有序 vs 快速：要按顺序遍历就选 set；只要快速判断在不在就选 unordered_set）" << endl;
    return 0;
}

看到什么算成功：

unordered_set 里 3 个（apple 重复被去掉）：cherry banana apple 
（注意顺序：不是字母序，是哈希桶序 —— 和 set 比一眼就看出来）
set 的顺序（有序）：apple banana cherry 
词频（unordered_map）：
  cat -> 1
  the -> 3
  dog -> 1
  brown -> 1
  quick -> 1
  fox -> 1
（哈希表的迭代器是前向的：不能 --，也不能 sort）
-- 查找 --
us.count("apple") = 1
（有序 vs 快速：要"按顺序遍历"选 set；只要"快速判断在不在"选 unordered_set）

"有序版"和"哈希版"的取舍：

"平均 O(1)"里的"平均"要留意：哈希冲突严重时（比如所有 key 都落进同一个桶）会退化成 O(n)。 现实里哈希函数一般都够好，所以"平均 O(1)"基本成立。但如果你要"性能绝对有保证"，set 的 O(log n) 反而是更稳的选择 —— 这也是"最坏情况"和"平均情况"的取舍。

四、动手 Demo：什么时候"前向"就够、什么时候必须"双向"

任务：用 forward_list 和 list 各做一遍"遍历 + 处理"，找出前向迭代器的边界。

#include <iostream>
#include <forward_list>
#include <list>
#include <algorithm>
#include <numeric>
#include <iterator>
using namespace std;

template <typename C>
void show(const char *t, const C &c) {
    cout << t << "：";
    for (int x : c) cout << x << " ";
    cout << endl;
}

int main() {
    forward_list<int> fl = {3, 1, 4, 1, 5, 9, 2, 6};

    // ── ① 前向能做：遍历、累加、找、按条件删 ──
    show("原始          ", fl);
    cout << "① 累加（accumulate）：" << accumulate(fl.begin(), fl.end(), 0) << endl;

    forward_list<int> f2 = fl;
    f2.remove_if([](int x) { return x > 4; });          // ✅ 成员函数（真删）
    show("① 删掉 >4 之后", f2);

    // 算法版也能用（只要"能 ++"）
    forward_list<int> f3 = fl;
    cout << "① count(1) = " << count(f3.begin(), f3.end(), 1) << "（算法也能用）" << endl;

    // ── ② 前向不能做：reverse（要 --）、sort（要 +n）、size（没有）──
    // reverse(fl.begin(), fl.end());   // ❌ 要 --（双向）
    // sort(fl.begin(), fl.end());      // ❌ 要随机访问
    // cout << fl.size();               // ❌ 没有 size()
    cout << "② 不能用 reverse/sort，也没有 size()（要自己 distance）" << endl;
    cout << "   自己数一遍：" << distance(fl.begin(), fl.end()) << " 个" << endl;

    // ── ③ 想"倒着看"？先复制到 vector ─────────
    vector<int> v(fl.begin(), fl.end());
    reverse(v.begin(), v.end());
    show("③ 倒过来（借 vector）", v);

    // ── ④ 双向的 list 就能直接 reverse ────────
    list<int> l = {3, 1, 4, 1, 5};
    reverse(l.begin(), l.end());
    show("④ list 直接 reverse", l);

    cout << "-- 结论 --" << endl;
    cout << "前向迭代器：能遍历、能读写、能多遍 —— 足够对付只看一遍/顺着一遍的算法" << endl;
    cout << "要倒着走或跳着走，就得升级到双向 / 随机访问" << endl;
    return 0;
}

看到什么算成功：

原始          ：3 1 4 1 5 9 2 6 
① 累加（accumulate）：31
① 删掉 >4 之后：3 1 4 1 2 
① count(1) = 2（算法也能用）
② 不能用 reverse/sort，也没有 size()（要自己 distance）
   自己数一遍：8 个
③ 倒过来（借 vector）：6 2 9 5 1 4 1 3 
④ list 直接 reverse：5 1 4 1 3 
-- 结论 --
前向迭代器：能遍历、能读写、能多遍 —— 足够对付"只看一遍/顺着一遍"的算法
要"倒着走"或"跳着走"，就得升级到双向 / 随机访问

这个 Demo 里有个实用技巧："先把数据从弱迭代器的容器复制到 vector，再用强大的算法" —— vector<int> v(fl.begin(), fl.end());（用区间构造一次搞定）。这是"容器能力不够时的标准变通手段"（13.1.1 区间构造的用法）。 但也要想清楚代价：复制一份数据要花时间和内存。如果这是热点代码，就得重新考虑"是不是一开始就该用 vector"。

30 秒实验

1. 验证"没有 size()"：fl.size() → 编译不过。用 distance(fl.begin(), fl.end())（O(n)）。
2. 验证"不能 --"：auto it = fl.end(); --it; → 编译不过。
3. insert_after vs insert：fl.insert_after(fl.begin(), 99); 插在第一个元素之后；l.insert(l.begin(), 99); 插在第一个元素之前。这两个 API 的差别背后就是"能不能回头"。
4. unordered_set 的顺序：插 1..10 再遍历一次 → 基本不会是 1 2 3 ...（哈希桶序）。和 set 一起跑一下，差别一眼可见。

常见误区

1. "前向迭代器就是输入迭代器"——多两项能力：能写（*it = x）和能多遍。输入迭代器是"流式"的（读一遍就没了）。
2. "前向迭代器能 --"——不能。要 -- 得用双向迭代器（13.4.4）。
3. " forward_list 和 list 用法差不多"——差得多：forward_list 没有 push_back / pop_back / size()，插入删除是 insert_after / erase_after（在位置之后）。 它的目的是极致省内存。
4. "forward_list 适合替换 vector 来省内存"——要看需求：它就是"单链表"，只在"频繁在已知位置插入删除 + 内存紧张"时才合适；一般业务里 vector 几乎总是更好的默认选择（13.1.1）。
5. "unordered_map 比 map 全面更好"——不是：它无序、迭代器只有前向、不能做范围查询（没有 lower_bound）。要"按顺序遍历"或"查一段区间"，还得用 map。
6. "哈希表是 O(1)，所以一定快"——平均 O(1)，最坏 O(n)。特别在意最坏情况时，set / map 的 O(log n) 更可预测。
7. "unordered_* 的迭代器顺序稳定"——不稳定：重新哈希（插入变多）会改变元素的相对顺序。别写依赖顺序的代码。

• ☐ 下一节（13.4.4 双向迭代器）

相关笔记

• 输入迭代器 —— 上一节：只能读一遍
• 双向迭代器 —— 下一节：list / set / map 的等级
• 链表类模板 —— 双向链表 list
• 关联式容器 —— set / map 与哈希版的分工
• 迭代器 —— 五个等级的总览
• 🔷 C++基础 · 索引 —— 全课路线图