文档目录

一、std::list 的内存灾难

list 的每个节点单独 new 分配，分布在堆的各个角落：

list<int> l = {1, 2, 3, 4};

内存布局 (每个节点独立分配):
堆地址 0x1000: [1 | next→0x2000 | prev←null]
堆地址 0x2000: [2 | next→0x3000 | prev←0x1000]
堆地址 0x3000: [3 | next→0x4000 | prev←0x2000]
堆地址 0x4000: [4 | next←null  | prev←0x3000]

栈上:
list 对象: [_M_node 指向 0x1000 或哨兵节点]

遍历时的缓存行为：

CPU 遍历 list:
  读 0x1000 → Cache Miss (第一次加载缓存行，顺带加载了附近 64 字节的垃圾数据)
  读 0x2000 → Cache Miss (因为 0x2000 和 0x1000 不在同一缓存行)
  读 0x3000 → Cache Miss
  读 0x4000 → Cache Miss
  缓存命中率: ~0% ❌

CPU 遍历 vector:
  读 v[0] → Cache Miss (第一次，加载了 v[0]~v[15] 到缓存行)
  读 v[1] → Cache Hit ✅ (已经在缓存里了)
  读 v[2] → Cache Hit ✅
  ...
  缓存命中率: ~99% ✅

性能差距实测（1 亿次遍历，Release 编译）：

  • vector：~80ms
  • list：~3500ms（慢 40 倍）

结论：除非你需要频繁在中间插入/删除且不在乎遍历性能，否则别用 list。

二、std::deque 的中控器 + 分块结构

deque（双端队列）是 vector 和 list 之间的折中方案：

deque<int> d;
d.push_back(1);
d.push_front(2);

物理内存结构:
栈上:
deque 对象: [_M_impl._M_map (指向中控数组) | ...]

中控数组 (Map, 在堆上, 连续):
+──────────+──────────+──────────+──────────+──────────+
| nullptr  | nullptr  | 块指针A  | 块指针B  | nullptr  |
+──────────+──────────+──────────+──────────+──────────+
                ↑            ↑
                |            |
      块 A (512字节)    块 B (512字节)
      [2][ ][ ][ ]...    [1][ ][ ][ ]...
      ↑ front             ↑ back

关键特性：

  1. 非连续但分段连续：每块内部是连续内存，块之间不一定连续。
  2. 两端插入 $O(1)$：只在块不满时写一次，快于 vector 的尾部插入（无需搬移）。
  3. 中间插入 $O(N)$：需要搬移元素到相邻块，比 list 慢。
  4. 随机访问 $O(1)$：中控数组定位块 → 块内偏移，比 list 的 $O(N)$ 快。

为什么 stack 和 queue 的默认底层容器是 deque？

  • 它们只需要两端操作，不需要 vector 的 reserve/capacity 特性。
  • deque 两端插入不触发整体搬移（vector 可能在 push_front 时触发搬移）。
  • deque 的内存碎片比 list 少得多。