前向列表

前向串列（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}
}
```