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