1. 整體設(shè)計(jì)與思路拆解1.1 為什么選list作為模擬實(shí)現(xiàn)的切入點(diǎn)學(xué)習(xí)C的人遲早會(huì)碰到同一個(gè)問(wèn)題STL容器底層到底是怎么寫(xiě)的項(xiàng)目標(biāo)題說(shuō)得很直接——手寫(xiě)一個(gè)list容器把迭代器、構(gòu)造函數(shù)和STL風(fēng)格編程全部串起來(lái)。我的建議是如果你只打算手寫(xiě)一個(gè)STL容器來(lái)加深理解首選list而不是vector。原因在于vector的連續(xù)內(nèi)存特性會(huì)把很多細(xì)節(jié)掩蓋掉插入刪除要搬移元素實(shí)現(xiàn)上反而顯得“直覺(jué)化”list是雙向鏈表節(jié)點(diǎn)之間靠指針串聯(lián)結(jié)構(gòu)更清晰天然逼迫你去處理指針、節(jié)點(diǎn)生命周期、迭代器封裝這些STL最核心的問(wèn)題。把這些搞明白再回頭看vector、deque甚至哈希表都會(huì)順利很多。這里還要澄清一個(gè)認(rèn)知list不是簡(jiǎn)單地在C里寫(xiě)一個(gè)“節(jié)點(diǎn)指針”的鏈表就完事了。真正的STL風(fēng)格list至少要有allocator內(nèi)存分配器、迭代器包括const版本和反向迭代器、完整的構(gòu)造/拷貝/移動(dòng)/析構(gòu)家族、O(1)的insert/erase、以及“插入不影響其他迭代器、刪除只影響被刪迭代器”這樣的行為保證。模擬實(shí)現(xiàn)的價(jià)值在于你不是重復(fù)造一個(gè)能跑的產(chǎn)品輪子而是理解產(chǎn)品輪子為什么長(zhǎng)這樣。項(xiàng)目標(biāo)題把“構(gòu)造”單獨(dú)拿出來(lái)我覺(jué)得特別對(duì)——很多人以為list實(shí)現(xiàn)的大頭是鏈表操作其實(shí)構(gòu)造家族才最容易翻車(chē)拷貝構(gòu)造、拷貝賦值、移動(dòng)構(gòu)造、析構(gòu)之間的配合一旦出錯(cuò)程序會(huì)在莫名其妙的地方崩潰而且很難查。1.2 核心結(jié)構(gòu)節(jié)點(diǎn)、哨兵與三指針模型動(dòng)手寫(xiě)之前先把紙面上的東西定下來(lái)。STL的list是雙向鏈表每個(gè)節(jié)點(diǎn)至少有兩個(gè)指針prev指向前驅(qū)next指向后繼。標(biāo)準(zhǔn)庫(kù)實(shí)際使用的list還有一個(gè)關(guān)鍵設(shè)計(jì)——哨兵頭節(jié)點(diǎn)dummy node。鏈表里總是保留一個(gè)不存儲(chǔ)有效數(shù)據(jù)的頭節(jié)點(diǎn)它的next指向第一個(gè)有效節(jié)點(diǎn)沒(méi)有則為nullptrprev指向最后一個(gè)有效節(jié)點(diǎn)沒(méi)有則為nullptr。有哨兵的好處是空鏈表和非空鏈表的操作邏輯完全統(tǒng)一你不需要在insert/erase里寫(xiě)一堆“if (head nullptr)”的特殊分支。我用三指針模型來(lái)理解這句話(huà)node* _M_head哨兵節(jié)點(diǎn)本身永遠(yuǎn)存在。_M_head-_M_next第一個(gè)有效節(jié)點(diǎn)空表時(shí)是nullptr。_M_head-_M_prev最后一個(gè)有效節(jié)點(diǎn)空表時(shí)是nullptr。實(shí)際存儲(chǔ)時(shí)還可以不單獨(dú)存_M_head指針而是讓哨兵節(jié)點(diǎn)作為list類(lèi)的一個(gè)成員對(duì)象。不過(guò)為了代碼清晰后續(xù)示例統(tǒng)一用_M_node指針指向哨兵節(jié)點(diǎn)。我們還要讓list類(lèi)同時(shí)持有allocator成員這樣節(jié)點(diǎn)分配和釋放都走分配器而不是直接new/delete——這是STL風(fēng)格的一個(gè)標(biāo)志容器不直接管理原始內(nèi)存它把內(nèi)存獲取和對(duì)象構(gòu)造解耦。模擬階段可以先簡(jiǎn)化但我建議一開(kāi)始就寫(xiě)上allocator模板參數(shù)省得以后想加還得改一堆簽名。template typename T, typename Alloc std::allocatorT class list { private: struct _Node { _Node* _M_prev; _Node* _M_next; T _M_data; explicit _Node(const T value) : _M_prev(nullptr), _M_next(nullptr), _M_data(value) {} explicit _Node(T value) : _M_prev(nullptr), _M_next(nullptr), _M_data(std::move(value)) {} }; using _NodeAlloc typename Alloc::template rebind_Node::other; using _NodePtr _Node*; using _DataAlloc Alloc; _NodePtr _M_node; // 哨兵節(jié)點(diǎn)指針 size_t _M_size; // 有效節(jié)點(diǎn)個(gè)數(shù) _NodeAlloc _M_node_alloc; public: using value_type T; using size_type size_t; using difference_type ptrdiff_t; using reference T; using const_reference const T; };rebind這個(gè)細(xì)節(jié)值得多說(shuō)一句。std::allocatorT本身分配的是T大小的內(nèi)存但鏈表節(jié)點(diǎn)是_Node包含指針和數(shù)據(jù)大小跟T不一定相同。STL規(guī)定allocator必須通過(guò)rebind_Node::other把分配器“轉(zhuǎn)綁”到節(jié)點(diǎn)類(lèi)型上。雖然默認(rèn)分配器的rebind就是換個(gè)模板參數(shù)但自定義分配器如果不支持rebind標(biāo)準(zhǔn)容器就無(wú)法工作。我在自己實(shí)現(xiàn)時(shí)第一步就把_NodeAlloc類(lèi)型別名寫(xiě)好后面所有節(jié)點(diǎn)級(jí)內(nèi)存操作都從_M_node_alloc發(fā)起這樣才是真正的STL風(fēng)格而不是披著STL外衣的裸new鏈表。1.3 迭代器為什么必須封裝成類(lèi)而不是裸指針這是list模擬實(shí)現(xiàn)最反直覺(jué)的一步。用慣了vector的人會(huì)覺(jué)得迭代器就是指針it就是地址加偏移但在list里這個(gè)想法直接崩掉。鏈表節(jié)點(diǎn)在內(nèi)存里是離散的node1并不是下一個(gè)節(jié)點(diǎn)所以迭代器如果要支持、--、*、-這些操作就必須保存“指向當(dāng)前節(jié)點(diǎn)的指針”然后讓運(yùn)算符重載來(lái)做“沿著next/prev移動(dòng)”這件事。也就是說(shuō)迭代器的數(shù)據(jù)成員就是一個(gè)_NodePtr而所有操作都是對(duì)指針的解引用和游走。還有一個(gè)比“能不能走”更隱蔽的問(wèn)題——空引用和類(lèi)型安全。原生指針T*可以隨便指向任何地方也能隨便做算術(shù)壓根不知道“這是一次鏈表游走”。list的迭代器把游走規(guī)則封裝在operator里你永遠(yuǎn)不會(huì)寫(xiě)出it it 3這種對(duì)鏈表毫無(wú)意義的代碼list迭代器是雙向迭代器只支持/--不支持隨機(jī)跳轉(zhuǎn)。封裝類(lèi)還讓“const迭代器和非const迭代器”有了本質(zhì)區(qū)別而原生指針只能靠const T*來(lái)表達(dá)“數(shù)據(jù)只讀”無(wú)法表達(dá)“從某個(gè)節(jié)點(diǎn)開(kāi)始只能向前走”。template typename T, typename Ref, typename Ptr struct _ListIterator { using iterator_category std::bidirectional_iterator_tag; using value_type T; using difference_type ptrdiff_t; using pointer Ptr; using reference Ref; _NodePtr _M_node; _ListIterator() noexcept : _M_node(nullptr) {} explicit _ListIterator(_NodePtr node) noexcept : _M_node(node) {} reference operator*() const noexcept { return _M_node-_M_data; } pointer operator-() const noexcept { return std::addressof(_M_node-_M_data); } _ListIterator operator() noexcept { _M_node _M_node-_M_next; return *this; } _ListIterator operator(int) noexcept { _ListIterator tmp(*this); (*this); return tmp; } _ListIterator operator--() noexcept { _M_node _M_node-_M_prev; return *this; } _ListIterator operator--(int) noexcept { _ListIterator tmp(*this); --(*this); return tmp; } friend bool operator(const _ListIterator a, const _ListIterator b) noexcept { return a._M_node b._M_node; } friend bool operator!(const _ListIterator a, const _ListIterator b) noexcept { return !(a b); } };注意到模板參數(shù)里有Ref和Ptr這是模仿gcc libstdc的經(jīng)典寫(xiě)法。它讓一個(gè)類(lèi)模板同時(shí)產(chǎn)出普通迭代器RefT, PtrT*和const迭代器Refconst T, Ptrconst T*不用寫(xiě)兩份幾乎相同的代碼。這個(gè)設(shè)計(jì)我強(qiáng)烈建議保留因?yàn)楹竺鎸?shí)現(xiàn)insert、erase、splice這類(lèi)接口時(shí)你會(huì)頻繁需要“用普通迭代器構(gòu)造const迭代器”的隱式轉(zhuǎn)換一對(duì)模板參數(shù)搞定。2. 迭代器實(shí)現(xiàn)與STL迭代器規(guī)范2.1 iterator_traits讓算法知道迭代器的類(lèi)型很多自學(xué)C的人會(huì)在這一步卡殼明明自己寫(xiě)的list里也有iterator類(lèi)型為什么std::reverse、std::distance、std::next這些標(biāo)準(zhǔn)庫(kù)算法就是不肯配合原因是標(biāo)準(zhǔn)算法不直接認(rèn)“你這個(gè)類(lèi)叫iterator”而是通過(guò)std::iterator_traitsIter去取迭代器的五件套iterator_category、value_type、difference_type、pointer、reference。只要你的迭代器類(lèi)內(nèi)部定義了這些嵌套類(lèi)型iterator_traits就有默認(rèn)的特化路徑能拿到它們。不過(guò)這里有個(gè)坑如果你在list類(lèi)內(nèi)部寫(xiě)了一個(gè)嵌套的iterator結(jié)構(gòu)std::iterator_traits仍然會(huì)正常工作嗎答案是會(huì)的C標(biāo)準(zhǔn)規(guī)定std::iterator_traitsIter的主模板就是直接取Iter::iterator_category這類(lèi)成員類(lèi)型前提是這些成員存在。但如果你的迭代器是const T*這種原生指針就必須靠偏特化std::iterator_traitsT*來(lái)補(bǔ)充定義。我建議在寫(xiě)list之前先做個(gè)快速驗(yàn)證把下面這段丟進(jìn)編譯器看看std::distance能不能在你的迭代器上工作static_assert(std::is_same_v std::iterator_traits_ListIteratorT, T, T*::iterator_category, std::bidirectional_iterator_tag); static_assert(std::is_same_v std::iterator_traits_ListIteratorT, T, T*::value_type, T);如果編譯過(guò)了說(shuō)明迭代器的“身份證”齊了。iterator_category尤其重要它決定了算法如何選擇重載。比如std::advance(it, n)在面對(duì)random_access_iterator_tag時(shí)可以直接it n而面對(duì)bidirectional_iterator_tag只能老老實(shí)實(shí)/--循環(huán)。list的迭代器是雙向迭代器所以這里必須寫(xiě)std::bidirectional_iterator_tag寫(xiě)錯(cuò)了或者不寫(xiě)某些算法會(huì)直接編譯失敗或者退化成無(wú)意義的死循環(huán)。2.2 const迭代器與隱式轉(zhuǎn)換讀寫(xiě)權(quán)限的邊界list類(lèi)里通常會(huì)這樣定義迭代器別名using iterator _ListIteratorT, T, T*; using const_iterator _ListIteratorT, const T, const T*; using reverse_iterator std::reverse_iteratoriterator; using const_reverse_iterator std::reverse_iteratorconst_iterator;std::reverse_iterator是一個(gè)適配器你只需要給它一個(gè)雙向迭代器它自動(dòng)把變成--、--變成這讓list不用為反向遍歷寫(xiě)出另一套底層結(jié)構(gòu)。但問(wèn)題來(lái)了容器類(lèi)型listT和listconst T是完全不同的類(lèi)型你不能簡(jiǎn)單靠類(lèi)模板的const來(lái)獲得const迭代器。所以容器內(nèi)部必須提供iterator begin()和const_iterator begin() const這樣的重載對(duì)并且要支持iterator到const_iterator的隱式轉(zhuǎn)換。這就是我們把迭代器寫(xiě)成模板的好處——給_ListIterator加一個(gè)轉(zhuǎn)換構(gòu)造函數(shù)template typename _Tp, typename _Ref, typename _Ptr struct _ListIterator { // 前面的成員不變... // 允許普通迭代器轉(zhuǎn)換為const迭代器但不允許反向轉(zhuǎn)換 template typename _Ref2, typename _Ptr2, typename std::enable_if_t std::is_convertible_v_Ref2, Ref std::is_convertible_v_Ptr2, Ptr _ListIterator(const _ListIteratorT, _Ref2, _Ptr2 other) noexcept : _M_node(other._M_node) {} };這個(gè)轉(zhuǎn)換構(gòu)造函數(shù)相當(dāng)克制它只允許“讀權(quán)限擴(kuò)大”的轉(zhuǎn)換也就是iterator - const_iteratorconst_iterator - iterator因?yàn)閏onst T無(wú)法轉(zhuǎn)換成T會(huì)被enable_if攔下。這一步做對(duì)了才不會(huì)出現(xiàn)你返回一個(gè)const迭代器、外部卻拿來(lái)修改數(shù)據(jù)的漏洞。很多初學(xué)者仿照網(wǎng)上簡(jiǎn)化版list寫(xiě)出的代碼到這里都是直接不寫(xiě)轉(zhuǎn)換構(gòu)造導(dǎo)致list.begin()和容器的const成員函數(shù)接口配對(duì)失敗編譯報(bào)出一大堆看不懂的模板報(bào)錯(cuò)。這里我踩過(guò)最痛的坑是沒(méi)有給迭代器加noexcept。別小看這個(gè)標(biāo)準(zhǔn)容器要求迭代器拷貝、移動(dòng)、比較這些操作不得拋異常因?yàn)楹芏喾盒退惴〞?huì)基于noexcept來(lái)選不同的移動(dòng)策略。如果你的迭代器寫(xiě)成了可能拋異常的拷貝構(gòu)造std::list::erase在刪除一批元素時(shí)可能就不再走高效的節(jié)點(diǎn)回收路徑了。2.3 迭代器與節(jié)點(diǎn)互換為什么insert需要私有構(gòu)造在實(shí)現(xiàn)insert和erase時(shí)需要把“迭代器”和“節(jié)點(diǎn)指針”相互轉(zhuǎn)換。迭代器看到的是一個(gè)封裝好的類(lèi)它的_M_node成員是私有的外部無(wú)法直接拿到裸指針去拼新節(jié)點(diǎn)。一個(gè)常見(jiàn)的做法是在list類(lèi)的內(nèi)部實(shí)現(xiàn)里再創(chuàng)建一個(gè)“裸構(gòu)造”的迭代器像這樣private: // 僅用于內(nèi)部構(gòu)造迭代器外部不可見(jiàn) static iterator _S_make_iterator(_NodePtr p) noexcept { return iterator(p); }因?yàn)閕terator只有一個(gè)帶_NodePtr參數(shù)的構(gòu)造函數(shù)而這個(gè)構(gòu)造函數(shù)如果寫(xiě)成public外部就能隨便把一個(gè)節(jié)點(diǎn)指針偽裝成迭代器破壞了封裝。所以我會(huì)把這個(gè)構(gòu)造函數(shù)放在private區(qū)然后在list類(lèi)的成員函數(shù)里通過(guò)friend或內(nèi)部工具函數(shù)使用。std::list現(xiàn)代實(shí)現(xiàn)也是這個(gè)套路iterator類(lèi)本身會(huì)聲明容器類(lèi)為friend保證“只有容器才能從節(jié)點(diǎn)指針安全構(gòu)造迭代器”。有了這個(gè)能力insert才能寫(xiě)出“返回指向新插入元素的迭代器”的語(yǔ)義。C標(biāo)準(zhǔn)規(guī)定list::insert()的返回值是插入后新元素的迭代器vector的insert則返回插入位置的迭代器二者不同。如果不小心把語(yǔ)義寫(xiě)錯(cuò)外部算法表現(xiàn)會(huì)非常奇怪比如連續(xù)insert時(shí)新迭代器總是指向舊元素。3. 構(gòu)造函數(shù)家族與內(nèi)存管理3.1 構(gòu)造函數(shù)的五大金剛默認(rèn)、填充、范圍、拷貝、移動(dòng)list的構(gòu)造函數(shù)數(shù)量比一般人想的多。除了默認(rèn)構(gòu)造STL還要求支持list(size_type n)、list(size_type n, const T value)、list(InputIt first, InputIt last)以及C11后的initializer_listT。模擬實(shí)現(xiàn)時(shí)不必每一個(gè)都寫(xiě)字字珠璣的實(shí)現(xiàn)但必須明白它們共用同一條內(nèi)部通道——_M_insert。以一個(gè)通用填充實(shí)現(xiàn)為例內(nèi)部關(guān)鍵是一段讓新手最容易頭暈的代碼也就是“邊申請(qǐng)節(jié)點(diǎn)邊插入任何一步拋異常都要回滾”。我不建議一上來(lái)就寫(xiě)異常安全滿(mǎn)分版本先寫(xiě)出能跑的版本再逐步加強(qiáng)。初級(jí)版本可以這樣組織template typename InputIt list(InputIt first, InputIt last, typename std::enable_if!std::is_integral_vInputIt::type* nullptr) { _M_init(); for (; first ! last; first) emplace_back(*first); }為什么要enable_if因?yàn)閘ist(size_type n)接收到整數(shù)參數(shù)時(shí)如果不做區(qū)分范圍構(gòu)造函數(shù)會(huì)跟整數(shù)版本產(chǎn)生重載歧義listint l(10, 20)到底是10個(gè)默認(rèn)值還是從迭代器范圍構(gòu)造標(biāo)準(zhǔn)庫(kù)靠iterator_traits區(qū)分我們模擬時(shí)用is_integral攔截就夠了。這也是熱詞里反復(fù)出現(xiàn)“構(gòu)造”、“拷貝構(gòu)造函數(shù)調(diào)用時(shí)機(jī)”背后的一個(gè)考點(diǎn)——構(gòu)造函數(shù)家族不僅講究“能編”還講究“重載決議不出歧義”。_M_init用來(lái)初始化哨兵節(jié)點(diǎn)并置零sizevoid _M_init() { _M_node _M_alloc_node(); // 分配一個(gè)哨兵節(jié)點(diǎn) _M_node-_M_next nullptr; _M_node-_M_prev nullptr; _M_size 0; }多啰嗦一句很多人的第一版list習(xí)慣用“空鏈表頭指針為nullptr”結(jié)果insert、erase、遍歷到處都要判空寫(xiě)起來(lái)非常累。而哨兵模式下一勞永逸遍歷的終點(diǎn)就是哨兵本身begin()是_M_node-_M_nextend()是_M_node天然閉合成環(huán)。這個(gè)設(shè)計(jì)在STL里已經(jīng)用了二十年是經(jīng)過(guò)實(shí)戰(zhàn)檢驗(yàn)的不要為了“少一個(gè)節(jié)點(diǎn)”而放棄它。3.2 allocator與節(jié)點(diǎn)的構(gòu)造/析構(gòu)誰(shuí)負(fù)責(zé)內(nèi)存誰(shuí)負(fù)責(zé)生命直接new一個(gè)節(jié)點(diǎn)不就行了嗎為什么還要allocator如果你只是為了寫(xiě)出“一個(gè)能跑的list”那確實(shí)可以new/delete但你定義的是listT, Alloc的模板就必須考慮分配器是外部注入的類(lèi)型。比如用戶(hù)可能傳入一個(gè)池化分配器希望所有節(jié)點(diǎn)從預(yù)先分配的內(nèi)存池里取。此外標(biāo)準(zhǔn)容器對(duì)異常安全有明確要求構(gòu)造元素時(shí)拋異常內(nèi)存不能泄漏銷(xiāo)毀元素時(shí)節(jié)點(diǎn)內(nèi)存要正確返還給分配器而不是簡(jiǎn)單delete。我習(xí)慣把節(jié)點(diǎn)內(nèi)存和對(duì)象生命周期拆成四個(gè)函數(shù)_NodePtr _M_alloc_node() { return _M_node_alloc.allocate(1); } template typename... Args _NodePtr _M_construct_node(Args... args) { _NodePtr p _M_alloc_node(); try { // 在已分配內(nèi)存上構(gòu)造節(jié)點(diǎn)而不是new p(args...) std::allocator_traits_NodeAlloc::construct( _M_node_alloc, p, std::forwardArgs(args)...); } catch (...) { _M_node_alloc.deallocate(p, 1); throw; } return p; } void _M_destroy_node(_NodePtr p) noexcept { std::allocator_traits_NodeAlloc::destroy(_M_node_alloc, p); _M_node_alloc.deallocate(p, 1); }關(guān)鍵在于construct、destroy這兩個(gè)allocator_traits接口。std::allocator_traits是一層“默認(rèn)實(shí)現(xiàn)”的殼如果你自定義的分配器沒(méi)提供construct它會(huì)退回到::new((void*)p) T(args...)如果提供了就用自定義版本。調(diào)用方統(tǒng)一走allocator_traits容器代碼就不需要判斷分配器到底支不支持自定義構(gòu)造。這也是STL源碼一眼望去全是allocator_traits的原因。我在模擬實(shí)現(xiàn)早期偷懶直接用了new (p) _Node(value)寫(xiě)起來(lái)很快但一旦把分配器換成帶統(tǒng)計(jì)功能的測(cè)試分配器就會(huì)發(fā)現(xiàn)問(wèn)題內(nèi)存計(jì)數(shù)對(duì)不上因?yàn)槔@過(guò)分配器的construct那一步。后來(lái)全部改成allocator_traits風(fēng)格內(nèi)存全程由分配器記賬調(diào)試自定義分配器時(shí)輕松很多。3.3 拷貝構(gòu)造的深拷貝實(shí)現(xiàn)異常安全是關(guān)鍵拷貝構(gòu)造是最能暴露鏈表功力的地方。你不能只拷貝頭指針那樣兩個(gè)list會(huì)共享同一串節(jié)點(diǎn)析構(gòu)時(shí)雙重釋放直接崩潰。深拷貝的常規(guī)做法是遍歷源鏈表依次尾插新節(jié)點(diǎn)但這個(gè)樸素寫(xiě)法有一個(gè)致命問(wèn)題——如果中途拋異常比如T的拷貝構(gòu)造拋了已經(jīng)插進(jìn)去的節(jié)點(diǎn)就泄漏了。我推薦寫(xiě)成“構(gòu)造一個(gè)新哨兵 異常時(shí)整體清理”的結(jié)構(gòu)list(const list other) { _M_init(); try { for (const_iterator it other.begin(); it ! other.end(); it) emplace_back(*it); } catch (...) { clear(); _M_dealloc_node(_M_node); _M_node nullptr; throw; } }這樣一旦中途失敗析構(gòu)入口還能看到有效對(duì)象狀態(tài)。不過(guò)在更學(xué)院派的實(shí)現(xiàn)里會(huì)用帶next指針的“半成品鏈表構(gòu)建器”構(gòu)造到一半再整體掛接那是為了追求強(qiáng)異常保證。模擬實(shí)現(xiàn)先保證“不泄漏”已經(jīng)夠及格有興趣可以繼續(xù)優(yōu)化到“copy期間源被修改不會(huì)影響當(dāng)前操作”。寫(xiě)完拷貝構(gòu)造后順手做一份測(cè)試定義兩個(gè)list互相拷貝然后修改其中一個(gè)另一個(gè)必須完全不受影響同時(shí)二者各自的end()、begin()迭代器不能交叉指向?qū)Ψ降墓?jié)點(diǎn)。這個(gè)測(cè)試不過(guò)關(guān)多半是拷貝構(gòu)造里不小心共享了哨兵節(jié)點(diǎn)。3.4 拷貝賦值與copy-and-swap最穩(wěn)的賦值寫(xiě)法拷貝賦值有兩條路線(xiàn)。一條是傳統(tǒng)的“先clear再逐個(gè)插入”它的問(wèn)題是如果插入中途拋異常當(dāng)前對(duì)象已經(jīng)被清空了處于“半空半新”的損壞狀態(tài)不滿(mǎn)足強(qiáng)異常安全。另一條是copy-and-swap先用拷貝構(gòu)造生成一個(gè)臨時(shí)list然后交換臨時(shí)list和當(dāng)前對(duì)象的內(nèi)容臨時(shí)對(duì)象析構(gòu)時(shí)帶走舊數(shù)據(jù)。實(shí)現(xiàn)swap時(shí)注意只需要交換三個(gè)東西哨兵指針、size、allocator。allocator比較麻煩C11后規(guī)定“分配器相等時(shí)容器可以交換”我們模擬階段先假定所有std::allocator都是相等的直接交換即可如果對(duì)象和臨時(shí)對(duì)象分配器不相等標(biāo)準(zhǔn)做法是逐節(jié)點(diǎn)搬移這個(gè)屬于進(jìn)階討論初學(xué)階段可以忽略。list operator(const list other) { if (this ! other) { list tmp(other); // 深拷貝 swap(tmp); // 交換所有成員 } // tmp析構(gòu)釋放舊數(shù)據(jù) return *this; }這個(gè)寫(xiě)法用三個(gè)“標(biāo)準(zhǔn)動(dòng)作”就完成了強(qiáng)異常保證要么賦值成功要么當(dāng)前對(duì)象保持原值。很多人一開(kāi)始不敢用copy-and-swap怕“拷貝整個(gè)鏈表太浪費(fèi)”。實(shí)際場(chǎng)景下大多數(shù)賦值操作本來(lái)就需要完整的深拷貝語(yǔ)義暫時(shí)無(wú)法復(fù)用舊節(jié)點(diǎn)寫(xiě)起來(lái)省心比省幾次拷貝更重要。如果你真在乎性能后續(xù)再優(yōu)化成“盡量復(fù)用已有節(jié)點(diǎn)”的版本但那些版本要處理的邊界非常多不建議作為第一版實(shí)現(xiàn)。移動(dòng)構(gòu)造和移動(dòng)賦值則簡(jiǎn)單很多。移動(dòng)構(gòu)造只要把源對(duì)象的哨兵指針收過(guò)來(lái)然后把源對(duì)象置為空表移動(dòng)賦值也走swap或者先swap再讓源對(duì)象持有舊數(shù)據(jù)收尾。list(list other) noexcept : _M_node(other._M_node), _M_size(other._M_size), _M_node_alloc(std::move(other._M_node_alloc)) { other._M_node nullptr; other._M_size 0; } list operator(list other) noexcept { if (this ! other) { clear(); _M_dealloc_node(_M_node); _M_node other._M_node; _M_size other._M_size; other._M_node nullptr; other._M_size 0; } return *this; }移動(dòng)構(gòu)造里有個(gè)小細(xì)節(jié)源對(duì)象置空后哨兵節(jié)點(diǎn)也沒(méi)了因此源對(duì)象的析構(gòu)函數(shù)必須支持_M_node nullptr。標(biāo)準(zhǔn)庫(kù)的實(shí)現(xiàn)里被移動(dòng)后的標(biāo)準(zhǔn)容器“有效但未指定狀態(tài)”允許為空表。我自己寫(xiě)析構(gòu)時(shí)一定會(huì)加這個(gè)判斷~list() { if (_M_node) { clear(); _M_dealloc_node(_M_node); _M_node nullptr; } }4. 實(shí)操核心操作實(shí)現(xiàn)與調(diào)試實(shí)錄4.1 插入與刪除統(tǒng)一走_(dá)M_insert、_M_erase兩條內(nèi)部通道先把外界最常調(diào)的接口列出來(lái)然后看它們?nèi)绾问諗康絻蓚€(gè)內(nèi)部函數(shù)。push_front等價(jià)于在begin()處插入push_back等價(jià)于在end()處插入insert(it, value)的返回值是新元素迭代器erase(it)的返回值是被刪元素的下一個(gè)元素的迭代器。注意list的erase返回的是下一個(gè)有效迭代器不是void這點(diǎn)和vector一致但是list的erase不會(huì)讓其他迭代器失效因?yàn)閯h除節(jié)點(diǎn)只動(dòng)了局部指針。內(nèi)部實(shí)現(xiàn)我統(tǒng)一這樣寫(xiě)iterator _M_insert(const_iterator position, const T value) { _NodePtr new_node _M_construct_node(value); _NodePtr pos position._M_node; new_node-_M_next pos; new_node-_M_prev pos-_M_prev; if (pos-_M_prev) pos-_M_prev-_M_next new_node; pos-_M_prev new_node; _M_size; return iterator(new_node); } iterator _M_erase(const_iterator position) { _NodePtr pos position._M_node; _NodePtr prev pos-_M_prev; _NodePtr next pos-_M_next; if (prev) prev-_M_next next; if (next) next-_M_prev prev; --_M_size; _M_destroy_node(pos); return iterator(next); }由于有哨兵節(jié)點(diǎn)的存在pos-_M_prev和pos-_M_next理論上都不會(huì)是nullptr除非你允許迭代器指向哨兵本身即end()所以很多實(shí)現(xiàn)直接省略空判斷。不過(guò)我在調(diào)試階段踩過(guò)“空鏈表上調(diào)用erase(end())”的坑標(biāo)準(zhǔn)庫(kù)里這是未定義行為但調(diào)試版四種標(biāo)準(zhǔn)庫(kù)都有斷言我自己實(shí)現(xiàn)寧可保留判空邏輯讓錯(cuò)誤提前暴露雖然在release版下會(huì)多幾條分支判斷體感無(wú)差別。emplace_back是push_back的進(jìn)階版它把參數(shù)包直接轉(zhuǎn)發(fā)給_M_construct_node在節(jié)點(diǎn)內(nèi)存上直接構(gòu)造T而不是先構(gòu)造T再拷貝進(jìn)節(jié)點(diǎn)。這一步省掉一次移動(dòng)/拷貝是“STL風(fēng)格編程”里很標(biāo)志性的寫(xiě)法。下面的代碼同時(shí)處理了參數(shù)的完美轉(zhuǎn)發(fā)template typename... Args void emplace_back(Args... args) { _NodePtr new_node _M_construct_node(std::forwardArgs(args)...); _NodePtr tail _M_node-_M_prev; if (tail) { tail-_M_next new_node; new_node-_M_prev tail; } else { _M_node-_M_next new_node; new_node-_M_prev _M_node; } new_node-_M_next _M_node; _M_node-_M_prev new_node; _M_size; }4.2 完整代碼組織頭文件結(jié)構(gòu)、namespace與內(nèi)聯(lián)模擬實(shí)現(xiàn)建議把代碼放在頭文件里全部聲明為inline或者直接定義在類(lèi)內(nèi)。不要試圖做list.h聲明加list.cpp定義分離模板類(lèi)分離編譯會(huì)帶來(lái)一堆鏈接錯(cuò)誤熱詞里“c#調(diào)用c出現(xiàn)access violation c0000005”、“vscode配置c/c環(huán)境”這類(lèi)問(wèn)題很多根源就是模板的聲明與定義分離。C模板只有在實(shí)例化時(shí)才知道具體類(lèi)型編譯器必須在每個(gè)翻譯單元都能看到完整實(shí)現(xiàn)否則只能換來(lái)一個(gè)“undefined reference”。通常的做法是建一個(gè)mylist命名空間避免污染全局命名空間。頭文件開(kāi)頭寫(xiě)好包含保護(hù)或#pragma once然后按順序組織節(jié)點(diǎn)結(jié)構(gòu) - 迭代器結(jié)構(gòu) - list類(lèi)框架 - 成員函數(shù)實(shí)現(xiàn)。這種組織方式跟你自己去翻bits/stl_list.h看到的源碼順序幾乎一致對(duì)著看的時(shí)候會(huì)覺(jué)得非常親切。我還會(huì)加一組static_assert來(lái)驗(yàn)證迭代器類(lèi)型和容器類(lèi)型別名這比編譯運(yùn)行后再手動(dòng)驗(yàn)證要省事得多。#pragma once #include memory #include iterator #include algorithm #include utility #include type_traits namespace mylist { // 節(jié)點(diǎn)、迭代器、list 的實(shí)現(xiàn)... } // namespace mylistnamespace是一個(gè)細(xì)節(jié)點(diǎn)標(biāo)準(zhǔn)庫(kù)的std::list也在namespacestd內(nèi)部外部代碼靠using聲明或者std::前綴訪(fǎng)問(wèn)。我們自己實(shí)現(xiàn)放獨(dú)立namespace能避免和標(biāo)準(zhǔn)庫(kù)的std::list沖突同時(shí)還能在同一個(gè)測(cè)試文件里同時(shí)includelist和mylist.h直接對(duì)比行為差異。4.3 測(cè)試驅(qū)動(dòng)遍歷、插入刪除、迭代器有效性完整代碼寫(xiě)完只是開(kāi)始測(cè)試才是真正見(jiàn)真章的地方。我通常先跑四組用例每一組都奔著某個(gè)特定崩潰點(diǎn)去第一組空表操作?？誰(shuí)ist的begin()end()應(yīng)該為真size()0push_front和push_back各插一個(gè)后size()2此時(shí)打斷點(diǎn)觀察哨兵節(jié)點(diǎn)的prev和next是否正確。第二組普通插入和刪除。插入10個(gè)元素用迭代器隔一個(gè)刪一個(gè)驗(yàn)證每次erase返回的迭代器能繼續(xù)安全。這是很多簡(jiǎn)化版list過(guò)不去的坎原因往往是erase返回的迭代器指向了已經(jīng)被destroy的節(jié)點(diǎn)然后下一輪訪(fǎng)問(wèn)野指針。第三組迭代器失效檢查。關(guān)鍵測(cè)試是保存一個(gè)指向第3個(gè)元素的迭代器然后push_back一個(gè)元素再訪(fǎng)問(wèn)舊迭代器它必須還能正常解引用。這個(gè)特性是list族容器最值錢(qián)的承諾如果你是用“vector式的整塊搬移”思路寫(xiě)鏈表這段話(huà)多半會(huì)翻車(chē)。第四組大容量構(gòu)造與析構(gòu)。創(chuàng)建10萬(wàn)個(gè)元素反復(fù)拷貝賦值和移動(dòng)賦值用系統(tǒng)自帶的任務(wù)管理器觀察內(nèi)存有沒(méi)有只漲不降。這一步能抓出析構(gòu)里漏掉的節(jié)點(diǎn)回收、拷貝賦值中未釋放的舊數(shù)據(jù)。我這里貼一個(gè)比較常用的測(cè)試?yán)铀瑫r(shí)覆蓋了“遍歷寫(xiě)、遍歷刪、反向遍歷”#include cassert #include iostream #include mylist.h int main() { mylist::listint nums; for (int i 0; i 10; i) nums.emplace_back(i); // 正向遍歷把偶數(shù)項(xiàng)刪掉 for (auto it nums.begin(); it ! nums.end();) { if (*it % 2 0) it nums.erase(it); else it; } // 反向遍歷打印奇數(shù)項(xiàng) for (auto it nums.rbegin(); it ! nums.rend(); it) std::cout *it ; std::cout \n; // 驗(yàn)證size和內(nèi)容 assert(nums.size() 5); int expect 1; for (auto x : nums) { assert(x expect); expect 2; } std::cout all tests passed std::endl; }這個(gè)程序里最值得注意的寫(xiě)法是用it nums.erase(it)而不是刪完再it。在list里erase后當(dāng)前迭代器已經(jīng)失效直接it就是訪(fǎng)問(wèn)被釋放內(nèi)存這一步在release版可能僥幸不崩在debug版必然觸發(fā)斷言或者得到隨機(jī)值。你去看各種C面試題十有八九會(huì)考這一點(diǎn)。5. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄5.1 迭代器失效與野指針為什么erase后不能再用舊迭代器模擬實(shí)現(xiàn)list遇到的最多的錯(cuò)誤就是刪除節(jié)點(diǎn)后繼續(xù)使用指向該節(jié)點(diǎn)的迭代器。比如for (auto it list.begin(); it ! list.end(); it) { if (*it 3) list.erase(it); // 錯(cuò)誤erase后it已經(jīng)失效 }在list里erase(it)已經(jīng)destroy了迭代器指向的節(jié)點(diǎn)并釋放了內(nèi)存后續(xù)對(duì)it的、*it都是懸垂訪(fǎng)問(wèn)輕則讀到臟數(shù)據(jù)重則直接段錯(cuò)誤。正確姿勢(shì)是讓迭代器“先走一步再刪”或者直接接收erase的返回值// 方法一先保存后繼 auto next_it std::next(it); list.erase(it); it next_it; // 方法二直接使用返回值推薦最簡(jiǎn)潔 it list.erase(it);另外一個(gè)常見(jiàn)的隱藏問(wèn)題不要在遍歷過(guò)程中const引用和普通迭代器混用。一個(gè)const迭代器和普通迭代器同時(shí)指向同一個(gè)節(jié)點(diǎn)刪除后再解引用const迭代器同樣會(huì)觸發(fā)spectre般的未定義行為。list能保證的是“其他未刪除節(jié)點(diǎn)的迭代器依舊有效”這已經(jīng)是性?xún)r(jià)比極高的承諾。5.2 訪(fǎng)問(wèn)沖突c0000005與破壞的鏈表結(jié)構(gòu)熱詞里有“c#調(diào)用c出現(xiàn)access violation c0000005”這是Windows下C調(diào)用方最常見(jiàn)的崩潰之一對(duì)應(yīng)Linux上的segmentation fault。放在list場(chǎng)景里絕大部分原因是鏈表指針斷鏈后的解引用。比如insert在空表時(shí)如果忘記掛接哨兵節(jié)點(diǎn)的next/prev之后訪(fǎng)問(wèn)_M_node-_M_next-_M_next就會(huì)讀到非法地址。我自己排過(guò)很多次這種問(wèn)題最有效的調(diào)試武器就是“內(nèi)存斷點(diǎn)”。所謂內(nèi)存斷點(diǎn)是在調(diào)試器里對(duì)一個(gè)節(jié)點(diǎn)的地址設(shè)置寫(xiě)入斷點(diǎn)比如你要檢查節(jié)點(diǎn)A的_M_next什么時(shí)候被改壞就給A-_M_next下斷點(diǎn)。此時(shí)任何一段代碼試圖改寫(xiě)這個(gè)地址都會(huì)立刻斷下來(lái)你就能看到是insert還是erase寫(xiě)錯(cuò)了順序。這個(gè)方法在Windows的Visual Studio和Linux的gdb里都支持gdb里的命令是watch *((long*)node-next)。這里再分享一個(gè)我經(jīng)常用到的鏈表完整性校驗(yàn)函數(shù)。把它掛在每次操作后跑一遍能在問(wèn)題擴(kuò)大之前抓住指針斷鏈void _M_check_linkage() const { if (_M_size 0) { assert(_M_node-_M_next nullptr || _M_node-_M_next nullptr); assert(_M_node-_M_prev nullptr || _M_node-_M_prev nullptr); } else { _NodePtr p _M_node-_M_next; size_t count 0; while (p ! _M_node) { count; assert(p-_M_next ! nullptr); assert(p-_M_next-_M_prev p); p p-_M_next; } assert(count _M_size); assert(_M_node-_M_prev p-_M_prev); } }這個(gè)函數(shù)檢查的是“雙向一致性”任意節(jié)點(diǎn)的next所指節(jié)點(diǎn)的prev必須指回自己。大多數(shù)鏈表崩潰追根究底都是這一步被破壞寫(xiě)錯(cuò)了insert的“先掛prev再改prev的next”就會(huì)導(dǎo)致回程遍歷時(shí)指針跳飛。5.3 構(gòu)造與析構(gòu)不匹配內(nèi)存泄漏、double-free熱詞里“拷貝構(gòu)造函數(shù)調(diào)用時(shí)機(jī)”和“microsoft visual c redistributable”同時(shí)出現(xiàn)我猜測(cè)提問(wèn)者很可能是在Windows上調(diào)試時(shí)遇到分配器或CRT報(bào)錯(cuò)。這里要區(qū)分兩個(gè)層面如果用的是std::allocator構(gòu)造和析構(gòu)只要嚴(yán)格配對(duì)不會(huì)有問(wèn)題但如果你為了練手寫(xiě)了自定義分配器那么最容易犯的錯(cuò)就是“用allocate分配卻用delete釋放”或者反過(guò)來(lái)。allocate和deallocate必須一對(duì)一construct和destroy必須一對(duì)一這兩對(duì)之間不能交叉。很多自定義分配器在里頭記錄了一個(gè)“已分配塊列表”交叉調(diào)用會(huì)導(dǎo)致斷言崩潰。檢查清單如下每個(gè)節(jié)點(diǎn)分配對(duì)應(yīng)一次節(jié)點(diǎn)銷(xiāo)毀和一次deallocate。銷(xiāo)毀哨兵節(jié)點(diǎn)時(shí)也要先destroy哨兵里的數(shù)據(jù)雖然沒(méi)有有效數(shù)據(jù)但標(biāo)準(zhǔn)庫(kù)的實(shí)現(xiàn)會(huì)把哨兵的data視為已構(gòu)造必須destroy再deallocate?？截愘x值時(shí)先釋放舊數(shù)據(jù)再裝新數(shù)據(jù)順序反了會(huì)double-free。我在調(diào)試時(shí)還會(huì)把_M_size和實(shí)際遍歷節(jié)點(diǎn)數(shù)比對(duì)數(shù)值不一致說(shuō)明有節(jié)點(diǎn)泄漏或重復(fù)釋放。搭配valgrindLinux或者Visual Studio的診斷模式Windows跑一遍測(cè)試用例通常能在五分鐘內(nèi)定位到問(wèn)題。如果工具暫時(shí)沒(méi)法用那就退回到“_M_check_linkage 內(nèi)存斷點(diǎn)”這條純手工路線(xiàn)。5.4 編譯報(bào)錯(cuò)的排除思路模板報(bào)錯(cuò)為什么又臭又長(zhǎng)手寫(xiě)模板容器最勸退人的地方就是編譯報(bào)錯(cuò)。刪除一個(gè)節(jié)點(diǎn)時(shí)報(bào)錯(cuò)信息能刷出一整屏的模板實(shí)例化上下文看著跟天書(shū)一樣。我的經(jīng)驗(yàn)是分三步走。第一步先看報(bào)錯(cuò)第一行和最后一行通常是“required from here”它會(huì)告訴你這次實(shí)例化是從哪句調(diào)用發(fā)起的。絕大多數(shù)情況下問(wèn)題出現(xiàn)在你調(diào)用容器的那個(gè)函數(shù)里而不是容器實(shí)現(xiàn)內(nèi)部。第二步把那些很奇怪的長(zhǎng)類(lèi)型名折疊掉。使用別名、using聲明、或者直接用auto接收返回值能顯著減少閱讀負(fù)擔(dān)。比如auto it nums.begin();而不是mylist::listint::iterator it nums.begin();。第三步用“最小復(fù)現(xiàn)”的方式把報(bào)錯(cuò)縮小。比如單獨(dú)寫(xiě)一行nums.erase(nums.begin());如果編譯不過(guò)再縮小到nums.begin()和nums.erase各自的類(lèi)型約束上。我遇到的大部分模板編譯失敗最終都落在“迭代器的value_type和容器的value_type不匹配”上比如把const_iterator傳給了需要iterator的重載。這時(shí)回頭檢查你的const轉(zhuǎn)換構(gòu)造函數(shù)是否寫(xiě)了enable_if十有八九就是它在攔路。開(kāi)發(fā)環(huán)境建議統(tǒng)一用近幾年的編譯器和標(biāo)準(zhǔn)。評(píng)論區(qū)經(jīng)常有人拿老式Visual Studio 2015編譯一堆C11時(shí)代的例子失敗這并不代表代碼有問(wèn)題而是老編譯器對(duì)模板的支持不完整。項(xiàng)目里熱詞反復(fù)出現(xiàn)“vscode配置c/c環(huán)境”說(shuō)明很多人在編輯器層面就卡住了。這里給個(gè)不出錯(cuò)的最小配置思路裝好編譯器后在vscode里配置tasks.json的編譯命令加-Wall -Wextra -g再配上c_cpp_properties.json里的cppStandard為c17就夠跑本文所有代碼了。不需要裝一堆花哨擴(kuò)展。6. 從模擬到實(shí)戰(zhàn)list之后還能擴(kuò)展什么做完這個(gè)list模擬實(shí)現(xiàn)其實(shí)已經(jīng)把STL容器設(shè)計(jì)里最硬核的牙齒啃下來(lái)了。后面可以順手做幾件很好玩的事給list加上std::initializer_list構(gòu)造讓{1,2,3}這種語(yǔ)法直接可用實(shí)現(xiàn)splice接口用O(1)時(shí)間把另一個(gè)list的一段節(jié)點(diǎn)搬過(guò)來(lái)寫(xiě)一個(gè)簡(jiǎn)單的std::hash特化讓list可以作為unordered_map的value。再往后可以試試用同樣的迭代器封裝思路去寫(xiě)一個(gè)unordered_map的bucket單向鏈表迭代器那種“跳到下一個(gè)桶”的感覺(jué)本質(zhì)上跟list的“跳到下一個(gè)節(jié)點(diǎn)”是一樣的。我個(gè)人更推薦的下一個(gè)實(shí)練項(xiàng)目是手寫(xiě)vectorchar的迭代器因?yàn)樗茏屇泱w會(huì)“隨機(jī)訪(fǎng)問(wèn)迭代器和雙向迭代器”的實(shí)現(xiàn)差異。操作起來(lái)會(huì)比list的迭代器簡(jiǎn)單不少但正因?yàn)楹?jiǎn)單你會(huì)發(fā)現(xiàn)必要時(shí)還要處理“迭代器失效”之外的“容量增長(zhǎng)時(shí)所有迭代器全部失效”的問(wèn)題。兩相對(duì)比才真正理解為什么標(biāo)準(zhǔn)庫(kù)里list和vector的迭代器承諾完全不同。很多人在這一步豁然開(kāi)朗原來(lái)之前糾結(jié)的“為什么vector插入會(huì)失效、list不會(huì)”根本不是玄學(xué)而是數(shù)據(jù)結(jié)構(gòu)物理形態(tài)決定的必然結(jié)果。如果還想繼續(xù)深化“STL風(fēng)格編程”建議去讀libstdc的bits/stl_list.h源碼重點(diǎn)看兩個(gè)點(diǎn)一是_List_node_base這個(gè)基類(lèi)如何用繼承來(lái)減輕模板膨脹二是_List_const_iterator和_List_iterator之間如何用宏或者模板參數(shù)復(fù)用實(shí)現(xiàn)?？吹臅r(shí)候拿自己寫(xiě)的代碼對(duì)照會(huì)發(fā)現(xiàn)你的版本和標(biāo)準(zhǔn)庫(kù)的版本相差的只是工程優(yōu)化核心骨架完全一致。這種“原來(lái)我寫(xiě)的思路跟大師差不多”的時(shí)刻是我覺(jué)得手寫(xiě)STL容器最能帶來(lái)成就感的地方。