std::forward_list是 C11 引入的單向鏈表容器定義在forward_list中。它和std::list很像但每個節(jié)點只保存一個指向下一個節(jié)點的指針因此更省內(nèi)存但只能單向遍歷。1. 核心特點底層結(jié)構(gòu)單向鏈表每個節(jié)點包含一個next指針和元素值。訪問方式只支持前向迭代器只能不能--也不能隨機訪問。沒有size()標準庫的std::forward_list不提供size()成員函數(shù)。如果需要元素個數(shù)只能用std::distance(begin(), end())復雜度 O(n)。插入刪除在已知位置之后插入/刪除是 O(1)。提供insert_after、emplace_after、erase_after沒有普通的insert/erase。頭部操作支持push_front、pop_front、emplace_front但沒有push_back、pop_back、back()。迭代器失效插入不會使任何迭代器失效erase_after只使被刪除元素的迭代器失效。內(nèi)存開銷每個元素一個指針比std::list少一個指針但仍比std::vector大。緩存友好性節(jié)點分散遍歷通常比vector慢。2. 常用操作cpp#include forward_list std::forward_listint fl {1, 2, 3}; fl.push_front(0); // 頭部插入 fl.pop_front(); // 刪除頭部 fl.emplace_front(10); // 頭部直接構(gòu)造 fl.insert_after(it, 5); // 在 it 之后插入返回新元素迭代器 fl.emplace_after(it, 6); // 在 it 之后直接構(gòu)造 fl.erase_after(it); // 刪除 it 之后的元素返回下一個迭代器 fl.before_begin(); // 第一個元素之前的“虛擬位置” fl.front(); // 第一個元素 fl.empty(); // 是否為空 fl.clear(); // 清空 fl.sort(); // 成員函數(shù)穩(wěn)定排序O(n log n) fl.reverse(); // 反轉(zhuǎn) fl.unique(); // 刪除連續(xù)重復元素通常先 sort fl.remove(3); // 刪除所有等于 3 的元素 fl.remove_if(pred); // 刪除滿足謂詞的元素 fl.merge(other); // 合并兩個有序 forward_list源變空 fl.splice_after(pos, other); // 把 other 的節(jié)點移動到 *this不拷貝元素注意std::sort不能用于std::forward_list因為它需要隨機訪問迭代器。必須用成員函數(shù)fl.sort()。3. 與std::list/std::vector的簡單對比特性std::forward_liststd::liststd::vector結(jié)構(gòu)單向鏈表雙向鏈表連續(xù)動態(tài)數(shù)組遍歷方向只能向前雙向隨機訪問隨機訪問不支持不支持支持 O(1)size()無有O(1)有O(1)中間插入刪除已知位置后 O(1)已知位置 O(1)O(n)迭代器失效插入不失效刪除只失效被刪插入不失效刪除只失效被刪插入可能全部失效每元素額外開銷1 個指針2 個指針通常較小可能有預(yù)留容量緩存友好差差好適用場景單向遍歷、省內(nèi)存、頻繁頭部/已知位置后操作需要雙向遍歷、頻繁中間操作頻繁隨機訪問、尾部操作、遍歷大多數(shù)情況下std::vector仍是默認選擇。只有當確實需要頻繁在已知位置后插入刪除并且不需要雙向遍歷時std::forward_list才更有優(yōu)勢。#include iostream #include forward_list #include string #include algorithm #include iterator int main() { // 1. 基本操作 std::forward_liststd::string tasks {write, test, deploy}; tasks.push_front(plan); // plan write test deploy // 在 test 前插入 code需要找到 test 的前驅(qū) auto prev tasks.before_begin(); auto it tasks.begin(); while (it ! tasks.end() *it ! test) { prev it; it; } if (it ! tasks.end()) { tasks.insert_after(prev, code); // plan write code test deploy } std::cout tasks: ; for (const auto t : tasks) { std::cout t ; } std::cout \n; // 刪除 deploy需要找到它的前驅(qū) prev tasks.before_begin(); it tasks.begin(); while (it ! tasks.end() *it ! deploy) { prev it; it; } if (it ! tasks.end()) { tasks.erase_after(prev); // 刪除 deploy } std::cout after erase: ; for (const auto t : tasks) { std::cout t ; } std::cout \n; tasks.remove(test); // 刪除所有 test std::cout after remove: ; for (const auto t : tasks) { std::cout t ; } std::cout \n; // 2. 排序、去重、反轉(zhuǎn) std::forward_listint nums {3, 1, 2, 2, 5, 4}; nums.sort(); // forward_list 成員函數(shù)穩(wěn)定排序 nums.unique(); // 刪除連續(xù)重復元素 nums.reverse(); // 反轉(zhuǎn) std::cout nums: ; for (int n : nums) { std::cout n ; } std::cout \n; // 3. splice_after把 b 的節(jié)點移動到 a 中不拷貝元素 std::forward_listint a {1, 2, 3}; std::forward_listint b {10, 20, 30}; auto pos a.begin(); // 指向 1 a.splice_after(pos, b); // 把 b 全部插入到 pos 之后1 10 20 30 2 3 std::cout a: ; for (int n : a) { std::cout n ; } std::cout \n; std::cout b empty: std::boolalpha b.empty() \n; // 注意forward_list 沒有 size() std::cout a size std::distance(a.begin(), a.end()) \n; return 0; }