現(xiàn)：動(dòng)態(tài)數(shù)組原理、擴(kuò)容策略與迭代器失效機(jī)制)
前兩天有朋友給我發(fā)消息說(shuō)自己在看一個(gè)項(xiàng)目叫vectore底層實(shí)現(xiàn)基礎(chǔ)學(xué)習(xí)問(wèn)我怎么理解。我當(dāng)時(shí)下意識(shí)就說(shuō)你拼錯(cuò)了應(yīng)該是vector——C標(biāo)準(zhǔn)庫(kù)里最常用的容器。這個(gè)話題其實(shí)挺有意思的vector每個(gè)人都在用但真要把它底層那點(diǎn)事兒說(shuō)清楚很多人都會(huì)卡殼。這篇文章是我個(gè)人對(duì)std::vector底層實(shí)現(xiàn)的學(xué)習(xí)總結(jié)核心圍繞動(dòng)態(tài)數(shù)組的內(nèi)存模型、擴(kuò)容策略、對(duì)象生命周期和迭代器行為展開(kāi)最后還會(huì)帶手寫(xiě)一個(gè)簡(jiǎn)化版vector的完整過(guò)程。適合已經(jīng)用會(huì)vector、但想往源碼層面走一步的人也適合應(yīng)付面試、想跟面試官掰扯底層細(xì)節(jié)的同學(xué)。整體設(shè)計(jì)vector不是魔法是一個(gè)動(dòng)態(tài)數(shù)組很多初學(xué)者會(huì)把vector和魔法容器聯(lián)系在一起不需要指定大小隨便往里塞數(shù)據(jù)好像它能自動(dòng)管理一切。實(shí)際上vector的本質(zhì)就是一塊連續(xù)內(nèi)存上的動(dòng)態(tài)數(shù)組所有自動(dòng)增長(zhǎng)都是代碼層面的主動(dòng)管理沒(méi)有什么魔法。為什么需要vector數(shù)組與鏈表的痛點(diǎn)原生數(shù)組很直接在棧上或堆上開(kāi)一塊連續(xù)內(nèi)存按下標(biāo)訪問(wèn)是O(1)但大小一旦定下來(lái)就沒(méi)法變。你開(kāi)一個(gè)int arr[1024]想塞1025個(gè)元素就溢出或者崩潰想縮到512個(gè)元素空間又白白浪費(fèi)。鏈表倒是能動(dòng)態(tài)增刪每個(gè)節(jié)點(diǎn)在堆上獨(dú)立分配往已知位置插入刪除是O(1)但隨機(jī)訪問(wèn)必須從頭遍歷而且節(jié)點(diǎn)之間在內(nèi)存里不連續(xù)緩存命中率很差。vector正是在這兩個(gè)痛點(diǎn)之間找平衡它像數(shù)組一樣用連續(xù)內(nèi)存支持O(1)隨機(jī)訪問(wèn)同時(shí)像鏈表一樣支持動(dòng)態(tài)增長(zhǎng)在尾部插入刪除的均攤復(fù)雜度是O(1)。這決定了它的核心場(chǎng)景大量按下標(biāo)遍歷、讀取操作集中在尾部。反過(guò)來(lái)如果你頻繁在中間插入刪除vector會(huì)搬移大量元素這時(shí)候它反而不如鏈表好使。底層結(jié)構(gòu)三個(gè)指針一臺(tái)戲典型的std::vector內(nèi)部一般保存三個(gè)迭代器成員在大多數(shù)實(shí)現(xiàn)里它們就是裸指針可以理解為start指向已用空間的第一個(gè)元素finish指向最后一個(gè)有效元素的后面end_of_storage指向分配到的整塊內(nèi)存的末尾size等于finish - startcapacity等于end_of_storage - start。這三個(gè)指針決定了vector的一切狀態(tài)開(kāi)始和結(jié)束兩個(gè)指針劃出一段有真實(shí)對(duì)象的區(qū)域第三個(gè)指針劃出整段擁有所有權(quán)的內(nèi)存區(qū)域。為什么不用起始地址元素個(gè)數(shù)容量來(lái)記錄因?yàn)榘训髯龀芍羔樦笏蠸TL操作都能直接走指針?biāo)阈g(shù)比如begin()返回startend()返回finishoperator[]就是*(start i)效率極高而且天然符合從前到后的序邏輯。STL迭代器本身就是對(duì)移動(dòng)、解引用、比較這些行為的抽象裸指針就是最樸素、最高效的一種實(shí)現(xiàn)。為什么連續(xù)內(nèi)存這么重要連續(xù)內(nèi)存最大的優(yōu)勢(shì)是緩存友好。CPU在加載數(shù)據(jù)時(shí)不是一個(gè)個(gè)字節(jié)讀的而是按緩存行去取一次可能拿走64字節(jié)。你遍歷vector時(shí)arr[0]被加載arr[1]、arr[2]很可能也跟著進(jìn)了緩存后續(xù)訪問(wèn)幾乎是直接命中。而鏈表節(jié)點(diǎn)在堆上東一個(gè)西一個(gè)訪問(wèn)一個(gè)節(jié)點(diǎn)往往要重新觸發(fā)一次內(nèi)存加載性能差距在數(shù)據(jù)量大、循環(huán)次數(shù)多的時(shí)候非常明顯。但連續(xù)內(nèi)存也有代價(jià)。在中間插入元素時(shí)必須把后續(xù)元素全部往后挪刪除中間元素時(shí)必須把后續(xù)元素全部往前移空間不夠時(shí)必須另起爐灶整體搬到一個(gè)更大的新內(nèi)存塊。這些操作都是O(n)的搬移成本。所以vector不是萬(wàn)能容器它是一個(gè)在隨機(jī)訪問(wèn)、尾部增刪、緩存局部性這些指標(biāo)上優(yōu)化得很極端的容器。核心細(xì)節(jié)內(nèi)存分配、擴(kuò)容與對(duì)象生命周期理解了三個(gè)指針之后還得搞懂vector內(nèi)部怎么管理對(duì)象的“生老病死”。這塊如果不清楚寫(xiě)代碼時(shí)很容易被迭代器失效和莫名其妙的內(nèi)存問(wèn)題坑到。reserve和resize到底改了什么日常開(kāi)發(fā)里這兩個(gè)方法經(jīng)常被混淆。簡(jiǎn)單記憶reserve修改的是capacitysize不變它只保證容器底層有足夠空間容納至少這么多元素不會(huì)構(gòu)造任何對(duì)象resize修改的是size會(huì)實(shí)際構(gòu)造或析構(gòu)元素。底層實(shí)現(xiàn)上reserve(n)當(dāng)且僅當(dāng)n capacity()時(shí)才真正擴(kuò)容如果你傳入一個(gè)比當(dāng)前capacity還小的值它什么都不做。resize(n)如果當(dāng)前size小于n會(huì)先保證容量足夠再在末尾逐個(gè)構(gòu)造新元素如果size大于n就直接銷(xiāo)毀尾部多余元素但不會(huì)把capacity降下來(lái)。這里有一個(gè)實(shí)際工程中的常見(jiàn)誤區(qū)很多人以為調(diào)用resize(n)之后容量也會(huì)變小其實(shí)不會(huì)。它只改變有效元素個(gè)數(shù)分配的內(nèi)存空間依然保留。真正想把容量降下來(lái)得用shrink_to_fit或者老的swap技巧。操作對(duì)size的影響對(duì)capacity的影響是否構(gòu)造元素reserve(n)不變可能變大不會(huì)變小否resize(n)變?yōu)閚可能變大不會(huì)變小變大時(shí)構(gòu)造變小時(shí)析構(gòu)shrink_to_fit()不變可能變小不額外構(gòu)造/析構(gòu)已存在元素但搬移可能發(fā)生擴(kuò)容策略為什么是2倍而不是每次加1如果每次push_back發(fā)現(xiàn)空間不夠就只額外分配一個(gè)元素的內(nèi)存那么往一個(gè)空vector里插入N個(gè)元素會(huì)發(fā)生N次擴(kuò)容每次都要把已有元素整體搬移到一個(gè)新地方。搬移總次數(shù)是123...(N-1)也就是O(N2)級(jí)別的拷貝操作完全沒(méi)法用。所以vector必須采用按倍數(shù)擴(kuò)容的策略申請(qǐng)新容量是當(dāng)前capacity的某個(gè)倍數(shù)比如2倍或者1.5倍。這樣擴(kuò)容次數(shù)大約只有l(wèi)og N次總搬移次數(shù)被控制在線性級(jí)別攤還到每次插入的均攤復(fù)雜度就是O(1)。這跟你去飯店吃飯加桌子一樣如果每來(lái)一個(gè)客人就換一張更大的桌子遲早累死不如一次性預(yù)留夠未來(lái)一段時(shí)間的位置。具體乘多少倍C標(biāo)準(zhǔn)沒(méi)有強(qiáng)制規(guī)定不同標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)不同。2倍是比較常見(jiàn)的舊實(shí)現(xiàn)理由是擴(kuò)容次數(shù)少1.5倍的內(nèi)存浪費(fèi)更少且能更好地復(fù)用被釋放的舊內(nèi)存塊。不管用哪個(gè)倍數(shù)擴(kuò)容都意味著元素被搬到了新內(nèi)存地址所以所有指向舊容量的迭代器、指針和引用會(huì)全部失效。這一點(diǎn)是vector使用中最容易踩的坑后面會(huì)專門(mén)說(shuō)。元素的構(gòu)造與析構(gòu)不要直接new[]和delete[]很多剛接觸底層的人以為vector內(nèi)部就是new T[n]這是錯(cuò)的。new T[n]會(huì)一次性構(gòu)造n個(gè)默認(rèn)對(duì)象而vector的很多元素其實(shí)還沒(méi)有被使用不需要構(gòu)造。vector把原始內(nèi)存分配和對(duì)象生命周期分開(kāi)了分配內(nèi)存通過(guò)分配器或者::operator new拿到一塊沒(méi)有對(duì)象的原始內(nèi)存構(gòu)造對(duì)象在需要放元素的時(shí)候通過(guò)placement new在指定內(nèi)存地址上構(gòu)造比如::new ((void*)ptr) T(value)析構(gòu)對(duì)象刪除元素時(shí)手動(dòng)調(diào)用析構(gòu)函數(shù)比如ptr-~T()釋放內(nèi)存最后把整塊原始內(nèi)存交還給分配器這樣做的好處是vectorT的默認(rèn)構(gòu)造函數(shù)通常不會(huì)分配任何堆內(nèi)存因?yàn)檫B第一個(gè)元素都不存在只有首次插入元素時(shí)才觸發(fā)分配。而且reserve之后即使capacity很大size依然為0不會(huì)浪費(fèi)大量時(shí)間在無(wú)意義的默認(rèn)構(gòu)造上?？截?、移動(dòng)與swap的底層行為拷貝構(gòu)造vector時(shí)需要為新容器分配一塊獨(dú)立內(nèi)存然后把源容器里的每個(gè)元素逐個(gè)拷貝過(guò)去整體復(fù)雜度O(n)。移動(dòng)構(gòu)造vector則要輕量得多直接把源容器的三個(gè)指針“偷”過(guò)來(lái)然后把源容器置成空狀態(tài)整個(gè)過(guò)程不搬元素復(fù)雜度O(1)。這也是為什么用std::move返回或者傳vector時(shí)移動(dòng)操作比深拷貝快好幾個(gè)量級(jí)。swap兩個(gè)vector更是高效只需要交換各自的三個(gè)指針O(1)完成而且不會(huì)讓任何迭代器失效——因?yàn)樵氐膶?shí)際地址沒(méi)有變。這個(gè)特性在實(shí)現(xiàn)異常安全時(shí)很常用也就是所謂的copy-and-swap技巧先拷貝一份新數(shù)據(jù)再和新對(duì)象swap即使拷貝過(guò)程中拋異常原對(duì)象也不會(huì)被破壞。手寫(xiě)一個(gè)簡(jiǎn)化版vector光看原理總歸有點(diǎn)虛不如直接動(dòng)手寫(xiě)一個(gè)能用的MiniVector。這個(gè)版本我會(huì)刻意簡(jiǎn)化但保留最核心的機(jī)制裸指針迭代器、按倍數(shù)擴(kuò)容、placement new構(gòu)造、手動(dòng)析構(gòu)、移動(dòng)支持。你完全可以照著代碼自己跑一遍觀察擴(kuò)容行為。基本骨架與迭代器設(shè)計(jì)先定義一個(gè)模板類(lèi)主要成員就是三個(gè)指針。begin返回起始指針end返回末尾指針size和capacity直接指針相減。為了教學(xué)簡(jiǎn)單這個(gè)版本直接用裸指針作為迭代器#include cstddef #include utility #include new template typename T class MiniVector { public: using value_type T; using iterator T*; using const_iterator const T*; MiniVector() noexcept : begin_(nullptr), end_(nullptr), capacity_end_(nullptr) {} ~MiniVector() { destroy_range(begin_, end_); ::operator delete(begin_, capacity() * sizeof(T)); } size_t size() const noexcept { return end_ - begin_; } size_t capacity() const noexcept { return capacity_end_ - begin_; } bool empty() const noexcept { return begin_ end_; } iterator begin() noexcept { return begin_; } iterator end() noexcept { return end_; } const_iterator begin() const noexcept { return begin_; } const_iterator end() const noexcept { return end_; } T operator[](size_t i) noexcept { return begin_[i]; } const T operator[](size_t i) const noexcept { return begin_[i]; } void reserve(size_t new_cap); void push_back(const T value); void push_back(T value); template typename... Args void emplace_back(Args... args); void resize(size_t new_size); void shrink_to_fit(); private: T* begin_; T* end_; T* capacity_end_; void destroy_range(T* first, T* last); void reallocate(size_t new_cap); };這里沒(méi)有寫(xiě)拷貝構(gòu)造和拷貝賦值實(shí)際項(xiàng)目中必須有否則會(huì)造成雙重釋放或淺拷貝問(wèn)題。要寫(xiě)完整的話拷貝構(gòu)造可以復(fù)用reserve push_back完成這里留給你作為練習(xí)。reserve先搬好家再塞新數(shù)據(jù)reserve的核心邏輯很簡(jiǎn)單只有當(dāng)請(qǐng)求的容量大于當(dāng)前capacity時(shí)才觸發(fā)reallocate。reallocate負(fù)責(zé)分配一塊新內(nèi)存把舊元素搬到新內(nèi)存再銷(xiāo)毀舊元素、釋放舊內(nèi)存最后更新三個(gè)指針。template typename T void MiniVectorT::reallocate(size_t new_cap) { T* new_begin static_castT*(::operator new(new_cap * sizeof(T))); size_t old_size size(); for (size_t i 0; i old_size; i) { ::new (static_castvoid*(new_begin i)) T(std::move(begin_[i])); } destroy_range(begin_, end_); ::operator delete(begin_, capacity() * sizeof(T)); begin_ new_begin; end_ new_begin old_size; capacity_end_ new_begin new_cap; } template typename T void MiniVectorT::reserve(size_t new_cap) { if (new_cap capacity()) { reallocate(new_cap); } }注意這里我用::operator new分配原始內(nèi)存它不會(huì)構(gòu)造任何對(duì)象正好符合我們先有內(nèi)存后有對(duì)象的需求。搬元素時(shí)用std::move盡量轉(zhuǎn)為移動(dòng)構(gòu)造如果T不支持移動(dòng)構(gòu)造編譯器會(huì)自動(dòng)退化到拷貝構(gòu)造。搬移結(jié)束后舊內(nèi)存里的對(duì)象已經(jīng)完成了它們的使命逐個(gè)調(diào)用析構(gòu)再用::operator delete釋放整塊內(nèi)存。這個(gè)簡(jiǎn)化版沒(méi)有處理異常安全。如果某個(gè)元素的移動(dòng)構(gòu)造拋異常新分配的內(nèi)存和已經(jīng)構(gòu)造好的前面那些元素都會(huì)泄漏。標(biāo)準(zhǔn)庫(kù)通常做得更嚴(yán)謹(jǐn)會(huì)先判斷T是否保證不拋移動(dòng)再?zèng)Q定用拷貝還是移動(dòng)并且在異常時(shí)回滾。教學(xué)版就先把注意力放在主流程上。push_back與emplace_back尾部插入的關(guān)鍵路徑push_back是vector最常用的操作之一。它先檢查空間是否足夠不夠就想辦法擴(kuò)容然后在end_指向的位置構(gòu)造元素最后把end_向后移一位。這里的擴(kuò)容策略是如果當(dāng)前容量是0新容量設(shè)為1否則翻倍。template typename T void MiniVectorT::push_back(const T value) { if (end_ capacity_end_) { size_t new_cap capacity() 0 ? 1 : capacity() * 2; reallocate(new_cap); } ::new (static_castvoid*(end_)) T(value); end_; } template typename T void MiniVectorT::push_back(T value) { if (end_ capacity_end_) { size_t new_cap capacity() 0 ? 1 : capacity() * 2; reallocate(new_cap); } ::new (static_castvoid*(end_)) T(std::move(value)); end_; } template typename T template typename... Args void MiniVectorT::emplace_back(Args... args) { if (end_ capacity_end_) { size_t new_cap capacity() 0 ? 1 : capacity() * 2; reallocate(new_cap); } ::new (static_castvoid*(end_)) T(std::forwardArgs(args)...); end_; }push_back和emplace_back的區(qū)別在于參數(shù)傳遞方式。push_back接收一個(gè)已經(jīng)構(gòu)造好的對(duì)象要么拷貝要么移動(dòng)emplace_back直接接收構(gòu)造參數(shù)在end_位置原地構(gòu)造對(duì)象省去了一次臨時(shí)對(duì)象的生成和移動(dòng)。比如emplace_back(1, 2)能直接調(diào)用兩個(gè)參數(shù)的構(gòu)造函數(shù)push_back(MyClass(1,2))則需要先構(gòu)造臨時(shí)對(duì)象再移動(dòng)。編譯器優(yōu)化后兩者差距可能被抹平但語(yǔ)義上emplace更直接。resize、shrink_to_fit與清理邏輯resize要處理三種情況擴(kuò)大size時(shí)在末尾構(gòu)造默認(rèn)對(duì)象縮小時(shí)析構(gòu)多余對(duì)象size不變則什么都不做。擴(kuò)大前要確保容量足夠否則先reserve。template typename T void MiniVectorT::resize(size_t new_size) { if (new_size size()) { destroy_range(begin_ new_size, end_); end_ begin_ new_size; } else if (new_size size()) { if (new_size capacity()) { reserve(new_size); } for (size_t i size(); i new_size; i) { ::new (static_castvoid*(begin_ i)) T(); } end_ begin_ new_size; } } template typename T void MiniVectorT::shrink_to_fit() { size_t cur_size size(); if (capacity() cur_size) { return; } if (cur_size 0) { destroy_range(begin_, end_); ::operator delete(begin_, capacity() * sizeof(T)); begin_ end_ capacity_end_ nullptr; } else { reallocate(cur_size); } }resize如果縮小到比當(dāng)前size小不會(huì)釋放底層內(nèi)存這根標(biāo)準(zhǔn)庫(kù)行為一致。shrink_to_fit才真正考慮釋放多余空間。如果size為0直接清空所有內(nèi)存然后回歸nullptr否則調(diào)用reallocate(cur_size)重新分配一塊恰好夠用的內(nèi)存。注意shrink_to_fit是一次完整的搬移不是免費(fèi)操作。如果你接下來(lái)還要繼續(xù)插入元素這次縮小就是白白浪費(fèi)時(shí)間。destroy_range簡(jiǎn)單遍歷指針區(qū)間逐個(gè)調(diào)用析構(gòu)函數(shù)。在析構(gòu)函數(shù)里先銷(xiāo)毀所有有效對(duì)象再釋放整塊堆內(nèi)存順序不能反。template typename T void MiniVectorT::destroy_range(T* first, T* last) { for (T* p first; p ! last; p) { p-~T(); } }測(cè)試擴(kuò)容看看內(nèi)部發(fā)生了什么寫(xiě)個(gè)小main函數(shù)觀察每次push_back后size和capacity的變化#include iostream int main() { MiniVectorint v; for (int i 0; i 10; i) { v.push_back(i); std::cout size v.size() cap v.capacity() \n; } for (int x : v) { std::cout x ; } std::cout \n; return 0; }輸出會(huì)是size1 cap1 size2 cap2 size3 cap4 size4 cap4 size5 cap8 ... size10 cap16容量序列是1、2、4、8、16這就是翻倍擴(kuò)容的軌跡。如果你預(yù)先知道要放10個(gè)元素直接reserve(10)可以把容量一次性定為至少10后面10次push_back一次擴(kuò)容都不用發(fā)生性能會(huì)好很多。這是vector底層機(jī)制帶來(lái)最直接的實(shí)際影響。常見(jiàn)問(wèn)題與排查技巧手寫(xiě)一個(gè)玩具版vector之后再回頭看實(shí)際工程里那些問(wèn)題思路就清晰很多了。這一節(jié)整理幾個(gè)最常見(jiàn)的坑都是我見(jiàn)過(guò)的真實(shí)案例有的發(fā)生在別人身上有的發(fā)生在我自己身上。迭代器為什么會(huì)失效怎么避免vector的迭代器失效規(guī)則比list要嚴(yán)格得多。凡是可能觸發(fā)擴(kuò)容的操作比如push_back、insert、reserve、resize都會(huì)讓所有舊迭代器、指針和引用失效因?yàn)樵乇话岬搅诵碌刂贰rase中間的元素會(huì)讓指向被刪除元素以及后續(xù)元素的迭代器失效因?yàn)楹罄m(xù)元素往前挪了位置。為避免失效最直接的方法是提前reserve足夠容量。如果你知道要插入多少元素先預(yù)留好循環(huán)里push_back就不會(huì)再改變底層地址。如果確實(shí)需要在循環(huán)里操作并依賴迭代器可以把迭代器轉(zhuǎn)化為下標(biāo)或者在下一次操作前重新獲取v.begin()。有一個(gè)典型誤區(qū)for (auto it v.begin(); it ! v.end(); it) { v.push_back(...); }這在擴(kuò)容之后it和v.end()都會(huì)失效運(yùn)行結(jié)果不可預(yù)測(cè)。正確做法是記錄當(dāng)前下標(biāo)按size()循環(huán)或者拷貝出需要的舊數(shù)據(jù)后再插入。頻繁擴(kuò)容的隱形開(kāi)銷(xiāo)不reserve直接循環(huán)push_back每次翻倍擴(kuò)容都會(huì)做一次“分配新內(nèi)存-搬舊元素-釋放舊內(nèi)存”的完整流程。這個(gè)過(guò)程對(duì)大型對(duì)象尤其昂貴因?yàn)榘嵋茖?duì)象本身也有cpu成本。我用一個(gè)簡(jiǎn)單的計(jì)時(shí)對(duì)比說(shuō)明往vector里插入100萬(wàn)個(gè)整數(shù)不reserve和reserve(1000000)的耗時(shí)差距可能有好幾倍。在時(shí)間敏感的服務(wù)里這種差距會(huì)被放大成線上延遲抖動(dòng)。解決辦法就是在數(shù)據(jù)量可預(yù)估時(shí)提前reserve。不過(guò)也不要過(guò)度預(yù)留reserve一個(gè)遠(yuǎn)大于實(shí)際數(shù)據(jù)量的容量會(huì)白白占用內(nèi)存尤其在嵌入式或其他內(nèi)存敏感環(huán)境下。shrink_to_fit不是銀彈shrink_to_fit的作用是請(qǐng)求容器把capacity降到接近size但是它是O(n)操作因?yàn)橐熏F(xiàn)存元素搬到一塊更小內(nèi)存里。如果你在完成一次批量導(dǎo)入之后還要繼續(xù)插入新數(shù)據(jù)這個(gè)操作等于白白搬一次家隨后擴(kuò)容又得再搬一次雙倍損失。老一點(diǎn)的C98時(shí)代沒(méi)有shrink_to_fit流行用vectorT(v).swap(v)來(lái)強(qiáng)行減容但這種方式會(huì)多一次完整拷貝?，F(xiàn)代C直接用shrink_to_fit()就好了只是記住這個(gè)請(qǐng)求不一定保證成功標(biāo)準(zhǔn)庫(kù)可以選擇忽略。反正它只是一個(gè)性能內(nèi)存權(quán)衡建議別把它當(dāng)成必須生效的命令。vector vs list vs deque該怎么選經(jīng)常有人問(wèn)既然vector中間插入O(n)是不是用list更好其實(shí)不見(jiàn)得。真實(shí)測(cè)試中如果容器里是幾個(gè)字節(jié)的整數(shù)中間插入少量元素時(shí)vector往往比list更快因?yàn)閘ist的節(jié)點(diǎn)分配需要走內(nèi)存分配器而且緩存不友好遍歷代價(jià)高。vector的搬移只是連續(xù)的memcpy級(jí)別的移動(dòng)在CPU層面非?？臁Ｈ萜麟S機(jī)訪問(wèn)頭部插入尾部插入內(nèi)存布局典型場(chǎng)景vectorO(1)O(n)均攤O(1)連續(xù)內(nèi)存讀多寫(xiě)少、尾部增刪listO(n)O(1)O(1)分散節(jié)點(diǎn)頻繁中間插入且需要迭代器穩(wěn)定dequeO(1)O(1)均攤O(1)分段連續(xù)需要兩端操作但不要求極緊密內(nèi)存實(shí)際工程中的建議是默認(rèn)用vector。只有你能明確說(shuō)出list比vector更好用的理由時(shí)才換容器。比如你需要大量已知位置的中間插入且元素本身拷貝開(kāi)銷(xiāo)極大或者你需要保持指向元素的指針/引用長(zhǎng)期有效、不被搬移。除此之外vector的緩存友好和底層連續(xù)特性在絕大多數(shù)場(chǎng)景下都更劃算。自定義類(lèi)型帶來(lái)的幾個(gè)坑自定義類(lèi)型作為vector元素時(shí)要考慮默認(rèn)構(gòu)造、拷貝構(gòu)造、移動(dòng)構(gòu)造和析構(gòu)是否都可用。resize變大時(shí)要默認(rèn)構(gòu)造新元素如果類(lèi)沒(méi)有默認(rèn)構(gòu)造函數(shù)編譯直接報(bào)錯(cuò)。push_back和insert隨時(shí)可能拷貝或移動(dòng)元素如果類(lèi)沒(méi)有拷貝構(gòu)造函數(shù)或移動(dòng)構(gòu)造函數(shù)很多vector操作沒(méi)法用。如果類(lèi)的拷貝代價(jià)很高每次擴(kuò)容就成了性能災(zāi)難所以實(shí)踐中建議在類(lèi)里實(shí)現(xiàn)高效的移動(dòng)構(gòu)造函數(shù)并且標(biāo)記noexcept這樣vector擴(kuò)容時(shí)會(huì)優(yōu)先移動(dòng)而不是拷貝。還有一個(gè)容易被忽略的問(wèn)題是如果元素類(lèi)型含有裸指針且拷貝是淺拷貝vector的自動(dòng)搬移會(huì)導(dǎo)致多個(gè)對(duì)象指向同一塊內(nèi)存析構(gòu)時(shí)造成double free。這種情況下必須先實(shí)現(xiàn)正確的拷貝語(yǔ)義或者把裸指針換成shared_ptr這類(lèi)智能指針。vector本身不會(huì)幫你解決所有權(quán)問(wèn)題它只是忠實(shí)地拷貝你寫(xiě)好的類(lèi)行為。寫(xiě)在最后幾個(gè)我踩過(guò)的坑我自己在前些年做一個(gè)后臺(tái)服務(wù)時(shí)遇到過(guò)一段非常隱蔽的問(wèn)題某個(gè)流程里先拿到了一個(gè)指向vector首元素的指針然后在循環(huán)里繼續(xù)push_back擴(kuò)容發(fā)生后舊內(nèi)存被釋放那個(gè)指針變成了懸垂指針程序表現(xiàn)時(shí)好時(shí)壞排查了很久才發(fā)現(xiàn)是擴(kuò)容導(dǎo)致地址失效。從那以后我只要看到有人在持有vector內(nèi)部指針或引用之后又繼續(xù)插入元素就會(huì)下意識(shí)提醒一句先reserve夠再說(shuō)。還有一次我在一個(gè)內(nèi)存緊張的環(huán)境里頻繁創(chuàng)建銷(xiāo)毀一個(gè)容量很大的vector每次創(chuàng)建都要分配和釋放大塊內(nèi)存導(dǎo)致內(nèi)存碎片越來(lái)越嚴(yán)重。后來(lái)改成用一個(gè)長(zhǎng)期復(fù)用、預(yù)留固定容量的vector對(duì)象池才把波動(dòng)壓下去。底層實(shí)現(xiàn)這東西平時(shí)寫(xiě)業(yè)務(wù)不深究也能活但一旦線上出問(wèn)題理解底層機(jī)制能讓你少走很多彎路。希望這篇學(xué)習(xí)總結(jié)對(duì)你也有用。 std::vector底層實(shí)現(xiàn)：動(dòng)態(tài)數(shù)組原理、擴(kuò)容策略與迭代器失效機(jī)制
前兩天有朋友給我發(fā)消息說(shuō)自己在看一個(gè)項(xiàng)目叫vectore底層實(shí)現(xiàn)基礎(chǔ)學(xué)習(xí)問(wèn)我怎么理解。我當(dāng)時(shí)下意識(shí)就說(shuō)你拼錯(cuò)了應(yīng)該是vector——C標(biāo)準(zhǔn)庫(kù)里最常用的容器。這個(gè)話題其實(shí)挺有意思的vector每個(gè)人都在用但真要把它底層那點(diǎn)事兒說(shuō)清楚很多人都會(huì)卡殼。這篇文章是我個(gè)人對(duì)std::vector底層實(shí)現(xiàn)的學(xué)習(xí)總結(jié)核心圍繞動(dòng)態(tài)數(shù)組的內(nèi)存模型、擴(kuò)容策略、對(duì)象生命周期和迭代器行為展開(kāi)最后還會(huì)帶手寫(xiě)一個(gè)簡(jiǎn)化版vector的完整過(guò)程。適合已經(jīng)用會(huì)vector、但想往源碼層面走一步的人也適合應(yīng)付面試、想跟面試官掰扯底層細(xì)節(jié)的同學(xué)。整體設(shè)計(jì)vector不是魔法是一個(gè)動(dòng)態(tài)數(shù)組很多初學(xué)者會(huì)把vector和魔法容器聯(lián)系在一起不需要指定大小隨便往里塞數(shù)據(jù)好像它能自動(dòng)管理一切。實(shí)際上vector的本質(zhì)就是一塊連續(xù)內(nèi)存上的動(dòng)態(tài)數(shù)組所有自動(dòng)增長(zhǎng)都是代碼層面的主動(dòng)管理沒(méi)有什么魔法。為什么需要vector數(shù)組與鏈表的痛點(diǎn)原生數(shù)組很直接在棧上或堆上開(kāi)一塊連續(xù)內(nèi)存按下標(biāo)訪問(wèn)是O(1)但大小一旦定下來(lái)就沒(méi)法變。你開(kāi)一個(gè)int arr[1024]想塞1025個(gè)元素就溢出或者崩潰想縮到512個(gè)元素空間又白白浪費(fèi)。鏈表倒是能動(dòng)態(tài)增刪每個(gè)節(jié)點(diǎn)在堆上獨(dú)立分配往已知位置插入刪除是O(1)但隨機(jī)訪問(wèn)必須從頭遍歷而且節(jié)點(diǎn)之間在內(nèi)存里不連續(xù)緩存命中率很差。vector正是在這兩個(gè)痛點(diǎn)之間找平衡它像數(shù)組一樣用連續(xù)內(nèi)存支持O(1)隨機(jī)訪問(wèn)同時(shí)像鏈表一樣支持動(dòng)態(tài)增長(zhǎng)在尾部插入刪除的均攤復(fù)雜度是O(1)。這決定了它的核心場(chǎng)景大量按下標(biāo)遍歷、讀取操作集中在尾部。反過(guò)來(lái)如果你頻繁在中間插入刪除vector會(huì)搬移大量元素這時(shí)候它反而不如鏈表好使。底層結(jié)構(gòu)三個(gè)指針一臺(tái)戲典型的std::vector內(nèi)部一般保存三個(gè)迭代器成員在大多數(shù)實(shí)現(xiàn)里它們就是裸指針可以理解為start指向已用空間的第一個(gè)元素finish指向最后一個(gè)有效元素的后面end_of_storage指向分配到的整塊內(nèi)存的末尾size等于finish - startcapacity等于end_of_storage - start。這三個(gè)指針決定了vector的一切狀態(tài)開(kāi)始和結(jié)束兩個(gè)指針劃出一段有真實(shí)對(duì)象的區(qū)域第三個(gè)指針劃出整段擁有所有權(quán)的內(nèi)存區(qū)域。為什么不用起始地址元素個(gè)數(shù)容量來(lái)記錄因?yàn)榘训髯龀芍羔樦笏蠸TL操作都能直接走指針?biāo)阈g(shù)比如begin()返回startend()返回finishoperator[]就是*(start i)效率極高而且天然符合從前到后的序邏輯。STL迭代器本身就是對(duì)移動(dòng)、解引用、比較這些行為的抽象裸指針就是最樸素、最高效的一種實(shí)現(xiàn)。為什么連續(xù)內(nèi)存這么重要連續(xù)內(nèi)存最大的優(yōu)勢(shì)是緩存友好。CPU在加載數(shù)據(jù)時(shí)不是一個(gè)個(gè)字節(jié)讀的而是按緩存行去取一次可能拿走64字節(jié)。你遍歷vector時(shí)arr[0]被加載arr[1]、arr[2]很可能也跟著進(jìn)了緩存后續(xù)訪問(wèn)幾乎是直接命中。而鏈表節(jié)點(diǎn)在堆上東一個(gè)西一個(gè)訪問(wèn)一個(gè)節(jié)點(diǎn)往往要重新觸發(fā)一次內(nèi)存加載性能差距在數(shù)據(jù)量大、循環(huán)次數(shù)多的時(shí)候非常明顯。但連續(xù)內(nèi)存也有代價(jià)。在中間插入元素時(shí)必須把后續(xù)元素全部往后挪刪除中間元素時(shí)必須把后續(xù)元素全部往前移空間不夠時(shí)必須另起爐灶整體搬到一個(gè)更大的新內(nèi)存塊。這些操作都是O(n)的搬移成本。所以vector不是萬(wàn)能容器它是一個(gè)在隨機(jī)訪問(wèn)、尾部增刪、緩存局部性這些指標(biāo)上優(yōu)化得很極端的容器。核心細(xì)節(jié)內(nèi)存分配、擴(kuò)容與對(duì)象生命周期理解了三個(gè)指針之后還得搞懂vector內(nèi)部怎么管理對(duì)象的“生老病死”。這塊如果不清楚寫(xiě)代碼時(shí)很容易被迭代器失效和莫名其妙的內(nèi)存問(wèn)題坑到。reserve和resize到底改了什么日常開(kāi)發(fā)里這兩個(gè)方法經(jīng)常被混淆。簡(jiǎn)單記憶reserve修改的是capacitysize不變它只保證容器底層有足夠空間容納至少這么多元素不會(huì)構(gòu)造任何對(duì)象resize修改的是size會(huì)實(shí)際構(gòu)造或析構(gòu)元素。底層實(shí)現(xiàn)上reserve(n)當(dāng)且僅當(dāng)n capacity()時(shí)才真正擴(kuò)容如果你傳入一個(gè)比當(dāng)前capacity還小的值它什么都不做。resize(n)如果當(dāng)前size小于n會(huì)先保證容量足夠再在末尾逐個(gè)構(gòu)造新元素如果size大于n就直接銷(xiāo)毀尾部多余元素但不會(huì)把capacity降下來(lái)。這里有一個(gè)實(shí)際工程中的常見(jiàn)誤區(qū)很多人以為調(diào)用resize(n)之后容量也會(huì)變小其實(shí)不會(huì)。它只改變有效元素個(gè)數(shù)分配的內(nèi)存空間依然保留。真正想把容量降下來(lái)得用shrink_to_fit或者老的swap技巧。操作對(duì)size的影響對(duì)capacity的影響是否構(gòu)造元素reserve(n)不變可能變大不會(huì)變小否resize(n)變?yōu)閚可能變大不會(huì)變小變大時(shí)構(gòu)造變小時(shí)析構(gòu)shrink_to_fit()不變可能變小不額外構(gòu)造/析構(gòu)已存在元素但搬移可能發(fā)生擴(kuò)容策略為什么是2倍而不是每次加1如果每次push_back發(fā)現(xiàn)空間不夠就只額外分配一個(gè)元素的內(nèi)存那么往一個(gè)空vector里插入N個(gè)元素會(huì)發(fā)生N次擴(kuò)容每次都要把已有元素整體搬移到一個(gè)新地方。搬移總次數(shù)是123...(N-1)也就是O(N2)級(jí)別的拷貝操作完全沒(méi)法用。所以vector必須采用按倍數(shù)擴(kuò)容的策略申請(qǐng)新容量是當(dāng)前capacity的某個(gè)倍數(shù)比如2倍或者1.5倍。這樣擴(kuò)容次數(shù)大約只有l(wèi)og N次總搬移次數(shù)被控制在線性級(jí)別攤還到每次插入的均攤復(fù)雜度就是O(1)。這跟你去飯店吃飯加桌子一樣如果每來(lái)一個(gè)客人就換一張更大的桌子遲早累死不如一次性預(yù)留夠未來(lái)一段時(shí)間的位置。具體乘多少倍C標(biāo)準(zhǔn)沒(méi)有強(qiáng)制規(guī)定不同標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)不同。2倍是比較常見(jiàn)的舊實(shí)現(xiàn)理由是擴(kuò)容次數(shù)少1.5倍的內(nèi)存浪費(fèi)更少且能更好地復(fù)用被釋放的舊內(nèi)存塊。不管用哪個(gè)倍數(shù)擴(kuò)容都意味著元素被搬到了新內(nèi)存地址所以所有指向舊容量的迭代器、指針和引用會(huì)全部失效。這一點(diǎn)是vector使用中最容易踩的坑后面會(huì)專門(mén)說(shuō)。元素的構(gòu)造與析構(gòu)不要直接new[]和delete[]很多剛接觸底層的人以為vector內(nèi)部就是new T[n]這是錯(cuò)的。new T[n]會(huì)一次性構(gòu)造n個(gè)默認(rèn)對(duì)象而vector的很多元素其實(shí)還沒(méi)有被使用不需要構(gòu)造。vector把原始內(nèi)存分配和對(duì)象生命周期分開(kāi)了分配內(nèi)存通過(guò)分配器或者::operator new拿到一塊沒(méi)有對(duì)象的原始內(nèi)存構(gòu)造對(duì)象在需要放元素的時(shí)候通過(guò)placement new在指定內(nèi)存地址上構(gòu)造比如::new ((void*)ptr) T(value)析構(gòu)對(duì)象刪除元素時(shí)手動(dòng)調(diào)用析構(gòu)函數(shù)比如ptr-~T()釋放內(nèi)存最后把整塊原始內(nèi)存交還給分配器這樣做的好處是vectorT的默認(rèn)構(gòu)造函數(shù)通常不會(huì)分配任何堆內(nèi)存因?yàn)檫B第一個(gè)元素都不存在只有首次插入元素時(shí)才觸發(fā)分配。而且reserve之后即使capacity很大size依然為0不會(huì)浪費(fèi)大量時(shí)間在無(wú)意義的默認(rèn)構(gòu)造上?？截?、移動(dòng)與swap的底層行為拷貝構(gòu)造vector時(shí)需要為新容器分配一塊獨(dú)立內(nèi)存然后把源容器里的每個(gè)元素逐個(gè)拷貝過(guò)去整體復(fù)雜度O(n)。移動(dòng)構(gòu)造vector則要輕量得多直接把源容器的三個(gè)指針“偷”過(guò)來(lái)然后把源容器置成空狀態(tài)整個(gè)過(guò)程不搬元素復(fù)雜度O(1)。這也是為什么用std::move返回或者傳vector時(shí)移動(dòng)操作比深拷貝快好幾個(gè)量級(jí)。swap兩個(gè)vector更是高效只需要交換各自的三個(gè)指針O(1)完成而且不會(huì)讓任何迭代器失效——因?yàn)樵氐膶?shí)際地址沒(méi)有變。這個(gè)特性在實(shí)現(xiàn)異常安全時(shí)很常用也就是所謂的copy-and-swap技巧先拷貝一份新數(shù)據(jù)再和新對(duì)象swap即使拷貝過(guò)程中拋異常原對(duì)象也不會(huì)被破壞。手寫(xiě)一個(gè)簡(jiǎn)化版vector光看原理總歸有點(diǎn)虛不如直接動(dòng)手寫(xiě)一個(gè)能用的MiniVector。這個(gè)版本我會(huì)刻意簡(jiǎn)化但保留最核心的機(jī)制裸指針迭代器、按倍數(shù)擴(kuò)容、placement new構(gòu)造、手動(dòng)析構(gòu)、移動(dòng)支持。你完全可以照著代碼自己跑一遍觀察擴(kuò)容行為。基本骨架與迭代器設(shè)計(jì)先定義一個(gè)模板類(lèi)主要成員就是三個(gè)指針。begin返回起始指針end返回末尾指針size和capacity直接指針相減。為了教學(xué)簡(jiǎn)單這個(gè)版本直接用裸指針作為迭代器#include cstddef #include utility #include new template typename T class MiniVector { public: using value_type T; using iterator T*; using const_iterator const T*; MiniVector() noexcept : begin_(nullptr), end_(nullptr), capacity_end_(nullptr) {} ~MiniVector() { destroy_range(begin_, end_); ::operator delete(begin_, capacity() * sizeof(T)); } size_t size() const noexcept { return end_ - begin_; } size_t capacity() const noexcept { return capacity_end_ - begin_; } bool empty() const noexcept { return begin_ end_; } iterator begin() noexcept { return begin_; } iterator end() noexcept { return end_; } const_iterator begin() const noexcept { return begin_; } const_iterator end() const noexcept { return end_; } T operator[](size_t i) noexcept { return begin_[i]; } const T operator[](size_t i) const noexcept { return begin_[i]; } void reserve(size_t new_cap); void push_back(const T value); void push_back(T value); template typename... Args void emplace_back(Args... args); void resize(size_t new_size); void shrink_to_fit(); private: T* begin_; T* end_; T* capacity_end_; void destroy_range(T* first, T* last); void reallocate(size_t new_cap); };這里沒(méi)有寫(xiě)拷貝構(gòu)造和拷貝賦值實(shí)際項(xiàng)目中必須有否則會(huì)造成雙重釋放或淺拷貝問(wèn)題。要寫(xiě)完整的話拷貝構(gòu)造可以復(fù)用reserve push_back完成這里留給你作為練習(xí)。reserve先搬好家再塞新數(shù)據(jù)reserve的核心邏輯很簡(jiǎn)單只有當(dāng)請(qǐng)求的容量大于當(dāng)前capacity時(shí)才觸發(fā)reallocate。reallocate負(fù)責(zé)分配一塊新內(nèi)存把舊元素搬到新內(nèi)存再銷(xiāo)毀舊元素、釋放舊內(nèi)存最后更新三個(gè)指針。template typename T void MiniVectorT::reallocate(size_t new_cap) { T* new_begin static_castT*(::operator new(new_cap * sizeof(T))); size_t old_size size(); for (size_t i 0; i old_size; i) { ::new (static_castvoid*(new_begin i)) T(std::move(begin_[i])); } destroy_range(begin_, end_); ::operator delete(begin_, capacity() * sizeof(T)); begin_ new_begin; end_ new_begin old_size; capacity_end_ new_begin new_cap; } template typename T void MiniVectorT::reserve(size_t new_cap) { if (new_cap capacity()) { reallocate(new_cap); } }注意這里我用::operator new分配原始內(nèi)存它不會(huì)構(gòu)造任何對(duì)象正好符合我們先有內(nèi)存后有對(duì)象的需求。搬元素時(shí)用std::move盡量轉(zhuǎn)為移動(dòng)構(gòu)造如果T不支持移動(dòng)構(gòu)造編譯器會(huì)自動(dòng)退化到拷貝構(gòu)造。搬移結(jié)束后舊內(nèi)存里的對(duì)象已經(jīng)完成了它們的使命逐個(gè)調(diào)用析構(gòu)再用::operator delete釋放整塊內(nèi)存。這個(gè)簡(jiǎn)化版沒(méi)有處理異常安全。如果某個(gè)元素的移動(dòng)構(gòu)造拋異常新分配的內(nèi)存和已經(jīng)構(gòu)造好的前面那些元素都會(huì)泄漏。標(biāo)準(zhǔn)庫(kù)通常做得更嚴(yán)謹(jǐn)會(huì)先判斷T是否保證不拋移動(dòng)再?zèng)Q定用拷貝還是移動(dòng)并且在異常時(shí)回滾。教學(xué)版就先把注意力放在主流程上。push_back與emplace_back尾部插入的關(guān)鍵路徑push_back是vector最常用的操作之一。它先檢查空間是否足夠不夠就想辦法擴(kuò)容然后在end_指向的位置構(gòu)造元素最后把end_向后移一位。這里的擴(kuò)容策略是如果當(dāng)前容量是0新容量設(shè)為1否則翻倍。template typename T void MiniVectorT::push_back(const T value) { if (end_ capacity_end_) { size_t new_cap capacity() 0 ? 1 : capacity() * 2; reallocate(new_cap); } ::new (static_castvoid*(end_)) T(value); end_; } template typename T void MiniVectorT::push_back(T value) { if (end_ capacity_end_) { size_t new_cap capacity() 0 ? 1 : capacity() * 2; reallocate(new_cap); } ::new (static_castvoid*(end_)) T(std::move(value)); end_; } template typename T template typename... Args void MiniVectorT::emplace_back(Args... args) { if (end_ capacity_end_) { size_t new_cap capacity() 0 ? 1 : capacity() * 2; reallocate(new_cap); } ::new (static_castvoid*(end_)) T(std::forwardArgs(args)...); end_; }push_back和emplace_back的區(qū)別在于參數(shù)傳遞方式。push_back接收一個(gè)已經(jīng)構(gòu)造好的對(duì)象要么拷貝要么移動(dòng)emplace_back直接接收構(gòu)造參數(shù)在end_位置原地構(gòu)造對(duì)象省去了一次臨時(shí)對(duì)象的生成和移動(dòng)。比如emplace_back(1, 2)能直接調(diào)用兩個(gè)參數(shù)的構(gòu)造函數(shù)push_back(MyClass(1,2))則需要先構(gòu)造臨時(shí)對(duì)象再移動(dòng)。編譯器優(yōu)化后兩者差距可能被抹平但語(yǔ)義上emplace更直接。resize、shrink_to_fit與清理邏輯resize要處理三種情況擴(kuò)大size時(shí)在末尾構(gòu)造默認(rèn)對(duì)象縮小時(shí)析構(gòu)多余對(duì)象size不變則什么都不做。擴(kuò)大前要確保容量足夠否則先reserve。template typename T void MiniVectorT::resize(size_t new_size) { if (new_size size()) { destroy_range(begin_ new_size, end_); end_ begin_ new_size; } else if (new_size size()) { if (new_size capacity()) { reserve(new_size); } for (size_t i size(); i new_size; i) { ::new (static_castvoid*(begin_ i)) T(); } end_ begin_ new_size; } } template typename T void MiniVectorT::shrink_to_fit() { size_t cur_size size(); if (capacity() cur_size) { return; } if (cur_size 0) { destroy_range(begin_, end_); ::operator delete(begin_, capacity() * sizeof(T)); begin_ end_ capacity_end_ nullptr; } else { reallocate(cur_size); } }resize如果縮小到比當(dāng)前size小不會(huì)釋放底層內(nèi)存這根標(biāo)準(zhǔn)庫(kù)行為一致。shrink_to_fit才真正考慮釋放多余空間。如果size為0直接清空所有內(nèi)存然后回歸nullptr否則調(diào)用reallocate(cur_size)重新分配一塊恰好夠用的內(nèi)存。注意shrink_to_fit是一次完整的搬移不是免費(fèi)操作。如果你接下來(lái)還要繼續(xù)插入元素這次縮小就是白白浪費(fèi)時(shí)間。destroy_range簡(jiǎn)單遍歷指針區(qū)間逐個(gè)調(diào)用析構(gòu)函數(shù)。在析構(gòu)函數(shù)里先銷(xiāo)毀所有有效對(duì)象再釋放整塊堆內(nèi)存順序不能反。template typename T void MiniVectorT::destroy_range(T* first, T* last) { for (T* p first; p ! last; p) { p-~T(); } }測(cè)試擴(kuò)容看看內(nèi)部發(fā)生了什么寫(xiě)個(gè)小main函數(shù)觀察每次push_back后size和capacity的變化#include iostream int main() { MiniVectorint v; for (int i 0; i 10; i) { v.push_back(i); std::cout size v.size() cap v.capacity() \n; } for (int x : v) { std::cout x ; } std::cout \n; return 0; }輸出會(huì)是size1 cap1 size2 cap2 size3 cap4 size4 cap4 size5 cap8 ... size10 cap16容量序列是1、2、4、8、16這就是翻倍擴(kuò)容的軌跡。如果你預(yù)先知道要放10個(gè)元素直接reserve(10)可以把容量一次性定為至少10后面10次push_back一次擴(kuò)容都不用發(fā)生性能會(huì)好很多。這是vector底層機(jī)制帶來(lái)最直接的實(shí)際影響。常見(jiàn)問(wèn)題與排查技巧手寫(xiě)一個(gè)玩具版vector之后再回頭看實(shí)際工程里那些問(wèn)題思路就清晰很多了。這一節(jié)整理幾個(gè)最常見(jiàn)的坑都是我見(jiàn)過(guò)的真實(shí)案例有的發(fā)生在別人身上有的發(fā)生在我自己身上。迭代器為什么會(huì)失效怎么避免vector的迭代器失效規(guī)則比list要嚴(yán)格得多。凡是可能觸發(fā)擴(kuò)容的操作比如push_back、insert、reserve、resize都會(huì)讓所有舊迭代器、指針和引用失效因?yàn)樵乇话岬搅诵碌刂贰rase中間的元素會(huì)讓指向被刪除元素以及后續(xù)元素的迭代器失效因?yàn)楹罄m(xù)元素往前挪了位置。為避免失效最直接的方法是提前reserve足夠容量。如果你知道要插入多少元素先預(yù)留好循環(huán)里push_back就不會(huì)再改變底層地址。如果確實(shí)需要在循環(huán)里操作并依賴迭代器可以把迭代器轉(zhuǎn)化為下標(biāo)或者在下一次操作前重新獲取v.begin()。有一個(gè)典型誤區(qū)for (auto it v.begin(); it ! v.end(); it) { v.push_back(...); }這在擴(kuò)容之后it和v.end()都會(huì)失效運(yùn)行結(jié)果不可預(yù)測(cè)。正確做法是記錄當(dāng)前下標(biāo)按size()循環(huán)或者拷貝出需要的舊數(shù)據(jù)后再插入。頻繁擴(kuò)容的隱形開(kāi)銷(xiāo)不reserve直接循環(huán)push_back每次翻倍擴(kuò)容都會(huì)做一次“分配新內(nèi)存-搬舊元素-釋放舊內(nèi)存”的完整流程。這個(gè)過(guò)程對(duì)大型對(duì)象尤其昂貴因?yàn)榘嵋茖?duì)象本身也有cpu成本。我用一個(gè)簡(jiǎn)單的計(jì)時(shí)對(duì)比說(shuō)明往vector里插入100萬(wàn)個(gè)整數(shù)不reserve和reserve(1000000)的耗時(shí)差距可能有好幾倍。在時(shí)間敏感的服務(wù)里這種差距會(huì)被放大成線上延遲抖動(dòng)。解決辦法就是在數(shù)據(jù)量可預(yù)估時(shí)提前reserve。不過(guò)也不要過(guò)度預(yù)留reserve一個(gè)遠(yuǎn)大于實(shí)際數(shù)據(jù)量的容量會(huì)白白占用內(nèi)存尤其在嵌入式或其他內(nèi)存敏感環(huán)境下。shrink_to_fit不是銀彈shrink_to_fit的作用是請(qǐng)求容器把capacity降到接近size但是它是O(n)操作因?yàn)橐熏F(xiàn)存元素搬到一塊更小內(nèi)存里。如果你在完成一次批量導(dǎo)入之后還要繼續(xù)插入新數(shù)據(jù)這個(gè)操作等于白白搬一次家隨后擴(kuò)容又得再搬一次雙倍損失。老一點(diǎn)的C98時(shí)代沒(méi)有shrink_to_fit流行用vectorT(v).swap(v)來(lái)強(qiáng)行減容但這種方式會(huì)多一次完整拷貝?，F(xiàn)代C直接用shrink_to_fit()就好了只是記住這個(gè)請(qǐng)求不一定保證成功標(biāo)準(zhǔn)庫(kù)可以選擇忽略。反正它只是一個(gè)性能內(nèi)存權(quán)衡建議別把它當(dāng)成必須生效的命令。vector vs list vs deque該怎么選經(jīng)常有人問(wèn)既然vector中間插入O(n)是不是用list更好其實(shí)不見(jiàn)得。真實(shí)測(cè)試中如果容器里是幾個(gè)字節(jié)的整數(shù)中間插入少量元素時(shí)vector往往比list更快因?yàn)閘ist的節(jié)點(diǎn)分配需要走內(nèi)存分配器而且緩存不友好遍歷代價(jià)高。vector的搬移只是連續(xù)的memcpy級(jí)別的移動(dòng)在CPU層面非?？臁Ｈ萜麟S機(jī)訪問(wèn)頭部插入尾部插入內(nèi)存布局典型場(chǎng)景vectorO(1)O(n)均攤O(1)連續(xù)內(nèi)存讀多寫(xiě)少、尾部增刪listO(n)O(1)O(1)分散節(jié)點(diǎn)頻繁中間插入且需要迭代器穩(wěn)定dequeO(1)O(1)均攤O(1)分段連續(xù)需要兩端操作但不要求極緊密內(nèi)存實(shí)際工程中的建議是默認(rèn)用vector。只有你能明確說(shuō)出list比vector更好用的理由時(shí)才換容器。比如你需要大量已知位置的中間插入且元素本身拷貝開(kāi)銷(xiāo)極大或者你需要保持指向元素的指針/引用長(zhǎng)期有效、不被搬移。除此之外vector的緩存友好和底層連續(xù)特性在絕大多數(shù)場(chǎng)景下都更劃算。自定義類(lèi)型帶來(lái)的幾個(gè)坑自定義類(lèi)型作為vector元素時(shí)要考慮默認(rèn)構(gòu)造、拷貝構(gòu)造、移動(dòng)構(gòu)造和析構(gòu)是否都可用。resize變大時(shí)要默認(rèn)構(gòu)造新元素如果類(lèi)沒(méi)有默認(rèn)構(gòu)造函數(shù)編譯直接報(bào)錯(cuò)。push_back和insert隨時(shí)可能拷貝或移動(dòng)元素如果類(lèi)沒(méi)有拷貝構(gòu)造函數(shù)或移動(dòng)構(gòu)造函數(shù)很多vector操作沒(méi)法用。如果類(lèi)的拷貝代價(jià)很高每次擴(kuò)容就成了性能災(zāi)難所以實(shí)踐中建議在類(lèi)里實(shí)現(xiàn)高效的移動(dòng)構(gòu)造函數(shù)并且標(biāo)記noexcept這樣vector擴(kuò)容時(shí)會(huì)優(yōu)先移動(dòng)而不是拷貝。還有一個(gè)容易被忽略的問(wèn)題是如果元素類(lèi)型含有裸指針且拷貝是淺拷貝vector的自動(dòng)搬移會(huì)導(dǎo)致多個(gè)對(duì)象指向同一塊內(nèi)存析構(gòu)時(shí)造成double free。這種情況下必須先實(shí)現(xiàn)正確的拷貝語(yǔ)義或者把裸指針換成shared_ptr這類(lèi)智能指針。vector本身不會(huì)幫你解決所有權(quán)問(wèn)題它只是忠實(shí)地拷貝你寫(xiě)好的類(lèi)行為。寫(xiě)在最后幾個(gè)我踩過(guò)的坑我自己在前些年做一個(gè)后臺(tái)服務(wù)時(shí)遇到過(guò)一段非常隱蔽的問(wèn)題某個(gè)流程里先拿到了一個(gè)指向vector首元素的指針然后在循環(huán)里繼續(xù)push_back擴(kuò)容發(fā)生后舊內(nèi)存被釋放那個(gè)指針變成了懸垂指針程序表現(xiàn)時(shí)好時(shí)壞排查了很久才發(fā)現(xiàn)是擴(kuò)容導(dǎo)致地址失效。從那以后我只要看到有人在持有vector內(nèi)部指針或引用之后又繼續(xù)插入元素就會(huì)下意識(shí)提醒一句先reserve夠再說(shuō)。還有一次我在一個(gè)內(nèi)存緊張的環(huán)境里頻繁創(chuàng)建銷(xiāo)毀一個(gè)容量很大的vector每次創(chuàng)建都要分配和釋放大塊內(nèi)存導(dǎo)致內(nèi)存碎片越來(lái)越嚴(yán)重。后來(lái)改成用一個(gè)長(zhǎng)期復(fù)用、預(yù)留固定容量的vector對(duì)象池才把波動(dòng)壓下去。底層實(shí)現(xiàn)這東西平時(shí)寫(xiě)業(yè)務(wù)不深究也能活但一旦線上出問(wèn)題理解底層機(jī)制能讓你少走很多彎路。希望這篇學(xué)習(xí)總結(jié)對(duì)你也有用。