empty() 是唯一可移植、O(1)、不崩溃的空判断方式;size() 在 C++17 前非强制 O(1),libstdc++ 多数版本仍为遍历实现,易致性能退化或编译失败。

别用 size() 判空,也别指望它快;empty() 才是唯一可移植、O(1)、不崩溃的空判断方式。如果你正因 std::forward_list 性能掉坑、迭代器误删、拼接变慢而卡住,问题大概率出在这三个地方:判空逻辑、前驱参数理解、splice_after() 的使用姿势。
为什么 size() 不能信,empty() 才是铁律
std::forward_list::size() 在 C++17 前标准只要求“可实现为 O(1)”,但 libstdc++(GCC 默认)至今多数版本仍用 std::distance(begin(), end()) 实现——每次调就是一次全链表遍历。你写 if (fl.size() == 0),轻则性能退化,重则在旧版嵌入式 STL 上编译失败或返回垃圾值。
- 永远用
fl.empty()替代所有fl.size() == 0、!fl.size()或fl.size() > 0 - 真要长度且只用一次:写
auto len = std::distance(fl.begin(), fl.end());,存局部变量复用 - 高频访问长度(如 LRU 计数器):手动维护一个
size_t m_size,并在每次push_front()、insert_after()、erase_after()后同步增减 - 禁止在循环条件里写
for (size_t i = 0; i —— 这是典型的 O(n²) 隐患
insert_after() 和 erase_after() 的参数到底指谁
这两个函数的操作对象永远是「参数迭代器所指节点的下一个节点」,不是参数本身。这是单向链表无法回溯的硬约束,不是 API 设计疏漏。传错迭代器(比如 fl.begin() 或 fl.end())直接触发未定义行为。
- 头插唯一安全写法:
fl.insert_after(fl.before_begin(), val),或更简洁的fl.push_front(val) - 删首节点必须用:
fl.erase_after(fl.before_begin()),等价于fl.pop_front();传fl.begin()会删第二个元素 - 删第 n 个元素(n ≥ 1):
auto prev = std::next(fl.before_begin(), n - 1); fl.erase_after(prev); - 遍历时删当前匹配节点:初始化
auto prev = fl.before_begin();,循环内用auto curr = std::next(prev);定位,匹配后执行prev = fl.erase_after(prev);跳过被删节点
什么时候必须用 splice_after() 而不是循环插入
splice_after() 是 std::forward_list 唯一真正 O(1) 的物理拼接操作:不调用构造/析构、不分配内存、只改 next 指针。任何用 insert_after() 循环拷贝、或先 push_front() 再反转的做法,都会让内存和性能优势彻底归零。
立即学习“C++免费学习笔记(深入)”;
- 整体迁移:
dst.splice_after(pos, src),src变为空,dst在pos后接上全部节点 - 单节点迁移:
dst.splice_after(pos, src, it),把src中it所指节点移到dst的pos后 - 范围迁移:
dst.splice_after(pos, src, first, last),仅拼接[first, last)左闭右开区间 - 禁止自拼接:
fl.splice_after(fl.before_begin(), fl)是未定义行为;src和dst必须是不同对象
最常被忽略的一点:std::forward_list 不是 std::list 的“瘦身版”,它是有明确取舍的专用工具。一旦你需要尾部操作、反向遍历、随机索引访问,或者节点里存的是 std::string 这类大对象,那省下的 8 字节 next 指针就毫无意义——该换容器就换,别硬扛。


















