C++ 容器 forward_list
关键要点
<forward_list>是 C++11 引入的单向链表容器，适合需要高效插入和删除的场景。- 它比双向链表
std::list更节省内存，但不支持随机访问和反向遍历。 - 研究表明，它在需要向前遍历且内存效率重要时是理想选择。
简介
<forward_list> 是 C++ 标准库中的一个容器，底层使用单向链表实现。它的主要优势是插入和删除操作快，特别适合需要在列表任意位置频繁修改的场景。不过，它不支持随机访问，只能从头到尾遍历。
特点
- 内存效率：相比
std::list，<forward_list>使用单向链表，内存占用更少，适合不需要双向迭代的场景。 - 遍历限制：只能向前遍历，没有反向迭代器。
- 访问方式：不支持按索引直接访问元素，必须从头开始逐个遍历，效率较低。
使用场景
当你需要频繁在列表中插入或删除元素，且不关心随机访问或反向遍历时，<forward_list> 是一个不错的选择。例如，在排序算法中，它的表现通常优于其他容器。
支持的资源包括：
- CSDN 博客: C++11中std::forward_list单向链表的使用
- C语言中文网: C++ STL forward_list容器完全攻略
- 简书: C++ STL 之 forward_list
详细报告
引言
C++ 容器 <forward_list> 是 C++11 标准中引入的一个单向链表容器，旨在提供高效的插入和删除操作，同时在内存使用上更节省资源。本报告将详细探讨其特点、使用方法、与 std::list 的比较以及适用场景，旨在为用户提供全面的中文讲解。
背景与定义
<forward_list> 是 C++ 标准库中的序列容器，其模板定义在头文件 <forward_list> 中。它基于单向链表实现，每个元素通过指针连接到下一个元素，形成了线性序列。与传统的数组或向量（vector）不同，<forward_list> 的元素存储位置是分散的，顺序通过指针维持。
主要特点
以下是 <forward_list> 的核心特点，总结自多个权威资源：
- 结构：单向链表，每个节点只包含指向下一个节点的指针，没有指向前一个节点的链接。
- 内存效率：相比
std::list（双向链表），<forward_list>节省了存储前向指针的内存空间，尤其在元素数量较多时优势明显。 - 遍历方式：只支持向前遍历，提供前向迭代器（forward iterator），不支持反向迭代器，因此没有
rbegin()和rend()等成员函数。 - 访问效率：不支持随机访问（random access），要访问特定位置的元素，必须从头开始逐个遍历，时间复杂度为 O(n)。
- 大小操作：没有
size()成员函数，为提高效率，需通过std::distance(begin(), end())计算元素数量。 - 操作效率：插入和删除操作的时间复杂度为 O(1)，特别适合在列表任意位置进行修改，广泛用于排序算法等场景。
以下表格总结了 <forward_list> 的主要特性对比：
| 特性 | 描述 |
|---|---|
| 内存使用 | 比 std::list 更高效，无双向指针开销 |
| 遍历方向 | 仅向前遍历，无反向迭代器 |
| 随机访问 | 不支持，需线性遍历 |
| 插入/删除效率 | O(1)，在任意位置高效 |
| 大小获取 | 无 size()，需用 std::distance 计算 |
使用方法
<forward_list> 的使用方法包括创建实例和调用各种成员函数。以下是常见创建方式：
- 空列表：
std::forward_list<int> values; - 包含 N 个默认值元素：
std::forward_list<int> values(10);// 10 个元素，默认值为 0（对于 int 类型） - 包含 N 个指定值元素：
std::forward_list<int> values(10, 5);// 10 个元素，每个值为 5 - 拷贝构造：
std::forward_list<int> value2(value1);// 从现有列表拷贝 - 从数组创建：
int a[] = {1,2,3,4,5}; std::forward_list<int> values(a, a+5);// 从数组范围初始化
关键成员函数
<forward_list> 提供了多种成员函数，涵盖元素访问、修改和算法支持。以下是部分重要函数的说明：
| 函数名 | 描述 |
|---|---|
before_begin() | 返回第一个元素之前的迭代器，用于插入到开头 |
begin() | 返回第一个元素的迭代器 |
end() | 返回最后一个元素之后的迭代器 |
empty() | 检查列表是否为空，返回布尔值 |
front() | 返回第一个元素的引用 |
push_front() | 在列表开头添加元素 |
pop_front() | 移除第一个元素 |
insert_after() | 在指定位置之后插入元素 |
emplace_after() | 在指定位置之后构造并插入元素 |
erase_after() | 在指定位置之后移除元素 |
splice_after() | 将元素从另一个列表转移到当前列表的指定位置之后 |
remove() | 移除所有等于指定值的元素 |
remove_if() | 移除满足条件的元素，使用一元谓词 |
unique() | 移除连续重复的元素，保持第一个 |
merge() | 合并两个已排序的列表，保持排序 |
sort() | 对列表进行排序，支持自定义比较器 |
例如，使用 sort() 可以对列表排序：
- 升序：
data.sort();// 例如{1,5,0,3,2,4}排序后为{0,1,2,3,4,5} - 降序：
data.sort(std::greater<>);
merge() 用于合并两个已排序的列表，例如 {1,3,5,7,9}.merge({0,2,4,6,8}) 结果为 {0,1,2,3,4,5,6,7,8,9}。
与 std::list 的比较
<forward_list> 与 std::list 都是链表容器，但有显著差异：
- 内存使用：
<forward_list>使用单向链表，内存开销更低；std::list使用双向链表，每个节点需要两个指针。 - 遍历能力：
<forward_list>只能向前遍历；std::list支持双向遍历。 - 功能限制：
<forward_list>没有push_back()、pop_back()等函数，因为无法直接访问尾部。
研究表明，当不需要双向迭代时，<forward_list> 是更优的选择，尤其在内存敏感的场景下。
适用场景
<forward_list> 适合以下场景：
- 需要频繁在列表任意位置插入或删除元素，例如排序算法中。
- 不需要随机访问或反向遍历，优先考虑内存效率。
- 对比
std::list，当双向迭代不是必需时，<forward_list>是更好的选择。
例如，在实现一个需要快速插入和删除的队列时，<forward_list> 可能比 vector 或 deque 更合适，但如果需要按索引访问元素，则应选择其他容器。
结论
<forward_list> 是 C++11 引入的一个高效的单向链表容器，特别适合需要快速插入/删除且内存效率重要的场景。尽管它不支持随机访问和反向遍历，但其设计目标是提供与手写单向链表相当的性能，广泛应用于排序算法和其他需要线性遍历的场景。
参考资料
本报告基于以下资源整理，供进一步阅读：