前向串列

前向串列(英語: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}
}

參考文獻