前向列表

前向串列（forward list）是于标准样板函式库中的序列容器（sequence containers），以单向链接串列实现，自C++11标准开始被定义于C++标准函式库里的 `<forward_list>` 标头档。

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

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

## 模板

### 自C++11

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

### 自C++17

```c++
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::pointer｜指向元素的指标类型

const_pointer｜std::allocator_traits::const_pointer｜指向常量元素的指标类型

iterator｜LegacyForwardIterator to value_type｜迭代器类型，可用于遍历容器中的元素

const_iterator｜LegacyForwardIterator to const value_type｜常量迭代器类型，用于以只读方式遍历容器中的元素

## 成员函式

成员函数｜解释

(constructor)｜建构函数，用于建构 `forward_list`

(destructor)｜解构函数，用于销毁 `forward_list`

将值赋予容器

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++ 程式码实例

### 建构

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

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

### 插入元素

```cpp
# 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}
}
```

### 删除所有指定值

```cpp
# include <iostream>
# include <forward_list>

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

### 反转串列

```cpp
# 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)`。

```cpp
# 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)

```cpp
# 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 相同的元素
}
```

### 原地建构

```cpp
# 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)

```cpp
# 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)

```cpp
# 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}
}
```