最近去參加了拼多多的C++ 面試，真可謂是一場充滿挑戰(zhàn)的技術(shù)大考驗！面試過程中，面試官突然拋出一個讓我心跳加速的問題：“請手撕 std::vector?！?這就好比在戰(zhàn)場上，敵人突然給你來個措手不及的襲擊 。

當(dāng)時聽到這個題目，心里既緊張又興奮。緊張是因為現(xiàn)場手撕代碼本就壓力巨大，稍有不慎就可能出錯；興奮則是因為這是一個展示自己技術(shù)實力的好機會。std::vector 作為 C++ 標(biāo)準(zhǔn)庫中極為重要的容器，在日常開發(fā)里使用頻率超高，可真要在面試時現(xiàn)場實現(xiàn)它，還得把每個細(xì)節(jié)都處理好，那難度著實不小。

這個要求不僅考查對 C++ 語言特性的掌握程度，比如模板、內(nèi)存管理等，還檢驗對數(shù)據(jù)結(jié)構(gòu)和算法的理解。可以說，這道題就像一面鏡子，能清晰映照出面試者的技術(shù)功底是否扎實。 接下來，我就和大家詳細(xì)分享一下 std::vector 的實現(xiàn)思路以及其中涉及的關(guān)鍵知識點。

Part1.std::vector 基礎(chǔ)認(rèn)知

1.1定義與功能簡述

std::vector 是 C++ 標(biāo)準(zhǔn)庫中的一個強大工具，它是一個模板類，定義在<vector>頭文件中 ，就像是一個智能的動態(tài)數(shù)組容器。說它智能，是因為它能夠在運行時根據(jù)你的需求，自動調(diào)整自身的大小。這就好比你有一個神奇的背包，一開始它可能是空的，容量也不大，但隨著你不斷往里面裝東西，它能自動變大，來容納更多物品，而且還會幫你管理好這些物品在內(nèi)存中的存儲。

從底層實現(xiàn)來看，std::vector 在內(nèi)存中維護(hù)著一塊連續(xù)的存儲空間，這使得它在訪問元素時有著極高的效率。你可以把它想象成一排緊密相連的小房間，每個房間都存放著一個元素，只要知道房間號（也就是元素的索引），就能瞬間找到對應(yīng)的元素 。比如有個std::vector<int> numbers，當(dāng)你想獲取第三個元素時，只需numbers[2]就能快速訪問到，這和傳統(tǒng)數(shù)組的訪問方式類似，但又比傳統(tǒng)數(shù)組多了動態(tài)管理大小的功能。

1.2在 C++ 編程中的廣泛應(yīng)用場景

在數(shù)據(jù)處理領(lǐng)域，當(dāng)你讀取一組數(shù)據(jù)，而這組數(shù)據(jù)的數(shù)量事先并不確定時，std::vector 就派上大用場了。例如，從文件中讀取一系列整數(shù)，你無需預(yù)先知道文件里到底有多少個整數(shù)，直接用std::vector<int>來存儲，它會自動根據(jù)讀取的數(shù)據(jù)量進(jìn)行擴展。像下面這樣：

#include <iostream>
#include <vector>
#include <fstream>

int main() {
    std::vector<int> data;
    std::ifstream file("data.txt");
    int num;
    while (file >> num) {
        data.push_back(num);
    }
    // 后續(xù)可以對data進(jìn)行各種處理
    return 0;
}

在算法實現(xiàn)方面，許多算法都依賴于能夠動態(tài)調(diào)整大小的數(shù)據(jù)結(jié)構(gòu)。以排序算法為例，假設(shè)你要對一組動態(tài)生成的數(shù)字進(jìn)行排序，使用std::vector來存儲這些數(shù)字，然后調(diào)用標(biāo)準(zhǔn)庫中的排序算法std::sort，就能輕松完成排序操作 ：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};
    std::sort(numbers.begin(), numbers.end());
    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

再比如在實現(xiàn)圖算法時，圖的節(jié)點和邊的數(shù)量往往是不確定的，std::vector可以用來存儲圖的鄰接表等數(shù)據(jù)結(jié)構(gòu)，方便進(jìn)行圖的遍歷、最短路徑計算等操作?？梢哉f，在 C++ 編程的世界里，std::vector 就像一把萬能鑰匙，打開了許多復(fù)雜問題的解決之門。

Part2.手撕std::vector全過程

2.1關(guān)鍵接口實現(xiàn)

(1)push_back

實現(xiàn)思路：當(dāng)調(diào)用push_back向std::vector中添加元素時，首先要檢查當(dāng)前vector的容量（capacity）是否足夠。這就好比你有一個杯子，要往里倒水，得先看看杯子還有沒有空間。如果容量不足，就需要進(jìn)行擴容操作 。

擴容操作：通常情況下，std::vector會以原大小的兩倍重新分配一塊新的內(nèi)存空間。這是因為如果每次只增加一點點空間，可能會導(dǎo)致頻繁的內(nèi)存分配和拷貝，效率很低。而翻倍擴容可以減少這種開銷。比如原來vector的容量是 4，當(dāng)要添加第 5 個元素時，就會分配一塊容量為 8 的新內(nèi)存 。

拷貝元素與釋放舊空間：分配好新內(nèi)存后，要把原來vector中的元素逐個拷貝到新的內(nèi)存空間中，這就像把舊杯子里的水小心翼翼地倒入新杯子。完成拷貝后，舊的內(nèi)存空間就不再需要了，需要將其釋放，避免內(nèi)存泄漏 。

插入新元素：最后，把要添加的新元素放入新內(nèi)存空間的末尾。例如，有個std::vector<int> v，執(zhí)行v.push_back(10)，如果此時容量足夠，直接在末尾插入 10；如果容量不足，經(jīng)過上述擴容等操作后，將 10 插入到新內(nèi)存空間的末尾 。

(2)pop_back

刪除最后一個元素：pop_back的作用是刪除std::vector中的最后一個元素。它的實現(xiàn)邏輯相對簡單，直接將vector的大?。╯ize）減 1 即可。這就好比你有一排擺放整齊的物品，把最后一個物品拿走，那么這排物品的數(shù)量就減少了 1 。

釋放內(nèi)存空間：需要注意的是，雖然pop_back減少了元素數(shù)量，但vector占用的內(nèi)存空間并不會立即釋放。這是因為如果頻繁釋放內(nèi)存，后續(xù)又可能需要重新分配，會增加開銷。例如，std::vector<int> v = {1, 2, 3, 4, 5}，執(zhí)行v.pop_back()后，v的大小變?yōu)?4，最后一個元素 5 被 “刪除”，但內(nèi)存中仍然保留著原來為 5 分配的空間，以備后續(xù)添加元素使用 。

(3)operator[]

重載運算符實現(xiàn)元素訪問：operator[]的作用是讓std::vector能夠像數(shù)組一樣通過下標(biāo)來訪問元素。通過重載這個運算符，我們可以實現(xiàn)高效的隨機訪問。它的實現(xiàn)很直觀，就是返回指定下標(biāo)位置的元素的引用。例如，有個std::vector<int> v = {10, 20, 30}，當(dāng)執(zhí)行int num = v[1]時，operator[]會返回v中第二個元素（下標(biāo)從 0 開始）的引用，也就是 20，這樣num就被賦值為 20 。

邊界檢查（可選）：在實際實現(xiàn)中，標(biāo)準(zhǔn)庫的std::vector的operator[]并不進(jìn)行邊界檢查，這是為了提高效率。但如果我們自己實現(xiàn)，也可以考慮添加邊界檢查，當(dāng)訪問的下標(biāo)超出vector的大小時，拋出異?；蛘叻祷匾粋€默認(rèn)值，以增強程序的健壯性 。

2.2內(nèi)存管理機制剖析

(1)動態(tài)擴容策略

原理：當(dāng)std::vector的容量不足以容納新元素時，就會觸發(fā)動態(tài)擴容。前面提到，一般會以原容量的兩倍來分配新的內(nèi)存空間 。

示例：假設(shè)有一個初始std::vector<int> v，初始容量為 0，當(dāng)?shù)谝淮螆?zhí)行v.push_back(1)時，會分配一塊能容納 1 個元素的內(nèi)存。當(dāng)執(zhí)行v.push_back(2)時，發(fā)現(xiàn)容量不足，就會重新分配一塊能容納 2 個元素的內(nèi)存，把 1 拷貝到新內(nèi)存，再把 2 放入新內(nèi)存 。當(dāng)繼續(xù)執(zhí)行v.push_back(3)時，又會觸發(fā)擴容，分配一塊能容納 4 個元素的內(nèi)存，將 1 和 2 拷貝過去，再放入 3 。

優(yōu)點：這種翻倍擴容的策略有效地減少了內(nèi)存分配的次數(shù)，因為每次擴容后的容量都能滿足后續(xù)多次添加元素的需求，避免了頻繁的小幅度擴容帶來的開銷 。

(2)內(nèi)存釋放策略

特點：std::vector的內(nèi)存占用只增不減，即使通過pop_back刪除元素，或者調(diào)用clear清空所有元素，其占用的內(nèi)存空間也不會自動釋放 。這是因為考慮到后續(xù)可能還會添加元素，如果頻繁釋放和重新分配內(nèi)存，會降低性能。

swap 技巧釋放內(nèi)存：不過，我們可以利用swap技巧來釋放多余的內(nèi)存。具體做法是創(chuàng)建一個臨時的std::vector，然后將當(dāng)前vector與臨時vector進(jìn)行swap操作。例如：

#include <iostream>
#include <vector>

void releaseExtraMemory(std::vector<int>& v) {
    std::vector<int>().swap(v);
}

int main() {
    std::vector<int> v;
    for (int i = 0; i < 100; i++) {
        v.push_back(i);
    }
    // 假設(shè)現(xiàn)在不需要這么多空間了
    releaseExtraMemory(v);
    std::cout << "Capacity after release: " << v.capacity() << std::endl;
    return 0;
}

在這個例子中，std::vector<int>()創(chuàng)建了一個臨時的空vector，它的容量通常為 0。通過swap操作，當(dāng)前v的內(nèi)存與臨時vector的內(nèi)存進(jìn)行了交換，這樣v就擁有了臨時vector的小容量（通常為 0），從而釋放了原來占用的大量內(nèi)存，而臨時vector則擁有了原來v的大內(nèi)存，但由于它是臨時的，在離開作用域時會自動銷毀，其占用的內(nèi)存也會被釋放 。

2.3迭代器相關(guān)實現(xiàn)要點

(1)迭代器的作用和原理

作用：迭代器就像是一個 “指針”，用于遍歷std::vector中的元素。它提供了一種統(tǒng)一的方式來訪問容器中的元素，不管容器內(nèi)部是如何存儲的 。使用迭代器，我們可以方便地進(jìn)行元素的遍歷、查找、修改等操作。例如，通過迭代器可以實現(xiàn)對std::vector中所有元素的累加：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    int sum = 0;
    for (auto it = v.begin(); it != v.end(); ++it) {
        sum += *it;
    }
    std::cout << "Sum: " << sum << std::endl;
    return 0;
}

原理：std::vector的迭代器本質(zhì)上是基于指針實現(xiàn)的。它可以指向vector中的某個元素，通過對迭代器進(jìn)行自增（++）操作，可以使其指向下一個元素，就像指針在內(nèi)存中移動一樣 。而且，由于std::vector的元素在內(nèi)存中是連續(xù)存儲的，這種基于指針的迭代器能夠高效地遍歷元素 。

(2)迭代器失效場景及應(yīng)對

插入元素導(dǎo)致迭代器失效：當(dāng)在std::vector中插入元素時，如果插入操作導(dǎo)致了擴容，那么原來的所有迭代器都會失效。這是因為擴容后元素被拷貝到了新的內(nèi)存空間，原來指向舊內(nèi)存空間的迭代器就不再有效了。例如：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    auto it = v.begin();
    v.push_back(4); // 可能觸發(fā)擴容
    if (it != v.end()) {
        std::cout << "Element: " << *it << std::endl; // 這里it可能失效，導(dǎo)致未定義行為
    }
    return 0;
}

刪除元素導(dǎo)致迭代器失效：從std::vector中刪除元素時，指向被刪除元素及其之后元素的迭代器都會失效。因為刪除元素后，后面的元素會向前移動，迭代器指向的位置就不再對應(yīng)原來的元素了 。例如：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = v.begin();
    v.erase(it); // 刪除第一個元素
    while (it != v.end()) {
        std::cout << *it << " "; // 這里it已失效，會導(dǎo)致未定義行為
        ++it;
    }
    return 0;
}

應(yīng)對方法：為了避免迭代器失效帶來的問題，在進(jìn)行可能導(dǎo)致迭代器失效的操作后，要重新獲取迭代器。比如在插入或刪除元素后，使用操作返回的新迭代器來繼續(xù)操作 。例如：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = v.begin();
    it = v.erase(it); // 獲取刪除元素后的新迭代器
    while (it != v.end()) {
        std::cout << *it << " ";
        ++it;
    }
    return 0;
}

在這個例子中，erase操作返回了指向被刪除元素下一個元素的迭代器，我們用it接收這個新迭代器，從而避免了迭代器失效的問題 。

Part3.std::vector 源碼深度解讀

3.1關(guān)鍵數(shù)據(jù)結(jié)構(gòu)與成員變量

⑴_Vector_base 基類結(jié)構(gòu)

在深入剖析std::vector時，不能忽視其背后的_Vector_base基類。從繼承關(guān)系上看，std::vector通過保護(hù)繼承_Vector_base來獲取底層的內(nèi)存管理等功能。在實際代碼中，_Vector_base主要負(fù)責(zé)內(nèi)存的分配與釋放等關(guān)鍵操作 。例如，當(dāng)std::vector需要擴容時，會調(diào)用_Vector_base中定義的內(nèi)存分配函數(shù)。

在 GCC 的std::vector實現(xiàn)中，_Vector_base中定義了_M_allocate和_M_deallocate函數(shù)，分別用于分配和釋放內(nèi)存 。當(dāng)std::vector的容量不足時，就會通過_M_allocate函數(shù)來分配新的內(nèi)存空間，這確保了std::vector能夠靈活地管理內(nèi)存，滿足動態(tài)存儲元素的需求 。

⑵_Vector_impl_data 結(jié)構(gòu)體

• _Vector_impl_data結(jié)構(gòu)體在std::vector的內(nèi)存管理中扮演著重要角色，它包含了三個關(guān)鍵指針：_M_start、_M_finish和_M_end_of_storage 。_M_start指針指向當(dāng)前已分配內(nèi)存塊的第一個元素，就像指向一排房子的第一間 。_M_finish指針指向最后一個元素的下一個位置，它標(biāo)記了當(dāng)前已使用內(nèi)存的邊界，比如一排房子中住了人的最后一間的下一間 。_M_end_of_storage指針則指向整個已分配內(nèi)存的末尾，也就是這排房子的最后一間 。
• 這三個指針相互配合，精確地管理著內(nèi)存和元素。通過它們，可以輕松地獲取std::vector的大?。╛M_finish - _M_start）和容量（_M_end_of_storage - _M_start） 。當(dāng)需要添加新元素時，通過比較_M_finish和_M_end_of_storage，就能判斷是否需要擴容 。如果_M_finish等于_M_end_of_storage，就意味著當(dāng)前內(nèi)存已滿，需要進(jìn)行擴容操作 。

3.2重要成員函數(shù)源碼解析

⑴insert_aux 函數(shù)

insert_aux函數(shù)是std::vector中處理插入元素的關(guān)鍵函數(shù)，其實現(xiàn)邏輯相當(dāng)復(fù)雜且精妙 。當(dāng)調(diào)用insert_aux插入元素時，首先要判斷當(dāng)前std::vector的容量是否足夠 。如果容量不足，就需要進(jìn)行擴容操作 。在擴容時，會以原容量的兩倍（通常情況）重新分配一塊新的內(nèi)存空間 。例如，假設(shè)原std::vector的容量為 4，當(dāng)要插入新元素且容量不足時，會分配一塊容量為 8 的新內(nèi)存 。

接著，要進(jìn)行元素的拷貝操作 。從插入位置開始，將原std::vector中插入位置及之后的元素依次拷貝到新內(nèi)存中相應(yīng)的位置 。這就好比將書架上從某一格開始的書，依次搬到新書架的對應(yīng)位置 。然后，將新元素插入到指定位置 。完成插入和拷貝后，還需要更新_M_start、_M_finish和_M_end_of_storage這三個指針，以反映內(nèi)存和元素的變化 。同時，由于插入操作可能會改變元素的位置，所有指向插入位置及之后元素的迭代器都會失效，需要重新獲取有效的迭代器 。

⑵erase 函數(shù)

erase函數(shù)用于刪除std::vector中的元素，它的實現(xiàn)主要涉及內(nèi)存調(diào)整和迭代器更新 。當(dāng)調(diào)用erase刪除指定位置的元素時，首先將刪除位置之后的元素依次向前移動一個位置，以填補被刪除元素留下的空缺 。例如，有個std::vector<int> v = {1, 2, 3, 4, 5}，當(dāng)執(zhí)行v.erase(v.begin() + 2)刪除第三個元素 3 時，后面的 4 和 5 會向前移動，變成{1, 2, 4, 5} 。

移動元素后，_M_finish 指針需要向前移動一個位置，以反映當(dāng)前 std::vector 的實際大小 。同時，指向被刪除元素及其之后元素的迭代器都會失效 。為了避免使用失效的迭代器導(dǎo)致未定義行為，在調(diào)用erase后，需要重新獲取有效的迭代器 。比如，可以使用erase 函數(shù)返回的迭代器，它指向被刪除元素的下一個元素，以此來繼續(xù)后續(xù)的操作 。

Part4.面試應(yīng)對技巧與總結(jié)

4.1面試官考察意圖剖析

面試官出 “手撕 std::vector” 這道題，有著多方面的考察意圖。首先，是想檢驗面試者對 C++ 標(biāo)準(zhǔn)庫的理解程度。std::vector 作為 C++ 標(biāo)準(zhǔn)庫的重要組成部分，對它的深入理解，能反映出面試者對整個標(biāo)準(zhǔn)庫體系的掌握情況 。就像如果把 C++ 標(biāo)準(zhǔn)庫比作一座大廈，std::vector 就是大廈中一間關(guān)鍵的房間，了解這個房間的構(gòu)造和功能，有助于理解整座大廈的布局 。

其次，這道題能考察面試者的編程能力。現(xiàn)場實現(xiàn) std::vector，需要面試者熟練運用 C++ 語言特性，如模板、內(nèi)存管理等知識，并且能夠?qū)⑦@些知識有機地結(jié)合起來，編寫出正確、高效的代碼 。這就如同廚師需要熟練運用各種食材和烹飪技巧，做出美味的菜肴一樣，面試者要熟練運用語言特性做出 “合格的代碼菜肴” 。

再者，面試官通過這道題來考察面試者的問題解決能力。在實現(xiàn)過程中，必然會遇到各種問題，比如內(nèi)存分配失敗的處理、迭代器失效的解決等。面試者如何分析這些問題，找到解決方案，體現(xiàn)了其思維的邏輯性和靈活性 。這就好比在迷宮中尋找出口，面對各種岔路和障礙，能否找到正確的路徑，展現(xiàn)出面試者解決問題的能力 。

4.2回答該問題的要點與技巧

回答這個問題時，清晰闡述思路至關(guān)重要。在開始編碼前，先向面試官講解實現(xiàn) std::vector 的整體流程，比如先介紹數(shù)據(jù)結(jié)構(gòu)的設(shè)計，包括成員變量的定義和作用，再說明各個接口的實現(xiàn)思路，像push_back如何實現(xiàn)擴容、erase如何處理元素移動等 。就像建造房屋前先展示設(shè)計藍(lán)圖，讓面試官清楚了解你的 “建造計劃” 。

在實現(xiàn)過程中，要特別注意細(xì)節(jié)。例如，在進(jìn)行內(nèi)存分配時，要考慮分配失敗的情況，進(jìn)行適當(dāng)?shù)腻e誤處理；在操作迭代器時，要時刻關(guān)注迭代器失效的問題，并加以處理 。這些細(xì)節(jié)就像房屋建造中的小零件，雖然微小，但卻關(guān)乎整個 “房屋”（代碼）的穩(wěn)定性和正確性 。

同時，要思考如何優(yōu)化實現(xiàn)。比如在擴容時，選擇合適的擴容因子，以減少內(nèi)存分配和拷貝的次數(shù)；在實現(xiàn)某些接口時，采用更高效的算法 。這就好比在房屋建造中，選擇更優(yōu)質(zhì)的材料和更合理的施工工藝，讓房屋更加堅固、美觀（代碼更加高效、健壯） 。

4.3對后續(xù)面試者的建議

對于后續(xù)準(zhǔn)備面試的小伙伴們，一定要深入學(xué)習(xí) C++ 知識。不僅要掌握 std::vector 這樣的標(biāo)準(zhǔn)庫容器，還要理解其背后的原理和設(shè)計思想 ?？梢酝ㄟ^閱讀相關(guān)書籍，如《C++ Primer》《Effective C++》等，深入鉆研 C++ 的語言特性和編程技巧 。

多做練習(xí)也是必不可少的?？梢栽?LeetCode、?？途W(wǎng)等在線平臺上，尋找與 C++ 編程相關(guān)的題目進(jìn)行練習(xí)，尤其是關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的題目，通過實踐來提高自己的編程能力 。這就像運動員通過大量的訓(xùn)練來提高自己的競技水平一樣，面試者要通過大量練習(xí)來提升編程水平 。

此外，要善于總結(jié)面試經(jīng)驗。每一次面試都是一次寶貴的學(xué)習(xí)機會，面試后要回顧自己的表現(xiàn)，分析回答得好的地方和存在的不足，不斷改進(jìn) 。如果在面試中被問到某個問題回答得不好，面試后就去深入研究這個問題，確保下次遇到類似問題能夠應(yīng)對自如 。