用過STL的人基本都繞不開list這個容器看起來太簡單了——雙向鏈表嘛插入刪除O(1)?？烧姹粏柕絣ist的迭代器為什么不是一個指針它的insert到底做了什么為什么list沒有自己的sort就是編譯錯誤的時候很多寫了幾年C的人也會愣一下。這篇文章我想從list的底層實現(xiàn)出發(fā)把節(jié)點結(jié)構(gòu)、哨兵節(jié)點、迭代器機制和核心操作源碼一層層拆開搞清楚它究竟是怎么工作的。源碼以開源社區(qū)的libstdc風格實現(xiàn)為藍本剝掉模板包裝看核心骨架。對剛接觸STL源碼的讀者來說這篇能幫你建立完整的底層認知少走彎路。1. list的底層數(shù)據(jù)結(jié)構(gòu)雙向鏈表的核心設計1.1 序列容器里的第三個選擇C標準庫提供了三種經(jīng)典序列容器vector、deque、list還有C11加入的forward_list。vector用連續(xù)內(nèi)存隨機訪問快但頭部插入刪除是O(n)deque用分段連續(xù)內(nèi)存兩頭操作是攤還O(1)但中間插入刪除依然是O(n)。list解決的就是這個特定痛點只要你知道位置在任何地方插入或刪除都是O(1)而且不會讓其他元素的迭代器失效。這個能力完全來自底層數(shù)據(jù)結(jié)構(gòu)——雙向鏈表。每個節(jié)點獨立分配節(jié)點之間靠兩個指針連接插入刪除只需要修改相鄰節(jié)點的指針指向不涉及元素本身的搬移。這是理解list一切行為的起點。1.2 節(jié)點結(jié)構(gòu)數(shù)據(jù)加兩個指針在libstdc的實現(xiàn)里節(jié)點不是簡單的一個T加兩個指針而是拆成了基類和派生類兩層// 基類只存指針 struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev; }; // 派生類繼承指針加上數(shù)據(jù) templatetypename T struct _List_node : public _List_node_base { T _M_data; };為什么要這么拆兩個原因。第一所有不依賴具體T類型的鏈表操作都可以只操作指針。比如后面要講的_M_hook把節(jié)點掛到鏈表上和_M_unhook把節(jié)點從鏈表上摘下來它們只關心_M_next和_M_prev兩個指針根本不需要知道T是什么。把指針放在基類里這些函數(shù)就能用不依賴模板參數(shù)的形式寫出來編譯器不用為每個T都實例化一份。第二內(nèi)存布局更清晰。64位系統(tǒng)下一個listint節(jié)點的大小是兩個指針16字節(jié)int數(shù)據(jù)4字節(jié)對齊填充4字節(jié)總共24字節(jié)。稍后看到內(nèi)存對比時你會體會到這個節(jié)點大小直接決定了list的緩存不友好性。1.3 哨兵節(jié)點讓所有邊界情況消失這是list實現(xiàn)里最精妙的一個設計。鏈表里常見的問題是邊界處理空鏈表怎么表示在頭部插入和尾部插入要不要特判迭代器怎么判斷已經(jīng)走完了libstdc的做法是list對象內(nèi)部維護一個哨兵節(jié)點也叫頭節(jié)點它不屬于有效數(shù)據(jù)但永遠存在。templatetypename T, typename Alloc class _List_base { _List_node _M_node; // 哨兵節(jié)點 public: iterator begin() { return iterator(_M_node._M_next); } iterator end() { return iterator(_M_node); } };哨兵節(jié)點的_M_next指向第一個有效節(jié)點_M_prev指向最后一個有效節(jié)點。空鏈表時哨兵節(jié)點的_M_next和_M_prev都指向它自己。這個設計帶來的好處是巨大的空鏈表和非空鏈表統(tǒng)一處理插入、刪除代碼不需要寫if (empty())分支end()不是nullptr而是一個真實存在的地址所以while (it ! lst.end())的循環(huán)永遠安全從尾部往前遍歷也安全--end()就是最后一個元素不會越界插入和刪除操作里哨兵節(jié)點就像一個普通節(jié)點一樣參與指針連接邊界情況自動消失我在教學時習慣把哨兵節(jié)點比作環(huán)形走廊里的起點標志——它不占任何座位但你在走廊里走永遠知道起點在哪也永遠不會走出邊界。2. list迭代器的實現(xiàn)原理為什么它不是一個裸指針2.1 迭代器必須是類對象vector的迭代器在絕大多數(shù)實現(xiàn)里就是一個裸指針因為vector元素內(nèi)存連續(xù)it就是指針1簡單直接。但list不行它的節(jié)點散落在堆上it必須從當前節(jié)點的_M_next取出下一個節(jié)點地址。所以list的迭代器是一個類內(nèi)部封裝了一個指向節(jié)點的指針通過重載運算符來模擬指針行為templatetypename T, typename Ref, typename Ptr struct _List_iterator { _List_node_base* _M_node; _List_iterator operator() { _M_node _M_node-_M_next; return *this; } _List_iterator operator--() { _M_node _M_node-_M_prev; return *this; } bool operator(const _List_iterator x) const { return _M_node x._M_node; } };注意這里_M_node的類型是_List_node_base*而不是_List_nodeT*。為什么因為迭代器只操作指針不需要知道T。等真正訪問數(shù)據(jù)時才把基類指針轉(zhuǎn)回派生類指針。這個設計讓迭代器的增刪查操作不用依賴模板參數(shù)間接減少了模板實例化代碼量。2.2 解引用操作符從指針到引用迭代器的operator*是訪問數(shù)據(jù)的關鍵。標準庫的實現(xiàn)大概是reference operator*() const { return *static_cast_List_nodeT*(_M_node)-_M_valptr(); } pointer operator-() const { return *operator*(); }static_cast_List_nodeT*把基類指針轉(zhuǎn)回具體的節(jié)點類型然后取出_M_data。operator-則是先取引用再取地址這樣it-member這種表達式才能正常工作。這些操作符必須返回引用而不是值否則it-member或者it-value 1這種修改就無效了。這也是為什么迭代器要定義reference和pointer類型別名——它們是STL算法和容器交互的契約。2.3 迭代器失效規(guī)則list最讓人安心的地方看源碼之前先記住list迭代器失效的幾個結(jié)論它們直接來自上面的指針結(jié)構(gòu)insert和splice操作不會使任何迭代器失效erase只會使被刪除元素的迭代器失效其他迭代器全部保持有效push_back、push_front同樣不會讓已有迭代器失效前提是分配內(nèi)存不拋異常對比一下vectorvector只要發(fā)生擴容所有迭代器全部失效erase中間元素后面所有迭代器全部失效。list之所以能這么穩(wěn)根源就在于它不搬元素節(jié)點地址一旦確定就不變。但請注意list的節(jié)點地址不變不代表引用永遠有效。如果那個元素本身被erase了你手里還攥著指向它的迭代器那依然是懸空指針?？煽坎坏扔谌f能這句話下面還會反復提到。3. 核心操作源碼拆解push、insert、erase是怎么改指針的3.1 push_back的完整鏈路push_back是所有操作里最簡單直觀的順著它看整個插入機制void push_back(const T x) { _M_insert(end(), x); } void _M_insert(iterator __position, const value_type __x) { _List_nodeT* __tmp _M_create_node(__x); // 分配節(jié)點拷貝構(gòu)造 __tmp-_M_hook(__position._M_node); // 把節(jié)點掛到position前面 }_M_create_node負責兩件事用分配器分配一塊sizeof(_List_nodeT)的內(nèi)存然后在上面執(zhí)行T的拷貝構(gòu)造。這一步如果拋異常內(nèi)存會正確回滾這是異常安全的基礎。真正改變鏈表結(jié)構(gòu)的是_M_hook它是從SGI STL時代流傳下來的經(jīng)典四步指針操作void _M_hook(_List_node_base* __position) { this-_M_next __position; this-_M_prev __position-_M_prev; __position-_M_prev-_M_next this; __position-_M_prev this; }逐行解釋一下假設要在節(jié)點P前面插入新節(jié)點NN-_M_next P新節(jié)點后繼指向PN-_M_prev P-_M_prev新節(jié)點前驅(qū)指向P的前驅(qū)P-_M_prev-_M_next NP原來的前驅(qū)的后繼指向N第一個斷開的鏈接在這里接上P-_M_prev NP的前驅(qū)指向N步驟3和4的順序不能顛倒因為第4行要用到的P-_M_prev在第3行執(zhí)行后還保留著舊值。實際執(zhí)行時第2行已經(jīng)先把舊前驅(qū)保存到了N-_M_prev里所以第3行和第4行的先后其實就變得不敏感了。但在自己手寫鏈表時我強烈建議用局部變量先保存舊前驅(qū)再改指針這樣最不容易出錯。3.2 insert任意位置插入的通用原語push_back只是insert在end()位置的特例。insert(position, x)的正確定義是在position指向的元素之前插入新元素返回新插入元素的位置。iterator insert(iterator position, const T x) { _List_nodeT* __tmp _M_create_node(x); __tmp-_M_hook(position._M_node); return iterator(__tmp); }這段代碼提示我們一個很容易忽略的事實list的insert返回的是指向新節(jié)點的迭代器而vector::insert返回的是指向最后一個插入元素的迭代器。兩者默認行為都是在pos之前插入但返回值語義相同只是list的O(1)和vector的O(n)差距明顯。如果需要批量插入同一個值n次標準庫內(nèi)部會循環(huán)調(diào)用_M_insert每次新建獨立節(jié)點。這里沒有做一個節(jié)點存多個值之類的優(yōu)化因為鏈表的設計就是每個元素一個節(jié)點。3.3 erase從鏈表里摘下節(jié)點刪除操作比插入稍微多幾個步驟因為除了改寫指針還要釋放資源和內(nèi)存void _M_unhook() { _List_node_base* __next this-_M_next; _List_node_base* __prev this-_M_prev; __prev-_M_next __next; __next-_M_prev __prev; } iterator erase(iterator position) { _List_nodeT* __victim static_cast_List_nodeT*(position._M_node); __victim-_M_unhook(); // 1. 斷開前后指針 // 2. 調(diào)用T的析構(gòu)函數(shù) // 3. 釋放節(jié)點內(nèi)存 return iterator(position._M_node-_M_next); // 返回被刪元素的后繼 }_M_unhook做的是_M_hook的逆操作讓前驅(qū)的_M_next直接指向后繼讓后繼的_M_prev直接指向前驅(qū)被刪除的節(jié)點就從鏈表上脫落了。注意三點。第一返回的迭代器指向被刪元素的下一個位置這是為了配合it lst.erase(it)這種慣用寫法。如果你寫成lst.erase(it)然后繼續(xù)用it就是未定義行為——it已經(jīng)懸空了。第二刪除后必須調(diào)用析構(gòu)函數(shù)。T可能有內(nèi)部資源比如string的堆內(nèi)存漏掉析構(gòu)就是內(nèi)存泄漏。標準庫的做法是先讓節(jié)點的數(shù)據(jù)成員執(zhí)行析構(gòu)再釋放節(jié)點內(nèi)存。第三_M_unhook不關心哨兵節(jié)點。如果刪除的是最后一個有效元素那么__prev和__next都是哨兵節(jié)點它們互相指向?qū)Ψ芥湵砘氐娇諣顟B(tài)。哨兵節(jié)點讓這種情況不需要任何if判斷。3.4 spliceO(1)的鏈表拼接list有一個其他容器都沒有的成員函數(shù)——splice作用是把一個鏈表的一段元素整體轉(zhuǎn)移到另一個鏈表時間復雜度O(1)。void splice(iterator position, list x) { if (x.empty()) return; // 把x的整個鏈表段轉(zhuǎn)移到position之前 position._M_node-_M_transfer(x.begin()._M_node, x.end()._M_node); }底層實現(xiàn)的核心是_M_transfer——將[first, last)區(qū)間整體移動到position之前。這個操作只需要修改三個節(jié)點的指針不復制任何元素所以是常數(shù)時間。std::list::splice配合splice還能實現(xiàn)O(1)的移動單個元素和合并兩個鏈表片段。這在某些場景下極其有用比如實現(xiàn)維護按時間排序的任務隊列時把一個任務從一個隊列挪到另一個隊列splice比eraseinsert快一個數(shù)量級——因為它壓根不構(gòu)造和析構(gòu)元素。4. 內(nèi)存占用與性能畫像list到底省了什么、貴在哪里4.1 節(jié)點分配每次插入都是一次堆分配這是list最容易被忽視的性能代價。vector::push_back在容量足夠時只是拷貝元素到預先分配的內(nèi)存里不涉及堆分配而list::push_back每次都要調(diào)用分配器申請一塊新內(nèi)存。以64位系統(tǒng)下的listint為例每個節(jié)點24字節(jié)其中只有4字節(jié)是你的數(shù)據(jù)20字節(jié)是管理開銷16字節(jié)指針4字節(jié)填充。如果存儲的是int這種小對象list的賬面性能非常難看。默認情況下list使用標準分配器std::allocatorT底層是new/delete。頻繁插入刪除會導致大量小內(nèi)存塊的分配與釋放可能帶來碎片化和性能抖動。某些舊實現(xiàn)里list有專門的內(nèi)存池來緩解這個問題現(xiàn)代標準庫默認不再做節(jié)點池把內(nèi)存策略交給使用者通過Allocator模板參數(shù)定制。4.2 list vs vector vs forward_list一張表看懂維度vectordequelistforward_list底層結(jié)構(gòu)連續(xù)數(shù)組分段連續(xù)數(shù)組雙向鏈表單向鏈表隨機訪問O(1)O(1)O(n)最低效O(n)中間插入刪除O(n)且搬移元素O(n)但仍搬移O(1)改指針O(1)改指針頭插/頭刪O(n)O(1)O(1)O(1)尾插/尾刪O(1)攤還O(1)O(1)O(n)迭代器失效門檻擴容全失效、中途插入后移中間插入失效較多僅刪除元素失效僅刪除元素失效內(nèi)存開銷/元素低可能有預留中等高兩指針對齊低一指針反向遍歷支持支持支持不支持默認排序std::sortstd::sort成員函數(shù)list::sort成員函數(shù)forward_list::sort我把這個表格當作選型時的決策參考要隨機訪問就vector要兩端操作就deque要中間插入且迭代器穩(wěn)定就list想省一個指針的內(nèi)存且只需單向遍歷就forward_list。4.3 什么場景真正需要list根據(jù)我自己的項目經(jīng)驗適合list的場景大致有三個特征已知位置的頻繁插入刪除。如果你總是需要先find再插入那find本身O(n)的代價可能淹沒插入O(1)的好處此時vector二分未必更差。迭代器需要長期保持穩(wěn)定。比如管理一堆對象其他地方長期持有指向這些對象的迭代器且這些對象會被刪除和新增。這時list的非刪除元素迭代器永不失效特性極其寶貴。元素本身不適合移動。C11以后移動語義緩解了vector的拷貝代價但某些類型依然移動成本高或不可移動而list插入時只需要初始化新節(jié)點從不搬動已存在元素。反過來遍歷為主的算法千萬別用list。鏈表節(jié)點在堆上分散遍歷時每次都要跳到一個隨機地址緩存局部性極差。實測大量場景下listint的遍歷性能比vectorint慢一個數(shù)量級都不奇怪。5. 實戰(zhàn)坑點速查迭代器失效、性能誤判與排查經(jīng)驗5.1 迭代器失效的經(jīng)典陷阱erase的返回值最經(jīng)典的錯誤是這樣寫std::listint lst {1, 2, 3, 4, 5}; for (auto it lst.begin(); it ! lst.end(); it) { if (*it % 2 0) { lst.erase(it); // 錯誤erase后it失效再是未定義行為 } }正確寫法是for (auto it lst.begin(); it ! lst.end();) { if (*it % 2 0) { it lst.erase(it); // erase返回下一個迭代器 } else { it; } }這里要特別澄清一個流傳很廣的誤解在list里erase后直接丟棄返回值、然后it通常看起來也能跑因為節(jié)點雖然被釋放但指針值還沒變。這是典型的碰巧沒崩不是合法行為。調(diào)試器查不出來不代表沒問題使用懸空迭代器就是未定義行為。5.2 遍歷中刪除多個節(jié)點的安全姿勢除了erase返回值還有一個替代方案被不少老項目使用——remove_iflst.remove_if([](int x) { return x % 2 0; });remove_if是list的成員函數(shù)底層等價于遍歷erase但它把刪除邏輯封裝好了不會出現(xiàn)迭代器失效問題。標準庫還有remove刪除所有等于某值的元素、unique刪除相鄰重復、merge歸并兩個有序鏈表等成員函數(shù)它們都比手寫循環(huán)更安全。用成員函數(shù)而不是算法有一個技術(shù)原因很多標準算法依賴隨機訪問迭代器而list只提供雙向迭代器。std::remove能在list上運行但它的返回值對list沒什么意義因為它不能真的收縮容器必須配合erase使用而且中間過程會搬移元素——和list的設計思想沖突。凡是list獨有的成員函數(shù)盡量優(yōu)先用成員版本。5.3 排序別用std::sort另一個高頻報錯是std::sort(lst.begin(), lst.end()); // 編譯錯誤沒有隨機訪問迭代器std::sort要求隨機訪問迭代器list的雙向迭代器不滿足。正確做法是用lst.sort()。list::sort的實現(xiàn)通常是歸并排序也有混合插入排序的優(yōu)化版本時間復雜度O(n log n)但它不需要隨機訪問也不需要額外的大塊內(nèi)存只要求能雙向遍歷。注意std::stable_sort也不能用于list。如果面試或筆試里遇到如何給鏈表排序這類題答案既可以是list::sort也可以自己寫歸并排序——自己寫歸并排序時遞歸式地拆鏈表、合并同樣只需要雙向迭代能力。5.4 性能誤判l(wèi)ist不總是快好幾次聽人說我用了list所以插入刪除就是O(1)性能肯定沒問題。這種說法忽略了前置條件。我做過一個簡單測試在100萬個元素的容器中間循環(huán)插入和刪除位置已知的元素list確實比vector快很多但如果是隨機遍歷一遍再插list因為緩存不友好總耗時反而可能超過vector。還有個容易被忽略的角度節(jié)點大小。如果T本身很大比如一個幾百字節(jié)的結(jié)構(gòu)體list節(jié)點里多出兩個指針的開銷占比就變小了list的優(yōu)勢會被放大。反之如果T是int、bool這類小對象list等于每個元素平白多付16字節(jié)的管理成本數(shù)據(jù)量一大內(nèi)存占用和緩存性能都吃虧。5.5 調(diào)試建議看看節(jié)點長什么樣排查鏈表相關問題時我習慣把核心邏輯簡化成最小可復現(xiàn)demo再配合gdb或者打印節(jié)點地址驗證。比如懷疑迭代器失效就在erase前后打印迭代器指向的節(jié)點地址你會發(fā)現(xiàn)erase后那個地址的節(jié)點已經(jīng)被釋放往里面讀數(shù)據(jù)就是踩野指針。如果你在閱讀標準庫源碼認準幾個關鍵函數(shù)_M_hook插入、_M_unhook摘除、_M_transfer區(qū)間轉(zhuǎn)移。這三個函數(shù)理解了list的絕大部分成員函數(shù)都能找出脈絡。其他函數(shù)無非是組合它們再加上分配、析構(gòu)、異常處理。最后一個經(jīng)驗分享寫自定義鏈表時先實現(xiàn)哨兵節(jié)點再實現(xiàn)插入刪除。沒哨兵節(jié)點的鏈表每個操作都要小心翼翼判斷頭尾代碼又長又容易漏。照著list的設計先定義一個哨兵頭節(jié)點插入刪除的四步指針操作就能和標準庫一樣干凈。這個設計思路不光適用于C的鏈表很多環(huán)形隊列、LRU緩存之類的結(jié)構(gòu)都可以借鑒把邊界特判消滅在每個數(shù)據(jù)結(jié)構(gòu)自己的實現(xiàn)里而不是責怪調(diào)用者不小心。