C++/STL/forward list

<forward_list> 是自b:C++11标准开始，b:C++标准程式库中的一个b:头文件，定义了b:C++标准中单链表序列容器的类模板前向链表（forward_list）。

单链表（singly linked list）存储所包含的每个成员在不同、不相关的位置；顺序保持是通过关联每个成员与其在序列中的下一个成员。由于只有指向下一个表项的链接，因此具有插入、删除表项速度快、消耗内存空间少的特点。但只能向前遍历。

与之不同，std::list是双向链表，每个成员保持指向下一项与前一项的两个指针，因此可以双向遍历，但消耗内存空间更多，插入或删除成员时的速度稍慢。

与其他b:C++标准程式库中的序列容器（array、vector、deque）相比，forward_list在容器内任意位置的成员的插入、提取（extracting）、移动、删除操作的速度更快，因此被广泛用于排序算法。

前向链表（以及std::list）的主要缺点是不能在常量时间内随机访问任意成员，对成员的访问需要线性时间代价；以及存储链接信息需要消耗内存，特别是当包含大量的小规模成员时。std::forward_list处于效率考虑，有意不提供size()成员函数。获取std::forward_list所包含的成员个数需要用std::distance(_begin,_end)算法。

模板类

template < class T, class Alloc = allocator<T> > class forward_list;

成员类型

成员类型	定义	注释
value_type	第一个模板参数(T)
allocator_type	第二个模板参数(Alloc)	缺省allocator<value_type>
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits<allocator_type>::pointer	对于缺省分配器为value_type*
const_pointer	allocator_traits<allocator_type>::const_pointer	对于缺省分配器为const value_type*
iterator	指向value_type的前向迭代器	可转换为const_iterator
const_iterator	指向const value_type的前向迭代器
difference_typ	有符号的整形，即iterator_traits<iterator>::difference_type	通常为 ptrdiff_t
size_type	可表示difference_type的任何非负值的无符号整形	通常为size_t

成员函数

(constructor) 构造函数
(destructor) 析构函数
operator= 拷贝赋值运算符、移动赋值运算符、初始化器运算符
迭代器
- before_begin 返回开始位置之前的迭代器
- begin 返回指向开始位置的迭代器
- end 返回指向结束位置的迭代器
- cbefore_begin 返回开始位置之前的const迭代器
- cbegin 返回指向开始位置的const迭代器
- cend 返回指向结束位置的const迭代器
容量Capacity
- empty 测试容器是否为空
- max_size 返回容器的可能允许的最大容量
成员访问（Element access）
- front 返回第一个成员的引用
修改器（Modifier）
- assign 赋值替换全部内容
- emplace_front 在链表头部原位构造新的成员并插入到链表最开始处
- push_front 在链表头部插入元素，使用拷贝语义或移动语义
- pop_front 删除链表头部元素
- emplace_after 在当前位置的尾方向原位插入元素
- insert_after 在当前位置的尾方向插入成员，可译为拷贝语义、移动语义、值被插入多次、插入一个序列、插入初始化器的内容
- erase_after 在当前位置的尾方向的下一个成员或子序列被删除
- swap 交换两个链表的内容
- resize 改变链表的容量
- clear 清空链表的内容
操作（Operation）
- splice_after 把另一个链表的单个成员、或子序列、或整个序列，移动插入到当前链表指定位置之后
- remove 删除（析构）具有特定内容的成员
- remove_if 删除使谓词为真的成员
- unique 删除与序列中前一个成员相等（或者二元谓词为真）的成员。特别适用于排序后链表
- merge 两个已经有序的链表做有序合并
- sort 对一个链表的成员做稳定排序，要求是strict weak ordering谓词^[1]
- reverse 把一个链表所有成员逆序
观察器（Observer）
- get_allocator 获取当前的分配器

重载的非成员函数模板

比较两个前向链表的关系运算符函数模板
- bool operator==(lhs, rhs)，两个链表的对应成员两两比较
- bool operator!=(lhs, rhs)
- bool operator<(lhs, rhs)，两个链表的对应成员做词典（lexicographical）比较
- bool operator>(lhs, rhs)
- bool operator<=(lhs, rhs)
- bool operator>=(lhs, rhs)
swap (lhs, rhs)

参考文献

页面Template:ReflistH/styles.css没有内容。

↑
见 Effective STL 条款21：
- Strict: pred (X, X) is always false.
- Weak: If ! pred (X, Y) && !pred (Y, X), X==Y.
- Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z).

C++ reference for forward list

[1] 见 Effective STL 条款21：
Strict: pred (X, X) is always false.

Weak: If ! pred (X, Y) && !pred (Y, X), X==Y.

Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z).

[2] Strict: pred (X, X) is always false.

[3] Weak: If ! pred (X, Y) && !pred (Y, X), X==Y.

[4] Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z).

[1]