17370845950

std::forward_list 是 C++11 引入的轻量单向链表，仅支持前向遍历和头/指定位置插入（无 push_back），内存开销小于 list，size() 在 C++17 前非 O(1)，推荐用 empty() 判空，适用于内存敏感、高频头插删场景。

std::forward_list 是 C++11 引入的单向链表容器，底层基于单链表实现，只支持前向遍历（从头到尾），不提供随机访问、也不保存尾指针，因此内存开销比 std::list 更小，插入/删除操作常数时间，但不支持 size()（C++11 中无 O(1) 大小记录，需手动计数或遍历）。

初始化和基本操作

声明方式与其它 STL 容器类似，但注意它没有 push_back()（因为无尾指针），只能在头部或指定位置前插入：

• std::forward_list fl = {1, 2, 3}; —— 初始化列表构造
• fl.push_front(0); —— 头部插入，O(1)
• fl.emplace_front(42); —— 原地构造插入头部
• fl.insert_after(fl.before_begin(), 99); —— 在开头前插入（即变成新头）
• auto it = fl.begin(); ++it; fl.insert_after(it, 55); —— 在第二个元素后插入

遍历和访问元素

只能用前向迭代器，且不支持 operator[] 或 at()：

• 正向遍历：用 for (auto it = fl.begin(); it != fl.end(); ++it) 或范围 for（for (int x : fl)）
• 获取首元素：用 fl.front()（非空时安全），无 back() 成员函数
• 判断为空：用 fl.empty()，不能依赖 fl.size() == 0（因 C++11 标准中 size() 是线性复杂度，部分实现可能未提供；C++17 起要求 size() 为 O(1)，但可移植代码仍建议用 empty() 判空）

删除和修改操作

所有删除都通过迭代器完成，注意迭代器失效规则（仅被删节点迭代器失效，其余有效）：

• fl.pop_front(); —— 删除首元素
• fl.erase_after(it); —— 删除 it 所指节点的下一个节点（it 必须合法且非 end()）
• fl.erase_after(fl.before_begin(), fl.end()); —— 清空全部（等价于 fl.clear()）
• 批量删除满足条件的元素：fl.remove_if([](int x) { return x % 2 == 0; });
• 去重（相邻重复）：fl.unique();（需先排序）

与其他链表对比和使用建议

std::forward_list 的设计目标是极致轻量，适合对内存敏感、频繁头插/头删、且不需要反向遍历或快速获取长度的场景：

• 比 std::list 节省约一个指针大小的内存（每个节点只存 next，不存 prev）
• 不支持 reverse_iterator、splice()（但有 splice_after()）、merge()（但有 merge()，要求已排序）
• 若需要尾部操作频繁，应考虑 std::deque 或自行维护尾指针的封装
• 若需频繁查长度，可额外维护一个 size_t 计数器，或改用 std::list/std::vector