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