C++/STL/forward list

<forward_list> 是自b:C++11標準開始，b:C++標準程式庫中的一個b:頭文件，定義了b:C++標準中單鍊表序列容器的類模板前向鍊表（forward_list）。

單鍊表（singly linked list）存儲所包含的每個成員在不同、不相關的位置；順序保持是通過關聯每個成員與其在序列中的下一個成員。由於只有指向下一個表項的連結，因此具有插入、刪除表項速度快、消耗內存空間少的特點。但只能向前遍歷。

與之不同，std::list是雙向鍊表，每個成員保持指向下一項與前一項的兩個指針，因此可以雙向遍歷，但消耗內存空間更多，插入或刪除成員時的速度稍慢。

與其他b:C++標準程式庫中的序列容器（array、vector、deque）相比，forward_list在容器內任意位置的成員的插入、提取（extracting）、移動、刪除操作的速度更快，因此被廣泛用於排序算法。

前向鍊表（以及std::list）的主要缺點是不能在常量時間內隨機訪問任意成員，對成員的訪問需要線性時間代價；以及存儲連結信息需要消耗內存，特別是當包含大量的小規模成員時。std::forward_list處於效率考慮，有意不提供size()成員函數。獲取std::forward_list所包含的成員個數需要用std::distance(_begin,_end)算法。

模板類

template < class T, class Alloc = allocator<T> > class forward_list;

成員類型

成員類型	定義	註釋
value_type	第一個模板參數(T)
allocator_type	第二個模板參數(Alloc)	缺省allocator<value_type>
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits<allocator_type>::pointer	對於缺省分配器為value_type*
const_pointer	allocator_traits<allocator_type>::const_pointer	對於缺省分配器為const value_type*
iterator	指向value_type的前向迭代器	可轉換為const_iterator
const_iterator	指向const value_type的前向迭代器
difference_typ	有符號的整形，即iterator_traits<iterator>::difference_type	通常為 ptrdiff_t
size_type	可表示difference_type的任何非負值的無符號整形	通常為size_t

成員函數

(constructor) 構造函數
(destructor) 析構函數
operator= 拷貝賦值運算符、移動賦值運算符、初始化器運算符
迭代器
- before_begin 返回開始位置之前的迭代器
- begin 返回指向開始位置的迭代器
- end 返回指向結束位置的迭代器
- cbefore_begin 返回開始位置之前的const迭代器
- cbegin 返回指向開始位置的const迭代器
- cend 返回指向結束位置的const迭代器
容量Capacity
- empty 測試容器是否為空
- max_size 返回容器的可能允許的最大容量
成員訪問（Element access）
- front 返回第一個成員的引用
修改器（Modifier）
- assign 賦值替換全部內容
- emplace_front 在鍊表頭部原位構造新的成員並插入到鍊表最開始處
- push_front 在鍊表頭部插入元素，使用拷貝語義或移動語義
- pop_front 刪除鍊表頭部元素
- emplace_after 在當前位置的尾方向原位插入元素
- insert_after 在當前位置的尾方向插入成員，可譯為拷貝語義、移動語義、值被插入多次、插入一個序列、插入初始化器的內容
- erase_after 在當前位置的尾方向的下一個成員或子序列被刪除
- swap 交換兩個鍊表的內容
- resize 改變鍊表的容量
- clear 清空鍊表的內容
操作（Operation）
- splice_after 把另一個鍊表的單個成員、或子序列、或整個序列，移動插入到當前鍊表指定位置之後
- remove 刪除（析構）具有特定內容的成員
- remove_if 刪除使謂詞為真的成員
- unique 刪除與序列中前一個成員相等（或者二元謂詞為真）的成員。特別適用於排序後鍊表
- merge 兩個已經有序的鍊表做有序合併
- sort 對一個鍊表的成員做穩定排序，要求是strict weak ordering謂詞^[1]
- reverse 把一個鍊表所有成員逆序
觀察器（Observer）
- get_allocator 獲取當前的分配器

重載的非成員函數模板

比較兩個前向鍊表的關係運算符函數模板
- bool operator==(lhs, rhs)，兩個鍊表的對應成員兩兩比較
- bool operator!=(lhs, rhs)
- bool operator<(lhs, rhs)，兩個鍊表的對應成員做詞典（lexicographical）比較
- bool operator>(lhs, rhs)
- bool operator<=(lhs, rhs)
- bool operator>=(lhs, rhs)
swap (lhs, rhs)

參考文獻

頁面Template:ReflistH/styles.css沒有內容。

↑
見 Effective STL 條款21：
- Strict: pred (X, X) is always false.
- Weak: If ! pred (X, Y) && !pred (Y, X), X==Y.
- Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z).

C++ reference for forward list

[1] 見 Effective STL 條款21：
Strict: pred (X, X) is always false.

Weak: If ! pred (X, Y) && !pred (Y, X), X==Y.

Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z).

[2] Strict: pred (X, X) is always false.

[3] Weak: If ! pred (X, Y) && !pred (Y, X), X==Y.

[4] Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z).

[1]