List | ZaynPei's Base

std::list 是一个序列容器，它的底层实现是双向链表（Doubly-Linked List）。理解了“双向链表”这个数据结构，就理解了 std::list 的所有优缺点和行为特性。

std::list 的核心特性

与 std::vector（动态数组）的连续内存布局截然不同，std::list 的元素在内存中是非连续存储的。每个元素（节点）都包含三部分信息：

存储的数据本身。
一个指向前一个元素节点的指针 (prev)。
一个指向后一个元素节点的指针 (next)。

这种结构赋予了 std::list 一系列独特的特性：

快速的插入和删除: 这是 std::list 最主要的优点。在链表的任何位置（开头、中间、结尾）插入或删除一个元素，时间复杂度都是常数时间 O(1)（前提是你已经有了指向该位置的迭代器）。
- 原因：插入/删除操作只需要修改相邻节点的 next 和 prev 指针，将新节点“链接”进去或将旧节点“断开链接”，而不需要像 std::vector 那样移动大量后续元素。
慢速的随机访问: 这是 std::list 最主要的缺点。它不支持快速的随机访问。
- 由于内存不连续，你无法像数组那样通过计算偏移量来直接定位到第 n 个元素。要访问第 n 个元素，必须从头节点（或尾节点）开始，沿着指针逐个遍历 n 次。因此，访问操作的时间复杂度是线性时间 O(n)。
- 正因如此，std::list 没有提供 operator[] 访问符。
迭代器稳定性: 这是一个非常重要的优点。向 std::list 中插入或删除元素，不会导致指向其他元素的迭代器失效。
- 插入或删除只影响被操作节点及其邻居的指针，其他节点在内存中的位置和它们之间的链接关系保持不变。而在 std::vector 中，一次插入或删除就可能导致所有或部分迭代器失效。
更高的内存开销: 相比 std::vector，std::list 的每个元素都需要额外的空间来存储前向和后向指针，因此总的内存占用会更大。

常用操作

使用 std::list 需要包含头文件。

初始化

#include <list>
std::list<int> myList; // 创建一个空的整数列表
std::list<int> myList2 = {1, 2, 3, 4, 5}; // 使用初始化列表创建
std::list<int> myList3(myList2); // 通过拷贝另一个列表创建
std::list<int> myList4(10, 42); // 指定个数和初始化内容创建, 创建一个包含10个42的列表

添加元素

std::list 提供了在头部和尾部快速添加元素的方法。

#include <list>
#include <iostream>

std::list<int> myList;

// 在尾部添加元素
myList.push_back(10); // {10}
myList.push_back(20); // {10, 20}

// 在头部添加元素 (vector 没有这个方法)
myList.push_front(5); // {5, 10, 20}

删除元素

同样，std::list 也能在头部和尾部快速删除元素

1 2	myList.pop_back(); // 删除尾部元素 {5, 10} myList.pop_front(); // 删除头部元素 {10}

遍历

遍历 std::list 通常使用迭代器或范围 for 循环。

std::list<int> numbers = {1, 2, 3, 4, 5};
for (int num : numbers) {
    std::cout << num << " "; // 输出: 1 2 3 4 5
}

for (auto it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " "; // 输出: 1 2 3 4 5
}

在中间插入和删除

使用 insert() 和 erase() 方法，需要一个指向特定位置的迭代器。

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

// 在 it 指向的位置(2)之前插入 99
numbers.insert(it, 99); // {1, 99, 2, 3, 4, 5}
numbers.insert(it+2, 100); // 注意这是错误的用法, list 迭代器不支持随机访问

// 删除 it 指向的元素(2)
// erase 会返回指向被删除元素下一个元素的迭代器
it = numbers.erase(it); // {1, 99, 3, 4, 5}

同样, erase()成功后迭代器会自动前进一位, 需要额外考虑

std::list 特有的高效操作

std::list 提供了一些 std::vector 所没有的高效成员函数，这些函数充分利用了其链表结构的优势，通过直接操纵节点指针来完成，避免了元素的拷贝。

splice()：将一个 list 的全部或部分元素“剪切”并“粘贴”到另一个 list 中。这是一个 O(1) 的操作，非常高效。
merge()：将一个已排序的 list 合并到另一个已排序的 list 中，并保持排序。
sort()：std::list 拥有自己的 sort() 成员函数。不能使用全局的 std::sort()，因为 std::sort 要求随机访问迭代器，而 list 的迭代器是双向的。
reverse()：反转链表中元素的顺序。
unique()：移除连续的重复元素。

什么时候应该使用 std::list

根据以上对比，我们可以得出结论, 你应该在以下情况考虑使用 std::list：

需要频繁地在序列的任意位置（尤其是中间）进行插入和删除操作。
对迭代器的稳定性有很高的要求，不希望因为插入/删除操作而需要频繁更新迭代器。
不需要进行频繁的随机访问操作。

现代 C++ 的观点和建议是, 尽管 std::list 在特定场景下有其理论上的优势，但在现代 C++ 编程中，std::vector 仍然是绝大多数场景下的首选默认容器。

原因是现代计算机的 CPU 拥有多级缓存（Cache）。std::vector 的连续内存布局具有极佳的缓存友好性，CPU 可以预取数据，从而大大加快遍历速度。而 std::list 的节点分散在内存各处，遍历时会导致频繁的缓存未命中（Cache Miss），这带来的性能损失往往会抵消其 O(1) 插入/删除的理论优势。

除非你的程序经过性能分析（Profiling），明确显示出瓶颈在于 std::vector 的中间插入/删除，否则请优先使用 std::vector。