C++ vector從入門到模擬實(shí)現(xiàn)過程

更新時(shí)間：2026年06月02日 10:22:13 作者：晚風(fēng)吹紅霞

這段文章詳細(xì)講解了C++ STL中的vector容器,從其優(yōu)勢、基礎(chǔ)刪查改操作到迭代器失效等,并提供了模擬實(shí)現(xiàn)和常見陷阱的解析,幫助開發(fā)者全面掌握vector的用法,重點(diǎn)強(qiáng)調(diào)了reserve的用法、迭代器失效的處理和深拷貝、淺拷貝的區(qū)別,感興趣的朋友一起看看吧

一、為什么 vector 是“最強(qiáng)容器”？

在 C++ 標(biāo)準(zhǔn)模板庫（STL）中，vector 是一個(gè)動(dòng)態(tài)數(shù)組。它與普通數(shù)組的區(qū)別在于：

大小可以自動(dòng)增長（不需要手動(dòng) realloc）。
支持隨機(jī)訪問（[] 運(yùn)算符，O(1) 時(shí)間）。
在尾部增刪元素效率高（均攤 O(1)）。
提供豐富的成員函數(shù)，如 push_back、pop_back、insert、erase 等。

學(xué)習(xí) STL 有三個(gè)境界：能用 → 明理 → 能擴(kuò)展。本文會(huì)幫你至少達(dá)到第二個(gè)境界，并向第三個(gè)境界邁進(jìn)。

二、vector 的基礎(chǔ)使用

使用 vector 需要包含 <vector> 頭文件，并引入 std 命名空間。

2.1 構(gòu)造方式

#include <vector>
using namespace std;
int main() {
    vector<int> v1;               // 空 vector
    vector<int> v2(5, 10);        // 5 個(gè)元素，每個(gè)都是 10
    vector<int> v3(v2);           // 拷貝構(gòu)造
    vector<int> v4(v2.begin(), v2.end()); // 迭代器區(qū)間構(gòu)造
    int arr[] = {1,2,3,4};
    vector<int> v5(arr, arr+4);   // 使用數(shù)組構(gòu)造
    return 0;
}

2.2 迭代器與遍歷

vector 支持隨機(jī)訪問迭代器，常用方式有三種：

vector<int> v = {1, 2, 3, 4, 5};
// 1. 下標(biāo) operator[]
for (size_t i = 0; i < v.size(); ++i)
    cout << v[i] << " ";
// 2. 迭代器
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    cout << *it << " ";
// 3. C++11 范圍 for
for (auto e : v)
    cout << e << " ";

2.3 容量相關(guān)：size、capacity、resize、reserve

這是 vector 新手最容易混淆的地方。

size()：當(dāng)前實(shí)際存儲(chǔ)的元素個(gè)數(shù)。
capacity()：當(dāng)前分配的內(nèi)存能容納的元素個(gè)數(shù)（capacity >= size）。
resize(n, val)：改變 size 為 n。若 n > size，則用 val 填充（默認(rèn)用 0 或默認(rèn)構(gòu)造）；若 n < size，則截?cái)?。它?huì)影響 size，也可能改變 capacity。
reserve(n)：預(yù)留至少 n 個(gè)元素的空間（改變 capacity 但不改變 size）。常用于提前知道元素?cái)?shù)量，避免多次擴(kuò)容。

vector<int> v;
v.reserve(100);          // 容量至少 100，size 仍為 0
for (int i = 0; i < 100; ++i)
    v.push_back(i);      // 不會(huì)觸發(fā)擴(kuò)容
cout << v.size() << " " << v.capacity() << endl; // 100 至少100

2.4 擴(kuò)容機(jī)制：1.5 倍還是 2 倍？

不同 STL 實(shí)現(xiàn)的擴(kuò)容策略不同，這是一個(gè)?？嫉狞c(diǎn)。

VS (微軟)：按 1.5 倍 擴(kuò)容。
g++ (Linux / SGI STL)：按 2 倍 擴(kuò)容。

測試代碼：

vector<int> v;
size_t sz = v.capacity();
for (int i = 0; i < 100; ++i) {
    v.push_back(i);
    if (sz != v.capacity()) {
        sz = v.capacity();
        cout << "capacity changed: " << sz << endl;
    }
}

VS 輸出示例：1, 2, 3, 4, 6, 9, 13, 19, 28, 42, 63, 94, 141 …
g++ 輸出：1, 2, 4, 8, 16, 32, 64, 128 …

結(jié)論：不要迷信“2 倍”這個(gè)說法。編寫可移植代碼時(shí)，不要假設(shè)擴(kuò)容因子。需要高效時(shí)，主動(dòng)使用 reserve。

三、增刪查改操作

函數(shù)	作用
`push_back(val)`	尾插
`pop_back()`	尾刪
`insert(pos, val)`	在迭代器 pos 前插入 val
`erase(pos)`	刪除迭代器 pos 處的元素
`find(begin, end, val)`	算法中的查找，不是 vector 成員
`swap(vec)`	交換兩個(gè) vector 的數(shù)據(jù)
`operator[]`	隨機(jī)訪問

示例：

vector<int> v = {1, 2, 3};
v.push_back(4);           // 1 2 3 4
v.pop_back();             // 1 2 3
v.insert(v.begin(), 0);   // 0 1 2 3
v.erase(v.begin() + 1);   // 0 2 3

四、迭代器失效 —— 最容易踩的坑

迭代器本質(zhì)是一個(gè)指針（或封裝后的指針），指向容器中的某個(gè)元素。當(dāng)容器的內(nèi)存布局發(fā)生變化時(shí)，舊的迭代器可能指向無效內(nèi)存，稱為迭代器失效。

4.1 會(huì)導(dǎo)致擴(kuò)容的操作（insert、push_back、reserve、resize、assign）

這些操作可能重新分配內(nèi)存，使得原有的迭代器全部失效。

vector<int> v{1,2,3};
auto it = v.begin();
v.reserve(100);      // 擴(kuò)容，it 失效
// 此時(shí) it 已經(jīng)不安全，不能再使用
while (it != v.end()) { // 錯(cuò)誤！可能崩潰
    cout << *it;
}

正確做法：在可能導(dǎo)致擴(kuò)容的操作后，重新獲取迭代器。

it = v.begin();      // 重新賦值

4.2 erase 導(dǎo)致的失效

erase 刪除元素后，被刪除元素及其之后的所有迭代器都會(huì)失效（因?yàn)樵匕l(fā)生了移動(dòng)）。典型的錯(cuò)誤寫法：

vector<int> v{1,2,3,4};
auto it = v.begin();
while (it != v.end()) {
    if (*it % 2 == 0)
        v.erase(it);   // 錯(cuò)誤：erase 后 it 失效，再 ++it 就是野指針
    ++it;
}

正確寫法：利用 erase 返回下一個(gè)有效迭代器。

while (it != v.end()) 
{ if (*it % 2 == 0) it = v.erase(it); 
// erase 返回被刪除元素的下一個(gè)位置 else ++it;
 }

4.3 Linux (g++) 與 VS 的差異

VS 對迭代器失效非常敏感，一旦使用失效迭代器，大概率立即崩潰（調(diào)試模式下會(huì)斷言）。
g++ 則相對寬容，擴(kuò)容后舊迭代器可能仍指向原內(nèi)存（但已被釋放），程序可能“看起來正常”，實(shí)則存在隱患，例如輸出亂碼或段錯(cuò)誤。

建議：統(tǒng)一按照“任何修改容量的操作都會(huì)導(dǎo)致迭代器失效”來編程，不要依賴編譯器行為。

五、OJ 實(shí)戰(zhàn)：鞏固 vector 使用

5.1 只出現(xiàn)一次的數(shù)字（異或法）

int singleNumber(vector<int>& nums) {
    int ret = 0;
    for (auto e : nums) ret ^= e;
    return ret;
}

5.2 楊輝三角（vector<vector<int>>）

vector<vector<int>> generate(int numRows) {
    vector<vector<int>> vv(numRows);
    for (int i = 0; i < numRows; ++i) {
        vv[i].resize(i + 1, 1);
    }
    for (int i = 2; i < numRows; ++i) {
        for (int j = 1; j < i; ++j) {
            vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
        }
    }
    return vv;
}

練習(xí)推薦：

刪除排序數(shù)組中的重復(fù)項(xiàng)
數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
電話號(hào)碼的字母組合

六、模擬實(shí)現(xiàn) vector：核心框架

為了深入理解 vector，我們嘗試自己實(shí)現(xiàn)一個(gè)簡化版，命名為 bit::vector。

6.1 成員變量與基本接口

namespace bit {
    template<class T>
    class vector {
    public:
        // 迭代器就是原生指針
        typedef T* iterator;
        typedef const T* const_iterator;
        // 構(gòu)造、析構(gòu)
        vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
        vector(int n, const T& val = T()) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
            reserve(n);
            for (int i = 0; i < n; ++i)
                push_back(val);
        }
        ~vector() {
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;
        }
        // 迭代器
        iterator begin() { return _start; }
        iterator end() { return _finish; }
        const_iterator begin() const { return _start; }
        const_iterator end() const { return _finish; }
        // 容量
        size_t size() const { return _finish - _start; }
        size_t capacity() const { return _end_of_storage - _start; }
        bool empty() const { return _start == _finish; }
        // 元素訪問
        T& operator[](size_t pos) { return _start[pos]; }
        const T& operator[](size_t pos) const { return _start[pos]; }
        // 修改
        void push_back(const T& val);
        void pop_back();
        void reserve(size_t n);
        void resize(size_t n, const T& val = T());
        iterator insert(iterator pos, const T& val);
        iterator erase(iterator pos);
    private:
        iterator _start;          // 指向數(shù)據(jù)起始
        iterator _finish;         // 指向最后一個(gè)有效數(shù)據(jù)的下一個(gè)位置
        iterator _end_of_storage; // 指向已分配內(nèi)存的末尾
    };
}

6.2 核心實(shí)現(xiàn)：reserve 與 push_back

template<class T>
void vector<T>::reserve(size_t n) {
    if (n > capacity()) {
        size_t old_size = size();
        T* new_data = new T[n];
        if (_start) {
            // 拷貝舊數(shù)據(jù)
            for (size_t i = 0; i < old_size; ++i)
                new_data[i] = _start[i];
            delete[] _start;
        }
        _start = new_data;
        _finish = _start + old_size;
        _end_of_storage = _start + n;
    }
}
template<class T>
void vector<T>::push_back(const T& val) {
    if (_finish == _end_of_storage) {
        size_t new_cap = capacity() == 0 ? 1 : capacity() * 2;
        reserve(new_cap);
    }
    *_finish = val;
    ++_finish;
}

6.3 深拷貝與 insert/erase

template<class T>
typename vector<T>::iterator vector<T>::insert(iterator pos, const T& val) {
    // 判斷擴(kuò)容
    if (_finish == _end_of_storage) {
        size_t offset = pos - _start;
        reserve(capacity() == 0 ? 1 : capacity() * 2);
        pos = _start + offset;   // 更新 pos，因?yàn)閿U(kuò)容后原迭代器失效
    }
    // 后移元素
    for (iterator it = _finish; it > pos; --it)
        *it = *(it - 1);
    *pos = val;
    ++_finish;
    return pos;
}
template<class T>
typename vector<T>::iterator vector<T>::erase(iterator pos) {
    for (iterator it = pos; it < _finish - 1; ++it)
        *it = *(it + 1);
    --_finish;
    return pos;   // 返回被刪除元素的下一個(gè)位置
}

七、致命陷阱：memcpy 淺拷貝問題

在模擬實(shí)現(xiàn) reserve 時(shí)，如果用 memcpy 進(jìn)行內(nèi)存復(fù)制會(huì)怎樣？

// 錯(cuò)誤示范
void reserve(size_t n) {
    if (n > capacity()) {
        T* tmp = new T[n];
        if (_start) {
            memcpy(tmp, _start, size() * sizeof(T));  // 危險(xiǎn)！
            delete[] _start;
        }
        _start = tmp;
        // ...
    }
}

問題：
如果 T 是 string 或其他管理資源的類型（如 vector<int>），memcpy 只是按字節(jié)復(fù)制指針（淺拷貝），導(dǎo)致兩個(gè)對象指向同一塊堆內(nèi)存。當(dāng)舊對象被 delete[] 時(shí)，會(huì)析構(gòu)每個(gè)元素，釋放資源；而新對象中的元素仍持有已釋放的指針，最終導(dǎo)致雙重釋放或內(nèi)存泄漏。

正確做法：使用賦值操作（深拷貝）。

for (size_t i = 0; i < old_size; ++i)
    tmp[i] = _start[i];   // 調(diào)用 T 的拷貝賦值，實(shí)現(xiàn)深拷貝

因此，在編寫通用容器時(shí)，絕不能使用 memcpy 處理非 POD 類型。

八、動(dòng)態(tài)二維數(shù)組：vector<vector<T>>

楊輝三角的代碼展示了 vector 的嵌套使用。物理上，外層 vector 的每個(gè)元素又是一個(gè)內(nèi)層 vector，它們的內(nèi)存不一定是連續(xù)的，但每個(gè)內(nèi)層 vector 內(nèi)部連續(xù)。

vector<vector<int>> vv(5);   // 5 行
for (int i = 0; i < 5; ++i)
    vv[i].resize(i+1, 1);    // 每行長度 i+1，初始化 1

這種結(jié)構(gòu)比 C 語言的“指針數(shù)組”更安全、更易用。

九、總結(jié)與建議

優(yōu)先使用 vector：動(dòng)態(tài)數(shù)組是絕大多數(shù)場景的最佳選擇。
善用 reserve：提前分配空間，避免頻繁擴(kuò)容。
警惕迭代器失效：任何可能改變?nèi)萘康牟僮骱?，原來持有的迭代器都可能失效，?wù)必重新獲取。
模擬實(shí)現(xiàn)是提升內(nèi)功的最佳途徑：親手實(shí)現(xiàn) reserve、push_back、insert、erase，你會(huì)對深拷貝、淺拷貝、異常安全有更深理解。
不要用 memcpy 拷貝非 POD 元素：始終使用賦值或拷貝構(gòu)造。

vector 的用法看似簡單，但其中的陷阱和原理值得每個(gè) C++ 開發(fā)者反復(fù)琢磨。希望這篇文章能幫你徹底掌握 vector，并在面試和工程中游刃有余。

練習(xí)題推薦：

LeetCode 26. 刪除有序數(shù)組中的重復(fù)項(xiàng)
LeetCode 118. 楊輝三角
LeetCode 17. 電話號(hào)碼的字母組合

下一篇預(yù)告：我們將深入 list 容器，對比 vector 與 list 的優(yōu)劣，并探討迭代器失效在不同容器中的表現(xiàn)。敬請期待！

到此這篇關(guān)于C++ vector從入門到模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ vector實(shí)現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

C++
vector

最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

C++ vector從入門到模擬實(shí)現(xiàn)過程

目錄

一、為什么 vector 是“最強(qiáng)容器”？

二、vector 的基礎(chǔ)使用

2.1 構(gòu)造方式

2.2 迭代器與遍歷

2.3 容量相關(guān)：size、capacity、resize、reserve

2.4 擴(kuò)容機(jī)制：1.5 倍還是 2 倍？

三、增刪查改操作

四、迭代器失效 —— 最容易踩的坑

4.1 會(huì)導(dǎo)致擴(kuò)容的操作（insert、push_back、reserve、resize、assign）

4.2 erase 導(dǎo)致的失效

4.3 Linux (g++) 與 VS 的差異

五、OJ 實(shí)戰(zhàn)：鞏固 vector 使用

5.1 只出現(xiàn)一次的數(shù)字（異或法）

5.2 楊輝三角（vector<vector<int>>）

六、模擬實(shí)現(xiàn) vector：核心框架

6.1 成員變量與基本接口

6.2 核心實(shí)現(xiàn)：reserve 與 push_back

6.3 深拷貝與 insert/erase

七、致命陷阱：memcpy 淺拷貝問題

八、動(dòng)態(tài)二維數(shù)組：vector<vector<T>>

九、總結(jié)與建議

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

C++ vector從入門到模擬實(shí)現(xiàn)過程

目錄

一、為什么 vector 是“最強(qiáng)容器”？

二、vector 的基礎(chǔ)使用

2.1 構(gòu)造方式

2.2 迭代器與遍歷

2.3 容量相關(guān)：size、capacity、resize、reserve

2.4 擴(kuò)容機(jī)制：1.5 倍還是 2 倍？

三、增刪查改操作

四、迭代器失效 —— 最容易踩的坑

4.1 會(huì)導(dǎo)致擴(kuò)容的操作（insert、push_back、reserve、resize、assign）

4.2 erase 導(dǎo)致的失效

4.3 Linux (g++) 與 VS 的差異

五、OJ 實(shí)戰(zhàn)：鞏固 vector 使用

5.1 只出現(xiàn)一次的數(shù)字（異或法）

5.2 楊輝三角（vector<vector<int>>）

六、模擬實(shí)現(xiàn) vector：核心框架

6.1 成員變量與基本接口

6.2 核心實(shí)現(xiàn)：reserve 與 push_back

6.3 深拷貝與 insert/erase

七、致命陷阱：memcpy 淺拷貝問題

八、動(dòng)態(tài)二維數(shù)組：vector<vector<T>>

九、總結(jié)與建議

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

一、為什么 vector 是“最強(qiáng)容器”？

二、vector 的基礎(chǔ)使用

2.3 容量相關(guān)：size、capacity、resize、reserve

2.4 擴(kuò)容機(jī)制：1.5 倍還是 2 倍？

三、增刪查改操作

四、迭代器失效 —— 最容易踩的坑

4.1 會(huì)導(dǎo)致擴(kuò)容的操作（insert、push_back、reserve、resize、assign）

六、模擬實(shí)現(xiàn) vector：核心框架

八、動(dòng)態(tài)二維數(shù)組：vector<vector<T>>

九、總結(jié)與建議