1. 什么是 list？
std::list 是 STL 提供的双向链表容器，每个元素存放在一个独立的节点中，节点之间通过指针链接。结构特点：
-
内存不连续，不支持随机访问（没有 [] 和 at()）。
-
在任意位置插入或删除元素都非常高效，时间复杂度 O(1)（前提是你已经拥有指向该位置的迭代器）。
-
不需要像 vector 那样扩容或移动元素，插入后其他元素的地址不会改变。
-
自带一些高效的成员函数：sort、merge、reverse、splice（拼接）、remove、unique 等。
一句话概括：当程序频繁在序列中间插入或删除元素，且不需要随机访问时，优先考虑 list。
2. 引入头文件与基本声明
使用 list 前，必须包含头文件：
#include <list>
声明一个 list 对象：
std::list<int> lst; // 存放 int 的空链表
std::list<std::string> words; // 存放字符串
std::list<double> prices; // 存放价格
同样，我们用 std:: 前缀，保持代码清晰。
3. 初始化方法
list 的初始化与 vector 基本一致：
list<int> l1; // 空链表
list<int> l2(5); // 5 个元素，默认值 0
list<int> l3(5, 10); // 5 个元素，都是 10
list<int> l4 = {1, 2, 3, 4}; // 列表初始化
list<int> l5(l4); // 拷贝构造
list<int> l6(l4.begin(), l4.end());// 用迭代器范围构造
注意：list 没有类似 vector 的 capacity() 和 reserve()，因为它根本不需要预分配连续内存。
4. 常用操作详解
list 比 vector 多了很多首部操作，而且有自己专属的算法成员。
4.1 添加元素
list<int> lst;
// 尾部添加
lst.push_back(30);
lst.emplace_back(40); // 原地构造，更高效
// 首部添加
lst.push_front(20);
lst.emplace_front(10);
// 任意位置插入
auto it = lst.begin();
++it; // 移动到第二个位置
lst.insert(it, 25); // 在迭代器前插入 25
lst.insert(it, 2, 7); // 插入两个 7
lst.insert(it, {1,2,3}); // 插入初始化列表（C++11）
因为 list 是双向链表，在头部操作非常快，这是 vector 做不到的（vector 头插要移动所有元素）。
4.2 访问元素
list 不提供随机访问，只能访问头尾：
int first = lst.front(); // 第一个元素
int last = lst.back(); // 最后一个元素
如果要访问中间元素，必须使用迭代器逐一遍历。下面这样是错误的：
// int x = lst[2]; // 编译错误！list 没有 operator[]
4.3 删除元素
lst.pop_back(); // 删除尾部元素
lst.pop_front(); // 删除头部元素
// 删除指定迭代器所指元素
auto it = lst.begin();
++it;
lst.erase(it); // 返回下一个有效迭代器
// 删除所有值为 val 的元素
lst.remove(10); // 删除所有等于 10 的元素
// 按条件删除（C++11 的 lambda 很方便）
lst.remove_if([](int x) { return x % 2 == 0; }); // 删除所有偶数
lst.clear(); // 清空链表
注意 remove 是 list 的成员函数，它会真正删除节点并调整链接，与头文件 <algorithm> 中的泛型 std::remove 不同（后者只是移动元素，不改变容器大小）。
4.4 其他特色操作
list 还有一些独门绝技，特别适合某些算法：
// 反转链表
lst.reverse();
// 排序（list 自带的 sort，效率优于 std::sort）
lst.sort(); // 默认升序
lst.sort(std::greater<int>()); // 降序
// 合并两个已排序链表（合并后，另一个链表为空）
list<int> other = {2,4,6};
lst.merge(other); // 要求两个链表都已排序
// 移除连续重复元素（通常配合 sort 使用）
lst.unique(); // 只保留连续相同元素中的第一个
// 拼接（splice）—— 将另一个链表的元素整个移动到指定位置
list<int> extra = {100, 200};
auto pos = lst.begin();
++pos;
lst.splice(pos, extra); // extra 中所有元素移到 pos 前，extra 变空
splice 是 list 的一大亮点：它将另一个链表的节点“偷”过来，只修改指针，不复制元素，效率极高。实现复杂的数据结构（如 LRU 缓存）时非常有用。
5. 遍历 list
因为没有下标，我们主要使用范围 for 循环或迭代器。
范围 for（推荐）
for (int x : lst) {
cout << x << " ";
}
需要修改元素时用引用：
cpp
for (int& x : lst) {
x *= 2;
}
迭代器
for (auto it = lst.begin(); it != lst.end(); ++it) {
cout << *it << " ";
}
list 的迭代器是双向迭代器，可以 ++ 和 –，但不能 it += 3 这样随机移动。如果需要跳过多个元素，只能循环递增。
6. list 的内存管理特点
-
非连续内存：每个元素是独立的节点，节点中包含数据以及指向前驱和后继的两个指针。因此 list 占用的总内存比 vector 多（多出指针开销）。
-
没有 capacity 和 reserve：添加元素时就分配一个新节点，删除时立即释放节点内存。
-
迭代器稳定性：在 list 上插入或删除元素不会导致其他元素的迭代器失效（当然，被删除的那个元素自己的迭代器会失效）。这一点比 vector 安全得多，vector 扩容会让所有迭代器失效。
-
不能通过下标访问：访问第 n 个元素需要从头（或尾）遍历 n 步，复杂度 O(n)。因此不要用 list 做频繁的随机访问操作。
7. 常见误区与注意事项
试图用 [] 访问元素
list 没有 operator[]，编译错误。请用迭代器或范围 for。
对 list 使用全局 std::sort
std::sort(lst.begin(), lst.end()); // 错误！list 迭代器不是随机访问迭代器
必须用成员函数 lst.sort()。
删除元素时迭代器失效
类似 vector，erase 会返回下一个有效迭代器，正确写法：
for (auto it = lst.begin(); it != lst.end(); ) {
if (需要删除 *it) {
it = lst.erase(it);
} else {
++it;
}
}
如果写成 lst.erase(it); ++it;，it 已经失效，程序会崩溃。
remove 与全局 std::remove 的混淆
使用 lst.remove(value) 是 O(n) 删除所有匹配节点，真正改变大小；而 std::remove 配合 erase 是另一种惯用法，但不适用于 list（而且更繁琐）。建议在 list 上就用成员 remove。
误以为 list 总是比 vector 快
链表的插入删除是 O(1)，但找到插入位置可能需要 O(n) 的遍历。而且链表的内存分散，缓存局部性差，遍历速度远不如 vector。实际选择时要基于场景。
unique 只移除连续的重复
如果希望移除所有重复元素，需要先排序
8. 小结
-
list 是双向链表，头尾操作和任意位置插入删除极快。
-
不支持随机访问，没有 []，遍历速度不如 vector。
-
自带 sort、merge、reverse、splice、remove、unique 等高效成员函数。
-
插入删除不导致其他迭代器失效，这是它的重要安全优势。
-
选择合适的容器：需要随机访问用 vector，频繁中间插入删除用 list。
可以这样理解：vector 是你的瑞士军刀，list 是你的手术刀——各有专长。
