前向串列
外觀
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目需要補充更多來源。 (2024年3月22日) |
前向串列(英語: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}
}
參考文獻
[編輯]
|