forward_list是单向链表，头文件<forward_list>。
特点：只能正向遍历，插入/删除操作 O(1)，极致省内存（比list少一个指针）。
注意：无size()，无push_back/pop_back，无反向迭代器。
一、核心特点
| 项目 | 说明 |
|---|---|
| 底层 | 单向链表（每个节点只有 next 指针） |
| 迭代器 | 正向迭代器（只能 ++，不能 --） |
| 内存 | 比 list 省一个指针 |
| 优势 | 插入/删除 O(1)，内存占用小 |
| 劣势 | 无 size()，不能反向遍历，只能在头部和指定位置之后操作 |
💡 所有“在 pos 之前”的操作变为“在 pos 之后”（
_after后缀）。
二、声明与初始化
#include <forward_list>
using namespace std;
forward_list<int> L; // 空
forward_list<int> L(5, 10); // 5个10
forward_list<int> L{1,2,3}; // 初始化列表
forward_list<int> L(beg, end); // 迭代器区间
forward_list<int> L2(L1); // 拷贝三、元素访问（只有头部）
| 操作 | 说明 | 时间复杂度 |
|---|---|---|
L.front() | 第一个元素 | O(1) |
❌ 无
back()，要访问尾部需遍历。
四、插入操作
| 操作 | 示例 | 时间复杂度 |
|---|---|---|
| 头插 | L.push_front(10); | O(1) |
| 指定位置之后插入 | L.insert_after(it, 30); | O(1) |
| 插入 n 个相同值 | L.insert_after(it, 3, 5); | O(k) |
| 头构造插入 | L.emplace_front(args...); | O(1) |
| 指定位置之后构造 | L.emplace_after(it, args...); | O(1) |
emplace vs push：
emplace直接传递构造参数，避免临时对象拷贝。
⚠ 注意insert_after和emplace_after是在迭代器之后插入，不是之前。
forward_list<int> L{1,2,3};
auto it = L.begin(); // 指向1
L.insert_after(it, 99); // 1,99,2,3
L.emplace_after(it, 100); // 1,100,99,2,3五、删除操作
| 操作 | 时间复杂度 |
|---|---|
L.pop_front() | O(1) |
L.erase_after(it) — 删除 it 之后的节点 | O(1) |
L.erase_after(beg, end) — 删除 (beg, end) 区间 | O(k) |
L.remove(val) — 删除所有等于 val 的节点 | O(n) |
L.remove_if(pred) | O(n) |
L.clear() | O(n) |
注意
erase_after不能删除第一个节点（用pop_front），也没有erase直接删除当前节点。
六、大小相关
| 操作 | 时间复杂度 |
|---|---|
L.empty() | O(1) |
L.max_size() | O(1) |
⚠
forward_list不提供size()成员函数（C++11 起标准未要求，通常实现为无）。若要获取长度需遍历 O(n)。
七、迭代器操作（均 O(1)）
| 操作 | 说明 |
|---|---|
L.begin() | 指向第一个元素 |
L.end() | 尾后迭代器 |
L.cbegin() / L.cend() | 常量迭代器 |
L.before_begin() | 指向“首元素之前”的占位迭代器（用于在头部之前插入） |
💡
before_begin()是forward_list特有的，配合insert_after可实现头插效果：L.insert_after(L.before_begin(), val)等价于L.push_front(val)。
八、高级操作
| 操作 | 说明 | 时间复杂度 |
|---|---|---|
L.splice_after(pos, other) | 将 other 全部移到 pos 之后 | O(1) |
L.splice_after(pos, other, it) | 将 other 中 it 之后的节点移到 pos 之后 | O(1) |
L.splice_after(pos, other, beg, end) | 将 other 的 (beg, end) 移到 pos 之后 | O(1) |
L.sort() / L.sort(cmp) | 排序 | O(n log n) |
L.merge(other) | 合并两个已排序链表，other 清空 | O(n+m) |
L.unique() | 移除连续重复元素 | O(n) |
L.reverse() | 反转链表 | O(n) |
L.assign(n,val) / L.assign(beg,end) | 替换内容 | O(n) |
L.swap(other) | 交换内容 | O(1) |
注意所有
splice_after操作都是“移动到指定位置之后”，参数中的迭代器也指向“之前”的位置。
九、时间复杂度速查表
| 操作 | 复杂度 |
|---|---|
push_front, pop_front, insert_after, erase_after(单节点), emplace_* | O(1) |
empty, begin, end, front, before_begin | O(1) |
splice_after（任意形式） | O(1) |
remove, remove_if, reverse, unique | O(n) |
sort | O(n log n) |
merge | O(n+m) |
clear, assign, erase_after(区间) | O(n) |
获取 size()（需自己遍历） | O(n) |