C++容器之 forward_list (单向链表)使用说明
目录
1. 语法格式
2. 说明
3. 用法示例
1. 语法格式
描述控制可变长度元素序列的对象。该序列存储为单向(前向)链接的节点列表，每个节点包含一个 Type 类型的成员。
template <class Type,
class Allocator = allocator<Type>>
class forward_list;
Type：要存储在 forward_list 中的元素数据类型。
Allocator：存储的分配器对象，封装了有关 forward_list 内存分配和释放的详细信息。此参数为可选参数。默认值为 allocator<Type>。
2. 说明
forward_list 对象通过基于 allocator 类(通常称为 std::allocator)的 Allocator 类存储对象为其控制的序列分配和释放存储空间。allocator 对象必须具有与 allocator 类型对象相同的外部接口。
当迭代器、指针和引用所控制的序列中的元素通过 forward_list 删除时，它们可能会失效。通过 forward_list 对受控序列执行插入和拼接操作不会使迭代器失效。
受控序列的添加可以通过调用 forward_list::insert_after 来实现，该函数是唯一一个调用构造函数 Type(const T&) 的成员函数。forward_list 也可能调用移动构造函数。如果此类表达式引发异常，则容器对象不会插入任何新元素并重新引发异常。因此，当发生此类异常时，forward_list 类型的对象处于已知状态。
分配容器对象时，不会复制存储的分配器对象。
forward_list 容器和双向链表容器list的主要设计区别在于，前者在内部只保留指向下一个元素的链接，而后者每一个元素保留两个链接：一个指向下一个元素，一个指向前一个元素，从而允许双向高效迭代，但每个元素会消耗额外的存储空间，并且插入和删除元素的时间开销略高。因此，forward_list 对象比列表对象更高效，尽管它们只能向前迭代。对于存储零个或少数几个元素的场景非常合适。
与其他基本标准序列容器(数组、向量和双端队列)相比，forward_list 在容器内任何位置插入、提取和移动元素方面通常表现更佳，因此在大量使用这些元素的算法(例如排序算法)中也表现出色。
与其他序列容器相比，forward_list 和列表的主要缺点在于它们无法通过元素的位置直接访问元素；例如，要访问 forward_list 中的第六个元素，必须从起始位置迭代(即遍历)到该位置，这需要线性时间。它们还会消耗一些额外的内存来保存与每个元素关联的链接信息(这对于包含小元素的大型列表来说可能是一个重要因素)。
forward_list 类模板在设计时就考虑到了效率：从设计上讲，它与简单的手写 C 语言单链表一样高效，事实上，它是唯一一个出于效率考虑而故意省略 size 成员函数的标准容器：由于其链表性质，如果 size 成员函数的执行时间是常量级的，则需要维护一个内部计数器来记录其大小(就像双向list一样)。这会消耗一些额外的存储空间，并使插入和删除操作的效率略有降低。要获取 forward_list 对象的大小，可以使用距离算法及其 begin 和 end 函数，这是一个线性时间操作。
3. 用法示例
// forward_list_splice_after.cpp
// compile with: /EHsc /W4
#include <forward_list>
#include <iostream>
using namespace std;
template <typename S> void print(const S& s) {
for (const auto& p : s) {
cout << "(" << p << ") ";
}
cout << endl;
}
int main()
{
forward_list<int> c1{ 10, 11 };
forward_list<int> c2{ 20, 21, 22 };
forward_list<int> c3{ 30, 31 };
forward_list<int> c4{ 40, 41, 42, 43 };
forward_list<int>::iterator where_iter;
forward_list<int>::iterator first_iter;
forward_list<int>::iterator last_iter;
cout << "Beginning state of lists:" << endl;
cout << "c1 = ";
print(c1);
cout << "c2 = ";
print(c2);
cout << "c3 = ";
print(c3);
cout << "c4 = ";
print(c4);
where_iter = c2.begin();
++where_iter; // start at second element
c2.splice_after(where_iter, c1);
cout << "After splicing c1 into c2:" << endl;
cout << "c1 = ";
print(c1);
cout << "c2 = ";
print(c2);
first_iter = c3.begin();
c2.splice_after(where_iter, c3, first_iter);
cout << "After splicing the first element of c3 into c2:" << endl;
cout << "c3 = ";
print(c3);
cout << "c2 = ";
print(c2);
first_iter = c4.begin();
last_iter = c4.end();
// set up to get the middle elements
++first_iter;
c2.splice_after(where_iter, c4, first_iter, last_iter);
cout << "After splicing a range of c4 into c2:" << endl;
cout << "c4 = ";
print(c4);
cout << "c2 = ";
print(c2);
}
输出：
Beginning state of lists:c1 = (10) (11)c2 = (20) (21) (22)c3 = (30) (31)c4 = (40) (41) (42) (43)After splicing c1 into c2:c1 =c2 = (20) (21) (10) (11) (22)After splicing the first element of c3 into c2:c3 = (30)c2 = (20) (21) (31) (10) (11) (22)After splicing a range of c4 into c2:c4 = (40) (41)c2 = (20) (21) (42) (43) (31) (10) (11) (22)