C++ std::forward_list用法 _ 单向链表性能优势与操作限制【详解】

std::forward_list 为什么不能用 size()？

问题出在它的设计定位上——std::forward_list 追求的是极致轻量，标准委员会明确要求 size() 必须是 O(1) 复杂度，但维护一个实时更新的计数器，会在每次插入、删除时增加额外开销，哪怕是加 1 或减 1，也违背了它的“零开销”原则。所以，它干脆不存这个字段。

真要获取长度，只能用 std::distance(fl.begin(), fl.end()) 从前往后数一遍，复杂度自然是 O(n)。如果你频繁需要长度，那说明 std::forward_list 不是你的菜，该换 std::list 或 std::vector 了。

• 得注意，别在循环里反复调用 std::distance，那会直接引发性能雪崩。
• 如果只是判断是否为空，用 fl.empty()——这是 O(1) 的，千万别用 distance 去判断空。
• 有些编译器，比如 libstdc++，提供了非标准的 __size() 扩展，但这不是标准行为，别依赖它。

insert_after 和 erase_after：唯一合法的增删位置

std::forward_list 没有 insert()、erase() 这种“随机位置”操作接口，除了 push_front()。所有中间插入和删除，都必须通过 insert_after() 和 erase_after()，并且参数必须是一个有效的迭代器——指向某个节点，而不是 end()。

原因很简单，单向链表没有 prev 指针，你没法从后往前找前驱节点。比如你想在第 3 个元素后插入，那得先遍历到第 3 个，再执行 insert_after()。

• fl.insert_after(fl.before_begin(), val) 等价于 push_front()。
• fl.erase_after(fl.before_begin()) 删除首节点，等价于 pop_front()。
• 把 fl.end() 传给 erase_after() 是未定义行为——它不是一个有效节点。
• 想删第 n 个？先用 std::next(it, n-1) 走到前一个节点，再执行 erase_after()。

splice_after()：这才是它的核心优势

std::forward_list 不支持像 std::list::splice() 那样直接把另一容器的整段节点“摘下来”接过来——它只有 splice_after()，并且只能拼接另一个 forward_list 的一段（从某位置开始到结尾，或指定范围）。

但拼接本身是真正的 O(1) 指针操作——不拷贝元素，不调用构造析构，只改几个 next 指针。这在需要高频重组链表的场景，比如 LRU 缓存淘汰、任务队列迁移，就是不可替代的性能优势。

• dst.splice_after(pos, src)：把整个 src 拼到 dst 中 pos 后面，src 变空。
• dst.splice_after(pos, src, it)：把 src 中 it 指向的节点移到 dst 的 pos 后。
• src 和 dst 必须是同一类型，且不能是自身（自拼接是未定义行为）。
• 注意：splice_after() 不影响被移动元素的值，但会使迭代器失效（在原属容器中失效）。

和 std::list / std::vector 对比时的关键取舍点

选 std::forward_list 不是因为它“快”，而是因为它“最省”——内存占用最小（每个节点只存一个 next 指针），插入/删除首部最快（O(1) 且无内存分配），并且允许常数时间拼接。但代价也很实在：不能反向遍历、不能随机访问、不能高效查长度、没有 begin() - 1 这种前驱能力。

• 如果你需要 operator[] 或 at()，直接排除它。
• 如果你常做 find_if 后立刻删，forward_list 比 list 多一次遍历（先 find，再 next 找前驱），不如 list 直接。
• 如果容器生命周期短、节点少、且主要操作是头插/头删/拼接（比如解析 token 流、临时构建链式结构），它就是最优解。
• 别以为“听说链表快”就盲目用它——在缓存友好的场景下，vector 的 push_back + erase(remove_if) 往往更快。

它的存在意义不是通用替代，而是精准解决一类低开销链式操作问题。用错地方，代价比想象中大。