c++oding="utf-8" ?>
应使用 empty() 判空、迭代器遍历替代 size() 循环;insert_after/erase_after 操作目标为参数节点的下一节点;splice_after 是唯一 o(1) 节点搬运操作;仅在纯前向操作且值类型小时 std::forward_list 才具优势。

别用 size() 判空或做循环条件,它在多数真实环境里是 O(n);empty() 才是唯一可移植、O(1)、始终安全的选择。
为什么 size() 在 std::forward_list 里不能信
标准允许 size() 是 O(n),而 libstdc++(GCC 默认 STL)至今不维护计数器——每次调用都遍历全链表。MSVC 或 libc++ 可能返回 O(1),但你没法保证部署环境。更糟的是:某些裁剪版 STL 根本没实现 size(),编译可能过,运行时却崩溃或返回垃圾值。
- 写
if (fl.size() == 0)→ 改成if (fl.empty()) - 写
for (size_t i = 0; i → 性能直接退化成 O(n²),必须重写为迭代器遍历 - 真需要长度且高频?自己加一个
size_t count,每次push_front()、insert_after()、erase_after()后手动同步 - 临时查一次长度?用
std::distance(fl.begin(), fl.end()),只调一次
insert_after() 和 erase_after() 的参数到底指谁
它们操作的永远是「参数迭代器所指节点的下一个节点」,不是参数本身。这是单向链表无法反查前驱的硬约束,不是 API 设计失误。
- 头插唯一安全写法:
fl.insert_after(fl.before_begin(), x);传fl.begin()是错的,传fl.end()是未定义行为 - 删首元素:
fl.erase_after(fl.before_begin())(等价于pop_front());传fl.begin()会删第二个元素 - 删第 n 个元素(n ≥ 1):先
auto prev = std::next(fl.before_begin(), n - 1),再fl.erase_after(prev);注意是 n−1,不是 n - 边遍历边删当前节点?必须用
it = fl.erase_after(it)接收返回值,它自动跳过被删节点
splice_after() 是唯一真正 O(1) 的节点搬运操作
它不构造、不析构、不分配内存,只改 next 指针——这是 std::forward_list 唯一不可替代的性能优势。其他所有“拼接”方式(比如循环 push_front())都会触发 n 次内存操作,彻底毁掉内存节省的意义。
-
dst.splice_after(pos, src):把整个src拼到dst的pos后,src变空;src和dst必须是不同对象 -
dst.splice_after(pos, src, it):只把src中it指向的单个节点移到dst的pos后 -
dst.splice_after(pos, src, first, last):拼接[first, last)范围(左闭右开) - LRU 缓存中把命中节点提到头部:
fl.splice_after(fl.before_begin(), fl, it),但要注意:自拼接(fl.splice_after(..., fl))是未定义行为
它的内存优势只在节点量大、值类型小(如 int、char*)、且操作模式严格匹配(纯前向、高频头插/删、无尾部需求)时才成立;一旦需要 back()、at()、反向遍历或频繁查长度,就该立刻换 std::list 或带计数器封装的容器——硬撑只会让代码越来越难维护,还省不出几 MB 内存。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











