前向列表

前向列表（英语：forward list）^[1]是于标准模板函数库中的序列容器（sequence containers），以单向链表实现，自C++11标准开始被定义于C++标准函数库里的 <forward_list> 头文件^[2]。

与 std::list 相比，原本 std::list 是一个双向链表，每个节点都有指向上一个节点与下一个节点的指针，所以可以双向遍历，但这样会使得内存空间消耗得更多，速度会相对地变慢。但 std::forward_list 提供了不需要双向迭代时，更节省存储空间的容器。

std::forward_list 的优点是能够支持在容器中的任何位置更快速地插入、移除、提取与移动元素。但因为它是以单向链表实现，因此不支持随机存取，须以线性时间来走访。

模板

自C++11

template<
    class T,
    class Allocator = std::allocator<T>
> class forward_list

自C++17

namespace pmr {
    template< class T >
    using forward_list = std::forward_list<T, std::pmr::polymorphic_allocator<T>>;
}

成员类型

属性	类型	解释
value_type	T	容器中存储的元素类型
allocator_type	Allocator	用于分配内存的分配器类型
size_type	Unsigned integer type (usually std::size_t)	表示容器大小的无符号整数类型，通常是 std::size_t
difference_type	Signed integer type (usually std::ptrdiff_t)	表示迭代器之间距离的有符号整数类型，通常是 std::ptrdiff_t
reference	value_type&	元素的引用类型
const_reference	const value_type&	元素的常量引用类型
pointer	std::allocator_traits<Allocator>::pointer	指向元素的指针类型
const_pointer	std::allocator_traits<Allocator>::const_pointer	指向常量元素的指针类型
iterator	LegacyForwardIterator to value_type	迭代器类型，可用于遍历容器中的元素
const_iterator	LegacyForwardIterator to const value_type	常量迭代器类型，用于以只读方式遍历容器中的元素

成员函数

成员函数	解释
(constructor)	构造函数，用于建构 forward_list
(destructor)	析构函数，用于销毁 forward_list
operator=	将值赋予容器
assign	将值赋予容器
assign_range(C++23)	将一个值范围赋予容器
get_allocator	返回相关系的分配器

成员访问

成员函数	解释
front	访问第一个元素

迭代器

成员函数	解释
before_begin cbefore_begin	返回指向起始之前的元素的迭代器
begin cbegin	返回指向起始的迭代器
end cend	返回指向尾端的迭代器

容量

成员函数	解释
empty	检查容器是否为空
max_size	返回可能存储的最大元素数量

修饰语

成员函数	解释
clear	清空内容
insert_after	在一个元素之后插入元素
emplace_after	在一个元素之后原地构造元素
insert_range_after(C++23)	在一个元素之后插入一个值范围的元素
erase_after	在一个元素之后删除一个元素
push_front	在开始处插入一个元素
emplace_front	在开始处原地构造一个元素
prepend_range(C++23)	在开始处添加一个值范围的元素
pop_front	删除第一个元素
resize	改变存储的元素数量
swap	交换内容

操作

成员函数	解释
merge	合并两个排序的列表
splice_after	从另一个 forward_list 移动元素
remove remove_if	删除满足特定条件的元素
reverse	反转元素的顺序
unique	删除连续重复的元素
sort	对元素进行排序

C++ 代码实例

建构

# include <iostream>
# include <forward_list> // 導入前向串列標頭檔

int main(){
    std::forward_list<int> list1 = {1, 2, 3, 4};
}

插入元素

# include <iostream>
# include <forward_list> 

int main(){
    std::forward_list<int> list1 = {1, 2, 3, 4};
    auto it = list1.begin();
    std::advance(it, 2);
    list1.insert_after(it, 5);
    // list1 = {1, 2, 3, 5, 4}
}

删除所有指定值

# include <iostream>
# include <forward_list>

int main(){
    std::forward_list<int> list1 = {1, 2, 3, 3, 4};
    list1.remove(3);
    // list1 = {1, 2, 4}
}

反转串列

# include <iostream>
# include <forward_list>

int main(){
    std::forward_list<int> list1 = {1, 2, 3, 4};
    list1.reverse();
    // list1 = {4, 3, 2, 1}
}

获取长度

基于效率考量，std::forward_list 不提供 size() 的方法。取而代之，得到成员个数需使用std::distance(_begin, _end)。

# include <iostream>
# include <forward_list> 

int main(){
    std::forward_list<int> list1 = {1, 2, 3, 4};
    std::cout << "Size of list1: " << std::distance(list1.begin(), list1.end()) << std::endl;
}

指定范围(C++23)

# include <iostream>
# include <forward_list>

int main(){
    std::forward_list<int> list1 = {1, 2, 3, 4};
    std::forward_list<int> list2;
    
    // 使用 assign_range 將 list1 中的元素賦值給 list2
    list2.assign_range(list1.begin(), list1.end());
    
    // list2 現在包含與 list1 相同的元素
}

原地建构

# include <iostream>
# include <forward_list>

int main(){
    std::forward_list<int> list1 = {1, 2, 3, 4};
    auto it = list1.begin();
    std::advance(it, 2);
    
    // 在位置 it 的後面原地建構元素 5
    list1.emplace_after(it, 5);
    // list1 = {1, 2, 3, 5, 4}
}

插入范围(C++23)

# include <iostream>
# include <forward_list>
# include <vector>

int main(){
    std::forward_list<int> list1 = {1, 2, 3, 4};
    std::vector<int> vec = {5, 6, 7};
    auto it = list1.begin();
    std::advance(it, 2);
    
    // 在位置 it 的後面插入 vec 中的元素
    list1.insert_range_after(it, vec.begin(), vec.end());
    // list1 = {1, 2, 3, 5, 6, 7, 4}
}

前置范围(C++23)

# include <iostream>
# include <forward_list>
# include <vector>

int main(){
    std::forward_list<int> list1 = {3, 4, 5};
    std::vector<int> vec = {1, 2};
    
    // 在開始處加入 vec 中的元素
    list1.prepend_range(vec.begin(), vec.end());
    // list1 = {1, 2, 3, 4, 5}
}