前向列表

前向串列（英語：）[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}
}

參考文獻

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] （英文）C++ 參考：std::foward_list（C++ reference: std::foward_list）

[2] （英文）C++ 標準樣板函式庫：<foward_list>標頭檔（C++ Standard library header：<forward_list>）