現(xiàn)：動(dòng)態(tài)數(shù)組原理、擴(kuò)容策略與迭代器失效機(jī)制)
前兩天有朋友給我發(fā)消息說自己在看一個(gè)項(xiàng)目叫vectore底層實(shí)現(xiàn)基礎(chǔ)學(xué)習(xí)問我怎么理解。我當(dāng)時(shí)下意識(shí)就說你拼錯(cuò)了應(yīng)該是vector——C標(biāo)準(zhǔn)庫里最常用的容器。這個(gè)話題其實(shí)挺有意思的vector每個(gè)人都在用但真要把它底層那點(diǎn)事兒說清楚很多人都會(huì)卡殼。這篇文章是我個(gè)人對(duì)std::vector底層實(shí)現(xiàn)的學(xué)習(xí)總結(jié)核心圍繞動(dòng)態(tài)數(shù)組的內(nèi)存模型、擴(kuò)容策略、對(duì)象生命周期和迭代器行為展開最后還會(huì)帶手寫一個(gè)簡化版vector的完整過程。適合已經(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)增長都是代碼層面的主動(dòng)管理沒有什么魔法。為什么需要vector數(shù)組與鏈表的痛點(diǎn)原生數(shù)組很直接在棧上或堆上開一塊連續(xù)內(nèi)存按下標(biāo)訪問是O(1)但大小一旦定下來就沒法變。你開一個(gè)int arr[1024]想塞1025個(gè)元素就溢出或者崩潰想縮到512個(gè)元素空間又白白浪費(fèi)。鏈表倒是能動(dòng)態(tài)增刪每個(gè)節(jié)點(diǎn)在堆上獨(dú)立分配往已知位置插入刪除是O(1)但隨機(jī)訪問必須從頭遍歷而且節(jié)點(diǎn)之間在內(nèi)存里不連續(xù)緩存命中率很差。vector正是在這兩個(gè)痛點(diǎn)之間找平衡它像數(shù)組一樣用連續(xù)內(nèi)存支持O(1)隨機(jī)訪問同時(shí)像鏈表一樣支持動(dòng)態(tài)增長在尾部插入刪除的均攤復(fù)雜度是O(1)。這決定了它的核心場景大量按下標(biāo)遍歷、讀取操作集中在尾部。反過來如果你頻繁在中間插入刪除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)開始和結(jié)束兩個(gè)指針劃出一段有真實(shí)對(duì)象的區(qū)域第三個(gè)指針劃出整段擁有所有權(quán)的內(nèi)存區(qū)域。為什么不用起始地址元素個(gè)數(shù)容量來記錄因?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)勢是緩存友好。CPU在加載數(shù)據(jù)時(shí)不是一個(gè)個(gè)字節(jié)讀的而是按緩存行去取一次可能拿走64字節(jié)。你遍歷vector時(shí)arr[0]被加載arr[1]、arr[2]很可能也跟著進(jìn)了緩存后續(xù)訪問幾乎是直接命中。而鏈表節(jié)點(diǎn)在堆上東一個(gè)西一個(gè)訪問一個(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不是萬能容器它是一個(gè)在隨機(jī)訪問、尾部增刪、緩存局部性這些指標(biāo)上優(yōu)化得很極端的容器。核心細(xì)節(jié)內(nèi)存分配、擴(kuò)容與對(duì)象生命周期理解了三個(gè)指針之后還得搞懂vector內(nèi)部怎么管理對(duì)象的“生老病死”。這塊如果不清楚寫代碼時(shí)很容易被迭代器失效和莫名其妙的內(nèi)存問題坑到。reserve和resize到底改了什么日常開發(fā)里這兩個(gè)方法經(jīng)常被混淆。簡單記憶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就直接銷毀尾部多余元素但不會(huì)把capacity降下來。這里有一個(gè)實(shí)際工程中的常見誤區(qū)很多人以為調(diào)用resize(n)之后容量也會(huì)變小其實(shí)不會(huì)。它只改變有效元素個(gè)數(shù)分配的內(nè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í)別的拷貝操作完全沒法用。所以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)。這跟你去飯店吃飯加桌子一樣如果每來一個(gè)客人就換一張更大的桌子遲早累死不如一次性預(yù)留夠未來一段時(shí)間的位置。具體乘多少倍C標(biāo)準(zhǔn)沒有強(qiáng)制規(guī)定不同標(biāo)準(zhǔn)庫實(shí)現(xiàn)不同。2倍是比較常見的舊實(shí)現(xiàn)理由是擴(kuò)容次數(shù)少1.5倍的內(nèi)存浪費(fèi)更少且能更好地復(fù)用被釋放的舊內(nèi)存塊。不管用哪個(gè)倍數(shù)擴(kuò)容都意味著元素被搬到了新內(nèi)存地址所以所有指向舊容量的迭代器、指針和引用會(huì)全部失效。這一點(diǎn)是vector使用中最容易踩的坑后面會(huì)專門說。元素的構(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í)還沒有被使用不需要構(gòu)造。vector把原始內(nèi)存分配和對(duì)象生命周期分開了分配內(nèi)存通過分配器或者::operator new拿到一塊沒有對(duì)象的原始內(nèi)存構(gòu)造對(duì)象在需要放元素的時(shí)候通過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í)間在無意義的默認(rèn)構(gòu)造上。拷貝、移動(dòng)與swap的底層行為拷貝構(gòu)造vector時(shí)需要為新容器分配一塊獨(dú)立內(nèi)存然后把源容器里的每個(gè)元素逐個(gè)拷貝過去整體復(fù)雜度O(n)。移動(dòng)構(gòu)造vector則要輕量得多直接把源容器的三個(gè)指針“偷”過來然后把源容器置成空狀態(tài)整個(gè)過程不搬元素復(fù)雜度O(1)。這也是為什么用std::move返回或者傳vector時(shí)移動(dòng)操作比深拷貝快好幾個(gè)量級(jí)。swap兩個(gè)vector更是高效只需要交換各自的三個(gè)指針O(1)完成而且不會(huì)讓任何迭代器失效——因?yàn)樵氐膶?shí)際地址沒有變。這個(gè)特性在實(shí)現(xiàn)異常安全時(shí)很常用也就是所謂的copy-and-swap技巧先拷貝一份新數(shù)據(jù)再和新對(duì)象swap即使拷貝過程中拋異常原對(duì)象也不會(huì)被破壞。手寫一個(gè)簡化版vector光看原理總歸有點(diǎn)虛不如直接動(dòng)手寫一個(gè)能用的MiniVector。這個(gè)版本我會(huì)刻意簡化但保留最核心的機(jī)制裸指針迭代器、按倍數(shù)擴(kuò)容、placement new構(gòu)造、手動(dòng)析構(gòu)、移動(dòng)支持。你完全可以照著代碼自己跑一遍觀察擴(kuò)容行為?；竟羌芘c迭代器設(shè)計(jì)先定義一個(gè)模板類主要成員就是三個(gè)指針。begin返回起始指針end返回末尾指針size和capacity直接指針相減。為了教學(xué)簡單這個(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); };這里沒有寫拷貝構(gòu)造和拷貝賦值實(shí)際項(xiàng)目中必須有否則會(huì)造成雙重釋放或淺拷貝問題。要寫完整的話拷貝構(gòu)造可以復(fù)用reserve push_back完成這里留給你作為練習(xí)。reserve先搬好家再塞新數(shù)據(jù)reserve的核心邏輯很簡單只有當(dāng)請(qǐng)求的容量大于當(dāng)前capacity時(shí)才觸發(fā)reallocate。reallocate負(fù)責(zé)分配一塊新內(nèi)存把舊元素搬到新內(nèi)存再銷毀舊元素、釋放舊內(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è)簡化版沒有處理異常安全。如果某個(gè)元素的移動(dòng)構(gòu)造拋異常新分配的內(nèi)存和已經(jīng)構(gòu)造好的前面那些元素都會(huì)泄漏。標(biāo)準(zhǔn)庫通常做得更嚴(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)化后兩者差距可能被抹平但語義上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)庫行為一致。shrink_to_fit才真正考慮釋放多余空間。如果size為0直接清空所有內(nèi)存然后回歸nullptr否則調(diào)用reallocate(cur_size)重新分配一塊恰好夠用的內(nèi)存。注意shrink_to_fit是一次完整的搬移不是免費(fèi)操作。如果你接下來還要繼續(xù)插入元素這次縮小就是白白浪費(fèi)時(shí)間。destroy_range簡單遍歷指針區(qū)間逐個(gè)調(diào)用析構(gòu)函數(shù)。在析構(gòu)函數(shù)里先銷毀所有有效對(duì)象再釋放整塊堆內(nèi)存順序不能反。template typename T void MiniVectorT::destroy_range(T* first, T* last) { for (T* p first; p ! last; p) { p-~T(); } }測試擴(kuò)容看看內(nèi)部發(fā)生了什么寫個(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ī)制帶來最直接的實(shí)際影響。常見問題與排查技巧手寫一個(gè)玩具版vector之后再回頭看實(shí)際工程里那些問題思路就清晰很多了。這一節(jié)整理幾個(gè)最常見的坑都是我見過的真實(shí)案例有的發(fā)生在別人身上有的發(fā)生在我自己身上。迭代器為什么會(huì)失效怎么避免vector的迭代器失效規(guī)則比list要嚴(yán)格得多。凡是可能觸發(fā)擴(kuò)容的操作比如push_back、insert、reserve、resize都會(huì)讓所有舊迭代器、指針和引用失效因?yàn)樵乇话岬搅诵碌刂?。erase中間的元素會(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ù)測。正確做法是記錄當(dāng)前下標(biāo)按size()循環(huán)或者拷貝出需要的舊數(shù)據(jù)后再插入。頻繁擴(kuò)容的隱形開銷不reserve直接循環(huán)push_back每次翻倍擴(kuò)容都會(huì)做一次“分配新內(nèi)存-搬舊元素-釋放舊內(nèi)存”的完整流程。這個(gè)過程對(duì)大型對(duì)象尤其昂貴因?yàn)榘嵋茖?duì)象本身也有cpu成本。我用一個(gè)簡單的計(jì)時(shí)對(duì)比說明往vector里插入100萬個(gè)整數(shù)不reserve和reserve(1000000)的耗時(shí)差距可能有好幾倍。在時(shí)間敏感的服務(wù)里這種差距會(huì)被放大成線上延遲抖動(dòng)。解決辦法就是在數(shù)據(jù)量可預(yù)估時(shí)提前reserve。不過也不要過度預(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í)代沒有shrink_to_fit流行用vectorT(v).swap(v)來強(qiáng)行減容但這種方式會(huì)多一次完整拷貝?，F(xiàn)代C直接用shrink_to_fit()就好了只是記住這個(gè)請(qǐng)求不一定保證成功標(biāo)準(zhǔn)庫可以選擇忽略。反正它只是一個(gè)性能內(nèi)存權(quán)衡建議別把它當(dāng)成必須生效的命令。vector vs list vs deque該怎么選經(jīng)常有人問既然vector中間插入O(n)是不是用list更好其實(shí)不見得。真實(shí)測試中如果容器里是幾個(gè)字節(jié)的整數(shù)中間插入少量元素時(shí)vector往往比list更快因?yàn)閘ist的節(jié)點(diǎn)分配需要走內(nèi)存分配器而且緩存不友好遍歷代價(jià)高。vector的搬移只是連續(xù)的memcpy級(jí)別的移動(dòng)在CPU層面非常快。容器隨機(jī)訪問頭部插入尾部插入內(nèi)存布局典型場景vectorO(1)O(n)均攤O(1)連續(xù)內(nèi)存讀多寫少、尾部增刪listO(n)O(1)O(1)分散節(jié)點(diǎn)頻繁中間插入且需要迭代器穩(wěn)定dequeO(1)O(1)均攤O(1)分段連續(xù)需要兩端操作但不要求極緊密內(nèi)存實(shí)際工程中的建議是默認(rèn)用vector。只有你能明確說出list比vector更好用的理由時(shí)才換容器。比如你需要大量已知位置的中間插入且元素本身拷貝開銷極大或者你需要保持指向元素的指針/引用長期有效、不被搬移。除此之外vector的緩存友好和底層連續(xù)特性在絕大多數(shù)場景下都更劃算。自定義類型帶來的幾個(gè)坑自定義類型作為vector元素時(shí)要考慮默認(rèn)構(gòu)造、拷貝構(gòu)造、移動(dòng)構(gòu)造和析構(gòu)是否都可用。resize變大時(shí)要默認(rèn)構(gòu)造新元素如果類沒有默認(rèn)構(gòu)造函數(shù)編譯直接報(bào)錯(cuò)。push_back和insert隨時(shí)可能拷貝或移動(dòng)元素如果類沒有拷貝構(gòu)造函數(shù)或移動(dòng)構(gòu)造函數(shù)很多vector操作沒法用。如果類的拷貝代價(jià)很高每次擴(kuò)容就成了性能災(zāi)難所以實(shí)踐中建議在類里實(shí)現(xiàn)高效的移動(dòng)構(gòu)造函數(shù)并且標(biāo)記noexcept這樣vector擴(kuò)容時(shí)會(huì)優(yōu)先移動(dòng)而不是拷貝。還有一個(gè)容易被忽略的問題是如果元素類型含有裸指針且拷貝是淺拷貝vector的自動(dòng)搬移會(huì)導(dǎo)致多個(gè)對(duì)象指向同一塊內(nèi)存析構(gòu)時(shí)造成double free。這種情況下必須先實(shí)現(xiàn)正確的拷貝語義或者把裸指針換成shared_ptr這類智能指針。vector本身不會(huì)幫你解決所有權(quán)問題它只是忠實(shí)地拷貝你寫好的類行為。寫在最后幾個(gè)我踩過的坑我自己在前些年做一個(gè)后臺(tái)服務(wù)時(shí)遇到過一段非常隱蔽的問題某個(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夠再說。還有一次我在一個(gè)內(nèi)存緊張的環(huán)境里頻繁創(chuàng)建銷毀一個(gè)容量很大的vector每次創(chuàng)建都要分配和釋放大塊內(nèi)存導(dǎo)致內(nèi)存碎片越來越嚴(yán)重。后來改成用一個(gè)長期復(fù)用、預(yù)留固定容量的vector對(duì)象池才把波動(dòng)壓下去。底層實(shí)現(xiàn)這東西平時(shí)寫業(yè)務(wù)不深究也能活但一旦線上出問題理解底層機(jī)制能讓你少走很多彎路。希望這篇學(xué)習(xí)總結(jié)對(duì)你也有用。 std::vector底層實(shí)現(xiàn)：動(dòng)態(tài)數(shù)組原理、擴(kuò)容策略與迭代器失效機(jī)制
前兩天有朋友給我發(fā)消息說自己在看一個(gè)項(xiàng)目叫vectore底層實(shí)現(xiàn)基礎(chǔ)學(xué)習(xí)問我怎么理解。我當(dāng)時(shí)下意識(shí)就說你拼錯(cuò)了應(yīng)該是vector——C標(biāo)準(zhǔn)庫里最常用的容器。這個(gè)話題其實(shí)挺有意思的vector每個(gè)人都在用但真要把它底層那點(diǎn)事兒說清楚很多人都會(huì)卡殼。這篇文章是我個(gè)人對(duì)std::vector底層實(shí)現(xiàn)的學(xué)習(xí)總結(jié)核心圍繞動(dòng)態(tài)數(shù)組的內(nèi)存模型、擴(kuò)容策略、對(duì)象生命周期和迭代器行為展開最后還會(huì)帶手寫一個(gè)簡化版vector的完整過程。適合已經(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)增長都是代碼層面的主動(dòng)管理沒有什么魔法。為什么需要vector數(shù)組與鏈表的痛點(diǎn)原生數(shù)組很直接在棧上或堆上開一塊連續(xù)內(nèi)存按下標(biāo)訪問是O(1)但大小一旦定下來就沒法變。你開一個(gè)int arr[1024]想塞1025個(gè)元素就溢出或者崩潰想縮到512個(gè)元素空間又白白浪費(fèi)。鏈表倒是能動(dòng)態(tài)增刪每個(gè)節(jié)點(diǎn)在堆上獨(dú)立分配往已知位置插入刪除是O(1)但隨機(jī)訪問必須從頭遍歷而且節(jié)點(diǎn)之間在內(nèi)存里不連續(xù)緩存命中率很差。vector正是在這兩個(gè)痛點(diǎn)之間找平衡它像數(shù)組一樣用連續(xù)內(nèi)存支持O(1)隨機(jī)訪問同時(shí)像鏈表一樣支持動(dòng)態(tài)增長在尾部插入刪除的均攤復(fù)雜度是O(1)。這決定了它的核心場景大量按下標(biāo)遍歷、讀取操作集中在尾部。反過來如果你頻繁在中間插入刪除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)開始和結(jié)束兩個(gè)指針劃出一段有真實(shí)對(duì)象的區(qū)域第三個(gè)指針劃出整段擁有所有權(quán)的內(nèi)存區(qū)域。為什么不用起始地址元素個(gè)數(shù)容量來記錄因?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)勢是緩存友好。CPU在加載數(shù)據(jù)時(shí)不是一個(gè)個(gè)字節(jié)讀的而是按緩存行去取一次可能拿走64字節(jié)。你遍歷vector時(shí)arr[0]被加載arr[1]、arr[2]很可能也跟著進(jìn)了緩存后續(xù)訪問幾乎是直接命中。而鏈表節(jié)點(diǎn)在堆上東一個(gè)西一個(gè)訪問一個(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不是萬能容器它是一個(gè)在隨機(jī)訪問、尾部增刪、緩存局部性這些指標(biāo)上優(yōu)化得很極端的容器。核心細(xì)節(jié)內(nèi)存分配、擴(kuò)容與對(duì)象生命周期理解了三個(gè)指針之后還得搞懂vector內(nèi)部怎么管理對(duì)象的“生老病死”。這塊如果不清楚寫代碼時(shí)很容易被迭代器失效和莫名其妙的內(nèi)存問題坑到。reserve和resize到底改了什么日常開發(fā)里這兩個(gè)方法經(jīng)常被混淆。簡單記憶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就直接銷毀尾部多余元素但不會(huì)把capacity降下來。這里有一個(gè)實(shí)際工程中的常見誤區(qū)很多人以為調(diào)用resize(n)之后容量也會(huì)變小其實(shí)不會(huì)。它只改變有效元素個(gè)數(shù)分配的內(nè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í)別的拷貝操作完全沒法用。所以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)。這跟你去飯店吃飯加桌子一樣如果每來一個(gè)客人就換一張更大的桌子遲早累死不如一次性預(yù)留夠未來一段時(shí)間的位置。具體乘多少倍C標(biāo)準(zhǔn)沒有強(qiáng)制規(guī)定不同標(biāo)準(zhǔn)庫實(shí)現(xiàn)不同。2倍是比較常見的舊實(shí)現(xiàn)理由是擴(kuò)容次數(shù)少1.5倍的內(nèi)存浪費(fèi)更少且能更好地復(fù)用被釋放的舊內(nèi)存塊。不管用哪個(gè)倍數(shù)擴(kuò)容都意味著元素被搬到了新內(nèi)存地址所以所有指向舊容量的迭代器、指針和引用會(huì)全部失效。這一點(diǎn)是vector使用中最容易踩的坑后面會(huì)專門說。元素的構(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í)還沒有被使用不需要構(gòu)造。vector把原始內(nèi)存分配和對(duì)象生命周期分開了分配內(nèi)存通過分配器或者::operator new拿到一塊沒有對(duì)象的原始內(nèi)存構(gòu)造對(duì)象在需要放元素的時(shí)候通過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í)間在無意義的默認(rèn)構(gòu)造上。拷貝、移動(dòng)與swap的底層行為拷貝構(gòu)造vector時(shí)需要為新容器分配一塊獨(dú)立內(nèi)存然后把源容器里的每個(gè)元素逐個(gè)拷貝過去整體復(fù)雜度O(n)。移動(dòng)構(gòu)造vector則要輕量得多直接把源容器的三個(gè)指針“偷”過來然后把源容器置成空狀態(tài)整個(gè)過程不搬元素復(fù)雜度O(1)。這也是為什么用std::move返回或者傳vector時(shí)移動(dòng)操作比深拷貝快好幾個(gè)量級(jí)。swap兩個(gè)vector更是高效只需要交換各自的三個(gè)指針O(1)完成而且不會(huì)讓任何迭代器失效——因?yàn)樵氐膶?shí)際地址沒有變。這個(gè)特性在實(shí)現(xiàn)異常安全時(shí)很常用也就是所謂的copy-and-swap技巧先拷貝一份新數(shù)據(jù)再和新對(duì)象swap即使拷貝過程中拋異常原對(duì)象也不會(huì)被破壞。手寫一個(gè)簡化版vector光看原理總歸有點(diǎn)虛不如直接動(dòng)手寫一個(gè)能用的MiniVector。這個(gè)版本我會(huì)刻意簡化但保留最核心的機(jī)制裸指針迭代器、按倍數(shù)擴(kuò)容、placement new構(gòu)造、手動(dòng)析構(gòu)、移動(dòng)支持。你完全可以照著代碼自己跑一遍觀察擴(kuò)容行為?；竟羌芘c迭代器設(shè)計(jì)先定義一個(gè)模板類主要成員就是三個(gè)指針。begin返回起始指針end返回末尾指針size和capacity直接指針相減。為了教學(xué)簡單這個(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); };這里沒有寫拷貝構(gòu)造和拷貝賦值實(shí)際項(xiàng)目中必須有否則會(huì)造成雙重釋放或淺拷貝問題。要寫完整的話拷貝構(gòu)造可以復(fù)用reserve push_back完成這里留給你作為練習(xí)。reserve先搬好家再塞新數(shù)據(jù)reserve的核心邏輯很簡單只有當(dāng)請(qǐng)求的容量大于當(dāng)前capacity時(shí)才觸發(fā)reallocate。reallocate負(fù)責(zé)分配一塊新內(nèi)存把舊元素搬到新內(nèi)存再銷毀舊元素、釋放舊內(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è)簡化版沒有處理異常安全。如果某個(gè)元素的移動(dòng)構(gòu)造拋異常新分配的內(nèi)存和已經(jīng)構(gòu)造好的前面那些元素都會(huì)泄漏。標(biāo)準(zhǔn)庫通常做得更嚴(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)化后兩者差距可能被抹平但語義上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)庫行為一致。shrink_to_fit才真正考慮釋放多余空間。如果size為0直接清空所有內(nèi)存然后回歸nullptr否則調(diào)用reallocate(cur_size)重新分配一塊恰好夠用的內(nèi)存。注意shrink_to_fit是一次完整的搬移不是免費(fèi)操作。如果你接下來還要繼續(xù)插入元素這次縮小就是白白浪費(fèi)時(shí)間。destroy_range簡單遍歷指針區(qū)間逐個(gè)調(diào)用析構(gòu)函數(shù)。在析構(gòu)函數(shù)里先銷毀所有有效對(duì)象再釋放整塊堆內(nèi)存順序不能反。template typename T void MiniVectorT::destroy_range(T* first, T* last) { for (T* p first; p ! last; p) { p-~T(); } }測試擴(kuò)容看看內(nèi)部發(fā)生了什么寫個(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ī)制帶來最直接的實(shí)際影響。常見問題與排查技巧手寫一個(gè)玩具版vector之后再回頭看實(shí)際工程里那些問題思路就清晰很多了。這一節(jié)整理幾個(gè)最常見的坑都是我見過的真實(shí)案例有的發(fā)生在別人身上有的發(fā)生在我自己身上。迭代器為什么會(huì)失效怎么避免vector的迭代器失效規(guī)則比list要嚴(yán)格得多。凡是可能觸發(fā)擴(kuò)容的操作比如push_back、insert、reserve、resize都會(huì)讓所有舊迭代器、指針和引用失效因?yàn)樵乇话岬搅诵碌刂?。erase中間的元素會(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ù)測。正確做法是記錄當(dāng)前下標(biāo)按size()循環(huán)或者拷貝出需要的舊數(shù)據(jù)后再插入。頻繁擴(kuò)容的隱形開銷不reserve直接循環(huán)push_back每次翻倍擴(kuò)容都會(huì)做一次“分配新內(nèi)存-搬舊元素-釋放舊內(nèi)存”的完整流程。這個(gè)過程對(duì)大型對(duì)象尤其昂貴因?yàn)榘嵋茖?duì)象本身也有cpu成本。我用一個(gè)簡單的計(jì)時(shí)對(duì)比說明往vector里插入100萬個(gè)整數(shù)不reserve和reserve(1000000)的耗時(shí)差距可能有好幾倍。在時(shí)間敏感的服務(wù)里這種差距會(huì)被放大成線上延遲抖動(dòng)。解決辦法就是在數(shù)據(jù)量可預(yù)估時(shí)提前reserve。不過也不要過度預(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í)代沒有shrink_to_fit流行用vectorT(v).swap(v)來強(qiáng)行減容但這種方式會(huì)多一次完整拷貝?，F(xiàn)代C直接用shrink_to_fit()就好了只是記住這個(gè)請(qǐng)求不一定保證成功標(biāo)準(zhǔn)庫可以選擇忽略。反正它只是一個(gè)性能內(nèi)存權(quán)衡建議別把它當(dāng)成必須生效的命令。vector vs list vs deque該怎么選經(jīng)常有人問既然vector中間插入O(n)是不是用list更好其實(shí)不見得。真實(shí)測試中如果容器里是幾個(gè)字節(jié)的整數(shù)中間插入少量元素時(shí)vector往往比list更快因?yàn)閘ist的節(jié)點(diǎn)分配需要走內(nèi)存分配器而且緩存不友好遍歷代價(jià)高。vector的搬移只是連續(xù)的memcpy級(jí)別的移動(dòng)在CPU層面非常快。容器隨機(jī)訪問頭部插入尾部插入內(nèi)存布局典型場景vectorO(1)O(n)均攤O(1)連續(xù)內(nèi)存讀多寫少、尾部增刪listO(n)O(1)O(1)分散節(jié)點(diǎn)頻繁中間插入且需要迭代器穩(wěn)定dequeO(1)O(1)均攤O(1)分段連續(xù)需要兩端操作但不要求極緊密內(nèi)存實(shí)際工程中的建議是默認(rèn)用vector。只有你能明確說出list比vector更好用的理由時(shí)才換容器。比如你需要大量已知位置的中間插入且元素本身拷貝開銷極大或者你需要保持指向元素的指針/引用長期有效、不被搬移。除此之外vector的緩存友好和底層連續(xù)特性在絕大多數(shù)場景下都更劃算。自定義類型帶來的幾個(gè)坑自定義類型作為vector元素時(shí)要考慮默認(rèn)構(gòu)造、拷貝構(gòu)造、移動(dòng)構(gòu)造和析構(gòu)是否都可用。resize變大時(shí)要默認(rèn)構(gòu)造新元素如果類沒有默認(rèn)構(gòu)造函數(shù)編譯直接報(bào)錯(cuò)。push_back和insert隨時(shí)可能拷貝或移動(dòng)元素如果類沒有拷貝構(gòu)造函數(shù)或移動(dòng)構(gòu)造函數(shù)很多vector操作沒法用。如果類的拷貝代價(jià)很高每次擴(kuò)容就成了性能災(zāi)難所以實(shí)踐中建議在類里實(shí)現(xiàn)高效的移動(dòng)構(gòu)造函數(shù)并且標(biāo)記noexcept這樣vector擴(kuò)容時(shí)會(huì)優(yōu)先移動(dòng)而不是拷貝。還有一個(gè)容易被忽略的問題是如果元素類型含有裸指針且拷貝是淺拷貝vector的自動(dòng)搬移會(huì)導(dǎo)致多個(gè)對(duì)象指向同一塊內(nèi)存析構(gòu)時(shí)造成double free。這種情況下必須先實(shí)現(xiàn)正確的拷貝語義或者把裸指針換成shared_ptr這類智能指針。vector本身不會(huì)幫你解決所有權(quán)問題它只是忠實(shí)地拷貝你寫好的類行為。寫在最后幾個(gè)我踩過的坑我自己在前些年做一個(gè)后臺(tái)服務(wù)時(shí)遇到過一段非常隱蔽的問題某個(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夠再說。還有一次我在一個(gè)內(nèi)存緊張的環(huán)境里頻繁創(chuàng)建銷毀一個(gè)容量很大的vector每次創(chuàng)建都要分配和釋放大塊內(nèi)存導(dǎo)致內(nèi)存碎片越來越嚴(yán)重。后來改成用一個(gè)長期復(fù)用、預(yù)留固定容量的vector對(duì)象池才把波動(dòng)壓下去。底層實(shí)現(xiàn)這東西平時(shí)寫業(yè)務(wù)不深究也能活但一旦線上出問題理解底層機(jī)制能讓你少走很多彎路。希望這篇學(xué)習(xí)總結(jié)對(duì)你也有用。