前向串列(英語: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 |
返回相關聯的分配器
|
成員存取
迭代器
成員函數 |
解釋
|
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}
}
參考文獻