list与forward_list
# 34.list与forward_list
# 目录介绍
- 1. 案例引入
- 2. 架构概览
- 3. list 的节点布局与内存模型
- 4. 迭代器与遍历性能
- 5. splice O(1) 的魔法
- 6. 节点级分配器
- 7. forward_list 的单向简化
- 8. 三容器全场景对决
- 9. 汇编全景与性能剖析
- 10. 综合案例串讲
# 1. 案例引入
# 1.1 事务日志的手工搬移悲剧
某数据库的事务引擎——在内存中维护「已提交事务」和「待提交事务」两个列表。每次提交时，需要把元素从待提交列转移到已提交列。原始实现用手工 O(N) 搬移：
// ====== 事故代码 V1：手工 O(N) 搬移 ======
std::vector<Transaction> pending;
std::vector<Transaction> committed;
void commit_one(int tx_id) {
auto it = std::find_if(pending.begin(), pending.end(),
[tx_id](auto& tx) { return tx.id == tx_id; });
if (it != pending.end()) {
committed.push_back(std::move(*it)); // ① 移动——O(1)
pending.erase(it); // ② 删除——O(N) 搬移！
}
}
// N=10000 个事务，commit_one 的 erase 要搬移 ~5000 个元素
// 10000 次 commit → 总元素搬移 ≈ 25M 次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
正确方案——list + splice(O(1))：
std::list<Transaction> pending;
std::list<Transaction> committed;
void commit_one(int tx_id) {
auto it = std::find_if(pending.begin(), pending.end(),
[tx_id](auto& tx) { return tx.id == tx_id; });
if (it != pending.end()) {
committed.splice(committed.end(), pending, it); // ← O(1) 搬移——只改四个指针！
}
}
// 10000 次 commit → 0 次元素搬移、0 次构造/析构
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
10000 次 commit 的实测：
| 方案 | 元素搬移次数 | 时间 |
|---|---|---|
| vector + erase | ~25M | 420 ms |
| list + splice | 0 | 8 ms |
# 1.2 把 list 当 vector 用的内存暴增
同一个代码库的配置管理器——存 10000 个 int。作者选了 std::list<int>（因为「链表更灵活」）。上线后内存占用翻倍：
// ====== 事故代码 V2：list 存小类型的代价 ======
std::list<int> lst(10000); // 内存 = 10000 * sizeof(list_node) ≈ 400KB
std::vector<int> vec(10000); // 内存 = 10000 * sizeof(int) = 40KB
// list_node 的 sizeof（libstdc++）：
// struct _List_node {
// void* _M_next; // 8B → 下一个节点
// void* _M_prev; // 8B → 前一个节点
// int _M_data; // 4B → 数据
// };
// sizeof(_List_node<int>) = 24 + padding = 32 字节（对齐后）
// 加上 allocator 的 metadata —— 每个节点总开销 ~40 字节
// → 4 字节的 int，吃掉 40 字节——内存效率 10%！
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
| 容器 | 10000 个 int 的内存 | 内存效率 |
|---|---|---|
| vector | 40 KB | 100% |
| list | 400 KB | 10% |
# 1.3 七个待解疑问
① list 的节点到底长什么样? 哨兵节点的作用是什么? → 第 3 章
② 为什么 list 遍历比 vector 慢那么多? 汇编层怎么看? → 第 4 / 第 9 章
③ splice 是怎么做到 O(1) 搬移元素的? 内部改了哪几个指针? → 第 5 章
④ 为什么 list 需要节点级分配器? 自定义分配器怎么接? → 第 6 章
⑤ forward_list 和 list 有什么区别? 为什么 forward_list 没有 size()? → 第 7 章
⑥ 为什么 90% 的场景不该用 list? 哪些场景反而应该用它? → 第 8 章
⑦ sort 在 list 和 vector 上各有多快? 为什么 list 有 sort 成员函数? → 第 4.3 / 第 9.3 章
1
2
3
4
5
6
7
2
3
4
5
6
7
# 2. 架构概览
# 2.1 节点式容器的本质
┌──────────────────────────────────┐
│ 节点式容器 (node-based) │
└──────────────────┬───────────────┘
│
┌──────────────────────────┼──────────────────────────┐
▼ ▼ ▼
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ std::list │ │forward_list │ │ 节点级分配器 │
│ 双向链表 │ │ 单向链表 │ │ 每个 node 一次│
│ │ │ │ │ alloc/dealloc│
├──────────────┤ ├──────────────┤ ├──────────────┤
│ 哨兵节点 │ │ 无哨兵(before │ │ 默认 std:: │
│ 双向迭代器 │ │ _begin) │ │ allocator │
│ splice O(1) │ │ 前向迭代器 │ │ 可自定义池 │
│ remove O(1) │ │ insert_after │ │ │
└──────────────┘ └──────────────┘ └──────────────┘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
和连续容器（vector/deque）的本质区别：节点式容器的元素在堆上的离散节点中——每个节点是独立分配的。这让插入/删除/搬移都是 O(1)，但代价是：
- 每个节点有 pointer 开销（list = +16 字节 per element）
- 遍历时 CPU 无法预测下一个元素的地址（cache miss 比 vector 高 10-50×）
- 每个节点一次 allocator 调用（性能代价）
# 2.2 为何这么切
疑惑：为什么 C++ 同时有 list 和 forward_list 两个链表？双向和单向差很多吗？
论证：
- 16 字节的差距在百万节点量级是真实的——
list的每个节点有两个指针（prev+next = 16B），forward_list只有一个（next = 8B）。百万节点 → 8MB 的额外内存。 - forward_list 的
insert_after语义——在单向链表中，插入需要「插入点之前的节点」——所以迭代器永远指向「我要插入的位置的前一个」。这导致 forward_list 有before_begin()（一个特殊的「在头节点之前」的迭代器）。 - 没有
size()是有意设计——单向链表的长度计算是 O(N)。如果你在 forward_list 上存一个size_t count，每次 splice 后都要更新两者的 count（可能跨列表），这个操作不是 O(1)。标准选择不存储——让 caller 自己维护计数或忍受 O(N)。
结论：list 是通用链表，forward_list 是「我能承受单向、只要最少开销」时的选择。两者的差距不是 2×——是内存（×1.5）和语义复杂度（insert_after vs insert）之间的权衡。
# 3. list 的节点布局与内存模型
# 3.1 双向链表节点的精确结构
// libstdc++ 的 list 节点结构
template <typename T>
struct _List_node {
_List_node* _M_next; // ① 指向后一个节点——8 字节
_List_node* _M_prev; // ② 指向前一个节点——8 字节
T _M_data; // ③ 存储的数据
// 总大小：
// sizeof(_List_node<int>) = 8+8+4+4(padding) = 24
// sizeof(_List_node<long>) = 8+8+8 = 24
// sizeof(_List_node<string>) = 8+8+32 = 48
};
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
每个节点的堆分配：
堆
┌──────────────────────────────────────────────┐
│ [_M_next: 8B] [_M_prev: 8B] [_M_data: TB] │
└──────────────────────────────────────────────┘
▲ ▲
│ │
前一个节点的 后一个节点的
_M_next 指向这里 _M_prev 指向这里
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 3.2 哨兵节点的巧妙设计
std::list 的实际结构不是「头节点→...→尾节点」——而是一个环形链表 + 哨兵节点：
哨兵 (sentinel node)
┌─────────────────────────────┐
│ _M_next → node_0 │
│ _M_prev → node_last │
│ _M_data = (未使用) │
└─────────────────────────────┘
▲ │
│ ▼
┌──────┐ ┌──────┐ ┌──────┐
│node_0│◄──►│node_1│◄──►│node_2│
└──────┘ └──────┘ └──────┘
begin() → sentinel._M_next
end() → &sentinel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
哨兵的存在意味着：
list从不「为空」——即使没有元素，哨兵仍然存在end()永远指向哨兵——--end()是最后一个有效元素- 首尾插入/删除不需要特殊逻辑（哨兵本身提供「下一个」和「上一个」的锚点）
# 3.3 sizeof 的灾难——每个 int 吃掉 40 字节
std::list<int> lst;
lst.push_back(42);
// 堆上发生了什么？
// ① operator new(sizeof(_List_node<int>)) = 24B → 实际分配 ≥ 24B
// （allocator 内部有 metadata，通常每个节点多占 8-16 字节）
// ② 总开销：24B (node) + 8~16B (allocator metadata) ≈ 32~40B
// ③ 实际有用数据：4B (int)
// ④ 内存效率：4 / 40 = 10%
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
精算一个 list<int> 的堆内存（glibc malloc，64 位）：
每次 push_back：
node × N 个：24B × N + (N-1) * padding = ~24N 字节
allocator metadata per node: ~16B × N
total: ~40N 字节
vector<int>：
sizeof(int) × N + capacity overhead = ~4N 字节
list / vector = 40 / 4 = 10× 内存差距
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 3.4 与 vector 的内存密度对比
| 容器 | 10000 × int 内存 | 每元素额外指针 | CPU prefetch |
|---|---|---|---|
| vector | 40 KB | 0 | ✅ 连续 |
| deque | ~80 KB | 0（但两级间址） | ⚠️ chunk 内连续 |
| list | ~400 KB | +16B | ❌ 完全离散 |
| forward_list | ~320 KB | +8B | ❌ 完全离散 |
# 4. 迭代器与遍历性能
# 4.1 双向迭代器的跳转本质
// list 的 operator++ 本质上就是这么简单
auto& operator++() {
_M_node = _M_node->_M_next; // 跟随 next 指针跳到下一个节点
return *this;
}
1
2
3
4
5
2
3
4
5
因为节点的堆地址是离散的——每次 ++it 都是在跳到一个不可预测的地址。CPU 的 branch predictor 和 cache prefetcher 完全失灵。
# 4.2 遍历的汇编对比
int sum_vec(const std::vector<int>& v) {
int s = 0;
for (int x : v) s += x;
return s;
}
int sum_lst(const std::list<int>& l) {
int s = 0;
for (int x : l) s += x;
return s;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
GCC 13.2 -O2：
; vector 遍历 —— 连续访问，CPU 预取管道全开
.Lloop_vec:
add eax, [rdx] ; 累加
add rdx, 4 ; 指针前进 → 下一条 L1 cache line
cmp rdx, rcx
jne .Lloop_vec ; 4 条指令循环——全流水线化
; list 遍历 —— 每次迭代要从堆上读 next 指针
.Lloop_lst:
mov rcx, [rax] ; rcx = node._M_next → 读堆内存！
add eax, [rax+16] ; 累加 node._M_data (偏移 16 = 跳过两个指针)
mov rax, rcx ; 跳到下一个节点
cmp rax, rsi
jne .Lloop_lst ; 5 条指令——但每次 [rax] 都可能 cache miss
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
100 万元素的遍历 benchmark：
| 容器 | 时间 | L1 miss rate | IPC |
|---|---|---|---|
| vector | 0.4 ms | 0.3% | 3.2 |
| deque | 1.1 ms | 7.1% | 1.8 |
| list | 8.3 ms | 42% | 0.6 |
| forward_list | 7.1 ms | 38% | 0.7 |
# 4.3 为什么 list 有 sort 成员函数
std::list 和 std::forward_list 都有 sort() 成员函数——这不是偶然：
std::list<int> lst = {5,2,8,1};
lst.sort(); // 用 merge sort —— 专门针对链表优化
// ❌ 不能用 std::sort——需要 random access iterator
// std::sort(lst.begin(), lst.end()); // 编译错误！
1
2
3
4
5
2
3
4
5
list::sort() 内部使用迭代归并排序——不需要随机访问、不需要额外内存（vector 的 sort 用堆排序/introsort，需要随机访问）。链表版本的 sort 是 O(N log N) 但不需要数组索引——它是通过切片链表递归归并的。
# 4.4 为什么 list 是唯一不会失效迭代器的容器
std::list<int> lst = {1,2,3,4};
auto it = std::next(lst.begin(), 2); // it → 3
lst.push_back(5); // ✅ it 仍然有效——指向 3
lst.push_front(0); // ✅ it 仍然有效
lst.erase(lst.begin()); // ✅ it 仍然有效——被删除的是另一个节点
lst.insert(lst.end(), 6); // ✅ it 仍然有效
// 只有删除 it 自己才会使它失效：
lst.erase(it); // it 失效——但其他迭代器全部有效！
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
| 操作 | list | vector | deque |
|---|---|---|---|
| push_front/back | ✅ 全部有效 | ❌ 可能全部失效(扩容) | ✅ 全部有效 |
| insert 中间 | ✅ 全部有效 | ❌ 插入点及之后失效 | ❌ 全部失效 |
| erase 一个元素 | 仅被删除者失效 | 删除点及之后失效 | ❌ 全部失效 |
# 5. splice O(1) 的魔法
# 5.1 splice 的三种重载
// ① 转移整个 other 到 pos 之前
lst1.splice(pos, lst2); // lst2 变空
// ② 转移 other 中的单个元素 it 到 pos 之前
lst1.splice(pos, lst2, it); // lst2 少一个元素
// ③ 转移 other 的范围 [first, last) 到 pos 之前
lst1.splice(pos, lst2, first, last);
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 5.2 内部实现——仅修改四个指针
// splice(pos, other, it) 的内部实现——伪代码
void splice(iterator pos, list& other, iterator it) {
// ① 从 other 中解链 it
it->_M_prev->_M_next = it->_M_next;
it->_M_next->_M_prev = it->_M_prev;
// ② 把 it 插入到 pos 之前
it->_M_next = pos._M_node;
it->_M_prev = pos._M_node->_M_prev;
pos._M_node->_M_prev->_M_next = it->_M_node;
pos._M_node->_M_prev = it->_M_node;
// 完成！没有 new / delete / 拷贝 / 移动
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
四步指针修改——零内存分配、零元素搬移：
other 链表: ... → A → [it] → B → ...
↓ (解链)
A → B (it 被取出)
pos 之前: ... → P → Q → ...
↓ (插入)
... → P → [it] → Q → ...
1
2
3
4
5
6
7
2
3
4
5
6
7
# 5.3 splice 的典型应用场景
场景①：LRU 缓存——把访问的元素移到列表头部：
std::list<int> cache = {1,2,3,4,5};
auto it = std::find(cache.begin(), cache.end(), 3);
cache.splice(cache.begin(), cache, it); // O(1) 移到头部
// cache: {3,1,2,4,5}
1
2
3
4
2
3
4
场景②：多队列调度——任务从一个队列移到另一个：
std::list<Task> high_priority, low_priority;
// 把低优先级队列的某个任务提升到高优先级
high_priority.splice(high_priority.end(), low_priority, task_it);
1
2
3
2
3
场景③：列表合并——batch 操作：
lst1.splice(lst1.end(), lst2); // 把 lst2 整个附加到 lst1 尾部——O(1)
1
# 5.4 为什么 vector 做不到 splice
vector 的元素是连续内存——要「转移一个元素到另一个 vector」，必须：
- 在目标 vector 分配空间（或利用已有空间）
- 拷贝/移动元素
- 在源 vector 里删除元素——触发后面元素的搬移
这是 O(N) 操作——不存在 vector 版的 splice。
# 6. 节点级分配器
# 6.1 为什么 list 需要自定义分配器
std::list 的默认分配器是 std::allocator<_List_node<T>>。push_back 内部的分配流程：
push_back(x):
① allocator.allocate(1) → operator new(sizeof(_List_node<T>))
→ 可能触发系统调用(mmap/brk)
② placement new → 构造节点
③ 链入链表
pop_back():
① 从链表解链
② 析构节点数据
③ allocator.deallocate(node, 1) → operator delete
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
每个元素的插入/删除都是一次 new/delete——100 万次 push_back = 100 万次 system call（在 glibc 的 fast bin 之外）。
# 6.2 节点池的实现方式
// 自定义分配器——预分配节点池
template <typename T>
class NodePoolAllocator {
std::vector<std::aligned_storage_t<sizeof(_List_node<T>),
alignof(_List_node<T>)>> pool_;
size_t next_ = 0;
public:
_List_node<T>* allocate(size_t n) {
if (next_ + n > pool_.size()) return /* 回退到默认 new */;
auto* p = reinterpret_cast<_List_node<T>*>(&pool_[next_]);
next_ += n;
return p;
}
void deallocate(_List_node<T>*, size_t) { /* 池化——不释放 */ }
};
// 使用
std::list<int, NodePoolAllocator<int>> lst;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 6.3 std::allocator 在 list 中的节点级工作流
std::allocator<_List_node<int>> alloc;
// allocate 阶段——仅在申请节点时调用
auto* node = alloc.allocate(1); // void* → _List_node<int>*
// 此时节点内存已分配，但 _M_data 尚未构造
// construct 阶段
alloc.construct(&node->_M_data, 42); // placement new int(42)
// destroy 阶段
alloc.destroy(&node->_M_data); // ~int()
// deallocate 阶段
alloc.deallocate(node, 1); // operator delete
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 7. forward_list 的单向简化
# 7.1 单向链表的节点结构
// libstdc++ 的 forward_list 节点——只省了一个指针
template <typename T>
struct _Fwd_list_node {
_Fwd_list_node* _M_next; // ① 只有 next——8 字节（vs list 的 16 字节）
T _M_data; // ② 数据
};
// sizeof(_Fwd_list_node<int>) = 8+4+4(padding) = 16 字节
// sizeof(_List_node<int>) = 8+8+4+4(padding) = 24 字节
// 每个节点省了 8 字节——约 33%
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 7.2 insert_after 与 before_begin 的设计
单向链表的限制——无法从当前节点找到前一个节点。所以所有插入操作都需要「前一个节点的迭代器」：
std::forward_list<int> fl = {1,2,4};
auto it = fl.before_begin(); // ← 特殊迭代器——指向「第一个元素之前」
++it; ++it; // it 现在指向 2
fl.insert_after(it, 3); // 在 2 之后插入 3 → {1,2,3,4}
// ❌ 没有 push_back——因为需要从最后一个节点找到它自己
// 但单向链表不知道「最后一个节点」是谁（只能从前往后遍历）
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 7.3 为什么 forward_list 没有 size()
疑惑：链表存一个 size_ 成员每次 push_back/pop_front 时更新——O(1) 维护。为什么 forward_list 不这样做？
论证：
splice_after是 O(1)——但被 splice 的forward_list的size()会改变「部分元素从另一个列表转移过来」——这个新 size 不是 O(1) 可计算（需要遍历被转移的子链表）。- 如果两个
forward_list各有一个size_——splice 之后需要更新两者的 size。如果被转移的是子范围 [first, last)——这段有多少个元素？必须遍历才知道。 没有双向，你无法从 first 直接跳到 last 去数。 - 标准选择不存
size()——让 splice 保持真正的 O(1)。
forward_list<int> a = {1,2,3,4,5};
forward_list<int> b = {6,7};
auto it = a.begin(); // it → 1
++it; // it → 2
// 把 a 的 [2,5) 转移到 b 尾部
b.splice_after(b.before_begin(), a, a.before_begin(), it);
// 没有 size_ 需要更新——真正的 O(1)
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 7.4 list vs forward_list 选型决策
| 需求 | list | forward_list |
|---|---|---|
| 需要 size() | ✅ | ❌ (不是成员函数) |
| 需要双向遍历 | ✅ | ❌ |
| 需要 pop_back | ✅ | ❌ |
| splice O(1) | ✅ | ✅ (splice_after) |
| 每节点内存 | 24B (int) | 16B (int) |
| 插入语义 | insert(pos, val) | insert_after(pos, val) |
| 哨兵节点 | 有（环形） | 无（before_begin 是特殊迭代器） |
# 8. 三容器全场景对决
# 8.1 vector vs deque vs list 的性能矩阵
| 操作 | vector | deque | list |
|---|---|---|---|
| 随机访问 [] | 1.8 ns | 4.6 ns | — |
| push_back | 2 ns (摊还) | 3 ns | 12 ns (alloc) |
| push_front | O(N) | 3 ns | 12 ns |
| insert 中间 | O(N) 搬移 | O(N) 搬移少的一侧 | O(1) + 查找 |
| erase 单个 | O(N) | O(N) (失效大量迭代器) | O(1) |
| 遍历 1M 元素 | 0.4 ms | 1.1 ms | 8.3 ms |
| sort | O(NlogN) 随机访问 | — | O(NlogN) 归并 |
| 内存效率(int) | 100% (4B/elem) | ~80% | ~10% (40B/elem) |
# 8.2 为什么 90% 场景不该用 list
原因 ①：遍历是 list 的最大痛点
list 的遍历比 vector 慢 20×（8.3ms vs 0.4ms for 1M）。因为链表节点的堆地址是离散的——CPU 的 L1/L2/L3 缓存对离散访问完全无效。
原因 ②：内存效率极低
list<int> 每元素 40 字节，vector<int> 每元素 4 字节——10× 差距。
原因 ③：频繁的堆分配
每次 push_back 都要 operator new——一次系统调用级别的开销。vector 一次分配可以存 N 个。
原因 ④：splice 和 O(1) 删除/插入的价值局限于特定场景
大多数 C++ 程序的数据流是「追加 + 随机访问 + 批量处理」——这些场景 list 全线劣势。
# 8.3 仅 list 适用三场景
| 场景 | 为什么不用 vector/deque |
|---|---|
| 频繁中间插入/删除 + 不需要随机访问 | vector 搬移 O(N)，deque 搬移+迭代器全失效 |
| 元素的迭代器必须永不失效 | vector 扩容全失效，deque 中间操作全失效 |
| splice / merge 频繁 | 只有链表能做到 O(1) 整段搬移 |
# 9. 汇编全景与性能剖析
# 9.1 push_back 的节点分配指令序列
std::list<int> lst;
lst.push_back(42);
1
2
2
GCC 13.2 -O2：
; push_back(42) —— 每次都是 new + placement new + link
; ① 分配节点
mov edi, 24 ; sizeof(_List_node<int>)
call operator new ; ← 堆分配——慢！
; ② placement new 构造数据
mov DWORD [rax+16], 42 ; 在偏移 16 处写入 42
; ③ 链入链表（修改哨兵和尾节点的指针）
mov rdx, [rdi+8] ; sentinel._M_prev（原来的尾节点）
mov [rax+8], rdx ; new_node._M_prev = 原尾节点
mov [rax], rdi ; new_node._M_next = &sentinel
mov [rdx], rax ; 原尾节点._M_next = new_node
mov [rdi+8], rax ; sentinel._M_prev = new_node
; ④ 更新 size
inc QWORD [rdi+16]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
和 vector 的 push_back 对比：vector 在 capacity 足够时只需 mov [ptr], val; ptr+=4——2 条指令。list 需要 10+ 条指令 + operator new。
# 9.2 遍历的 cache miss 量化
// 遍历 100 万个 int
int sum = 0;
for (int x : lst) sum += x;
1
2
3
2
3
perf stat：
| 指标 | list | vector | 差异 |
|---|---|---|---|
| 指令数 | 5.0M | 3.0M | +67% |
| L1-dcache-load-misses | 42.3% | 0.3% | 141× |
| LLC-load-misses | 18.1% | 0.01% | 1810× |
| IPC | 0.6 | 3.2 | -81% |
# 9.3 sort 三容器对比 benchmark
100000 个随机 int 排序：
| 容器 | 算法 | 时间 | 说明 |
|---|---|---|---|
| vector | std::sort (introsort) | 3.2 ms | 随机访问——最优 |
| deque | std::sort | 5.1 ms | 两级间址——稍慢 |
| list | list::sort() (merge sort) | 18 ms | 归并——节点搬移无拷贝 |
| forward_list | forward_list::sort() | 16 ms | 比 list 稍快（少维护 prev 指针） |
# 10. 综合案例串讲
# 10.1 案例真相揭晓
| # | 疑问 | 答案 |
|---|---|---|
| ① | list 节点结构? | 第 3 章：prev+next+data；哨兵节点——begin=哨兵.next, end=&哨兵 |
| ② | 遍历为什么慢? | 第 4/9 章：离散地址→CPU 无法预取→L1 miss 141× |
| ③ | splice O(1)? | 第 5 章：只修改 4 个指针——零内存分配/零元素搬移 |
| ④ | 节点级分配器? | 第 6 章：每个 node 一次 alloc/dealloc——默认 allocator 即节点级；可定制池 |
| ⑤ | forward_list vs list? | 第 7 章：少 8B/node、无 size()、单向遍历、insert_after 语义 |
| ⑥ | 为什么不用 list? | 第 8 章：4 个原因——遍历慢 20×、内存效率 10%、频繁堆分配、价值局限 |
| ⑦ | sort 对比? | 第 9.3：list 用归并 O(NlogN)——比 vector 的 introsort 慢 ~6× |
案例①修复（手工搬移）：splice——从 420ms 降到 8ms。
案例②修复（内存暴增）：切回 vector<int>——内存从 400KB 降到 40KB。
# 10.2 一次 splice 的完整生涯
committed.splice(committed.end(), pending, it);
═══════ 运行期 ═══════
① 从 pending 解链 it:
it->_M_prev->_M_next = it->_M_next // prev 跳过 it
it->_M_next->_M_prev = it->_M_prev // next 跳过 it
② 插入到 committed 尾部:
it->_M_prev = committed 的尾节点
it->_M_next = &sentinel
尾节点._M_next = it
sentinel._M_prev = it
③ pending 的 size--
④ committed 的 size++
总指令：~4 条 mov + 2 条 inc
总时间：~2 ns
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 10.3 设计哲学回扣
哲学 1：O(1) 插入/删除的代价 = 内存碎片 + 缓存地狱
list 用每个节点 16 字节的指针开销和完全离散的内存布局，换来了 O(1) 的插入删除。这个 tradeoff 在插入/删除频率 >> 遍历频率的场景下是有利的——但绝大多数 C++ 程序的访问模式正好相反。 理解这个 tradeoff 才能真正理解为什么「list 存在、但大多数人不该用它」。
哲学 2：哨兵节点消去了全部分支——简洁来自结构
哨兵节点的存在让 begin()/end() 操作、首尾插入/删除不需要任何 if 判断（如「列表是否为空？」）。哨兵永远在——算法永远是「在它之前或之后操作」。好的数据结构设计不是写最聪明的代码——是让所有路径都走同一条代码。
哲学 3：splice 是 move 语义在容器层的体现
C++11 给对象引入了移动语义（偷资源），list 从 C++98 开始就有 splice（偷节点）。同样的哲学——不拷贝、不构造、不析构——只是作用在「容器层」而非「对象层」。
哲学 4：forward_list 的设计诚实——你知道单向的代价，所以你选择了它
没有 size()，没有 push_back()，只有 insert_after——forward_list 的 API 直接暴露了单向链表的物理限制。这是 C++ 容器设计诚实的一面：不给 O(N) 的操作起 O(1) 的名字。
# 10.4 速查表合集
list 操作复杂度速查：
| 操作 | 复杂度 | 迭代器失效 |
|---|---|---|
| push_front/back | O(1) | ❌ |
| insert | O(1) | ❌ |
| erase | O(1) | 仅被删除者 |
| splice | O(1) | ❌ |
| sort | O(N log N) | ❌ |
三容器一句话选型：
需要随机访问 → vector
需要前端插入 + 随机访问 → deque
需要任意位置 O(1) 插入/删除 + 迭代器永不失效 → list
只需要单向 + 省内存 → forward_list
1
2
3
4
2
3
4
下一篇：list 的节点级容器说清了。下一篇进入 35.关联容器红黑树——
map/set的底层红黑树五性质、节点重用extract/insert(node_type)、heterogeneous lookup 的 O(1) 免临时对象查找——为什么map.find("key")不需要构造std::string了。
上次更新: 2026/06/10, 11:13:41
