前向列表

前向串列（）C++ 參考：std::foward_list（C++ reference: std::foward_list） 是於標準樣板函式庫中的序列容器（sequence containers），以單向鏈結串列實現，自C++11標準開始被定義於C++標準函式庫裡的 <forward_list> 標頭檔C++ 標準樣板函式庫：<foward_list>標頭檔（C++ Standard library header：<forward_list>） 。

與 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}
}

參考文獻


Category:資料結構