输入（只读一遍）
  └─► 前向（+ 能写 + 能多遍）
        └─► 双向（+ 能 --）              ← 本节
              └─► 随机访问（+ 能 +n -n [] <）   ← 13.4.5

一、只多了 --，但解锁了一批算法

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

int main() {
    list<int> l = {1, 2, 3, 4, 5};

    // ── ① `--` 能往回走 ────────────────────
    list<int>::iterator it = l.end();
    --it;                                    // ★ 最后一个元素
    cout << "最后一个元素：" << *it << endl;
    --it;
    cout << "倒数第二个：  " << *it << endl;

    // ── ② 靠 -- 才能做的"倒着遍历" ──────────
    cout << "倒着遍历（list）：";
    for (list<int>::iterator i = l.end(); i != l.begin(); ) {
        --i;                                 // ★ 先退，再取值
        cout << *i << " ";
    }
    cout << endl;

    // ── ③ reverse 算法：要双向迭代器 ────────
    reverse(l.begin(), l.end());
    cout << "reverse 之后：      ";
    for (int x : l) cout << x << " ";
    cout << endl;

    // ── ④ 反向迭代器 rbegin / rend（13.2.1 见过）──
    cout << "rbegin 倒序遍历：   ";
    for (list<int>::reverse_iterator ri = l.rbegin(); ri != l.rend(); ++ri)
        cout << *ri << " ";
    cout << endl;

    // ── ⑤ set / map 也是双向 ────────────────
    set<int> s = {5, 1, 9, 3};
    cout << "set 倒序（最大的在前）：";
    for (set<int>::reverse_iterator ri = s.rbegin(); ri != s.rend(); ++ri)
        cout << *ri << " ";
    cout << endl;

    map<string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}};
    cout << "map 最后一个（键最大）：" << (--m.end())->first << endl;

    // ── ⑥ 但它依然不能做的事情 ──────────────
    // l.begin() + 2;               // ❌ 不能 +n
    // l[2];                        // ❌ 没有 []
    // l.begin() < l.end();         // ❌ 不能比大小
    // sort(l.begin(), l.end());    // ❌ sort 要随机访问
    cout << "（不能 +n、不能 []、不能比大小、不能用 sort）" << endl;
    return 0;
}

看到什么算成功：

最后一个元素：5
倒数第二个：  4
倒着遍历（list）：5 4 3 2 1 
reverse 之后：      5 4 3 2 1 
rbegin 倒序遍历：   5 4 3 2 1 
set 倒序（最大的在前）：9 5 3 1 
map 最后一个（键最大）：c
（不能 +n、不能 []、不能比大小、不能用 sort）

双向迭代器能用的算法清单（和 13.4.3 比）：

reverse 对 list 还有一个"更省事"的选择：l.reverse()（成员函数，13.1.3） —— 成员版更懂自己的结构（改指针而不是搬值），通常更快。"算法版能编过"不等于"该用它"。

二、为什么 set / map / list 都停在"双向"

这是个"结构决定能力"的问题：

对比 vector / deque：它们的内存是"连续 / 分段连续"，所以"begin() + 3 这个位置算得出来（首地址 + 3×元素大小）" —— 这就是"随机访问"的物理基础。

一句话："能不能随机访问"取决于"能不能用一次算术算出第 n 个元素的地址"。 - 连续内存 → 能 → 随机访问迭代器（13.4.5）； - 链表 / 树 → 不能（必须走 n 步）→ 只能双向。

所以"sort 用不了 list"不是"标准不想给"，而是"物理上做不到" —— sort 的算法（快排/堆排）需要"随机跳转"来选主元、交换元素。

三、prev / next / advance / distance：专门伺候迭代器的四个小工具

因为它们不能 +n，标准给了几个"用走的"的替代品（都在 <iterator> 里）：

#include <iostream>
#include <list>
#include <set>
#include <vector>
#include <iterator>              // ★ 四个工具都在这
using namespace std;

int main() {
    list<int> l = {10, 20, 30, 40, 50};

    // ── ① next：往前走 n 步（不改原迭代器）──
    list<int>::iterator it = l.begin();
    list<int>::iterator third = next(it, 2);        // 从 begin 走 2 步
    cout << "next(begin, 2) = " << *third << endl;

    // ── ② prev：往后走 n 步 ────────────────
    list<int>::iterator last = prev(l.end(), 1);    // end 往前 1 步 = 最后一个
    cout << "prev(end, 1)   = " << *last << endl;
    cout << "prev(end, 3)   = " << *prev(l.end(), 3) << endl;

    // ── ③ advance：原地前进（会改 it）──────
    it = l.begin();
    advance(it, 3);
    cout << "begin 走 3 步   = " << *it << endl;

    advance(it, -1);                                // ★ 双向才能负数！
    cout << "再退 1 步       = " << *it << endl;

    // ── ④ distance：两个迭代器之间有多远 ────
    cout << "begin 到 end 共 " << distance(l.begin(), l.end()) << " 个元素" << endl;
    cout << "begin 到第三个  " << distance(l.begin(), next(l.begin(), 2)) << " 步" << endl;

    // ── ⑤ 对随机访问迭代器，"走"和"算"的差别体现在效率 ──
    vector<int> v = {10, 20, 30, 40, 50};
    cout << "-- 效率差别（list 上是 O(n)，vector 上是 O(1)）--" << endl;
    cout << "v.begin() + 2    = " << *(v.begin() + 2) << "（一次加法）" << endl;
    cout << "next(v.begin(),2)= " << *next(v.begin(), 2) << "（vector 上也是 O(1)，但写法更通用）" << endl;

    // ── ⑥ 实用：想"倒着找最后一个满足条件的"──
    set<int> s = {1, 3, 5, 7, 9, 11};
    set<int>::iterator p = s.end();
    while (p != s.begin()) {
        --p;                                        // ★ 只能一步步退
        if (*p % 3 == 1) { cout << "从后往前第一个 mod 3 == 1 的：" << *p << endl; break; }
    }
    return 0;
}

看到什么算成功：

next(begin, 2) = 30
prev(end, 1)   = 50
prev(end, 3)   = 30
begin 走 3 步   = 40
再退 1 步       = 30
begin 到 end 共 5 个元素
begin 到第三个  2 步
-- 效率差别（list 上是 O(n)，vector 上是 O(1)）--
v.begin() + 2    = 30（一次加法）
next(v.begin(),2)= 30（vector 上也是 O(1)，但写法更通用）
从后往前第一个 mod 3 == 1 的：7

四个工具的分工：

为什么要有这四个：因为不是所有迭代器都支持 +。 直接写 it + 3 在 list 上编译不过；写 next(it, 3) 则"处处都能编过"（代价是 list 上是 O(n) 的走）。 所以有个写法上的建议：要写"通用代码"（不关心容器是什么）时，用 next / advance；已经确定是 vector 时，用 it + n（更直观、更快）。 advance(it, -1) 这种负数是双向迭代器的专属能力（前向迭代器只能正数）。

四、动手 Demo：链式结构上的"倒着操作"

任务：一个"紧急任务清单"（list），要求支持"插到最急的位置""从后往前找第一个可延期的"。

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

struct Task {
    string name;
    int    priority;      // 越大越急
    Task(const string &n, int p) : name(n), priority(p) {}
};

void show(const char *t, const list<Task> &l) {
    cout << t << "：";
    for (const Task &x : l) cout << x.name << "(" << x.priority << ") ";
    cout << endl;
}

int main() {
    list<Task> q = {
        Task("写日报", 2), Task("修线上故障", 5), Task("整理文档", 1), Task("回邮件", 3)
    };
    show("原始      ", q);

    // ── ① 用 reverse 看一眼"从后往前"的顺序 ──
    list<Task> r = q;
    r.reverse();                              // ★ 成员版（比算法版更懂 list）
    show("倒过来看  ", r);

    // ── ② 从后往前找第一个"优先级 <= 2"的 ────
    //    （因为要"从后往前"，必须用双向的 --）
    for (list<Task>::reverse_iterator ri = q.rbegin(); ri != q.rend(); ++ri) {
        if (ri->priority <= 2) {
            cout << "② 优先级 <= 2 的最后一个：" << ri->name
                 << "(" << ri->priority << ")" << endl;
            break;
        }
    }

    // ── ③ 用 prev 取"最后一个元素"（比 rbegin 更明确）──
    cout << "③ 队列最后一个（最不急的）：" << prev(q.end())->name << endl;

    // ── ④ 按优先级降序排（list 的成员 sort 配合 reverse）──
    q.sort([](const Task &a, const Task &b) { return a.priority < b.priority; });
    q.reverse();                              // 想从大到小：先升序再反转
    show("④ 按优先级降序", q);

    // ── ⑤ 在"最急的"前面插一个更急的 ────────
    q.insert(q.begin(), Task("总裁来电", 9));
    show("⑤ 插入总裁来电", q);

    // ── ⑥ 从头尾各删一个 ────────────────────
    q.pop_front();
    q.pop_back();
    show("⑥ 头尾各删一个", q);
    return 0;
}

看到什么算成功：

原始      ：写日报(2) 修线上故障(5) 整理文档(1) 回邮件(3) 
倒过来看  ：回邮件(3) 整理文档(1) 修线上故障(5) 写日报(2) 
② 优先级 <= 2 的最后一个：写日报(2)
③ 队列最后一个（最不急的）：回邮件
④ 按优先级降序：修线上故障(5) 回邮件(3) 写日报(2) 整理文档(1) 
⑤ 插入总裁来电：总裁来电(9) 修线上故障(5) 回邮件(3) 写日报(2) 整理文档(1) 
⑥ 头尾各删一个：修线上故障(5) 回邮件(3) 写日报(2) 

几个用法要点：

"先升序再 reverse"这个技巧值得记：成员 sort 的比较器语义永远"谁排前面"，写成 > 也行，但有些老编译器对 list::sort 的降序支持不好；用"升序 + reverse"最保险。 std::sort 那边可以直接用 greater<T>() 或 > 的比较器。

30 秒实验

1. -- 的边界：list<int> l; list<int>::iterator it = l.begin(); --it; → 未定义行为（空容器不能 --）。prev(l.begin()) 也是错的。
2. set 的倒序遍历：for (auto ri = s.rbegin(); ri != s.rend(); ++ri) → 从最大到最小。这是 set 唯一"顺手"的降序方式。
3. 验证 +n 不能用：l.begin() + 2 → no match for 'operator+'；换成 next(l.begin(), 2) → 能编过。
4. advance 的负数：在 list 上 advance(it, -2) 可以；在 forward_list 上用负数 → 编译不过（前向迭代器只能正数）。

常见误区

1. "list 既然能 --，那也能 +n 吧"——不能。-- 是"顺着链子退一步"，+n 需要"一次算出第 n 个"，链表做不到。 要用 next / advance（代价 O(n)）。
2. "set 能 sort"——不能（只有双向迭代器）。而且它本来就排好序了。
3. "reverse(l.begin(), l.end()) 比 l.reverse() 好"——成员版通常更快（list 只需改指针方向，算法版要一个个交换值）。
4. "rbegin() 和 end() - 1 一样"——意思一样，但写法不一样：end() - 1 在 list 上编译不过（不能减），rbegin() 处处可用。要"最后一个元素"，通用写法是 prev(v.end()) 或 *v.rbegin()。
5. "advance(it, n) 返回新迭代器"——它原地改 it，返回 void。想拿新的（不动老的）用 next / prev。
6. "distance 是 O(1) 的"——只在随机访问迭代器上是 O(1)（直接减）；在 list / set 上是 O(n)（要走一遍数）。所以在 list 上反复调 distance 会很慢。
7. "双向迭代器就是"次一等"的随机访问"——方向不同：它多了"能回头"，但少了"能跳"。 要"跳"就得上随机访问（13.4.5），而那是"改容器"才能得到的能力。

• ☐ 下一节（13.4.5 随机访问迭代器）

相关笔记

• 前向迭代器 —— 上一节：只能往前走
• 随机访问迭代器 —— 下一节：能跳着走的那一级
• 链表类模板 —— list 的 insert 是"在位置之前"
• set类模板（含实例02） —— rbegin 取最大值
• 排序算法（含实例07） —— 为什么 set 用不了 sort
• 迭代器 —— 五个等级的总览
• 🔷 C++基础 · 索引 —— 全课路线图