C++ 中的 list

在现代 C++ 开发中，虽然 std::vector 足以应付绝大多数的场景，但是在某些特定场景下，std::list 依旧是不可替代的神器。

核心概念与底层原理

• 头文件：#include <list>
• 本质：双向链表（Doubly Linked List）
• 内存模型：非连续内存。每个元素（节点）都是独立分配在堆上的，节点之间通过指针（prev 和 next）连接
• 特点：
  • 不支持随机访问：不能使用下标 l[5] 访问元素，必须从头一个一个遍历过去
  • 插入 / 删除极快：只要持有了某个位置的迭代器，在该位置插入或删除元素的操作是 $O(1)$ 的，且不需要移动其他元素

初始化与构造

用法与 std::vector 非常相似：

#include <list>

std::list<int> l1;              // 空链表
std::list<int> l2 = {1, 2, 3};  // 列表初始化
std::list<int> l3(l2);          // 拷贝构造
std::list<int> l4(5, 100);      // 5 个 元素，全是 100

独有的操作优势（std::vector 做不到的）

这是 std::list 存在的理由。由于它是链表，它支持一些操作极其高效，或者提供了 std::vector 根本没有的接口。

头部操作

std::vector 在头部插入 / 删除操作极其低效（$O(N)$），而 std::list 则是瞬间完成（$O(1)$）。

• push_front(val)：头部插入
• pop_front()：头部删除

接合（Splicing）

可以将一个 std::list 的元素（全部或部分）直接 “剪切” 并 “粘贴” 到另一个 std::list 中，这是纯指针操作，没有数据拷贝，所以速度极快。

std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};

auto it =  list1.begin();
++it; // 指向 2

// 将 list2 的所有元素 “移动” 到 list1 的 2 前面
// list2 变空，list1 变为 {1, 4, 5, 6, 2, 3}
list1.splice(it, list2);

专用成员函数

由于 std::list 无法随机访问，标准库算法（如 std::sort）对它无效。因此 list 自带了一套经过优化的成员函数：

• l.sort()：排序（稳定排序，底层通常是归并排序）。注意：千万别读 std::list 用 std::sort(l.begin(), l.end())，编译会报错
• l.remove(val)：删除所有等于 val 的元素
• l.remove_if(pred)：删除满足条件的元素
• l.unique()：删除相邻的重复元素（去重前通常要先 sort）
• l.reverse()：逆置链表
• l.merge(l2)：合并两个已排序的链表（l2 会变空）

迭代器特性

这是决定选择 std::vector 还是 std::list 的关键因素。

• 类型：双向迭代器（Bidirectional Iterator）
  • 支持：++it、--it、*it
  • 不支持：it + 5，it < other_it（不能跳跃，不能比较大小）
• 稳定性（Validity）：极高
  • 掺入操作：绝对不会让现有的迭代器失效
  • 删除操作：只有指向被删除节点的那个迭代器会失效，其他的完全不受影响
  • 对比 std::vector：std::vector 一旦扩容，所有迭代器全部失效；中间插入，后面所有迭代器失效。

std::list 和 std::vector 的选择

这是一个经典的 Trade-off（权衡）问题：

特性	std::vector	std::list
随机访问	$O(1)$（支持 []）	不支持（$O(N)$）
尾部插入	$O(1)$	$O(1)$
头部/中间插入	$O(N)$（很慢，要挪动数据）	$O(1)$（很快，前提是有迭代器）
内存布局	连续（Cache 命中率高）	分散（Cache 命中率低）
额外内存	较少（少量预留空间）	较大（每个元素都要存两个指针）
迭代器失效	容易失效	几乎不失效

结论：

• 95% 的情况用 std::vector：现代 CPU 的缓存机制非常依赖内存连续性。即使是在中间插入，对于小对象（如 int），std::vector 往往也比 std::list 快，因为 std::list 的遍历会导致大量的 Cache Miss。
• 以下情况可以用 std::list：
  1. 需要频繁在头部或中间插入 / 删除，且元素总数很多
  2. 对象非常大，拷贝代价极高（虽然 C++11 移动语义缓解了这个问题）
  3. 核心需求：你需要保存指向某个元素的迭代器，并且在后续操作中（无论怎么插入删除其他元素），希望这个迭代器一直有效

C++11 新增：std::forword_list

C++11 引入了 std::forword_list（单向链表）：

• 特点：只有 next 指针，没有 prev 指针
• 优势：比 std::list 更省内存（少存一个指针）
• 劣势：只能向前遍历，功能受限
• 场景：极其追求内存优化的哈希表桶实现等