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