前向列表

前向列表(英语: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}
}

参考文献