點(diǎn)與實(shí)現(xiàn)細(xì)節(jié))
很多人都在用std::list可一旦被問(wèn)到它底層到底怎么實(shí)現(xiàn)的十有八九會(huì)卡殼。std::list底層是一個(gè)雙向鏈表節(jié)點(diǎn)在堆上獨(dú)立分配通過(guò)prev和next指針串起來(lái)跟vector那種連續(xù)內(nèi)存完全是兩個(gè)世界。它解決的是序列容器里“插入刪除不搬元素”的需求為此犧牲了隨機(jī)訪問(wèn)和緩存友好性。這篇文章我會(huì)從設(shè)計(jì)取舍、節(jié)點(diǎn)結(jié)構(gòu)、迭代器、內(nèi)存分配講到手寫(xiě)一個(gè)能跑的最小 list再整理迭代器失效、splice、性能陷阱這些常踩的坑適合想讀 STL 源碼卻不知道從哪下手的讀者也適合準(zhǔn)備 C 面試的朋友。1. 整體設(shè)計(jì)為什么 C 需要 std::list1.1 vector 與 list 的本質(zhì)差異老話說(shuō)“沒(méi)有銀彈”容器也一樣。vector 是連續(xù)內(nèi)存上的動(dòng)態(tài)數(shù)組list 是雙向鏈表兩者在設(shè)計(jì)目標(biāo)上就是互補(bǔ)的。我見(jiàn)過(guò)不少人把 list 當(dāng)成 vector 的“更靈活版本”這其實(shí)是誤解。list 的靈活是有代價(jià)的而且代價(jià)非常實(shí)在。維度vectorstd::list內(nèi)存布局連續(xù)內(nèi)存非連續(xù)節(jié)點(diǎn)指針鏈接隨機(jī)訪問(wèn)O(1) via operator[]不支持只能線性遍歷中間插入/刪除O(n) 移動(dòng)元素找到位置后 O(1) 改指針迭代器類(lèi)型隨機(jī)訪問(wèn)迭代器雙向迭代器緩存友好性高低元素地址穩(wěn)定性擴(kuò)容時(shí)失效始終穩(wěn)定額外空間開(kāi)銷(xiāo)幾乎為零每節(jié)點(diǎn)至少兩個(gè)指針這個(gè)表格基本概括了兩者最核心的區(qū)別。實(shí)際工程里vector 因?yàn)榫彺嬗押煤碗S機(jī)訪問(wèn)優(yōu)勢(shì)往往是默認(rèn)選擇而 list 真正的舞臺(tái)是“頻繁在已知位置插入刪除、元素拷貝代價(jià)高、需要長(zhǎng)期持有指向元素的指針”這類(lèi)場(chǎng)景。1.2 雙向鏈表的設(shè)計(jì)取舍既然要深挖底層第一個(gè)問(wèn)題就是為什么是雙向鏈表而不是單向鏈表很簡(jiǎn)單單向鏈表想刪除一個(gè)已知節(jié)點(diǎn)必須從頭遍歷找到前驅(qū)否則鏈表就斷了。這樣刪除操作就不是 O(1)而是 O(n)list 的價(jià)值直接打折。雙向鏈表每個(gè)節(jié)點(diǎn)都保存前驅(qū)和后繼指針拿到當(dāng)前節(jié)點(diǎn)就能同時(shí)改前驅(qū)的 next 和后繼的 prev刪除操作才能做到常數(shù)時(shí)間。雙向的另一個(gè)價(jià)值是反向遍歷。STL 里的 reverse_iterator 底層就是包裝了普通雙向迭代器正著走是 反向走實(shí)際是 --。如果沒(méi)有雙向指針reverse_iterator、rbegin() 這些接口全都無(wú)從談起。所以雙向鏈表不是拍腦袋決定的它是“刪除 O(1) 反向遍歷 迭代器靈活性”三件事共同推出來(lái)的結(jié)果。代價(jià)就是每個(gè)節(jié)點(diǎn)多了一個(gè)指針的開(kāi)銷(xiāo)64 位平臺(tái)上一個(gè)節(jié)點(diǎn)額外占用 16 字節(jié)。1.3 標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)里的哨兵節(jié)點(diǎn)如果你打開(kāi) GCC 的 libstdc 頭文件會(huì)看到_List_node_base、_List_node_header這些東西。它們不是為了炫技而是為了解決一個(gè)很樸素的問(wèn)題空鏈表怎么處理邊界。有了哨兵節(jié)點(diǎn)也叫頭節(jié)點(diǎn)、啞節(jié)點(diǎn)空鏈表不是head nullptr而是哨兵節(jié)點(diǎn)的 next 和 prev 都指向自己。這樣插入刪除不需要寫(xiě)一堆 if 判斷首尾邊界統(tǒng)一邏輯在任意位置插入只需要把當(dāng)前節(jié)點(diǎn)的前驅(qū)和后繼與新節(jié)點(diǎn)互相連起來(lái)刪除同理。哨兵節(jié)點(diǎn)同時(shí)也是end()迭代器指向的位置。begin()是哨兵的 nextend()是哨兵本身完美符合 STL 前閉后開(kāi)區(qū)間的習(xí)慣。我給新手講 list 時(shí)最?lèi)?ài)說(shuō)一句話把哨兵節(jié)點(diǎn)當(dāng)成環(huán)上的一個(gè)“錨點(diǎn)”所有節(jié)點(diǎn)的 next 最終都會(huì)回到哨兵所有節(jié)點(diǎn)的 prev 最終也都會(huì)回到哨兵。理解這一點(diǎn)list 的實(shí)現(xiàn)就通了。2. 核心細(xì)節(jié)拆解節(jié)點(diǎn)、迭代器與內(nèi)存管理2.1 節(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)和指針的布局std::list 的節(jié)點(diǎn)不是簡(jiǎn)單的“三個(gè)成員塞一塊”。為了性能標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)會(huì)做很多細(xì)節(jié)優(yōu)化。在 libstdc 里節(jié)點(diǎn)結(jié)構(gòu)大概是這個(gè)樣子struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev; }; template typename _Tp struct _List_node : public _List_node_base { _Tp _M_data; };故意把基類(lèi)單獨(dú)拆出來(lái)是有原因的鏈表的鏈接操作只關(guān)心 next 和 prev根本不關(guān)心 T 是什么。把這兩個(gè)指針抽到基類(lèi)_List_node_base的插入刪除函數(shù)就能完全脫離模板類(lèi)型避免模板代碼膨脹。你可能會(huì)問(wèn)為什么不像普通教科書(shū)那樣直接寫(xiě)template typename T struct node { node* prev; node* next; T data; };這種寫(xiě)法也能工作但在標(biāo)準(zhǔn)庫(kù)這種“連內(nèi)存對(duì)齊都摳”的場(chǎng)景里基類(lèi)劃分配合__aligned_membuf這類(lèi)工具能更靈活地控制數(shù)據(jù)成員的對(duì)齊與構(gòu)造時(shí)機(jī)。實(shí)際源碼里數(shù)據(jù)不是直接放在派生類(lèi)里而是用_M_storage這樣的對(duì)齊緩沖保存再通過(guò)_M_valptr()獲取真正對(duì)象的指針。這樣做的核心目的把“內(nèi)存分配/釋放”和“對(duì)象構(gòu)造/析構(gòu)”徹底解耦配合 allocator_traits 做更精細(xì)的內(nèi)存管理。2.2 迭代器雙向遍歷的秘密list 的迭代器本質(zhì)上就是一個(gè)指針包裝類(lèi)。它不需要像 vector 那樣存儲(chǔ)“位置 容器”信息只需要一個(gè)指向節(jié)點(diǎn)基類(lèi)的指針。關(guān)鍵重載很簡(jiǎn)單template typename T struct list_iterator { _List_node_base* node; // 實(shí)際源碼里通常還帶分配器或容器指針這里簡(jiǎn)化 T operator*() const { return static_cast_List_nodeT*(node)-_M_data; } list_iterator operator() { node node-_M_next; return *this; } list_iterator operator--() { node node-_M_prev; return *this; } bool operator(const list_iterator rhs) const { return node rhs.node; } };有沒(méi)有發(fā)現(xiàn)迭代器自增自減就是“指針后移到 next / 前移到 prev”這和鏈表本身的操作完全一一對(duì)應(yīng)。因?yàn)?list 節(jié)點(diǎn)在內(nèi)存里不連續(xù)所以迭代器不支持it 5這種隨機(jī)跳躍。編譯器層面就是沒(méi)重載operator語(yǔ)義層面是做不到。這里有個(gè)值得注意的細(xì)節(jié)list 的迭代器雙向都可以走所以std::sort不能對(duì)它生效因?yàn)?sort 需要隨機(jī)訪問(wèn)迭代器。list 有自己的成員函數(shù)sort()那是基于歸并排序?qū)崿F(xiàn)的只用了 prev/next 就能完成。這也是為什么你的代碼里如果對(duì) list 用了std::sort編譯會(huì)報(bào)錯(cuò)的根本原因。2.3 內(nèi)存分配行為與性能賬單list 每插入一個(gè)元素就要單獨(dú)分配一個(gè)節(jié)點(diǎn)每次push_back都走一次 allocator。默認(rèn)的std::allocator底層就是單個(gè)operator new意味著插入 100 萬(wàn)個(gè)元素會(huì)有 100 萬(wàn)次小型內(nèi)存分配。內(nèi)存分配是有系統(tǒng)調(diào)用的時(shí)間開(kāi)銷(xiāo)不小。對(duì)比 vectorvector 擴(kuò)容時(shí)是一次性分配一大塊然后拷貝/移動(dòng)元素老內(nèi)存批量釋放。雖然元素拷貝有成本但分配次數(shù)少整體往往更快。list 的優(yōu)勢(shì)不用在“總耗時(shí)”上而是用在“每次操作都是可控常數(shù) 已有元素一根汗毛都不動(dòng)”上。實(shí)際工程中如果確實(shí)大量使用 list可以考慮給它配一個(gè)內(nèi)存池分配器把節(jié)點(diǎn)內(nèi)存一次性申請(qǐng)并按塊分配。標(biāo)準(zhǔn)庫(kù)的std::listT, Allocator第二個(gè)模板參數(shù)就是干這個(gè)的。比如在嵌入式或游戲服務(wù)器場(chǎng)景小對(duì)象分配器能顯著降低碎片和時(shí)間開(kāi)銷(xiāo)。但別為了炫技而亂換分配器默認(rèn)分配器在節(jié)點(diǎn)生命周期分散、數(shù)量不大時(shí)完全夠用。3. 實(shí)操過(guò)程手寫(xiě)一個(gè)最小可用的 list3.1 環(huán)境準(zhǔn)備與代碼骨架準(zhǔn)備一個(gè) C11 以上環(huán)境任意編譯器都行。我們手寫(xiě)一個(gè)簡(jiǎn)化版list重點(diǎn)展示三大塊節(jié)點(diǎn)定義、迭代器、插入刪除邏輯。完整可編譯代碼在下面建議自己敲一遍比看十遍源碼都管用。#include iostream template typename T struct list_node { list_node* prev; list_node* next; T data; explicit list_node(const T value) : prev(nullptr), next(nullptr), data(value) {} }; template typename T class list_iterator { list_nodeT* ptr; public: explicit list_iterator(list_nodeT* p nullptr) : ptr(p) {} T operator*() const { return ptr-data; } T* operator-() const { return ptr-data; } list_iterator operator() { ptr ptr-next; return *this; } list_iterator operator(int) { list_iterator tmp *this; (*this); return tmp; } list_iterator operator--() { ptr ptr-prev; return *this; } list_iterator operator--(int) { list_iterator tmp *this; --(*this); return tmp; } bool operator(const list_iterator rhs) const { return ptr rhs.ptr; } bool operator!(const list_iterator rhs) const { return ptr ! rhs.ptr; } };節(jié)點(diǎn)就是“雙指針 數(shù)據(jù)”。迭代器只封裝一個(gè)裸指針?biāo)胁僮鞫纪ㄟ^(guò)指針往返。3.2 容器類(lèi)實(shí)現(xiàn)插入與刪除的關(guān)鍵邏輯接下來(lái)是容器主體重點(diǎn)看 insert 和 erase 里指針怎么連接。我給這個(gè)類(lèi)禁用了拷貝構(gòu)造這只是一個(gè)教學(xué)簡(jiǎn)化真實(shí) list 是支持拷貝的。template typename T class list { using node list_nodeT; node* head; // 哨兵節(jié)點(diǎn) size_t sz 0; public: using iterator list_iteratorT; list() : head(new node(T())) { head-prev head; head-next head; } ~list() { clear(); delete head; } list(const list) delete; list operator(const list) delete; iterator begin() { return iterator(head-next); } iterator end() { return iterator(head); } bool empty() const { return sz 0; } size_t size() const { return sz; } void push_back(const T value) { insert(end(), value); } void push_front(const T value) { insert(begin(), value); } iterator insert(iterator pos, const T value) { node* cur pos.operator-(); // 這里簡(jiǎn)單演示實(shí)際建議提供私有接口 // 實(shí)際上應(yīng)該通過(guò)迭代器拿指針下面用 cur node* prev_node cur-prev; node* new_node new node(value); prev_node-next new_node; new_node-prev prev_node; new_node-next cur; cur-prev new_node; sz; return iterator(new_node); } iterator erase(iterator pos) { node* cur pos.operator-(); node* prev_node cur-prev; node* next_node cur-next; prev_node-next next_node; next_node-prev prev_node; delete cur; --sz; return iterator(next_node); } void clear() { node* cur head-next; while (cur ! head) { node* tmp cur; cur cur-next; delete tmp; } head-next head; head-prev head; sz 0; } };上面insert里我用了一個(gè)不太優(yōu)雅的方式獲取 pos 里的節(jié)點(diǎn)指針。實(shí)際上應(yīng)該給迭代器加一個(gè)friend聲明或者提供一個(gè)內(nèi)部函數(shù)。自己寫(xiě)的時(shí)候可以這樣改template typename T class list { // 在容器內(nèi)直接訪問(wèn)迭代器私有成員 friend class list_iteratorT; ... };但為了示例簡(jiǎn)潔也可以給迭代器增加一個(gè)_node()方法。這里更推薦的做法是讓迭代器公開(kāi)get()返回裸指針雖然是教學(xué)實(shí)現(xiàn)但設(shè)計(jì)上更干凈。修正后的核心邏輯應(yīng)該是iterator insert(iterator pos, const T value) { node* cur pos.get(); // 獲取待插入位置的節(jié)點(diǎn)指針 node* prev_node cur-prev; node* new_node new node(value); prev_node-next new_node; new_node-prev prev_node; new_node-next cur; cur-prev new_node; sz; return iterator(new_node); } iterator erase(iterator pos) { node* cur pos.get(); node* prev_node cur-prev; node* next_node cur-next; prev_node-next next_node; next_node-prev prev_node; delete cur; --sz; return iterator(next_node); }所以在最終實(shí)現(xiàn)里給list_iterator這樣加一個(gè)方法list_nodeT* get() const { return ptr; }然后容器直接調(diào)用pos.get()。3.3 運(yùn)行測(cè)試與結(jié)果分析完整測(cè)試代碼如下int main() { listint l; l.push_back(1); l.push_back(2); l.push_front(0); std::cout 初始序列: ; for (int v : l) std::cout v ; std::cout \n; auto it l.begin(); it; // 指向第二個(gè)元素 l.insert(it, 99); // 在第二個(gè)元素之前插入 99 l.erase(l.begin()); // 刪除第一個(gè)元素 std::cout 操作后: ; for (int v : l) std::cout v ; std::cout \n; std::cout size l.size() \n; return 0; }輸出結(jié)果初始序列: 0 1 2 操作后: 1 99 2 size 3范圍 for 能直接跑說(shuō)明 begin/end 和迭代器的!、*、都符合要求。你也可以手動(dòng)測(cè)試--l.end()會(huì)發(fā)現(xiàn)它確實(shí)能正確跑到最后一個(gè)節(jié)點(diǎn)這就是雙向鏈表的底氣。3.4 從手寫(xiě)實(shí)現(xiàn)反推標(biāo)準(zhǔn)庫(kù)設(shè)計(jì)自己寫(xiě)完一遍再看 libstdc 的_List_node_base::hook和unhook就會(huì)非常親切。核心永遠(yuǎn)都是四步改前驅(qū)的 next、改當(dāng)前節(jié)點(diǎn)的 prev、改當(dāng)前節(jié)點(diǎn)的 next、改后繼的 prev。順序可以換但絕不能漏。漏一步就是內(nèi)存踩踏或者環(huán)斷裂嚴(yán)重時(shí)程序直接崩潰。標(biāo)準(zhǔn)庫(kù)代碼看起來(lái)晦澀是因?yàn)樗压?jié)點(diǎn)聲明、分配器、構(gòu)造源碼、插入算法拆到不同基類(lèi)和成員函數(shù)里。但底子跟我們手寫(xiě)的完全一樣。讀源碼時(shí)不要逐行背抓“指針?biāo)牟阶摺本蛪蛄恕?. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄4.1 迭代器失效的“豁免”與例外list 對(duì)迭代器的承諾比 vector 好得多插入不會(huì)讓任何既有迭代器失效刪除只會(huì)讓指向被刪元素的迭代器失效其他迭代器不受影響。這條規(guī)則讓 list 在某些場(chǎng)景成為必然選擇。比如你持有一個(gè)指向 list 元素的迭代器另一個(gè)線程或者另一段代碼在中間插入了新元素你手里的迭代器依舊有效。但有兩個(gè)例外必須記住erase之后指向已刪除節(jié)點(diǎn)的迭代器失效這個(gè)失效是實(shí)打?qū)嵉睦^續(xù)解引用就是未定義行為。clear()或容器析構(gòu)之后所有迭代器都失效雖然迭代器對(duì)象本身可能還保存著舊地址但那個(gè)節(jié)點(diǎn)已經(jīng)歸還給內(nèi)存了碰都不能碰。還有一點(diǎn)經(jīng)常被忽略std::list::remove和std::list::erase不同。remove是遍歷并刪除所有匹配值的元素它會(huì)把匹配的元素刪掉然后把不匹配的元素按原順序留下來(lái)的迭代器返回。寫(xiě)代碼時(shí)千萬(wàn)別拿 Python 列表 remove 的錯(cuò)誤習(xí)慣套 C。4.2 緩存不友好為什么別拿 list 當(dāng)數(shù)組用鏈表節(jié)點(diǎn)散落在堆里每個(gè)節(jié)點(diǎn)之間距離大CPU 緩存命中率很低。遍歷一個(gè)含有 100 萬(wàn)個(gè) int 的 list要經(jīng)歷 100 萬(wàn)次指針跳轉(zhuǎn)而遍歷等量數(shù)據(jù)的 vector 幾乎就是線性掃描內(nèi)存。實(shí)測(cè)下來(lái)遍歷 list 比 vector 慢一個(gè)數(shù)量級(jí)很正常。這不是說(shuō) list 一無(wú)是處而是說(shuō)你要在正確場(chǎng)景用它。只在頻繁“插入/刪除 不遍歷全量數(shù)據(jù) 需要元素地址穩(wěn)定”的組合下list 的優(yōu)勢(shì)才真正兌現(xiàn)。如果你只是往屁股后頭追加數(shù)據(jù)偶爾讀讀末尾那 deque 或 vector 都更好。我自己的經(jīng)驗(yàn)法則需要隨機(jī)訪問(wèn) → 別選 list主要在頭部和尾部操作 → deque 更合適元素拷貝成本極高想在中間反復(fù)插入刪除 → list需要穩(wěn)定的引用/指針指向元素同時(shí)還要?jiǎng)討B(tài)增刪 → list4.3 splice零拷貝的節(jié)點(diǎn)搬家list 最容易被低估的功能是 splice。它能將一個(gè) list 中的節(jié)點(diǎn)直接“搬”到另一個(gè) list不拷貝元素不新建節(jié)點(diǎn)純粹改指針。這是個(gè) O(1) 操作很多面試題都會(huì)問(wèn)。std::listint a{1, 2, 3}; std::listint b{4, 5}; auto it a.begin(); it; // 指向 2 a.splice(it, b); // 把 b 所有節(jié)點(diǎn)搬到 a 中 2 的前面 // a: 1 4 5 2 3 // b: 空如果用inserterase一步一步做那就要復(fù)制每個(gè)元素復(fù)雜度是 O(n)還可能引發(fā)元素拷貝的額外開(kāi)銷(xiāo)。splice 是 list 獨(dú)有的“指針搬運(yùn)工”也是 list 在鏈表 merge、LRU 淘汰、任務(wù)隊(duì)列重組這些場(chǎng)景里不可替代的原因。有個(gè)容易踩的坑C11 之前標(biāo)準(zhǔn)沒(méi)有強(qiáng)制要求 splice 后size()實(shí)時(shí)更新所以跨 list splice 之后讀取 size 可能是錯(cuò)的?，F(xiàn)在 C11 要求容器 size 為 O(1)所以 splice 的庫(kù)實(shí)現(xiàn)必須同步維護(hù)兩個(gè) list 的大小。但這只在“自己寫(xiě)容器”時(shí)才是隱患用標(biāo)準(zhǔn)庫(kù)不用擔(dān)心前提是編譯器支持 C11 以上。4.4 經(jīng)典組合list 哈希表實(shí)現(xiàn) LRU Cache我在實(shí)際項(xiàng)目中用得最爽的組合就是std::list std::unordered_map做 LRU 緩存。list 保存實(shí)際數(shù)據(jù)unordered_map 保存 key 到 list 迭代器的映射。命中緩存時(shí)先用 key 查出迭代器再splice把對(duì)應(yīng)節(jié)點(diǎn)挪到鏈表頭部新數(shù)據(jù)插入時(shí)往頭部push_front。整個(gè)更新和淘汰都是 O(1)而且因?yàn)?list 元素的地址穩(wěn)定哈希表里保存的迭代器不會(huì)因?yàn)椴迦胄略囟А＿@個(gè)組合能成立完全建立在 list 的迭代器不失效特性上。有一次我在這套代碼上踩過(guò)坑從哈希表取迭代器后在另一個(gè)地方誤調(diào)用了erase再拿舊迭代器去splice程序直接野指針崩潰。排查了很久才定位到是“失效迭代器被復(fù)用”。所以我會(huì)格外強(qiáng)調(diào)從容器里拿到迭代器后它只能用于其指向?qū)ο筮€活著的時(shí)刻一旦 erase 或容器析構(gòu)立刻把它當(dāng)廢紙扔掉。4.5 fork 檢查手寫(xiě) list 常見(jiàn)的三個(gè)錯(cuò)誤如果是自己實(shí)現(xiàn)鏈表最容易犯三個(gè)錯(cuò)忘記更新哨兵節(jié)點(diǎn)的 prev/next導(dǎo)致 begin() 或 end() 指向空或舊節(jié)點(diǎn)。釋放節(jié)點(diǎn)后前驅(qū)的 next 沒(méi)有正確指向后繼鏈表斷開(kāi)。析構(gòu)時(shí)只釋放了數(shù)據(jù)節(jié)點(diǎn)忘記 delete 哨兵節(jié)點(diǎn)或者釋放哨兵節(jié)點(diǎn)后沒(méi)有把 iterator 置空懸垂指針被人碰到就是事故。這三個(gè)錯(cuò)誤都靠調(diào)試器死磕過(guò)很多次。所以我給讀者的建議是自己動(dòng)手寫(xiě) list 時(shí)先畫(huà)圖把哨兵、首節(jié)點(diǎn)、尾節(jié)點(diǎn)連一遍再下筆。畫(huà)圖五分鐘能省調(diào)試五小時(shí)。4.6 別被“l(fā)ist 接口”迷惑它包含哪些常用能力最后說(shuō)說(shuō)熱詞里常出現(xiàn)的 “l(fā)ist接口”。不少初學(xué)者把List接口和std::list混為一談。std::list的常用接口大概分幾類(lèi)元素訪問(wèn)front()、back()沒(méi)有operator[]迭代器begin()、end()、rbegin()、rend()容量empty()、size()、max_size()修改push_front()、push_back()、pop_front()、pop_back()、insert()、erase()、clear()鏈表特有操作splice()、remove()、remove_if()、unique()、merge()、sort()、reverse()這些獨(dú)有的鏈表操作就是它存在的意義。sort()和merge()依賴雙向節(jié)點(diǎn)的指針移動(dòng)unique()快速去重reverse()能把鏈表原地反轉(zhuǎn)。這些操作在 vector 上要么做不到要么代價(jià)巨大。但注意它們大多是成員函數(shù)不是 std 算法這也是因?yàn)榈餍枨蟛黄ヅ洹Ｔ趯?shí)際工程里list 通常不是“默認(rèn)容器”但它像是工具箱里的一把內(nèi)六角扳手平時(shí)用不到一旦遇到“需要穩(wěn)定引用 快速插入刪除 節(jié)點(diǎn)搬家”的組合你才會(huì)意識(shí)到它的好。最后那個(gè) splice 的小技巧是 list 留給有心人的彩蛋用好了能讓代碼在數(shù)據(jù)移動(dòng)上省掉一大截開(kāi)銷(xiāo)。 std::list 底層探秘：雙向鏈表、哨兵節(jié)點(diǎn)與實(shí)現(xiàn)細(xì)節(jié)
很多人都在用std::list可一旦被問(wèn)到它底層到底怎么實(shí)現(xiàn)的十有八九會(huì)卡殼。std::list底層是一個(gè)雙向鏈表節(jié)點(diǎn)在堆上獨(dú)立分配通過(guò)prev和next指針串起來(lái)跟vector那種連續(xù)內(nèi)存完全是兩個(gè)世界。它解決的是序列容器里“插入刪除不搬元素”的需求為此犧牲了隨機(jī)訪問(wèn)和緩存友好性。這篇文章我會(huì)從設(shè)計(jì)取舍、節(jié)點(diǎn)結(jié)構(gòu)、迭代器、內(nèi)存分配講到手寫(xiě)一個(gè)能跑的最小 list再整理迭代器失效、splice、性能陷阱這些常踩的坑適合想讀 STL 源碼卻不知道從哪下手的讀者也適合準(zhǔn)備 C 面試的朋友。1. 整體設(shè)計(jì)為什么 C 需要 std::list1.1 vector 與 list 的本質(zhì)差異老話說(shuō)“沒(méi)有銀彈”容器也一樣。vector 是連續(xù)內(nèi)存上的動(dòng)態(tài)數(shù)組list 是雙向鏈表兩者在設(shè)計(jì)目標(biāo)上就是互補(bǔ)的。我見(jiàn)過(guò)不少人把 list 當(dāng)成 vector 的“更靈活版本”這其實(shí)是誤解。list 的靈活是有代價(jià)的而且代價(jià)非常實(shí)在。維度vectorstd::list內(nèi)存布局連續(xù)內(nèi)存非連續(xù)節(jié)點(diǎn)指針鏈接隨機(jī)訪問(wèn)O(1) via operator[]不支持只能線性遍歷中間插入/刪除O(n) 移動(dòng)元素找到位置后 O(1) 改指針迭代器類(lèi)型隨機(jī)訪問(wèn)迭代器雙向迭代器緩存友好性高低元素地址穩(wěn)定性擴(kuò)容時(shí)失效始終穩(wěn)定額外空間開(kāi)銷(xiāo)幾乎為零每節(jié)點(diǎn)至少兩個(gè)指針這個(gè)表格基本概括了兩者最核心的區(qū)別。實(shí)際工程里vector 因?yàn)榫彺嬗押煤碗S機(jī)訪問(wèn)優(yōu)勢(shì)往往是默認(rèn)選擇而 list 真正的舞臺(tái)是“頻繁在已知位置插入刪除、元素拷貝代價(jià)高、需要長(zhǎng)期持有指向元素的指針”這類(lèi)場(chǎng)景。1.2 雙向鏈表的設(shè)計(jì)取舍既然要深挖底層第一個(gè)問(wèn)題就是為什么是雙向鏈表而不是單向鏈表很簡(jiǎn)單單向鏈表想刪除一個(gè)已知節(jié)點(diǎn)必須從頭遍歷找到前驅(qū)否則鏈表就斷了。這樣刪除操作就不是 O(1)而是 O(n)list 的價(jià)值直接打折。雙向鏈表每個(gè)節(jié)點(diǎn)都保存前驅(qū)和后繼指針拿到當(dāng)前節(jié)點(diǎn)就能同時(shí)改前驅(qū)的 next 和后繼的 prev刪除操作才能做到常數(shù)時(shí)間。雙向的另一個(gè)價(jià)值是反向遍歷。STL 里的 reverse_iterator 底層就是包裝了普通雙向迭代器正著走是 反向走實(shí)際是 --。如果沒(méi)有雙向指針reverse_iterator、rbegin() 這些接口全都無(wú)從談起。所以雙向鏈表不是拍腦袋決定的它是“刪除 O(1) 反向遍歷 迭代器靈活性”三件事共同推出來(lái)的結(jié)果。代價(jià)就是每個(gè)節(jié)點(diǎn)多了一個(gè)指針的開(kāi)銷(xiāo)64 位平臺(tái)上一個(gè)節(jié)點(diǎn)額外占用 16 字節(jié)。1.3 標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)里的哨兵節(jié)點(diǎn)如果你打開(kāi) GCC 的 libstdc 頭文件會(huì)看到_List_node_base、_List_node_header這些東西。它們不是為了炫技而是為了解決一個(gè)很樸素的問(wèn)題空鏈表怎么處理邊界。有了哨兵節(jié)點(diǎn)也叫頭節(jié)點(diǎn)、啞節(jié)點(diǎn)空鏈表不是head nullptr而是哨兵節(jié)點(diǎn)的 next 和 prev 都指向自己。這樣插入刪除不需要寫(xiě)一堆 if 判斷首尾邊界統(tǒng)一邏輯在任意位置插入只需要把當(dāng)前節(jié)點(diǎn)的前驅(qū)和后繼與新節(jié)點(diǎn)互相連起來(lái)刪除同理。哨兵節(jié)點(diǎn)同時(shí)也是end()迭代器指向的位置。begin()是哨兵的 nextend()是哨兵本身完美符合 STL 前閉后開(kāi)區(qū)間的習(xí)慣。我給新手講 list 時(shí)最?lèi)?ài)說(shuō)一句話把哨兵節(jié)點(diǎn)當(dāng)成環(huán)上的一個(gè)“錨點(diǎn)”所有節(jié)點(diǎn)的 next 最終都會(huì)回到哨兵所有節(jié)點(diǎn)的 prev 最終也都會(huì)回到哨兵。理解這一點(diǎn)list 的實(shí)現(xiàn)就通了。2. 核心細(xì)節(jié)拆解節(jié)點(diǎn)、迭代器與內(nèi)存管理2.1 節(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)和指針的布局std::list 的節(jié)點(diǎn)不是簡(jiǎn)單的“三個(gè)成員塞一塊”。為了性能標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)會(huì)做很多細(xì)節(jié)優(yōu)化。在 libstdc 里節(jié)點(diǎn)結(jié)構(gòu)大概是這個(gè)樣子struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev; }; template typename _Tp struct _List_node : public _List_node_base { _Tp _M_data; };故意把基類(lèi)單獨(dú)拆出來(lái)是有原因的鏈表的鏈接操作只關(guān)心 next 和 prev根本不關(guān)心 T 是什么。把這兩個(gè)指針抽到基類(lèi)_List_node_base的插入刪除函數(shù)就能完全脫離模板類(lèi)型避免模板代碼膨脹。你可能會(huì)問(wèn)為什么不像普通教科書(shū)那樣直接寫(xiě)template typename T struct node { node* prev; node* next; T data; };這種寫(xiě)法也能工作但在標(biāo)準(zhǔn)庫(kù)這種“連內(nèi)存對(duì)齊都摳”的場(chǎng)景里基類(lèi)劃分配合__aligned_membuf這類(lèi)工具能更靈活地控制數(shù)據(jù)成員的對(duì)齊與構(gòu)造時(shí)機(jī)。實(shí)際源碼里數(shù)據(jù)不是直接放在派生類(lèi)里而是用_M_storage這樣的對(duì)齊緩沖保存再通過(guò)_M_valptr()獲取真正對(duì)象的指針。這樣做的核心目的把“內(nèi)存分配/釋放”和“對(duì)象構(gòu)造/析構(gòu)”徹底解耦配合 allocator_traits 做更精細(xì)的內(nèi)存管理。2.2 迭代器雙向遍歷的秘密list 的迭代器本質(zhì)上就是一個(gè)指針包裝類(lèi)。它不需要像 vector 那樣存儲(chǔ)“位置 容器”信息只需要一個(gè)指向節(jié)點(diǎn)基類(lèi)的指針。關(guān)鍵重載很簡(jiǎn)單template typename T struct list_iterator { _List_node_base* node; // 實(shí)際源碼里通常還帶分配器或容器指針這里簡(jiǎn)化 T operator*() const { return static_cast_List_nodeT*(node)-_M_data; } list_iterator operator() { node node-_M_next; return *this; } list_iterator operator--() { node node-_M_prev; return *this; } bool operator(const list_iterator rhs) const { return node rhs.node; } };有沒(méi)有發(fā)現(xiàn)迭代器自增自減就是“指針后移到 next / 前移到 prev”這和鏈表本身的操作完全一一對(duì)應(yīng)。因?yàn)?list 節(jié)點(diǎn)在內(nèi)存里不連續(xù)所以迭代器不支持it 5這種隨機(jī)跳躍。編譯器層面就是沒(méi)重載operator語(yǔ)義層面是做不到。這里有個(gè)值得注意的細(xì)節(jié)list 的迭代器雙向都可以走所以std::sort不能對(duì)它生效因?yàn)?sort 需要隨機(jī)訪問(wèn)迭代器。list 有自己的成員函數(shù)sort()那是基于歸并排序?qū)崿F(xiàn)的只用了 prev/next 就能完成。這也是為什么你的代碼里如果對(duì) list 用了std::sort編譯會(huì)報(bào)錯(cuò)的根本原因。2.3 內(nèi)存分配行為與性能賬單list 每插入一個(gè)元素就要單獨(dú)分配一個(gè)節(jié)點(diǎn)每次push_back都走一次 allocator。默認(rèn)的std::allocator底層就是單個(gè)operator new意味著插入 100 萬(wàn)個(gè)元素會(huì)有 100 萬(wàn)次小型內(nèi)存分配。內(nèi)存分配是有系統(tǒng)調(diào)用的時(shí)間開(kāi)銷(xiāo)不小。對(duì)比 vectorvector 擴(kuò)容時(shí)是一次性分配一大塊然后拷貝/移動(dòng)元素老內(nèi)存批量釋放。雖然元素拷貝有成本但分配次數(shù)少整體往往更快。list 的優(yōu)勢(shì)不用在“總耗時(shí)”上而是用在“每次操作都是可控常數(shù) 已有元素一根汗毛都不動(dòng)”上。實(shí)際工程中如果確實(shí)大量使用 list可以考慮給它配一個(gè)內(nèi)存池分配器把節(jié)點(diǎn)內(nèi)存一次性申請(qǐng)并按塊分配。標(biāo)準(zhǔn)庫(kù)的std::listT, Allocator第二個(gè)模板參數(shù)就是干這個(gè)的。比如在嵌入式或游戲服務(wù)器場(chǎng)景小對(duì)象分配器能顯著降低碎片和時(shí)間開(kāi)銷(xiāo)。但別為了炫技而亂換分配器默認(rèn)分配器在節(jié)點(diǎn)生命周期分散、數(shù)量不大時(shí)完全夠用。3. 實(shí)操過(guò)程手寫(xiě)一個(gè)最小可用的 list3.1 環(huán)境準(zhǔn)備與代碼骨架準(zhǔn)備一個(gè) C11 以上環(huán)境任意編譯器都行。我們手寫(xiě)一個(gè)簡(jiǎn)化版list重點(diǎn)展示三大塊節(jié)點(diǎn)定義、迭代器、插入刪除邏輯。完整可編譯代碼在下面建議自己敲一遍比看十遍源碼都管用。#include iostream template typename T struct list_node { list_node* prev; list_node* next; T data; explicit list_node(const T value) : prev(nullptr), next(nullptr), data(value) {} }; template typename T class list_iterator { list_nodeT* ptr; public: explicit list_iterator(list_nodeT* p nullptr) : ptr(p) {} T operator*() const { return ptr-data; } T* operator-() const { return ptr-data; } list_iterator operator() { ptr ptr-next; return *this; } list_iterator operator(int) { list_iterator tmp *this; (*this); return tmp; } list_iterator operator--() { ptr ptr-prev; return *this; } list_iterator operator--(int) { list_iterator tmp *this; --(*this); return tmp; } bool operator(const list_iterator rhs) const { return ptr rhs.ptr; } bool operator!(const list_iterator rhs) const { return ptr ! rhs.ptr; } };節(jié)點(diǎn)就是“雙指針 數(shù)據(jù)”。迭代器只封裝一個(gè)裸指針?biāo)胁僮鞫纪ㄟ^(guò)指針往返。3.2 容器類(lèi)實(shí)現(xiàn)插入與刪除的關(guān)鍵邏輯接下來(lái)是容器主體重點(diǎn)看 insert 和 erase 里指針怎么連接。我給這個(gè)類(lèi)禁用了拷貝構(gòu)造這只是一個(gè)教學(xué)簡(jiǎn)化真實(shí) list 是支持拷貝的。template typename T class list { using node list_nodeT; node* head; // 哨兵節(jié)點(diǎn) size_t sz 0; public: using iterator list_iteratorT; list() : head(new node(T())) { head-prev head; head-next head; } ~list() { clear(); delete head; } list(const list) delete; list operator(const list) delete; iterator begin() { return iterator(head-next); } iterator end() { return iterator(head); } bool empty() const { return sz 0; } size_t size() const { return sz; } void push_back(const T value) { insert(end(), value); } void push_front(const T value) { insert(begin(), value); } iterator insert(iterator pos, const T value) { node* cur pos.operator-(); // 這里簡(jiǎn)單演示實(shí)際建議提供私有接口 // 實(shí)際上應(yīng)該通過(guò)迭代器拿指針下面用 cur node* prev_node cur-prev; node* new_node new node(value); prev_node-next new_node; new_node-prev prev_node; new_node-next cur; cur-prev new_node; sz; return iterator(new_node); } iterator erase(iterator pos) { node* cur pos.operator-(); node* prev_node cur-prev; node* next_node cur-next; prev_node-next next_node; next_node-prev prev_node; delete cur; --sz; return iterator(next_node); } void clear() { node* cur head-next; while (cur ! head) { node* tmp cur; cur cur-next; delete tmp; } head-next head; head-prev head; sz 0; } };上面insert里我用了一個(gè)不太優(yōu)雅的方式獲取 pos 里的節(jié)點(diǎn)指針。實(shí)際上應(yīng)該給迭代器加一個(gè)friend聲明或者提供一個(gè)內(nèi)部函數(shù)。自己寫(xiě)的時(shí)候可以這樣改template typename T class list { // 在容器內(nèi)直接訪問(wèn)迭代器私有成員 friend class list_iteratorT; ... };但為了示例簡(jiǎn)潔也可以給迭代器增加一個(gè)_node()方法。這里更推薦的做法是讓迭代器公開(kāi)get()返回裸指針雖然是教學(xué)實(shí)現(xiàn)但設(shè)計(jì)上更干凈。修正后的核心邏輯應(yīng)該是iterator insert(iterator pos, const T value) { node* cur pos.get(); // 獲取待插入位置的節(jié)點(diǎn)指針 node* prev_node cur-prev; node* new_node new node(value); prev_node-next new_node; new_node-prev prev_node; new_node-next cur; cur-prev new_node; sz; return iterator(new_node); } iterator erase(iterator pos) { node* cur pos.get(); node* prev_node cur-prev; node* next_node cur-next; prev_node-next next_node; next_node-prev prev_node; delete cur; --sz; return iterator(next_node); }所以在最終實(shí)現(xiàn)里給list_iterator這樣加一個(gè)方法list_nodeT* get() const { return ptr; }然后容器直接調(diào)用pos.get()。3.3 運(yùn)行測(cè)試與結(jié)果分析完整測(cè)試代碼如下int main() { listint l; l.push_back(1); l.push_back(2); l.push_front(0); std::cout 初始序列: ; for (int v : l) std::cout v ; std::cout \n; auto it l.begin(); it; // 指向第二個(gè)元素 l.insert(it, 99); // 在第二個(gè)元素之前插入 99 l.erase(l.begin()); // 刪除第一個(gè)元素 std::cout 操作后: ; for (int v : l) std::cout v ; std::cout \n; std::cout size l.size() \n; return 0; }輸出結(jié)果初始序列: 0 1 2 操作后: 1 99 2 size 3范圍 for 能直接跑說(shuō)明 begin/end 和迭代器的!、*、都符合要求。你也可以手動(dòng)測(cè)試--l.end()會(huì)發(fā)現(xiàn)它確實(shí)能正確跑到最后一個(gè)節(jié)點(diǎn)這就是雙向鏈表的底氣。3.4 從手寫(xiě)實(shí)現(xiàn)反推標(biāo)準(zhǔn)庫(kù)設(shè)計(jì)自己寫(xiě)完一遍再看 libstdc 的_List_node_base::hook和unhook就會(huì)非常親切。核心永遠(yuǎn)都是四步改前驅(qū)的 next、改當(dāng)前節(jié)點(diǎn)的 prev、改當(dāng)前節(jié)點(diǎn)的 next、改后繼的 prev。順序可以換但絕不能漏。漏一步就是內(nèi)存踩踏或者環(huán)斷裂嚴(yán)重時(shí)程序直接崩潰。標(biāo)準(zhǔn)庫(kù)代碼看起來(lái)晦澀是因?yàn)樗压?jié)點(diǎn)聲明、分配器、構(gòu)造源碼、插入算法拆到不同基類(lèi)和成員函數(shù)里。但底子跟我們手寫(xiě)的完全一樣。讀源碼時(shí)不要逐行背抓“指針?biāo)牟阶摺本蛪蛄恕?. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄4.1 迭代器失效的“豁免”與例外list 對(duì)迭代器的承諾比 vector 好得多插入不會(huì)讓任何既有迭代器失效刪除只會(huì)讓指向被刪元素的迭代器失效其他迭代器不受影響。這條規(guī)則讓 list 在某些場(chǎng)景成為必然選擇。比如你持有一個(gè)指向 list 元素的迭代器另一個(gè)線程或者另一段代碼在中間插入了新元素你手里的迭代器依舊有效。但有兩個(gè)例外必須記住erase之后指向已刪除節(jié)點(diǎn)的迭代器失效這個(gè)失效是實(shí)打?qū)嵉睦^續(xù)解引用就是未定義行為。clear()或容器析構(gòu)之后所有迭代器都失效雖然迭代器對(duì)象本身可能還保存著舊地址但那個(gè)節(jié)點(diǎn)已經(jīng)歸還給內(nèi)存了碰都不能碰。還有一點(diǎn)經(jīng)常被忽略std::list::remove和std::list::erase不同。remove是遍歷并刪除所有匹配值的元素它會(huì)把匹配的元素刪掉然后把不匹配的元素按原順序留下來(lái)的迭代器返回。寫(xiě)代碼時(shí)千萬(wàn)別拿 Python 列表 remove 的錯(cuò)誤習(xí)慣套 C。4.2 緩存不友好為什么別拿 list 當(dāng)數(shù)組用鏈表節(jié)點(diǎn)散落在堆里每個(gè)節(jié)點(diǎn)之間距離大CPU 緩存命中率很低。遍歷一個(gè)含有 100 萬(wàn)個(gè) int 的 list要經(jīng)歷 100 萬(wàn)次指針跳轉(zhuǎn)而遍歷等量數(shù)據(jù)的 vector 幾乎就是線性掃描內(nèi)存。實(shí)測(cè)下來(lái)遍歷 list 比 vector 慢一個(gè)數(shù)量級(jí)很正常。這不是說(shuō) list 一無(wú)是處而是說(shuō)你要在正確場(chǎng)景用它。只在頻繁“插入/刪除 不遍歷全量數(shù)據(jù) 需要元素地址穩(wěn)定”的組合下list 的優(yōu)勢(shì)才真正兌現(xiàn)。如果你只是往屁股后頭追加數(shù)據(jù)偶爾讀讀末尾那 deque 或 vector 都更好。我自己的經(jīng)驗(yàn)法則需要隨機(jī)訪問(wèn) → 別選 list主要在頭部和尾部操作 → deque 更合適元素拷貝成本極高想在中間反復(fù)插入刪除 → list需要穩(wěn)定的引用/指針指向元素同時(shí)還要?jiǎng)討B(tài)增刪 → list4.3 splice零拷貝的節(jié)點(diǎn)搬家list 最容易被低估的功能是 splice。它能將一個(gè) list 中的節(jié)點(diǎn)直接“搬”到另一個(gè) list不拷貝元素不新建節(jié)點(diǎn)純粹改指針。這是個(gè) O(1) 操作很多面試題都會(huì)問(wèn)。std::listint a{1, 2, 3}; std::listint b{4, 5}; auto it a.begin(); it; // 指向 2 a.splice(it, b); // 把 b 所有節(jié)點(diǎn)搬到 a 中 2 的前面 // a: 1 4 5 2 3 // b: 空如果用inserterase一步一步做那就要復(fù)制每個(gè)元素復(fù)雜度是 O(n)還可能引發(fā)元素拷貝的額外開(kāi)銷(xiāo)。splice 是 list 獨(dú)有的“指針搬運(yùn)工”也是 list 在鏈表 merge、LRU 淘汰、任務(wù)隊(duì)列重組這些場(chǎng)景里不可替代的原因。有個(gè)容易踩的坑C11 之前標(biāo)準(zhǔn)沒(méi)有強(qiáng)制要求 splice 后size()實(shí)時(shí)更新所以跨 list splice 之后讀取 size 可能是錯(cuò)的?，F(xiàn)在 C11 要求容器 size 為 O(1)所以 splice 的庫(kù)實(shí)現(xiàn)必須同步維護(hù)兩個(gè) list 的大小。但這只在“自己寫(xiě)容器”時(shí)才是隱患用標(biāo)準(zhǔn)庫(kù)不用擔(dān)心前提是編譯器支持 C11 以上。4.4 經(jīng)典組合list 哈希表實(shí)現(xiàn) LRU Cache我在實(shí)際項(xiàng)目中用得最爽的組合就是std::list std::unordered_map做 LRU 緩存。list 保存實(shí)際數(shù)據(jù)unordered_map 保存 key 到 list 迭代器的映射。命中緩存時(shí)先用 key 查出迭代器再splice把對(duì)應(yīng)節(jié)點(diǎn)挪到鏈表頭部新數(shù)據(jù)插入時(shí)往頭部push_front。整個(gè)更新和淘汰都是 O(1)而且因?yàn)?list 元素的地址穩(wěn)定哈希表里保存的迭代器不會(huì)因?yàn)椴迦胄略囟А＿@個(gè)組合能成立完全建立在 list 的迭代器不失效特性上。有一次我在這套代碼上踩過(guò)坑從哈希表取迭代器后在另一個(gè)地方誤調(diào)用了erase再拿舊迭代器去splice程序直接野指針崩潰。排查了很久才定位到是“失效迭代器被復(fù)用”。所以我會(huì)格外強(qiáng)調(diào)從容器里拿到迭代器后它只能用于其指向?qū)ο筮€活著的時(shí)刻一旦 erase 或容器析構(gòu)立刻把它當(dāng)廢紙扔掉。4.5 fork 檢查手寫(xiě) list 常見(jiàn)的三個(gè)錯(cuò)誤如果是自己實(shí)現(xiàn)鏈表最容易犯三個(gè)錯(cuò)忘記更新哨兵節(jié)點(diǎn)的 prev/next導(dǎo)致 begin() 或 end() 指向空或舊節(jié)點(diǎn)。釋放節(jié)點(diǎn)后前驅(qū)的 next 沒(méi)有正確指向后繼鏈表斷開(kāi)。析構(gòu)時(shí)只釋放了數(shù)據(jù)節(jié)點(diǎn)忘記 delete 哨兵節(jié)點(diǎn)或者釋放哨兵節(jié)點(diǎn)后沒(méi)有把 iterator 置空懸垂指針被人碰到就是事故。這三個(gè)錯(cuò)誤都靠調(diào)試器死磕過(guò)很多次。所以我給讀者的建議是自己動(dòng)手寫(xiě) list 時(shí)先畫(huà)圖把哨兵、首節(jié)點(diǎn)、尾節(jié)點(diǎn)連一遍再下筆。畫(huà)圖五分鐘能省調(diào)試五小時(shí)。4.6 別被“l(fā)ist 接口”迷惑它包含哪些常用能力最后說(shuō)說(shuō)熱詞里常出現(xiàn)的 “l(fā)ist接口”。不少初學(xué)者把List接口和std::list混為一談。std::list的常用接口大概分幾類(lèi)元素訪問(wèn)front()、back()沒(méi)有operator[]迭代器begin()、end()、rbegin()、rend()容量empty()、size()、max_size()修改push_front()、push_back()、pop_front()、pop_back()、insert()、erase()、clear()鏈表特有操作splice()、remove()、remove_if()、unique()、merge()、sort()、reverse()這些獨(dú)有的鏈表操作就是它存在的意義。sort()和merge()依賴雙向節(jié)點(diǎn)的指針移動(dòng)unique()快速去重reverse()能把鏈表原地反轉(zhuǎn)。這些操作在 vector 上要么做不到要么代價(jià)巨大。但注意它們大多是成員函數(shù)不是 std 算法這也是因?yàn)榈餍枨蟛黄ヅ洹Ｔ趯?shí)際工程里list 通常不是“默認(rèn)容器”但它像是工具箱里的一把內(nèi)六角扳手平時(shí)用不到一旦遇到“需要穩(wěn)定引用 快速插入刪除 節(jié)點(diǎn)搬家”的組合你才會(huì)意識(shí)到它的好。最后那個(gè) splice 的小技巧是 list 留給有心人的彩蛋用好了能讓代碼在數(shù)據(jù)移動(dòng)上省掉一大截開(kāi)銷(xiāo)。