1. 起手式為什么 std::list 值得認(rèn)真學(xué)看到Clist帶頭雙向鏈表增刪查改這個題目我第一反應(yīng)是——這應(yīng)該是絕大多數(shù) C 開發(fā)者繞不開的一關(guān)。不管你是剛啃完《C Primer》的前幾章、正在準(zhǔn)備校招數(shù)據(jù)結(jié)構(gòu)面試還是已經(jīng)寫了兩三年業(yè)務(wù)代碼但一直在用 vector 打天下list 這個容器都值得你停下來認(rèn)真捋一遍。先說清楚 list 是個什么東西。它是 C 標(biāo)準(zhǔn)模板庫STL里基于帶頭雙向鏈表實(shí)現(xiàn)的序列容器。每個元素是一個節(jié)點(diǎn)節(jié)點(diǎn)里除了存儲數(shù)據(jù)的 value 字段還有兩個指針prev 指向前一個節(jié)點(diǎn)next 指向后一個節(jié)點(diǎn)。所謂帶頭就是鏈表開頭有一個不存業(yè)務(wù)數(shù)據(jù)的哨兵節(jié)點(diǎn)也叫頭節(jié)點(diǎn)它讓空鏈表和非空鏈表的操作邏輯完全統(tǒng)一省掉了一堆第一個節(jié)點(diǎn)和最后一個節(jié)點(diǎn)的特殊判斷。很多朋友對 list 的認(rèn)知停留在能 insert、能 erase、插入刪除 O(1)然后真到用的時候又踩一堆坑迭代器怎么莫名其妙失效了為什么 sort 不能直接用而要用 list::sort為什么說好的 O(1) 插入跑起來比 vector 還慢這些問題在本文里都會逐個拆開講。這篇文章我打算分四個層次來講先講帶頭雙向鏈表的設(shè)計心法這是理解一切的基礎(chǔ)然后落到 STL list 的接口上把增刪查改四個操作掰開揉碎接著帶大家手寫一個簡化版帶頭雙向鏈表把源碼層面那些默認(rèn)構(gòu)造、拷貝構(gòu)造、析構(gòu)的關(guān)鍵細(xì)節(jié)過一遍最后整理我這些年用 list 踩過的坑和排查經(jīng)驗(yàn)。適合所有正在學(xué) C 數(shù)據(jù)結(jié)構(gòu)、準(zhǔn)備面試、或者想在實(shí)戰(zhàn)里正確選型的讀者。2. 帶頭雙向鏈表的內(nèi)存布局與核心心法2.1 節(jié)點(diǎn)設(shè)計一個 list 元素內(nèi)部長什么樣很多初學(xué)者把 list 當(dāng)成數(shù)組的替代品這是個誤解。list 不是連續(xù)內(nèi)存它是離散的。標(biāo)準(zhǔn)庫的實(shí)現(xiàn)中節(jié)點(diǎn)類型通常長這樣以 libstdc 的實(shí)現(xiàn)為參考簡化templatetypename T struct __list_node { __list_node* _M_prev; // 指向前一個節(jié)點(diǎn) __list_node* _M_next; // 指向后一個節(jié)點(diǎn) T _M_value; // 存儲的數(shù)據(jù) };注意這個結(jié)構(gòu)體很有意思兩個指針是放在數(shù)據(jù)前面的而不是用一個外面包一層結(jié)構(gòu)把三者合在一起。這設(shè)計的目的之一是為了方便實(shí)現(xiàn)一個空節(jié)點(diǎn)——也就是頭節(jié)點(diǎn)——讓它只包含兩個指針卻不包含實(shí)際數(shù)據(jù)或者數(shù)據(jù)被默認(rèn)構(gòu)造但從不使用。你從使用者的角度看到的是一個listint::iterator它本質(zhì)上就是__list_nodeT*的薄封裝。你解引用迭代器拿到的是節(jié)點(diǎn)里的_M_value。這解釋了為什么 list 的迭代器是雙向迭代器bidirectional iterator它只能和--不能 n跳躍式訪問因?yàn)閮?nèi)存不連續(xù)隨機(jī)訪問在物理上就不可能實(shí)現(xiàn)。我一開始用 list 的時候犯過一個很蠢的錯誤試圖用it 3來跳轉(zhuǎn)編譯報錯后查文檔才發(fā)現(xiàn) list 的迭代器根本不支持operator。這個內(nèi)存布局決定迭代器能力的因果關(guān)系建議每個初學(xué)者都記在心里后面很多迷惑行為都跟這個有關(guān)。2.2 頭節(jié)點(diǎn)不是乘客是看守為什么非要帶頭這正是單向鏈表和雙向鏈表工程的精髓所在。假設(shè)你實(shí)現(xiàn)一個不帶頭節(jié)點(diǎn)的雙鏈表插入頭部節(jié)點(diǎn)和刪除頭部節(jié)點(diǎn)時必須單獨(dú)判斷鏈表是否為空刪除的是不是頭節(jié)點(diǎn)否則頭指針就要移動。這類邊界條件最容易出 bug而且一旦出錯就是懸空指針級別的災(zāi)難。帶頭節(jié)點(diǎn)后頭節(jié)點(diǎn)永遠(yuǎn)是第一個節(jié)點(diǎn)它不參與業(yè)務(wù)邏輯。插入到鏈表頭部就是往頭節(jié)點(diǎn)的 next 后面插刪除鏈表第一個業(yè)務(wù)節(jié)點(diǎn)就是刪除頭節(jié)點(diǎn)的 next 指向的那個節(jié)點(diǎn)頭節(jié)點(diǎn)本身紋絲不動。空鏈表長什么樣頭節(jié)點(diǎn)的 prev 和 next 都指向自己非常優(yōu)雅。用生活類比來說頭節(jié)點(diǎn)就像火車站臺旁邊的調(diào)度員他不上客車、不載客但每列車進(jìn)站出站都必須經(jīng)過他確認(rèn)信號。調(diào)度員在站臺空的時候和不空的時候流程完全一致。這就是以空間換邏輯統(tǒng)一的經(jīng)典案例。所以 STL 的list::end()返回的迭代器本質(zhì)就是指向頭節(jié)點(diǎn)這也是為什么end()不能解引用——它指向的不是業(yè)務(wù)數(shù)據(jù)。2.3 迭代器鏈表的光標(biāo)list 的迭代器設(shè)計是理解所有增刪查改操作的鑰匙。迭代器你完全可以把它的理解為沿著 next 指針走到下一個節(jié)點(diǎn)把--理解為沿著 prev 指針走回上一個節(jié)點(diǎn)。begin()指向頭節(jié)點(diǎn)的下一個節(jié)點(diǎn)end()指向頭節(jié)點(diǎn)。執(zhí)行it時迭代器內(nèi)部執(zhí)行的是it it-_M_next。執(zhí)行erase(it)時你要注意erase返回的是被刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)的迭代器因?yàn)楫?dāng)前迭代器在刪除后已經(jīng)失效了繼續(xù)用它做是未定義行為。// 正確姿勢用 erase 的返回值繼續(xù)遍歷 for (auto it lst.begin(); it ! lst.end(); ) { if (*it % 2 0) { it lst.erase(it); // erase返回下一個有效迭代器 } else { it; } }這個代碼模式我在工作里寫過無數(shù)遍面試也考過無數(shù)遍。它背后體現(xiàn)的就是迭代器失效規(guī)則list 的 erase 只讓被刪節(jié)點(diǎn)那個迭代器失效其他迭代器統(tǒng)統(tǒng)不受影響。這一點(diǎn)和 vector 完全不同后面第五節(jié)我會專門做一張對比表。3. 增刪查改實(shí)戰(zhàn)把四個字落到代碼上3.1 增push_back、push_front、insert、emplace 各有各的用途先說最通用的三個接口。push_back往尾部追加push_front往頭部插入insert在指定位置插入。它們的復(fù)雜度都是 O(1)因?yàn)殒湵聿迦胫恍枰乃膫€指針以尾部插入為例#include list #include iostream std::listint lst {1, 2, 3}; // 尾部追加 lst.push_back(4); // {1, 2, 3, 4} // 頭部插入 lst.push_front(0); // {0, 1, 2, 3, 4} // 指定位置插入insert 返回指向新插入元素的迭代器 auto it std::find(lst.begin(), lst.end(), 2); if (it ! lst.end()) { auto newIt lst.insert(it, 100); // 在 2 前面插入 100返回指向100的迭代器 } // 現(xiàn)在 list: {0, 1, 100, 2, 3, 4}注意insert有幾個重載insert(pos, value)插入一個值insert(pos, count, value)插入 count 個相同的值insert(pos, first, last)插入一個區(qū)間insert(pos, ilist)插入一個初始化列表。我建議把返回值是新插入元素的迭代器這個細(xì)節(jié)記住很多人不知道這點(diǎn)導(dǎo)致想拿到新節(jié)點(diǎn)時還得重新 find 一遍。emplace系列是 C11 引入的。區(qū)別是push_back傳入的是已構(gòu)造好的對象內(nèi)部會調(diào)用移動構(gòu)造或拷貝構(gòu)造emplace_back則是把構(gòu)造參數(shù)直接傳給節(jié)點(diǎn)內(nèi) T 的構(gòu)造函數(shù)在節(jié)點(diǎn)內(nèi)存上直接就地構(gòu)造。對int這種平凡類型沒差別但如果你存的是std::string或者自定義大對象emplace_back(hello, 3)省掉了一次臨時對象和移動構(gòu)造性能上是實(shí)打?qū)嵉膬?yōu)化。lst.emplace_back(5); // 就地構(gòu)造 int(5) lst.emplace_front(-1); // 就地構(gòu)造 int(-1)增量場景的一個關(guān)鍵決策點(diǎn)是頻繁往頭部插入就用 list 或 deque別用 vector。vector 的insert(vec.begin(), x)會把后面全部元素往后挪O(n) 的代價不是說著玩的。3.2 刪pop 系列和 erase、remove、clear 的邊界感刪除操作有這么幾兄弟別混著用pop_back()刪除尾節(jié)點(diǎn)前提是容器非空否則未定義行為。pop_front()刪除頭節(jié)點(diǎn)業(yè)務(wù)頭同上。erase(pos)刪除指定迭代器指向的節(jié)點(diǎn)返回被刪節(jié)點(diǎn)的后繼。erase(first, last)刪除迭代器區(qū)間返回 last。這個接口做區(qū)間清理很方便。remove(value)刪除所有等于 value 的元素。注意這是 list 的成員函數(shù)不是 std::remove 算法。remove_if(pred)刪除所有滿足謂詞條件的元素。unique()刪除連續(xù)重復(fù)元素中除第一個外的所有元素。clear()清空全部業(yè)務(wù)元素保留頭節(jié)點(diǎn)。一個常見的新手錯誤想用erase刪除所有值為 3 的元素卻寫成了lst.erase(it)然后it——這個寫法在 list 上看起來能跑但本質(zhì)上依賴了list 刪除當(dāng)前節(jié)點(diǎn)不影響其他迭代器的規(guī)則看著沒問題其實(shí)你把it自增的時候自增操作的迭代器可能已經(jīng)是失效狀態(tài)了。雖然 list 的迭代器失效規(guī)則寬松但這個習(xí)慣一旦帶去 vector 就是災(zāi)難。老老實(shí)實(shí)寫成it lst.erase(it)或者直接用removelst.remove(3); // 一條命令簡潔高效 lst.remove_if([](int x) { return x % 3 0; });unique值得多說一句它只刪除相鄰且相等的重復(fù)項(xiàng)。如果 list 是{1, 1, 2, 2, 3, 1}調(diào)用unique()后是{1, 2, 3, 1}最后一個 1 不會被刪因?yàn)樗颓耙粋€節(jié)點(diǎn) 3 不相鄰。要想去重得先sort()再unique()這個排序用lst.sort()不是std::sort。3.3 查std::find 和遍歷的正確打開方式list 沒有 [] 操作符也沒有at()成員函數(shù)因?yàn)樗惶峁╇S機(jī)訪問。查找某一項(xiàng)最通用的方式是用算法庫的std::findauto it std::find(lst.begin(), lst.end(), 42); if (it ! lst.end()) { std::cout 找到了位置在; // 想輸出下標(biāo)別想了list 迭代器沒有 - 操作計算距離的能力 // 只能手動數(shù) int index 0; auto tmp lst.begin(); while (tmp ! it) { index; tmp; } std::cout index std::endl; } else { std::cout 沒找到 std::endl; }看見沒即使找到了想算下標(biāo)還得 O(n) 從頭遍歷。這就是雙向迭代器的局限。如果你在乎下標(biāo)訪問list 不適合你你在乎的是頻繁中間插入刪除后迭代器依然穩(wěn)定那 list 就是王者。除了std::findC20 還有std::ranges::find寫法更現(xiàn)代但原理一脈相承。想查所有滿足某條件的元素用find_if 循環(huán)或者直接在for (auto x : lst)里篩一遍。注意 range-for 的內(nèi)部實(shí)現(xiàn)就是基于 begin() 和 end() 的迭代器遍歷所以對 list 來說效率沒有問題。3.4 改通過迭代器修改配合 transform 批量處理list 的改本質(zhì)上就是拿到某個節(jié)點(diǎn)的迭代器然后給解引用的結(jié)果賦值。比如我想把所有偶數(shù)改成 0for (auto x : lst) { if (x % 2 0) { x 0; } }注意auto x的引用非常重要寫成auto x就是拷貝改了不生效。這個問題我在 Code Review 里見過太多次了。如果想批量變換可以配合std::transform但有個坑std::transform要求輸出迭代器支持寫入。你可以把結(jié)果放到另一個 liststd::listint src {1, 2, 3, 4, 5}; std::listint dst; dst.resize(src.size()); // list沒有預(yù)留機(jī)制必須提前把大小擴(kuò)出來 std::transform(src.begin(), src.end(), dst.begin(), [](int x) { return x * x; });或者用更順手的做法原地修改 std::for_eachstd::for_each(src.begin(), src.end(), [](int x) { x x 0 ? -x : x; });修改一個指定位置的元素通常的思路是先 find 再改auto it std::find(lst.begin(), lst.end(), 7); if (it ! lst.end()) { *it 99; // 把值為7的第一個節(jié)點(diǎn)改成99 }這個流程和 vector 完全一樣但有個細(xì)微差別vector 如果發(fā)生擴(kuò)容之前拿到的迭代器會全部失效list 不會只要節(jié)點(diǎn)還在迭代器永遠(yuǎn)有效。這個特性在很多需要記住某個位置、隨時可能在其前后插入的場景里極其有用。4. 從源碼層面手寫一個帶頭雙向鏈表講完 STL 的接口我強(qiáng)烈建議大家動手實(shí)現(xiàn)一個簡化版。原因有兩個一是面試經(jīng)?？级侵挥凶约簩懸槐椴拍苷嬲斫鉃槭裁?STL list 要這樣設(shè)計。下面我會給出一份我教學(xué)和面試中最常用到的核心框架代碼量不大但每個函數(shù)都值得推敲。4.1 節(jié)點(diǎn)與鏈表骨架template typename T class MyList { private: struct Node { Node* prev; Node* next; T value; Node(const T val T()) : prev(nullptr), next(nullptr), value(val) {} }; Node* head; // 哨兵節(jié)點(diǎn) size_t size_; public: // 迭代器類簡化版只實(shí)現(xiàn)雙向迭代器的基本操作 class iterator { public: Node* node; iterator(Node* n nullptr) : node(n) {} T operator*() { return node-value; } T* operator-() { return node-value; } iterator operator() { node node-next; return *this; } iterator operator--() { node node-prev; return *this; } bool operator(const iterator other) const { return node other.node; } bool operator!(const iterator other) const { return node ! other.node; } }; MyList(); ~MyList(); MyList(const MyList other); iterator begin() { return iterator(head-next); } iterator end() { return iterator(head); } void push_back(const T val); void push_front(const T val); iterator insert(iterator pos, const T val); iterator erase(iterator pos); void clear(); size_t size() const { return size_; } bool empty() const { return size_ 0; } };注意構(gòu)造和析構(gòu)的簽名里我有意寫了三件套里的默認(rèn)構(gòu)造、析構(gòu)、拷貝構(gòu)造而賦值運(yùn)算符operator我沒列全實(shí)際工程必須寫否則淺拷貝會爆炸。下面挨個實(shí)現(xiàn)。4.2 構(gòu)造、析構(gòu)與深拷貝三件套鏈表的構(gòu)造核心是讓頭節(jié)點(diǎn)的 prev 和 next 都指向自己。這樣空鏈表狀態(tài)下begin()end()循環(huán)判斷自然成立。template typename T MyListT::MyList() : head(new Node()), size_(0) { head-prev head; head-next head; }析構(gòu)的職責(zé)是把所有業(yè)務(wù)節(jié)點(diǎn)和頭節(jié)點(diǎn)全部釋放。一個常見的錯誤是只遍歷釋放了業(yè)務(wù)節(jié)點(diǎn)忘了釋放頭節(jié)點(diǎn)造成內(nèi)存泄漏。用erase(begin(), end())語義的話我們就手動寫template typename T MyListT::~MyList() { clear(); delete head; // 頭節(jié)點(diǎn)也要delete }clear()的內(nèi)部實(shí)現(xiàn)我的習(xí)慣是摘一個刪一個絕對不懸空template typename T void MyListT::clear() { while (head-next ! head) { Node* toDelete head-next; head-next toDelete-next; toDelete-next-prev head; delete toDelete; --size_; } }拷貝構(gòu)造必須深拷貝。不能只是把對方節(jié)點(diǎn)的指針復(fù)制過來否則兩個 list 對象會共享同一批節(jié)點(diǎn)任何一方的析構(gòu)都會導(dǎo)致另一方懸空。深拷貝的思路是先構(gòu)造一個空表然后把對方的每個節(jié)點(diǎn)值依次 push_backtemplate typename T MyListT::MyList(const MyList other) : head(new Node()), size_(0) { head-prev head; head-next head; for (Node* cur other.head-next; cur ! other.head; cur cur-next) { push_back(cur-value); } }賦值運(yùn)算符建議走拷貝并交換慣用法copy-and-swap這里不再展開但記住一句話任何涉及裸指針的類默認(rèn)拷貝和默認(rèn)賦值都是定時炸彈。4.3 增刪核心函數(shù)的實(shí)現(xiàn)細(xì)節(jié)前端插入push_front可以利用 insert 來復(fù)用代碼也可以直接手寫。我認(rèn)為手寫一次四指針操作是必要的能讓你對連接順序有肌肉記憶template typename T void MyListT::push_front(const T val) { Node* newNode new Node(val); Node* oldFirst head-next; // 新節(jié)點(diǎn)和后一個節(jié)點(diǎn)建立連接 newNode-next oldFirst; oldFirst-prev newNode; // 新節(jié)點(diǎn)和頭節(jié)點(diǎn)建立連接 newNode-prev head; head-next newNode; size_; }順序上我習(xí)慣先把 newNode 插入到當(dāng)前第一個業(yè)務(wù)節(jié)點(diǎn)之前再回頭調(diào)整頭節(jié)點(diǎn)的指針。你仔細(xì)想一下如果先改head-next newNode那原來的 oldFirst 就被孤立了之后你就再也找不回它了。所以先福利舊節(jié)點(diǎn)、再讓新節(jié)點(diǎn)上桌是鐵的紀(jì)律。insert(pos, val)的語義是在 pos 指向的節(jié)點(diǎn)之前插入新節(jié)點(diǎn)返回新節(jié)點(diǎn)的迭代器template typename T typename MyListT::iterator MyListT::insert(iterator pos, const T val) { Node* cur pos.node; Node* newNode new Node(val); newNode-next cur; newNode-prev cur-prev; cur-prev-next newNode; cur-prev newNode; size_; return iterator(newNode); }erase(pos)要小心如果 pos 指向頭節(jié)點(diǎn)即 end()應(yīng)該直接解引用或者拋錯標(biāo)準(zhǔn)庫中這是未定義行為我們不模擬 UB直接斷言。刪除一個節(jié)點(diǎn)要保證前后節(jié)點(diǎn)繞開被刪除節(jié)點(diǎn)再互相連接template typename T typename MyListT::iterator MyListT::erase(iterator pos) { Node* toDelete pos.node; if (toDelete head) { throw std::invalid_argument(cannot erase head node); } toDelete-prev-next toDelete-next; toDelete-next-prev toDelete-prev; Node* ret toDelete-next; delete toDelete; --size_; return iterator(ret); }整個手寫過程做完你再回頭看 STL list 的行為就通透多了為什么insert返回新節(jié)點(diǎn)迭代器、為什么erase返回后繼節(jié)點(diǎn)迭代器、為什么頭節(jié)點(diǎn)讓所有邊界條件消失。這些全部是自洽的設(shè)計選擇不是隨便定的。5. 常見問題排查與性能誤區(qū)5.1 迭代器失效規(guī)則速查表無論是 STL list 還是我們剛手寫的版本增刪查改中大家都最怕迭代器失效。我整理了 list 與 vector、forward_list 的對比這是面試高頻題也是實(shí)戰(zhàn)選型的核心依據(jù)。容器插入是否導(dǎo)致迭代器失效刪除是否導(dǎo)致迭代器失效隨機(jī)訪問頭部插入vector擴(kuò)容時全部失效不擴(kuò)容時插入點(diǎn)之后的迭代器失效刪除點(diǎn)及之后的迭代器失效O(1)O(n)list不影響任何其他迭代器僅被刪節(jié)點(diǎn)的迭代器失效不支持O(1)forward_list不影響任何其他迭代器單向僅被刪節(jié)點(diǎn)的迭代器失效不支持O(1)deque插入可能使全部迭代器失效刪除點(diǎn)附近的迭代器失效O(1)O(1)這個表我建議貼在顯示器旁邊。list 的迭代器穩(wěn)定性是它最迷人的地方你在遍歷過程中順手插入一個節(jié)點(diǎn)正在用的迭代器一點(diǎn)事沒有你在某個迭代器后面連續(xù) splice 一堆節(jié)點(diǎn)那個迭代器依然穩(wěn)穩(wěn)指向原節(jié)點(diǎn)。這種穩(wěn)定性在寫圖形學(xué)里的圖結(jié)構(gòu)、游戲引擎里的實(shí)體管理、或者消息隊(duì)列的場景中非常寶貴。5.2 list 不是比 vector 慢而是在錯誤場景下慢網(wǎng)上總有人說 list 慢這說法太粗糙了。list 的插入刪除確實(shí)是 O(1)但那是指接口復(fù)雜度不是實(shí)際運(yùn)行時間。鏈表插入一個節(jié)點(diǎn)需要 new 一次內(nèi)存分配而 vector 的尾部 push_back 在容量充足時只是把元素拷貝進(jìn)預(yù)分配緩沖區(qū)壓根沒有堆分配。如果你只是大量尾部添加然后線性遍歷vector 比 list 快出一兩個數(shù)量級很正常。list 真正的主場是這些場景需要頻繁在任意位置插入刪除且你已經(jīng)持有該位置附近的迭代器。需要在遍歷過程中反復(fù)插入刪除且需要保持其他元素的迭代器長期有效。需要頻繁把兩個 list 拼接splice這是 list 獨(dú)門絕技O(1) 搬家。元素本身很大、拷貝成本很高鏈表只需移動指針不用移動對象。另外必須提splice這是 list 壓箱底的本事std::listint a {1, 2, 3}; std::listint b {4, 5, 6}; auto itA std::find(a.begin(), a.end(), 2); b.splice(b.begin(), a, itA); // 把 a 中值為2的節(jié)點(diǎn)搬到 b 的頭部 // b: {2, 4, 5, 6}a: {1, 3}splice做到的是指針的重新接線沒有拷貝沒有任何堆分配。這是 list 獨(dú)有的vector 和 deque 永遠(yuǎn)做不到。5.3 踩坑實(shí)錄與避坑清單這么多年的使用經(jīng)歷我積累了一些值得寫下來的坑。第一個坑錯誤地對 list 使用 std::sort。std::sort要求隨機(jī)訪問迭代器編譯直接報錯。正確的做法是用成員函數(shù)lst.sort()。這里不光是編譯問題就算未來有人給 list 硬寫了排序list::sort 內(nèi)部的歸并排序?qū)︽湵砥鋵?shí)是天然最適配的復(fù)雜度穩(wěn)定 O(n log n) 且不需要額外大塊內(nèi)存。記住lst.sort()默認(rèn)升序加 greater 做降序lst.sort(); // 升序 lst.sort(std::greaterint()); // 降序第二個坑調(diào)用 size() 不是 O(1) 這是歷史問題。C11 之前標(biāo)準(zhǔn)只保證size()是常數(shù)或線性復(fù)雜度很多實(shí)現(xiàn)是線性遍歷的。C11 開始強(qiáng)制 O(1)但如果你用的是老代碼庫在主循環(huán)里頻繁調(diào)用 size() 可能會莫名其妙變慢。同樣empty()永遠(yuǎn)是 O(1)優(yōu)先用 empty 而非 size()0 做判斷。第三個坑在 list 里存了引用或者 const 元素。list 的節(jié)點(diǎn)構(gòu)造和析構(gòu)要求元素類型可拷貝或可移動而且listT是不合法的。如果需要存引用語義用std::reference_wrapperT。我見過有人試圖listconst int編譯直接崩。第四個坑內(nèi)存碎片化。list 每個節(jié)點(diǎn)獨(dú)立 new如果程序長期頻繁增刪千萬級節(jié)點(diǎn)堆上會出現(xiàn)大量碎片并且節(jié)點(diǎn)地址局部性差緩存命中率低遍歷性能完全拼不過連續(xù)內(nèi)存的 vector。排查性能瓶頸時只要看到 profiling 里 list 相關(guān)的 cache miss 高得離譜基本就是該換容器的信號。第五個坑remove、unique、sort 都是成員函數(shù)不要和同名算法混用。std::remove在 list 上不能真正刪除元素它只是把符合條件的值移動到容器尾部然后返回新的邏輯尾你必須再配合 erase 才能完成任務(wù)。而 list 成員函數(shù)remove和unique內(nèi)部已經(jīng)做實(shí)刪除一步到位。搞混了兩種語法輕則邏輯錯誤重則迭代器越界未定義行為。第六個坑splice 移動的是節(jié)點(diǎn)而不是值所以源 list 中對應(yīng)的節(jié)點(diǎn)會消失。如果我在 splice 后還保留著指向那個節(jié)點(diǎn)的迭代器它指向的節(jié)點(diǎn)已經(jīng)歸目標(biāo) list 所有了。這在雙端隊(duì)列或者工作隊(duì)列切換歸屬的場景里很好用但也容易引發(fā)這個節(jié)點(diǎn)到底在哪個 list 里的所有權(quán)困惑?？缛萜?splice 之后用舊的 source 端迭代器繼續(xù)操作就會出現(xiàn)邏輯上的混亂。6. 一點(diǎn)個人實(shí)戰(zhàn)體會如果你問我什么時候會主動用 list 而不是 vector我的答案很明確當(dāng)程序里需要持有某個元素的迭代器、長期不失效、且隨時需要在該元素前后插入或刪除的時候。最典型的例子是圖形渲染引擎里渲染對象的排序鏈表、文本編輯器里的 undo 歷史記錄、以及某些 LRU 緩存的手寫實(shí)現(xiàn)。這些場景如果用 vector每次新增刪除都要搬運(yùn)大片數(shù)據(jù)而且迭代器隨手就失效根本沒法長期持有。我自己手寫 LRU 緩存時核心結(jié)構(gòu)就是std::liststd::pairint, int配合std::unordered_mapint, std::list...::iterator。map 里存的是 list 迭代器飛書命中時用 splice 把節(jié)點(diǎn)挪到鏈表頭淘汰時直接從尾部 pop 并刪除 map 對應(yīng)鍵。整套邏輯依賴的正是 list 迭代器不失效這個鐵律——如果換 vectormap 里的索引下次擴(kuò)容就全廢了。這個案例也推薦大家自己動手實(shí)現(xiàn)一遍做完你對 list 所有接口的掌握會直接上一個臺階。最后給個學(xué)習(xí)順序建議先用 STL list 熟練增刪查改搞定迭代器使用然后手寫一遍簡化版雙向鏈表把樸素實(shí)現(xiàn)里的細(xì)節(jié)搞清楚最后看一遍 libstdc 或 libc 的 list 源碼別怕源碼其實(shí)比你想的容易讀。三條線走完C list 這關(guān)就算徹底過了。希望這篇能幫你省掉一些我當(dāng)年撞墻的時間。