C++

参考

<forward_list>

forward_list

类模板
<forward_list>

std::forward_list

template < class T, class Alloc = allocator<T> > class forward_list;
前向列表
前向列表是序列容器，允许在序列中的任何位置进行常量时间的插入和擦除操作。

前向列表是以单向链表的形式实现的；单向链表可以将其包含的每个元素存储在不同且不相关的存储位置。顺序是通过将每个元素关联到序列中下一个元素的链接来维持的。

一个forward_list容器和一个 list 容器之间的主要设计差异是，前者内部只保留一个指向下一个元素的链接，而后者每个元素保留两个链接：一个指向下一个元素，一个指向前一个元素，这允许双向的高效迭代，但每个元素会消耗额外的存储空间，并且在插入和移除元素时有稍高的时间开销。forward_list对象因此比 list 对象更高效，尽管它们只能向前迭代。

与其他基本标准序列容器（array、vector 和 deque）相比，forward_list 在容器内任何位置插入、提取和移动元素方面通常表现更好，因此在大量使用这些操作的算法（如排序算法）中也表现更佳。

与这些其他序列容器相比，forward_list和 list 的主要缺点是它们缺乏通过位置直接访问元素的能力；例如，要访问一个forward_list中的第六个元素，必须从头开始迭代到那个位置，这需要与距离成线性关系的时间。它们还会消耗一些额外的内存来保存与每个元素关联的链接信息（对于包含大量小尺寸元素的列表来说，这可能是一个重要因素）。

要放回的字符的forward_list类模板的设计考虑了效率：从设计上讲，它和一个简单的手写 C 风格单向链表一样高效，事实上，它是唯一一个出于效率考虑而故意缺少size成员函数的标准容器：由于其链表的性质，拥有一个size成员函数并使其耗时为常量时间，将要求它为自身的大小维护一个内部计数器（就像 list 那样）。这会消耗一些额外的存储空间，并使插入和移除操作的效率稍低。要获取一个forward_list对象的大小，您可以使用 distance 算法，并传入其 begin 和 end，这是一个耗时为线性的操作。

容器属性

序列
序列容器中的元素以严格的线性序列排序。单个元素通过其在此序列中的位置进行访问。
链表
每个元素都保存着如何定位下一个元素的信息，允许在特定元素之后进行常量时间的插入和擦除操作（甚至是整个范围），但不支持直接的随机访问。
感知分配器
容器使用分配器对象来动态处理其存储需求。

模板参数

T
元素的类型。
别名为成员类型forward_list::value_type.
Alloc
用于定义存储分配模型的分配器对象类型。默认情况下，使用 allocator 类模板，它定义了最简单的内存分配模型并且与值无关。
别名为成员类型forward_list::allocator_type.

成员类型

成员类型定义说明
value_type第一个模板参数 (T)
allocator_type第二个模板参数 (Alloc)默认为allocator<value_type>
引用value_type&
const_referenceconst value_type&
指针allocator_traits<allocator_type>::pointer对于默认的 allocatorvalue_type*
const_pointerallocator_traits<allocator_type>::const_pointer对于默认的 allocatorconst value_type*
iterator一个指向value_type的 随机访问迭代器，可转换为const_iterator
const_iterator一个指向const value_type
difference_type一个有符号整数类型，与iterator_traits<iterator>::difference_type相同，通常与 ptrdiff_t 一样
size_type一个可以表示任何非负值的difference_type的无符号整数类型，通常与 size_t 一样

成员函数

（构造函数）
构造 forward_list 对象 (公开成员函数)
(析构函数)
销毁 forward_list 对象 (公开成员函数)
operator=
赋新值 (公开成员函数)

迭代器

before_begin
返回指向起始位置之前的迭代器 (公开成员函数)
begin
返回指向起始位置的迭代器 (公开成员类型)
end
返回指向末尾的迭代器 (公开成员函数)
cbefore_begin
返回指向起始位置之前的 const_iterator (公开成员函数)
cbegin
返回指向起始位置的 const_iterator (公开成员函数)
cend
返回指向末尾的 const_iterator (公开成员函数)

容量

empty
测试数组是否为空 (公开成员函数)
max_size
返回最大大小 (公开成员函数)

元素访问

front
访问第一个元素 (公开成员函数)

修改器

assign
赋新值 (公开成员函数)
emplace_front
在起始位置构造并插入元素 (公开成员函数)
push_front
在起始位置插入元素 (公开成员函数)
pop_front
删除第一个元素 (公开成员函数)
emplace_after
构造并插入元素 (公开成员函数)
insert_after
插入元素 (公开成员函数)
erase_after
擦除元素 (公开成员函数)
swap
交换内容 (公开成员函数)
resize
改变大小 (公开成员函数)
clear
清除内容 (公开成员函数)

操作

splice_after
从另一个 forward_list 转移元素 (公开成员函数)
remove
移除具有特定值的元素 (公开成员函数)
remove_if
移除满足条件的元素 (公开成员函数模板)
unique
移除重复的值 (公开成员函数)
merge
合并已排序的列表 (公开成员函数)
sort
对容器中的元素排序 (公开成员函数)
reverse
反转元素的顺序 (公开成员函数)

观察器

get_allocator
获取分配器 (公开成员函数)

非成员函数重载

关系运算符 (forward_list)
forward_list 的关系运算符 (函数模板)
swap (forward_list)
交换两个 forward_list 容器的内容 (函数模板)