C++ forward_list怎么用 C++单向链表容器特性分析【STL】

forward_list 比 list 更轻量，因其仅存储后继指针、无前驱指针和 size 缓存，节省内存且插入删除为 O(1)，但不支持反向遍历、随机访问及 O(1) size 查询。

forward_list 为什么比 list 更轻量

forward_list 是 C++11 引入的单向链表容器，底层只存后继指针，不存前驱，也不维护 size 计数器。这意味着它比 list 节省内存（每个节点少一个指针），插入删除常数时间，但无法反向遍历，也不能直接调用 size()——调用会触发 O(n) 遍历计数。

适用场景：频繁在头部/中间插入删除、内存敏感、不需要随机访问或逆序迭代。

• forward_list 构造后为空，empty() 返回 true，size() 不推荐用（C++11 默认不缓存长度）
• 不支持 operator[]、at()、begin() + n 这类随机访问操作
• 迭代器是单向的：forward_list::iterator 只能 ++，不能 --

insert_after 和 erase_after 是核心操作接口

forward_list 没有 insert() 或 erase() 的“位置版”，所有修改都基于“某节点之后”——因为没有前驱指针，无法从当前位置安全定位前一个节点。所以必须用 before_begin() 获取逻辑头前哨，再配合 insert_after() / erase_after()。

常见错误：直接对 begin() 调用 insert_after() 会编译失败；正确做法是用 before_begin() 作为锚点。

立即学习“C++免费学习笔记（深入）”；

BlackBox AI

AI编程助手，智能对话问答助手

下载

• 在开头插入：fl.insert_after(fl.before_begin(), 42);
• 在 pos 后插入：fl.insert_after(pos, val);（注意 pos 是合法迭代器，不是 end()）
• 删除 pos 后节点：fl.erase_after(pos);（pos 不能是 end()，也不能是最后一个有效节点的迭代器）
• 清空全部（除哨兵）：fl.erase_after(fl.before_begin(), fl.end());

splice_after 实现高效节点转移

splice_after() 是 forward_list 独有的零拷贝拼接操作，把另一个 forward_list 的节点块“剪切”到当前链表某位置之后。不调用元素构造/析构，仅改指针，性能远优于 insert+erase 组合。

注意参数顺序和范围语义：目标位置是 to_pos，被移动的范围是 [from_first, from_last)，且两个容器类型必须一致。

• 把 other 全部接在 fl 开头：fl.splice_after(fl.before_begin(), other);
• 把 other 中 [it1, it2) 段接在 fl 的 pos 后：fl.splice_after(pos, other, it1, it2);
• other 在 splice 后变为空（除非只移动了部分节点）

遍历时小心迭代器失效和边界条件

forward_list 的迭代器在插入/删除时，只有被操作位置附近的迭代器可能失效——具体来说：insert_after(p, ...) 不会使任何迭代器失效；erase_after(p) 仅使被删节点的迭代器失效，p 本身仍有效。但新手常踩的坑是误用 end() 做 erase_after() 参数，或在循环中边遍历边删却没保存 next。

• 安全删除所有偶数：

  auto prev = fl.before_begin();
  auto curr = fl.begin();
  while (curr != fl.end()) {
      if (*curr % 2 == 0) {
          curr = fl.erase_after(prev); // erase_after 返回被删节点的下一个
      } else {
          prev = curr;
          ++curr;
      }
  }

• 遍历不要写 for (auto it = fl.begin(); it != fl.end(); ++it) 后在循环体内删节点——++it 可能解引用已释放内存
• before_begin() 返回的是特殊迭代器，不能解引用（*fl.before_begin() 未定义）