c++ list容器用法_c++双向链表操作教程_技术教程

std::list是双向链表，不支持随机访问和下标操作，仅通过迭代器、front/back访问；插入删除为O(1)（需有效迭代器），splice实现零拷贝节点转移，迭代器仅在所指节点被erase时失效。

std::list 是双向链表，不是数组或 vector

很多人一看到 std::list 就默认它像 std::vector 一样支持随机访问，结果写 my_list[5] 直接编译失败。它底层是带头结点的双向链表，只支持顺序遍历，operator[] 根本不存在。

真正能用的访问方式只有迭代器：begin()、end()、front()、back()。想取第 N 个元素？得用 std::next(it, n)，时间复杂度 O(n)，不是 O(1)。

别对 std::list 做下标访问 —— 没这个接口，编译不过
插入/删除任意位置是 O(1)，但前提是已有合法迭代器（比如从 find 得到）
size() 在 C++11 及以后是 O(1)，但某些老标准库实现仍是 O(n)，别依赖它做高频判断

insert 和 erase 必须传迭代器，不能传下标或值

std::list::insert 第一个参数永远是「插入位置的迭代器」，不是整数索引；erase 同理，删的是迭代器指向的节点，不是某个值。

常见错误：想删掉所有值为 5 的节点，却写成 my_list.erase(5) —— 这会尝试把整数 5 当作迭代器，编译报错：no matching function for call to 'std::list::erase(int)'。

删值要用 remove()（会擦除所有匹配值）或 remove_if()
删单个节点必须先 find() 得到迭代器，再传给 erase()
insert() 返回新插入元素的迭代器，可用于连续插入

std::list lst = {1, 2, 3};
auto it = std::find(lst.begin(), lst.end(), 2);
if (it != lst.end()) {
    lst.erase(it); // 正确：删迭代器
}
// 错误示例（注释掉）：
// lst.erase(2); // 编译失败

splice 转移节点不拷贝，是 list 独有高效操作

splice 是 std::list 最容易被忽略也最有价值的成员函数：它把另一个 list 的节点「剪切粘贴」过来，不调用构造/析构函数，零拷贝，O(1) 时间完成。

对比 merge 或手写循环 push_back：后者会逐个拷贝元素，触发多次内存分配和构造；而 splice 只改几个指针。

splice(pos, other)：把 other 全部移到 pos 前面
splice(pos, other, it)：只移一个节点
splice(pos, other, first, last)：移一段（[first, last)）
被转移的 other 会变为空，且原迭代器仍有效（因为节点没动，只是换主人）

std::list a = {1, 2}, b = {3, 4};
a.splice(a.end(), b); // a 变成 {1,2,3,4}，b 变成空
// 此时 b.empty() == true，且 b.size() == 0

迭代器失效规则比 vector 简单，但仍有陷阱

std::list 迭代器只在它所指的节点被 erase 时才失效；插入、拼接、排序等操作都不会让其他迭代器失效 —— 这是它比 std::vector 安全的地方。

但注意两个坑：

remove() 和 unique() 不会失效迭代器，但它们内部会调用 erase()，所以你手动保存的、指向被删元素的迭代器会失效
跨容器操作时，比如用 splice 把节点从 A 移到 B，原属于 A 的迭代器在 A 中失效，在 B 中依然有效 —— 但你得确保自己没把它当 A 的迭代器继续用
不要在循环中边 erase 边用 ++it，正确写法是 it = lst.erase(it)（erase 返回下一个有效迭代器）