第9.7章: list

概述

::fast_io::list 提供若干直接操作链表结构、不复制元素的操作。它们比 vector 上的等价操作更高效，因为只需调整指针。

1. 特有操作表

操作	说明
`splice(pos, it)`	把 `it` 所指元素移动到 `pos` 之前
`splice(pos, first, last)`	把范围 `[first, last)` 移动到 `pos` 之前
`splice(pos, other)`	把 `other` 中的所有元素移动到 `pos` 之前
`sort()` / `sort(cmp)`	就地排序整个链表
`sort(first, last)`	就地排序一个子范围
`merge(other)` / `merge(other, cmp)`	把已排序的 `other` 合并进这个已排序的链表
`reverse()`	反转所有元素的顺序
`is_single()`	恰有一个元素时返回 `true`
`has_multiple()`	有两个或更多元素时返回 `true`

2. 完整示例


#include <fast_io_dsal/list.h>
#include <fast_io.h>

int main() {
    ::fast_io::list<::std::size_t> a{10zu, 30zu, 50zu};
    ::fast_io::list<::std::size_t> b{20zu, 40zu};

    // Splice: move element from b to a
    auto bit = b.begin(); // points to 20
    auto ait = a.begin() + 1; // points to 30
    a.splice(ait, bit);
    // a is now {10zu, 20zu, 30zu, 50zu}
    // b is now {40zu}

    // Sort
    a.sort(); // a is now {10zu, 20zu, 30zu, 50zu} (already sorted)

    // Merge two sorted lists
    b.sort(); // b = {40}
    a.merge(::std::move(b));
    // a is now {10zu, 20zu, 30zu, 40zu, 50zu}
    // b is now empty

    // Reverse
    a.reverse();
    // a is now {50zu, 40zu, 30zu, 20zu, 10zu}
}

3. 为什么 list 往往比 vector 和 deque 慢得多

尽管在理论上插入与删除是 Θ(1)，list 在真实工作负载中往往比 vector 或 deque 慢 10× 到 100×。原因在于数据局部性——容器的内存布局与 CPU 缓存体系结构的契合程度。

缓存行利用率

现代 CPU 按缓存行取内存，通常一行 64 字节。只要访问到某行中的任意一个字节，整行 64 字节都会被载入 L1 缓存。问题在于：这一行里有多少是真正有用的数据？

容器	布局	每 64 字节缓存行中的有用字节数（以 `size_t` 为例）	效率
`vector`	连续：`[e0][e1][e2]...[e7]`	64 / 64 = 64 字节（8 个元素）	100%
`deque`	按块分块：每个块内部连续	64 / 64 = 64 字节（每块 8 个元素）	块内约 100%
`list`	结点散布：每个结点都是一次独立的堆分配	8 / 64 = 8 字节（每缓存行 1 个元素）	~12%

一个 list<::std::size_t> 结点除了 8 字节的值，还有两个 8 字节指针（prev/next），加上对齐填充总共约 24–32 字节。但每个结点位于不同的堆地址，所以每次访问都可能触发缓存未命中。CPU 必须等待主存（约 100 ns），而不是 L1 缓存（约 1 ns）。

指针追逐使预取器失效

现代 CPU 使用硬件预取器，它能识别顺序访问模式，并在需要之前把将要使用的缓存行载入。这对 vector（连续、可预测）效果完美，对 deque（顺序的块）效果尚可。但 list 需要指针追逐：每个结点的地址只有在读完前一个结点的 next 指针之后才知道。预取器无法预测这些地址，因此每次访问都可能缓存未命中。

常数因子压倒了渐近优势

链表提供 Θ(1) 的插入/删除，而 vector 是 O(n)（针对序列中间的操作）。但两者的常数因子差异巨大：

vector 插入：以约 10–50 GB/s 的速度用 memcpy 搬移约 n 个元素 — 一百万个元素只需几微秒。
list 插入：调整 4 个指针，但每次指针访问都可能是一次约 100 ns 的缓存未命中 — 即使是中等数量的元素也要几十微秒。

在实践中，除了需要稳定的迭代器（不会因为别处的插入/删除而失效的迭代器）之外，几乎任何工作负载下 vector 都会胜出。

基准测试：list 对 vector 对 deque

压入 1000 万个 ::std::size_t 元素，然后遍历求和：

容器	push_back	遍历（求和）	总计
`vector` (no reserve)	0.162 s	0.014 s	0.185 s
`vector` + `reserve()`	0.093 s	0.012 s	0.114 s
`deque` (plain)	0.096 s	0.026 s	0.138 s
`deque` + `resize_for_overwrite()`	0.078 s	0.012 s	0.105 s
`list`	0.768 s	0.121 s	1.686 s

list 比不带 reserve 的 vector 慢 9×（1.686 s 对 0.185 s），比带 reserve 的 vector 慢 15×（1.686 s 对 0.114 s）。甚至单纯遍历也比 vector 慢 9×（0.121 s 对 0.014 s），因为每访问一个结点都会缓存未命中。

数据规模越大，差距越悬殊。当数据集超出 RAM 时，操作系统会把页面换到磁盘。每次访问 list 结点都可能变成缺页，需要磁盘 I/O — 每次访问约 10 ms，比 L1 缓存命中（约 100 ns）慢 100,000×。相比之下，vector 能受益于操作系统的预读：当一个页面缺页时，操作系统会批量预取相邻页面，把磁盘延迟分摊到数百个元素上。对 list 来说，每个随机地址都不太可能落在已预取的页面里，于是几乎每次访问都要付出完整的磁盘代价。在网络存储的延迟下（每次访问数毫秒），list 完全不可用。

什么时候真的该用 list

你需要迭代器或引用在别处插入、删除之后依然有效。
你需要频繁地在容器之间 splice 元素。
元素很大（复制昂贵），并且你需要频繁地在中部插入。
你实现的算法在本质上需要链式结构（例如某些图算法）。

除此之外几乎所有场合 — 尤其是遍历密集的工作负载 — 请优先使用 vector 或 deque。

要点

splice() 在链表之间搬移元素而不复制。
sort()、merge() 和 reverse() 只调整指针。
is_single() 和 has_multiple() 是链表特有的查询。
链表操作从不会使未被移动或删除的元素的迭代器失效。
list 比 vector 慢约 9×，比 vector + reserve() 慢约 15× — 除非你需要稳定的迭代器，否则用 vector。