C++ 中的 list

核心概念与底层原理#

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

初始化与构造#

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

1
#include <list>
2

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

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

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

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

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

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

迭代器特性#

这是决定选择 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（权衡）问题：

结论：

• 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 更省内存（少存一个指针）
• 劣势：只能向前遍历，功能受限
• 场景：极其追求内存优化的哈希表桶实现等