103 std::forward_list (单向链表)
作者Lou Xiao, deepseek创建时间2025-04-02 17:40:46更新时间2025-04-02 17:40:46
1. 基本概念
1.1 定义与特性
- 单向链表：每个元素只指向下一个元素，没有指向前一个元素的指针
- 头节点：包含指向第一个元素的指针
- STL容器：C++标准模板库中的序列容器
- 内存效率：比
std::list更节省内存（每个节点少一个指针）
1.2 时间复杂度
| 操作 | 时间复杂度 |
|---|---|
| 插入/删除已知位置 | O(1) |
| 随机访问 | O(n) |
| 查找 | O(n) |
2. 基本操作
2.1 包含头文件
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <forward_list>
2.2 声明与初始化
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::forward_list<int> fl1; // 空链表
2
std::forward_list<int> fl2(5, 10); // 5个元素，每个都是10
3
std::forward_list<int> fl3 = {1, 2, 3}; // 初始化列表
4
std::forward_list<int> fl4(fl3); // 拷贝构造
5
std::forward_list<int> fl5(fl4.begin(), fl4.end()); // 范围构造
2.3 元素访问
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
front(); // 访问第一个元素
2
// 没有back(), at(), operator[]等方法
3. 迭代器
3.1 迭代器类型
- iterator：可读写
- const_iterator：只读
3.2 获取迭代器
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
before_begin(); // 返回第一个元素之前的迭代器
2
begin(); // 返回第一个元素的迭代器
3
end(); // 返回尾后迭代器
4
cbefore_begin(); // const版本
5
cbegin(); // const版本
6
cend(); // const版本
4. 容量操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
empty(); // 判断是否为空
2
max_size(); // 返回可能的最大元素数量
3
// 没有size()方法，因为计算size()是O(n)操作
5. 修改操作
5.1 插入操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
push_front(const T& value); // 头部插入
2
emplace_front(Args&&... args); // 头部构造插入
3
4
insert_after(pos, value); // 在pos之后插入
5
insert_after(pos, count, value);// 插入count个value
6
insert_after(pos, first, last); // 插入范围
7
insert_after(pos, {list}); // 插入初始化列表
8
9
emplace_after(pos, args...); // 在pos之后构造插入
5.2 删除操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
pop_front(); // 删除头部元素
2
3
erase_after(pos); // 删除pos之后的元素
4
erase_after(first, last); // 删除范围
5
6
clear(); // 清空链表
5.3 其他修改
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
resize(count); // 调整大小
2
resize(count, value); // 调整大小并用value填充
3
4
swap(other); // 交换两个链表内容
5
6
merge(other); // 合并两个有序链表
7
merge(other, comp); // 带比较函数的合并
8
9
sort(); // 排序
10
sort(comp); // 带比较函数的排序
11
12
reverse(); // 反转链表
13
14
unique(); // 删除连续重复元素
15
unique(pred); // 带谓词的unique
16
17
remove(value); // 删除所有等于value的元素
18
remove_if(pred); // 删除满足谓词的元素
6. 特殊操作
6.1 拼接操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
splice_after(pos, other); // 移动other所有元素
2
splice_after(pos, other, it); // 移动other中it之后的元素
3
splice_after(pos, other, first, last); // 移动other中范围
6.2 比较操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
operator==, !=, <, <=, >, >= // 按字典序比较
7. 使用示例
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <forward_list>
3
#include <algorithm>
4
5
int main() {
6
// 创建并初始化
7
std::forward_list<int> fl = {1, 2, 3, 4, 5};
8
9
// 在头部插入
10
fl.push_front(0);
11
12
// 遍历
13
for (auto it = fl.begin(); it != fl.end(); ++it) {
14
std::cout << *it << " ";
15
}
16
std::cout << "\n";
17
18
// 删除第二个元素
19
auto it = fl.begin();
20
fl.erase_after(it);
21
22
// 使用算法
23
fl.remove_if([](int n){ return n > 3; });
24
25
// 排序
26
fl.sort(std::greater<int>());
27
28
// 范围for遍历
29
for (int n : fl) {
30
std::cout << n << " ";
31
}
32
33
return 0;
34
}
8. 注意事项
- 没有size()：因为计算size()需要遍历整个链表，是O(n)操作
- 插入删除位置：所有插入删除操作都是基于"after"的
- 迭代器失效：
- 插入操作不会使任何迭代器失效
- 删除操作只会使被删除元素的迭代器失效
- 内存局部性：不如vector/array，因为元素分散在内存各处
- 适用场景：
- 需要频繁在头部插入/删除
- 内存受限环境
- 不需要随机访问
- 需要中间频繁插入/删除
9. 性能比较
| 操作 | forward_list | list | vector | deque |
|---|---|---|---|---|
| 头部插入 | O(1) | O(1) | O(n) | O(1) |
| 尾部插入 | O(n) | O(1) | O(1) | O(1) |
| 中间插入 | O(1) | O(1) | O(n) | O(n) |
| 随机访问 | O(n) | O(n) | O(1) | O(1) |
| 内存开销 | 最小 | 较大 | 最小 | 中等 |
std::forward_list 常用 API 的整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
push_front | 在链表头部插入元素 | void push_front(const T& value);void push_front(T&& value); | cpp<br>std::forward_list<int> list;<br>list.push_front(42);<br> | 插入后，新元素成为第一个元素。 |
emplace_front | 在头部直接构造元素（避免拷贝） | template<class... Args> void emplace_front(Args&&... args); | cpp<br>list.emplace_front(42); // 直接构造<br> | 更高效，适合复杂对象。 |
pop_front | 删除头部元素 | void pop_front(); | cpp<br>list.pop_front();<br> | 若链表为空，行为未定义。 |
insert_after | 在指定位置后插入元素 | iterator insert_after(const_iterator pos, const T& value); | cpp<br>auto it = list.insert_after(list.before_begin(), 10);<br> | 返回指向新元素的迭代器。pos 必须有效。 |
emplace_after | 在指定位置后直接构造元素 | template<class... Args> iterator emplace_after(const_iterator pos, Args&&... args); | cpp<br>list.emplace_after(it, 20);<br> | 类似 insert_after，但避免临时对象拷贝。 |
erase_after | 删除指定位置后的元素 | iterator erase_after(const_iterator pos); | cpp<br>it = list.erase_after(list.before_begin());<br> | 返回被删除元素的下一个元素的迭代器。 |
clear | 清空链表 | void clear() noexcept; | cpp<br>list.clear();<br> | 删除所有元素，保持 forward_list 为空。 |
splice_after | 将另一个链表的元素移动到当前链表 | void splice_after(const_iterator pos, forward_list& other); | cpp<br>list1.splice_after(list1.before_begin(), list2);<br> | 将 other 的所有元素移动到 pos 之后，other 变为空。 |
remove | 删除所有等于指定值的元素 | void remove(const T& value); | cpp<br>list.remove(42);<br> | 遍历链表，删除所有匹配项。 |
remove_if | 删除满足条件的元素 | template<class Predicate> void remove_if(Predicate pred); | cpp<br>list.remove_if([](int x) { return x % 2 == 0; });<br> | 对每个元素调用 pred，删除返回 true 的元素。 |
unique | 删除连续重复元素 | void unique(); | cpp<br>list.unique();<br> | 仅保留连续相同元素的第一个。 |
sort | 对链表排序（默认升序） | void sort();template<class Compare> void sort(Compare comp); | cpp<br>list.sort();<br>list.sort(std::greater<int>());<br> | 稳定排序，时间复杂度为 O(n log n)。 |
merge | 合并两个已排序链表 | void merge(forward_list& other); | cpp<br>list1.merge(list2); // list1 和 list2 必须已排序<br> | 合并后 other 为空，结果链表保持有序。 |
reverse | 反转链表顺序 | void reverse() noexcept; | cpp<br>list.reverse();<br> | 操作后，原第一个元素变为最后一个。 |
before_begin | 获取头节点前驱的迭代器 | iterator before_begin() noexcept; | cpp<br>auto it = list.before_begin();<br> | 用于在链表头部插入元素（配合 insert_after）。 |
empty | 检查链表是否为空 | bool empty() const noexcept; | cpp<br>if (list.empty()) { /* ... */ }<br> | 返回 true 表示链表为空。 |
max_size | 返回链表可容纳的最大元素数量 | size_type max_size() const noexcept; | cpp<br>size_t max = list.max_size();<br> | 由系统或库实现限制。 |
关键特性说明：
- 单向性：
forward_list仅支持单向遍历，无size()方法（需手动计算）。 - 迭代器失效：插入/删除操作通常只影响被操作节点及其相邻节点的迭代器。
- 性能：所有操作均为 O(1) 或 O(n)，适合频繁插入/删除场景。
文章目录