C++ list容器使用教程｜双向链表详解

list 不能用 {} 直接赋值因 initializer_list 构造函数为 explicit；插入删除仅使被操作节点迭代器失效；sort 不接受普通函数指针因不可默认构造；适用场景限于频繁中间增删且无需随机访问。

list 的构造和初始化为什么不能用 {} 直接赋值？

因为 std::list 在 C++11 之前不支持统一初始化语法，即使你用的是 C++11 或更高标准，list 的 initializer_list 构造函数是显式（explicit）的，编译器不会自动把 {1,2,3} 转成 list。直接写 list l = {1,2,3}; 在部分老编译器（比如 GCC 4.8）会报错，或触发隐式转换警告。

实操建议：

• 用构造函数显式初始化：list l{1,2,3};（C++11+，推荐）
• 老代码兼容写法：list l((initializer_list{1,2,3}));（括号套括号防解析歧义）
• 避免在模板上下文中依赖 auto 推导 + 大括号，比如 auto l = {1,2,3}; 得到的是 std::initializer_list，不是 list

insert / erase 后迭代器失效规则和指针还能用吗？

std::list 是双向链表，这是它和 vector 最关键的区别：插入、删除任意位置的元素，**只有被操作的那个节点的迭代器失效，其余全部保持有效**。这意味着你可以一边遍历一边删满足条件的元素，不用像 vector 那样担心迭代器崩掉。

但要注意：

• erase(it) 返回的是下一个有效迭代器（C++11 起），所以安全写法是：it = l.erase(it);，而不是 l.erase(it++);
• 指向被删节点的裸指针（int* p = &(*it);）在 erase 后立即悬空，不能再解引用
• splice 操作不拷贝元素，只改指针，所有源 list 和目标 list 的迭代器全都不失效

list::sort 为什么不能传普通函数指针做比较器？

list::sort() 是容器自带的成员函数，它要求比较器必须是可默认构造、可拷贝的类型——普通函数指针不满足“可默认构造”（函数指针没有默认构造函数），所以 l.sort(my_cmp); 在某些编译器下会编译失败，尤其是开启严格模板检查时。

正确做法：

• 用 lambda（带空捕获）：l.sort([](int a, int b) { return a > b; });
• 用函数对象（functor）：struct Greater { bool operator()(int a, int b) const { return a > b; } };，然后 l.sort(Greater{});
• 别用 std::sort(l.begin(), l.end(), ...) —— 这会退化成 O(n log n) 随机访问开销，list 不支持随机迭代器，编译不过

什么时候该用 list 而不是 vector 或 deque？

不是“链表听起来高级就用 list”，真实项目里 list 使用频率远低于 vector。它的优势只在一种场景：**需要频繁在中间（非尾部）做插入/删除，且不关心缓存局部性、也不需要随机访问**。

典型适用场景：

• 实现 LRU 缓存：用 list 存数据 + unordered_map 存 key→iterator 映射，splice 移动节点到头部，O(1)
• 多线程中某个线程只 append，另一个只 pop_front，且需保证顺序，list 的首尾操作都是 O(1)
• 要保留大量中间迭代器，并持续修改容器内容（比如图形编辑器中的图层列表）

反例：只要涉及下标访问、二分查找、内存连续性（如传给 OpenGL/Vulkan 的顶点数组），立刻换 vector。

真正容易被忽略的点是：list 每个节点额外占用两个指针大小内存（通常 16 字节），小对象（如 int）时内存开销翻几倍，cache miss 高得离谱。性能敏感代码里，先测再选。