一、链表长什么样：节点 + 指针

list:  ┌───┬───┬───┐    ┌───┬───┬───┐    ┌───┬───┬───┐
       │前 │ 1 │后 ├───►│前 │ 2 │后 ├───►│前 │ 3 │后 │
    ◄──┤针 │   │针 │◄───┤针 │   │针 │◄───┤针 │   │针 │
       └───┴───┴───┘    └───┴───┴───┘    └───┴───┴───┘
        在内存里可能分散在天南地北（每个节点单独 new 出来）

和 vector 一比，一切就清楚了：

记住这张表的一句话总结：没有哪个容器全面更好，只有"哪个操作你用得最多"。

二、list 的基本操作

这一节要特别留神一件事：list 的一切"定位"都得靠迭代器一步步走——因为它没有 []，也不能 begin() + n。

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

void show(const char *title, const list<string> &l) {
    cout << title << " [size=" << l.size() << "]：";
    for (const string &s : l) cout << s << " ";      // ★ 用范围 for 最省事
    cout << endl;
}

int main() {
    list<string> l;
    l.push_back("B");
    l.push_back("C");
    l.push_front("A");
    show("两头加之后", l);

    // ── 中间插入：先"走到位置"，再插入 ────
    list<string>::iterator it = l.begin();
    ++it;                                    // 走到 B 的位置（★ 不能写 l.begin() + 1）
    l.insert(it, "X");                       // 在 B 之前插入 X
    show("insert 后", l);

    // ── 删除：同样靠迭代器 ────────────────
    it = l.begin();
    ++it;                                    // 现在指向 X
    it = l.erase(it);                        // ★ 返回值是"删除后的下一个位置"，直接接住
    show("erase 后", l);

    // ── 两头删 ──────────────────────────
    l.pop_front();
    l.pop_back();
    show("两头各删一个后", l);

    // ── 首尾与判空 ──────────────────────
    cout << "front()=" << l.front() << "  back()=" << l.back()
         << "  empty()=" << (l.empty() ? "空" : "非空") << endl;

    // ── 清空 ────────────────────────────
    l.clear();
    cout << "clear 后 size=" << l.size() << endl;
    return 0;
}

看到什么算成功：

两头加之后 [size=3]：A B C 
insert 后 [size=4]：A X B C 
erase 后 [size=3]：A B C 
两头各删一个后 [size=1]：B 
front()=B  back()=B  empty()=非空
clear 后 size=0

三个和 vector 不同的地方：

最后一行是 list 的隐藏福利：插入不会让任何迭代器失效，删除只失效被删的那个。 而 vector 一插一删可能让"全部迭代器"作废。这也是为什么"边遍历边删除"在 list 里写起来比 vector 舒服。

三、list 的专属技能：别的容器没有

因为"改两个指针就能挪节点"，list 能做几件 vector 做不到的事：

#include <iostream>
#include <list>
using namespace std;

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

int main() {
    // ── ① remove：按值删掉所有匹配的元素 ──
    list<int> l = {1, 2, 3, 2, 4, 2, 5};
    show("原始       ", l);
    l.remove(2);                        // ★ 删掉所有 2（vector 没有这个方法）
    show("remove(2)  ", l);

    // ── ② remove_if：按条件删 ────────────
    l.remove_if([](int x) { return x % 2 == 1; });   // 删掉所有奇数
    show("删掉奇数后 ", l);

    // ── ③ unique：去掉"相邻"的重复 ───────
    list<int> u = {1, 1, 2, 2, 2, 3, 1, 1};
    show("unique 前  ", u);
    u.unique();                          // ★ 只合并"挨在一起"的重复
    show("unique 后  ", u);

    // ── ④ sort：链表自己的排序 ───────────
    list<int> s = {5, 2, 8, 1, 9, 3};
    show("sort 前    ", s);
    s.sort();                            // ★ 必须用成员函数，不能用 std::sort
    show("sort 后    ", s);
    s.sort(greater<int>());              // 从大到小
    show("倒序 sort  ", s);

    // ── ⑤ reverse：整个反转 ──────────────
    s.reverse();
    show("reverse 后 ", s);

    // ── ⑥ merge：两个有序链表合并（不复制！）──
    list<int> a = {1, 3, 5};
    list<int> b = {2, 4, 6};
    a.merge(b);                          // ★ a 变有序合并结果，b 被清空
    show("merge 后 a ", a);
    show("merge 后 b ", b);

    // ── ⑦ splice：把别人家的节点"整段摘过来"──
    list<int> src = {100, 200, 300};
    list<int> dst = {1, 2, 3};
    list<int>::iterator pos = dst.begin();
    ++pos;                               // 插到第 2 个位置
    dst.splice(pos, src);                // ★ src 的节点被"摘"到 dst，不复制、不 new
    show("splice 后 dst", dst);
    show("splice 后 src", src);
    return 0;
}

看到什么算成功：

原始       ：1 2 3 2 4 2 5 
remove(2)  ：1 3 4 5 
删掉奇数后 ：4 
unique 前  ：1 1 2 2 2 3 1 1 
unique 后  ：1 2 3 1 
sort 前    ：5 2 8 1 9 3 
sort 后    ：1 2 3 5 8 9 
倒序 sort  ：9 8 5 3 2 1 
reverse 后 ：1 2 3 5 8 9 
merge 后 a ：1 2 3 4 5 6 
merge 后 b ：
splice 后 dst：1 100 200 300 2 3 
splice 后 src：

四个点必须看懂：

1. remove(2) 一次删掉所有 2 —— 而 <algorithm> 里的 remove 只是把元素"挪到后面"不是真删（13.3.2 详讲）。名字一样、行为不同，是 STL 里的一处坑。
2. unique() 只合并"相邻"的重复 —— 1 1 2 2 2 3 1 1 变成 1 2 3 1（最后那两个 1 没合并，因为不挨着）。想全局去重：先 sort() 再 unique()。（这也是 std::unique 的规矩。）
3. splice 是"摘节点"不是"复制节点" —— 输出里 src 直接空了，dst 里的 100 200 300 就是原来那几个节点（连地址都没变）。这是 O(1) 的整段搬家——vector 里想干这个只能整体复制 + 删除。这是链表最独有的能力。
4. l.sort() 而不是 std::sort(l.begin(), l.end()) —— 后者根本编译不过（要随机访问迭代器）。原因见 13.4.5。

四、动手 Demo：list 版"任务调度队列"

任务：维护一个任务列表，支持"插急件到最前"、"干完一个删一个"、"取消某类任务"。

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

struct Task {
    string name;
    int    level;        // 1=急件, 2=普通, 3=低优先级

    Task(const string &n, int lv) : name(n), level(lv) {}
};

void show(const list<Task> &ts) {
    cout << "任务队列（" << ts.size() << " 项）：";
    for (const Task &t : ts) cout << "[" << t.level << "]" << t.name << "  ";
    cout << endl;
}

int main() {
    list<Task> q;
    q.push_back(Task("回邮件", 2));
    q.push_back(Task("写文档", 2));
    q.push_back(Task("整理桌面", 3));

    // ① 急件插到最前（list 的 push_front）
    q.push_front(Task("修线上故障", 1));
    show(q);

    // ② 干完一个：删掉队头
    cout << "处理：" << q.front().name << endl;
    q.pop_front();
    show(q);

    // ③ 取消所有低优先级任务（用 remove_if + 条件）
    q.remove_if([](const Task &t) { return t.level == 3; });
    show(q);

    // ④ 在"写文档"前面插一个（要靠迭代器走位）
    for (list<Task>::iterator it = q.begin(); it != q.end(); ++it) {
        if (it->name == "写文档") {                 // ★ it-> 就是 (*it). 
            q.insert(it, Task("先开会", 1));
            break;
        }
    }
    show(q);

    // ⑤ 用 list 自带的 sort 按优先级排一下
    q.sort([](const Task &a, const Task &b) { return a.level < b.level; });
    cout << "按优先级排序后：";
    for (const Task &t : q) cout << "[" << t.level << "]" << t.name << "  ";
    cout << endl;
    return 0;
}

看到什么算成功：

任务队列（4 项）：[1]修线上故障  [2]回邮件  [2]写文档  [3]整理桌面  
处理：修线上故障
任务队列（3 项）：[2]回邮件  [2]写文档  [3]整理桌面  
任务队列（2 项）：[2]回邮件  [2]写文档  
任务队列（3 项）：[2]回邮件  [1]先开会  [2]写文档  
按优先级排序后：[1]先开会  [2]回邮件  [2]写文档  

两个新东西：

1. it->name —— 当迭代器指向的是一个对象时，*it 是那个对象，it->name 就是 (*it).name 的简写。这就是 10.4.4 讲过的 this->x 同款的 -> 运算符**——对指针和迭代器都适用。
2. q.sort(比较函数) —— 成员函数版 sort 可以接受自定义比较。std::sort 也接受，但 list 用不了 std::sort（原因见 13.3.3 与 13.4.5）。

五、三个序列容器的"最终选择指南"

写到这里，你已经把三个盒子都见过了。实战里怎么选？按这个顺序问自己：

① 我要"[按下标] 随机访问"吗？而且要快？
     是 → vector（首选）；如果还"两头都进出" → deque
     否 ↓
② 我要在"[中间] 频繁插入删除"吗？
     是 → list
     否 ↓
③ 那我就"只在尾部长、经常遍历" → vector（90% 的场合答案都是它）

再加两条"排除法"：

教科书上有一句话值得记住：list 的"快"，只在"你已经拿着那个位置的迭代器"时才成立。 如果还要"先找到它在哪"，找的过程本身是 O(n)（因为没有 []）。很多"用了 list 反而更慢"的案例，就出在这里。

30 秒实验

1. 验证"不能随机访问"：写 cout << l[0]; → 报 no match for 'operator[]'；写 list<int>::iterator it = l.begin() + 1; → 报 no match for 'operator+'。这两个报错要认得。
2. 验证"不能 std::sort"：sort(l.begin(), l.end()); → 报一大串（核心是 no match for 'operator-'，因为 sort 内部要算 last - first）。改成 l.sort(); 就好了。
3. 对比 remove 的两种含义：先 l.remove(2)（成员，真删）；再用 <algorithm> 的 remove(l.begin(), l.end(), 2)（不是真删，详见 13.3.2）→ 看两者的 size() 有没有变。
4. splice 的地址实验：在 dst.splice(...) 之前打印 &(*src.begin())，之后在 dst 里找到那个元素再打印地址 → 完全一样（说明是"摘过来"不是"复制"）。

常见误区

1. "list 插入删除快，所以它最快"——只对"已知位置"成立。找位置要 O(n)（没有 []），而且遍历时到处跳，缓存命中率最差。大量"插入 + 查找"混着来时，vector 往往反而赢。
2. "list 也能 sort(l.begin(), l.end())"——编译不过。要用成员 l.sort()。同理，<algorithm> 里所有需要"随机访问迭代器"的算法（sort、random_shuffle（13.3.2）、nth_element 等）在 list 上都不能用。（能用的那些比如 find、count、for_each 是因为它们只要"能 ++ 就行"。）
3. "l.remove(x) 和 remove(l.begin(), l.end(), x) 是一回事"——完全不同：成员 remove 真删、size 变小；<algorithm> 的 remove 只把要删的挪到后面，返回新的"逻辑末尾"，size 不变（13.3.2 讲 erase-remove）。
4. "unique() 能全局去重"——只能合并相邻的重复。全局去重要先 sort 再 unique。
5. "list 每次操作都 new/delete，很慢吧"——每个节点确实单独分配，所以内存分配次数多、局部性差，这是它的固有代价。但"改指针"的操作本身是 O(1) 且极快。
6. "迭代器失效规则和 vector 一样"——list 好得多：插入不让任何迭代器失效；删除只让指向被删元素的迭代器失效。所以"边遍历边删"用 list 特别顺（但 erase 的返回值还是接住更稳）。
7. "splice 和 insert 一样"——insert 要逐个复制/移动元素，splice 只改几条指针（O(1)），而且元素地址不变。这是链表独有、别的容器给不了的能力。

• ☐ 下一节（13.2 关联式容器）

相关笔记

• 双端队列类模板 —— 上一节：两头的专家
• 关联式容器 —— 下一节：换一种存法（按值找，不按位置找）
• 序列容器 —— 三个盒子的性格总表
• 双向迭代器 —— list 的迭代器到底能干什么
• 排序算法 —— 为什么 sort 要求随机访问迭代器
• 指针 —— 链表节点的底层结构
• 🔷 C++基础 · 索引 —— 全课路线图