9. list容器：双向链表的艺术
说实话，在STL的序列容器里，list是个特别的存在。它不像vector那样"直来直去"，也不像deque那样"两头通吃"。list的本质是双向链表，这个数据结构的特点，决定了它的优势和短板。
我记得刚入行那会儿，有个同事在项目里用vector存了几十万个数据，频繁在中间插入删除，结果性能惨不忍睹。后来换成list，问题迎刃而解。嗯，选对容器，有时候比优化代码更重要。
9.1 list的构造与操作
list的构造方式，其实跟vector差不多。我习惯把它分成三类：空构造、带初始值的构造、以及拷贝构造。
#include <list>
using namespace std;
// 空构造
list<int> lst1;
// 构造并初始化
list<int> lst2(5, 100); // 5个100
list<int> lst3 = {1, 2, 3, 4, 5}; // C++11初始化列表
// 拷贝构造
list<int> lst4(lst3);
list<int> lst5(lst3.begin(), lst3.end());基本操作方面，list提供了push_back、push_front、pop_back、pop_front这些接口。你想想看，vector只有push_back和pop_back，因为它在头部操作需要移动所有元素。但list是链表，头尾操作都是O(1)的。
核心操作一览：
- 插入：insert(pos, val) — 在pos位置前插入
- 删除：erase(pos) 或 erase(start, end)
- 清空：clear()
- 大小：size() / empty()
- 访问：front() / back() — 注意list没有operator[]
这里有个坑，我曾经在代码里写了 list[3]，编译直接报错。list不支持随机访问，你要访问第4个元素，只能老老实实遍历过去。说白了，这是链表的天生缺陷。
9.2 list的迭代器
list的迭代器是双向迭代器，不是随机访问迭代器。这意味着什么？
- 支持
++it和--it，但不支持it += n - 不支持
it1 - it2这种距离计算 - 不支持
it[n]这种下标访问
list<int> lst = {10, 20, 30, 40, 50};
// 正向遍历
for (auto it = lst.begin(); it != lst.end(); ++it) {
cout << *it << " ";
}
// 反向遍历
for (auto rit = lst.rbegin(); rit != lst.rend(); ++rit) {
cout << *rit << " ";
}
// 错误用法：it += 2; // 编译错误！我个人建议，如果你需要频繁随机访问，就别用list了。vector或者deque更适合你。list的迭代器设计，就是为了配合链表的节点跳跃，而不是数组的连续内存。
小技巧：用 std::advance(it, n) 可以手动推进迭代器n步，虽然效率是O(n)，但至少能写。我在做链表分片处理时经常这么用。
9.3 list的排序与去重
list自带了sort和unique成员函数。为什么list不直接用STL的std::sort？因为std::sort需要随机访问迭代器，list不满足条件。
list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
// 排序
lst.sort(); // 默认升序
lst.sort(greater<int>()); // 降序
// 去重（必须先排序！）
lst.unique(); // 去除连续重复元素注意了，unique只去除连续的重复元素。如果你不先排序，结果可能不是你想要的。我曾经在项目里吃过这个亏——数据没排序就调unique，结果一堆重复值没去掉，排查了半天才发现问题。
避坑指南：list的sort采用的是归并排序，稳定且效率不错。但如果你对性能有极致要求，可以考虑先把list数据搬到vector里排序，再搬回来。虽然多了两次拷贝，但vector的排序速度更快。
9.4 list的splice操作
splice是list独有的"绝活"。它能在常数时间内把一个list的节点"剪切"到另一个list中。说白了，就是改几个指针的事，不需要拷贝数据。
list<int> lst1 = {1, 2, 3, 4, 5};
list<int> lst2 = {10, 20, 30};
// 把lst2的所有元素移动到lst1的头部
lst1.splice(lst1.begin(), lst2);
// lst1: 10, 20, 30, 1, 2, 3, 4, 5
// lst2: 空
// 把lst2的某个元素移动到lst1
lst1.splice(lst1.end(), lst2, lst2.begin());
// 只移动一个节点
// 把lst2的一段区间移动到lst1
lst1.splice(lst1.begin(), lst2, lst2.begin(), lst2.end());splice的三种重载形式，我工作中用得最多的是第一种——把整个list合并过来。比如做任务队列的合并，或者缓存分片的拼接，splice简直是神器。
splice vs insert：insert会拷贝元素，splice只移动节点。如果你不再需要源list的数据，用splice效率高得多。记住，splice后源list的节点就没了。
9.5 list与vector的对比
这个问题面试经常问。我直接给你一张对比表，一目了然：
| 特性 | list | vector |
|---|---|---|
| 底层结构 | 双向链表 | 动态数组 |
| 随机访问 | 不支持，O(n) | 支持，O(1) |
| 头部插入/删除 | O(1) | O(n) |
| 尾部插入/删除 | O(1) | 均摊O(1) |
| 中间插入/删除 | O(1)（已知迭代器） | O(n) |
| 内存占用 | 每个节点额外开销（prev/next指针） | 连续内存，几乎无额外开销 |
| 迭代器失效 | 只有被删除的迭代器失效 | 插入/删除可能导致全部失效 |
| 适用场景 | 频繁插入删除，不关心随机访问 | 频繁随机访问，尾部操作多 |
我个人经验是：80%的场景用vector就够了。list虽然在某些操作上很快，但它的内存不连续，对CPU缓存不友好。你想想看，遍历一个list比遍历一个vector慢得多，因为每次访问节点都可能触发缓存缺失。
那什么时候非用list不可？
- 需要在容器中间频繁插入删除，而且元素很大（拷贝成本高）
- 需要迭代器稳定性——插入操作不能让已有迭代器失效
- 需要splice这种"零拷贝"的节点转移操作
我的建议：先用vector，性能不够再分析。如果分析发现瓶颈在中间插入删除，再考虑换成list。别一开始就上list，容易过度设计。
知识体系总览
下面这张图，帮你把list的核心知识点串起来：
总结一下：list是个"偏科生"，它在插入删除和迭代器稳定性上表现优异，但在随机访问和内存效率上不如vector。选不选它，取决于你的业务场景。我个人建议，先把vector用明白，再考虑list的特殊能力。