一、它比双向多了"五种跳法"

#include <iostream>
#include <vector>
#include <deque>
#include <string>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40, 50, 60};

    // ── ① +n / -n：跳 ──────────────────────
    cout << "*(v.begin() + 3) = " << *(v.begin() + 3) << endl;      // 40
    cout << "*(v.end() - 1)   = " << *(v.end() - 1) << endl;        // 60

    // ── ② []：下标（这就是 13.1.1 的 v[i] 背后做的事）──
    vector<int>::iterator it = v.begin();
    cout << "it[2]            = " << it[2] << "（等价于 *(it + 2)）" << endl;

    // ── ③ 两个迭代器相减：算距离 + 得下标 ────
    vector<int>::iterator a = v.begin() + 1;
    vector<int>::iterator b = v.begin() + 5;
    cout << "b - a            = " << (b - a) << "（差 4 步）" << endl;
    cout << "a 的下标         = " << (a - v.begin()) << " ← 13.3.1 用过这招" << endl;

    // ── ④ 比大小：谁在前 ────────────────────
    cout << "(a < b)          = " << (a < b ? "true（a 在前）" : "false") << endl;

    // ── ⑤ 自增自减的"步长"写法 ──────────────
    it = v.begin();
    it += 2;                              // ★ += 只在随机访问上有
    cout << "it += 2 之后      = " << *it << endl;
    it -= 1;
    cout << "it -= 1 之后      = " << *it << endl;

    // ── ⑥ deque、string、裸数组也都是随机访问 ──
    deque<int> d = {1, 2, 3};
    cout << "deque: *(d.begin()+1) = " << *(d.begin() + 1) << endl;

    string s = "hello";
    cout << "string: s.begin()+1 指向 '" << *(s.begin() + 1) << "'" << endl;

    int arr[] = {7, 8, 9};
    cout << "裸数组: *(arr + 1)    = " << *(arr + 1) << "（指针本身就是随机访问迭代器）" << endl;
    return 0;
}

看到什么算成功：

*(v.begin() + 3) = 40
*(v.end() - 1)   = 60
it[2]            = 30（等价于 *(it + 2)）
b - a            = 4（差 4 步）
a 的下标         = 1 ← 13.3.1 用过这招
(a < b)          = true（a 在前）
it += 2 之后      = 30
it -= 1 之后      = 20
deque: *(d.begin()+1) = 2
string: s.begin()+1 指向 'e'
裸数组: *(arr + 1)    = 8（指针本身就是随机访问迭代器）

五种"跳法"总结（这就是它比双向多的全部）：

it2 - it1 算出来的不是"字节差"，是"元素个数差" —— vector 的迭代器里就存着"当前元素的下标"，所以相减就是下标差（O(1)）。 deque 也算随机访问：虽然它是"分段连续"，但"下标 → (哪一块, 块内偏移)"这两步计算仍是常数时间 —— 所以它同时具有"两端 O(1) 插入"和"随机访问"。 string 和裸数组当然也是 —— 数组的迭代器"就是"指针（13.4 导言讲过）。

二、只有它才能用的算法

这是"等级"最实际的影响：

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

int main() {
    // ── ① sort：要随机访问 ────────────────
    vector<int> v = {5, 2, 8, 1, 9};
    sort(v.begin(), v.end());
    cout << "sort(vector)  OK：";
    for (int x : v) cout << x << " ";
    cout << endl;

    deque<int> d = {5, 2, 8, 1, 9};
    sort(d.begin(), d.end());               // ★ deque 也可以！
    cout << "sort(deque)   OK：";
    for (int x : d) cout << x << " ";
    cout << endl;

    int arr[] = {5, 2, 8, 1, 9};
    sort(arr, arr + 5);                     // ★ 裸数组也可以
    cout << "sort(裸数组)  OK：";
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << endl;

    // list<int> l = {5, 2, 8, 1, 9};
    // sort(l.begin(), l.end());            // ❌ 编译不过（双向迭代器）
    cout << "sort(list)    ❌ 编译不过 —— 要用成员 l.sort()" << endl;

    // ── ② binary_search / nth_element / random_shuffle：同样要随机访问 ──
    vector<int> s = {1, 3, 5, 7, 9, 11};
    cout << "binary_search OK：" << (binary_search(s.begin(), s.end(), 7) ? "有" : "没有") << endl;

    vector<int> n = {9, 1, 8, 2, 7, 3};
    nth_element(n.begin(), n.begin() + 2, n.end());
    cout << "nth_element 后第 3 小的：" << n[2] << endl;

    vector<int> r = {1, 2, 3, 4, 5};
    random_shuffle(r.begin(), r.end());   // （C++17 起已移除；新写法见 13.3.2 的 shuffle）
    cout << "random_shuffle OK：";
    for (int x : r) cout << x << " ";
    cout << endl;

    cout << "-- 需要随机访问的算法清单（记这些就够）--" << endl;
    cout << "  sort / stable_sort / partial_sort / nth_element" << endl;
    cout << "  binary_search / lower_bound / upper_bound（算法版）" << endl;
    cout << "  random_shuffle / shuffle / reverse（其实 reverse 只要双向）" << endl;
    return 0;
}

看到什么算成功（打乱顺序每次不同）：

sort(vector)  OK：1 2 5 8 9 
sort(deque)   OK：1 2 5 8 9 
sort(裸数组)  OK：1 2 5 8 9 
sort(list)    ❌ 编译不过 —— 要用成员 l.sort()
binary_search OK：有
nth_element 后第 3 小的：3
random_shuffle OK：3 5 1 2 4 
-- 需要随机访问的算法清单（记这些就够）--
  sort / stable_sort / partial_sort / nth_element
  binary_search / lower_bound / upper_bound（算法版）
  random_shuffle / shuffle / reverse（其实 reverse 只要双向）

"要求随机访问"的算法清单（记这一张表，就不用背五级阶梯了）：

注意最后一行：最常用的"查找、计数、遍历、替换、删除"只需要最弱的迭代器 —— 所以那些算法在哪都能用。 "要求随机访问"的其实只有"排序 / 二分 / 乱序"这几家族。

三、动手 Demo：用"等级测试"来选容器

任务：写一个小程序，帮你在"不确定该用哪个容器"时做判断。

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

// 用"模板 + 重载"来在编译期区分迭代器等级（这里用最朴素的办法：看能不能编译）
// 实际工程里用 iterator_traits / C++20 的 concepts；这里只为说明问题

void showTable() {
    cout << "容器          迭代器等级      sort?  []?   +n?   --?" << endl;
    cout << "vector        随机访问        有     有    有    有" << endl;
    cout << "deque         随机访问        有     有    有    有" << endl;
    cout << "string        随机访问        有     有    有    有" << endl;
    cout << "裸数组指针    随机访问        有     有    有    有" << endl;
    cout << "list          双向            无     无    无    有" << endl;
    cout << "forward_list  前向            无     无    无    无" << endl;
    cout << "set / map     双向（只读）    无     无    无    有" << endl;
    cout << "unordered_*   前向（只读）    无     无    无    无" << endl;
}

int main() {
    cout << "-- 你的需求是什么？ --" << endl;
    cout << "① 要按下标随机取        → vector / deque" << endl;
    cout << "② 要排序 / 二分查找     → vector / deque（必须随机访问）" << endl;
    cout << "③ 要频繁在中间插删      → list" << endl;
    cout << "④ 要两头都进出          → deque" << endl;
    cout << "⑤ 要按值快速查找+有序   → set / map" << endl;
    cout << "⑥ 要按值快速查找+无序   → unordered_set / unordered_map" << endl;
    cout << endl;

    showTable();
    cout << endl;

    // ── 实测：同一个需求在两套容器上的代价 ──
    vector<int> v = {5, 3, 8, 1, 9, 2, 7, 4, 6};
    list<int>   l = {5, 3, 8, 1, 9, 2, 7, 4, 6};

    // 「找出第 3 个元素」
    cout << "-- 同一个需求「取第 3 个」。--" << endl;
    cout << "vector：v[2] = " << v[2] << "        （一次加法，O(1)）" << endl;
    list<int>::iterator it = l.begin();
    advance(it, 2);
    cout << "list  ：next 之后 = " << *it << "  （走了 2 步，O(n)）" << endl;

    // 「排序」
    cout << "-- 同一个需求「排序」。--" << endl;
    sort(v.begin(), v.end());
    cout << "vector：sort 直接用，OK" << endl;
    l.sort();
    cout << "list  ：只能用成员 l.sort()（内部是归并排序，只需要往前挪）" << endl;

    // 「按值找」
    cout << "-- 同一个需求「找 9」。--" << endl;
    cout << "vector：find 从头扫，O(n)" << endl;
    set<int> s = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    cout << "set   ：s.find(9) 走树，O(log n)" << endl;
    return 0;
}

看到什么算成功：

-- 你的需求是什么？ --
① 要按下标随机取        → vector / deque
② 要排序 / 二分查找     → vector / deque（必须随机访问）
③ 要频繁在中间插删      → list
④ 要两头都进出          → deque
⑤ 要按值快速查找+有序   → set / map
⑥ 要按值快速查找+无序   → unordered_set / unordered_map

容器          迭代器等级      sort?  []?   +n?   --?
vector        随机访问        有     有    有    有
...
-- 同一个需求「取第 3 个」。--
vector：v[2] = 8        （一次加法，O(1)）
list  ：next 之后 = 8  （走了 2 步，O(n)）
-- 同一个需求「排序」。--
vector：sort 直接用，OK
list  ：只能用成员 l.sort()（内部是归并，只往前挪）
-- 同一个需求「找 9」。--
vector：find 从头扫，O(n)
set   ：s.find(9) 走树，O(log n)

这个 Demo 想说的是最后一件事："选容器"和"选算法"不是两件独立的事 ——你选了 list，就等于放弃了 sort、[]、binary_search；你选了 vector，就等于接受了"中间插删要搬家"。 标准做法是"先按需求选容器，再按容器的能力选算法" —— 反过来（先想用什么算法、再硬套到不合适的容器上）几乎一定要走弯路。

四、一张总表收尾

把 13.1~13.4 全部装进一张表：

这张表值得抄一遍（或者记住"它的迭代器是哪一级"）——因为"等级"决定了它能用哪些算法，而"结构"决定了各操作的复杂度。 这两条加起来，就是"选容器"的全部依据。

30 秒实验

1. deque 的 sort：sort(d.begin(), d.end()) → 能编过（证明它也是随机访问）。
2. it1 - it2 在 list 上：写 l.begin() - l.end() → 编译不过；换成 distance(l.begin(), l.end()) → 能编过（O(n)）。
3. += 只在随机访问上有：list<int>::iterator it; it += 1; → 编译不过。
4. binary_search 用在 list 上：binary_search(l.begin(), l.end(), 5); → 编译不过（虽然 list 也可以有序，但二分要"跳到中间"，它做不到）。这一条最能说明"能编过"和"能不能用"是两回事。

常见误区

1. "所有容器都能 sort"——只有随机访问的能：vector / deque / 数组。list / set / map / forward_list 都不行（list 用成员 l.sort()；set / map 本来就排好了；forward_list 用成员）。更不能对 unordered_* 用 sort。
2. "deque 不是连续内存，所以不能 sort"——能。"随机访问"不要求"整块连续"，只要求"能 O(1) 算到第 n 个"——deque 用"块目录 + 块内偏移"照样是常数时间。
3. "it1 - it2 得到字节数"——得到的是"元素个数差"。
4. "能 ++ 就能 --"——不能。forward_list / unordered_* / istream_iterator 都只能 ++。
5. "比大小（<）很自然"——只有随机访问支持。双向迭代器只能 == / !=（因为它们"谁在前谁在后"没有 O(1) 的判法）。
6. "复杂度表里的 O(1) 都一样快"——常数因子不同：vector[i] 是一次内存访问；deque[i] 要多算一次"块索引"；unordered_* 要算哈希。大数据量时这些差别会显出来。
7. "选容器只看复杂度就够了"——还要看"缓存友好度"：vector 遍历时数据挨在一起，CPU 缓存命中率高；list / set 到处跳，缓存不友好。 这就是为什么"理论上都是 O(n) 的遍历，vector 往往快好几倍"。

• ☐ 下一节（13.5 小结）

相关笔记

• 双向迭代器 —— 上一节：能回头但不能跳
• 小结 —— 下一节：整章收束
• 迭代器 —— 五个等级的总览
• 排序算法（含实例07） —— sort 为什么要求随机访问
• 双端队列类模板 —— deque 为什么也能 sort
• 向量类模板（含实例01） —— v[i] 背后的机制
• 🔷 C++基础 · 索引 —— 全课路线图