17370845950

std::list是双向链表，支持O(1)任意位置增删但不支持随机访问；初始化方式多样，操作依赖迭代器，提供splice、merge、sort等高效特有方法。

C++ 的 std::list 是标准库提供的双向链表容器，底层不连续存储，支持高效地在任意位置插入、删除（O(1)），但不支持随机访问（不能用下标 [] 或 at() 直接取第 n 个元素）。

初始化和基本操作

创建 list 有多种方式：

• std::list lst; —— 空链表
• std::list lst = {1, 2, 3, 4}; —— 初始化列表构造（C++11 起）
• std::list lst(5, 10); —— 创建含 5 个值为 10 的元素
• std::list lst2(lst1); —— 拷贝构造

常用增删改查方法

所有操作都基于迭代器，没有下标访问：

• lst.push_front(x) —— 头插
• lst.push_back(x) —— 尾插
• lst.insert(it, x) —— 在迭代器 it 指向位置前插入（返回新元素迭代器）
• lst.erase(it) —— 删除 it 指向的单个元素（返回后继迭代器）
• lst.erase(first, last) —— 删除 [first, last) 区间
• lst.pop_front() / lst.pop_back() —— 删除首/尾元素（不返回值）
• lst.front() / lst.back() —— 获取首/尾元素引用（容器非空时才安全）

遍历与查找

只能用迭代器或范围 for 循环：

• 传统迭代器遍历：
  for (auto it = lst.begin(); it != lst.end(); ++it) { cout
• 范围 for（推荐）：
  for (const auto& x : lst) { cout
• 查找需手动循环或用 std::find：
  auto it = std::find(lst.begin(), lst.end(), 5); —— 返回第一个值为 5 的迭代器，未找到则为 end()

特殊操作与注意事项

list 提供了一些普通序列容器没有的高效操作：

• lst.splice(pos, other_lst) —— 把 other_lst 全部“剪切粘贴”到 pos 前（O(1)，不复制元素）
• lst.splice(pos, other_lst, it) —— 移动 other_lst 中 it 指向的单个节点
• lst.merge(other_lst) —— 合并两个已排序的 list（会清空 other_lst）
• lst.sort() —— 对本 list 排序（比 std::sort 更高效，因是链表）
• lst.remove(x) —— 删除所有等于 x 的元素
• lst.remove_if(pred) —— 删除满足谓词 pred 的元素
• 注意：插入/删除后，除被操作位置外，其他迭代器通常仍有效（这是 list 的优势）

不复杂但容易忽略：list 的 size() 在 C++11 前是 O(n)，C++11 起保证是 O(1)；频繁按位置访问（如要第 5 个元素）应考虑换用 vector 或 deque。