C++之vector剖析及模擬實(shí)現(xiàn)方式

更新時(shí)間：2025年09月18日 09:31:55 作者：一枝小雨

文章詳解C++ vector實(shí)現(xiàn),涵蓋三個(gè)指針管理動(dòng)態(tài)數(shù)組、容量擴(kuò)容機(jī)制、元素增刪操作及深拷貝原理,強(qiáng)調(diào)迭代器安全性和memcpy對(duì)自定義類型的風(fēng)險(xiǎn),提供使用示例與注意事項(xiàng)

1.0 std 庫 vector 源碼

官方文檔：vector

成員變量：

template<class T>
class vector
{
public:
        typedef T* iterator;

private:
        iterator _start;
        iterator _finish;
        iterator _endofstorage;
};

1.1 vector 類的基本結(jié)構(gòu)與迭代器

類定義與成員變量

template<class T>
class vector
{
public:
    typedef T* iterator;              // 普通迭代器類型
    typedef const T* const_iterator;  // const迭代器類型
    
private:
    iterator _start;         // 指向數(shù)組首元素
    iterator _finish;        // 指向最后一個(gè)元素的下一個(gè)位置
    iterator _endofstorage;  // 指向存儲(chǔ)空間末尾的下一個(gè)位置
};

vector 使用三個(gè)指針來管理動(dòng)態(tài)數(shù)組：

_start：指向數(shù)組的第一個(gè)元素
_finish：指向最后一個(gè)元素之后的位置（即當(dāng)前元素?cái)?shù)量的末尾）
_endofstorage：指向已分配內(nèi)存的末尾之后的位置（即當(dāng)前容量的末尾）

構(gòu)造函數(shù)與析構(gòu)函數(shù)

// 默認(rèn)構(gòu)造函數(shù)
vector()
    :_start(nullptr)
    ,_finish(nullptr)
    ,_endofstorage(nullptr)
{}

// 析構(gòu)函數(shù)
~vector()
{
    delete[] _start;  // 釋放動(dòng)態(tài)分配的內(nèi)存
    _start = _finish = _endofstorage = nullptr;  // 指針置空
}

默認(rèn)構(gòu)造函數(shù)初始化所有指針為 nullptr
析構(gòu)函數(shù)釋放動(dòng)態(tài)分配的內(nèi)存并重置所有指針

迭代器訪問方法

// 普通正向迭代器
iterator begin() { return _start; }
iterator end() { return _finish; }

// 只讀正向迭代器
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }

提供迭代器訪問方法，使 vector 支持范圍 for 循環(huán)和標(biāo)準(zhǔn)庫算法
const 版本確保 const 對(duì)象只能進(jìn)行只讀訪問

1.2 容量管理

容量查詢方法

// 獲取元素?cái)?shù)量
size_t size() const { return _finish - _start; }

// 獲取當(dāng)前容量
size_t capacity() const { return _endofstorage - _start; }

size() 返回當(dāng)前元素?cái)?shù)量
capacity() 返回當(dāng)前分配的內(nèi)存容量

擴(kuò)容機(jī)制

// 擴(kuò)容方法
void reserve(size_t n)
{
    size_t sz = size();  // 提前計(jì)算當(dāng)前大小
    if (n > capacity())
    {
        T* tmp = new T[n];  // 分配新內(nèi)存
        if (_start)  // 防止第一次分配內(nèi)存時(shí) memcpy 出錯(cuò)
        {
            // 這里使用 memcpy 是有問題的，只能對(duì)內(nèi)置類型
            // 的vector進(jìn)行擴(kuò)容，具體問題和解決方案在
            // 后續(xù)“memcpy：更深一層次的深淺拷貝問題”
            memcpy(tmp, _start, sizeof(T) * sz);  // 拷貝數(shù)據(jù)
            delete[] _start;  // 釋放舊內(nèi)存
        }
        _start = tmp;
        _finish = tmp + sz;
        _endofstorage = tmp + n;
    }
}

reserve 方法用于預(yù)分配內(nèi)存，避免多次重新分配
需要提前計(jì)算 size()，因?yàn)橹匦路峙浜?_start 會(huì)改變
注意：使用 memcpy 只能對(duì)內(nèi)置類型進(jìn)行拷貝，對(duì)于自定義類型會(huì)有問題

元素訪問方法

// 下標(biāo)運(yùn)算符重載
T& operator[](size_t i)
{
    assert(i < size());  // 越界檢查
    return _start[i];
}

// const 版本下標(biāo)運(yùn)算符
const T& operator[](size_t i) const
{
    assert(i < size());  // 越界檢查
    return _start[i];
}

提供類似數(shù)組的隨機(jī)訪問功能
包含越界檢查，提高代碼安全性

resize

/* resize */
// val不能給0，因?yàn)椴恢繲的類型，所以給一個(gè)T的缺省值
void resize(size_t n, const T& val = T())
{
        // 縮小size
        if (n < size())
                _finish = _start + n;
        else // 增大size
        {
                // 假如需要擴(kuò)容
                if (n > capacity())
                {
                        reserve(n);
                }

                while (_finish < _start + n)
                {
                        *_finish = val;
                        ++_finish;
                }
        }
}

可以增大或減小 vector 的大小
增大時(shí)用指定值填充新元素（默認(rèn)為 T 類型的默認(rèn)值）
縮小時(shí)只是調(diào)整 _finish 指針，不釋放內(nèi)存

1.3 添加與刪除元素

push_back

// 尾插元素
void push_back(const T& x)
{
    // 空間不足時(shí)擴(kuò)容
    if (_finish == _endofstorage)
    {
        size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
        reserve(newcapacity);
    }
    
    *_finish = x;  // 在末尾位置添加元素
    ++_finish;     // 更新末尾指針
}

// 也可以直接借助insert完成尾插
void push_back(const T& x) { insert(_finish, x); }

當(dāng)容量不足時(shí)自動(dòng)擴(kuò)容（通常翻倍）
在尾部添加元素并更新指針

insert

// pos位置插入
void insert(iterator pos, const T& x)
{
    assert(pos <= _finish);  // 檢查位置有效性
    
    // 空間不夠就增容
    if (_finish == _endofstorage)
    {
        // 記下pos相對(duì)于_start的位置
        size_t n = pos - _start;
        size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
        reserve(newcapacity);
        // 空間增容導(dǎo)致原pos迭代器失效，更新迭代器位置
        pos = _start + n;
    }
    
    // 后移元素
    iterator end = _finish - 1;
    while (end >= pos)  // 依次把pos及pos后面的數(shù)據(jù)往后挪1位
    {
        *(end + 1) = *end;
        --end;
    }
    
    *pos = x;    // 插入新元素
    ++_finish;   // 更新末尾指針
}

插入操作需要移動(dòng)后續(xù)元素，時(shí)間復(fù)雜度為 O(n)
擴(kuò)容會(huì)導(dǎo)致迭代器失效，需要重新計(jì)算位置

erase

// 刪除指定位置元素
iterator erase(iterator pos)
{
    assert(pos < _finish);  // 檢查位置有效性
    
    iterator it = pos;
    while (it < _finish)  // 將后續(xù)元素前移
    {
        *it = *(it + 1);
        ++it;
    }
    
    --_finish;  // 更新末尾指針
    return pos;  // 返回刪除后該位置的迭代器
}

// 尾刪
void pop_back() { erase(_finish - 1); }

刪除操作需要移動(dòng)后續(xù)元素，時(shí)間復(fù)雜度為 O(n)
返回刪除后位置的迭代器，便于連續(xù)刪除操作

1.4 拷貝構(gòu)造與賦值重載

拷貝構(gòu)造函數(shù)

/* 拷貝構(gòu)造函數(shù) */
vector(const vector<T>& v)
{
        _start = new T[v.capacity()];
        _finish = _start;
        _endofstorage = _start + v.capacity();
        // 拷貝數(shù)據(jù)
        for (size_t i = 0; i < v.size(); ++i)
        {
                *_finish = v[i];
                ++_finish;
        }
}

更簡(jiǎn)潔的寫法：

/* 拷貝構(gòu)造函數(shù)（更簡(jiǎn)潔的寫法） */
vector(const vector<T>& v)
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endofstorage(nullptr)
{
        reserve(v.capacity());        // 直接把空間開好，避免增容
        for (const auto& e : v)        // 把 v 的數(shù)據(jù)直接一個(gè)個(gè)push_back進(jìn)去
                push_back(e);
}

實(shí)現(xiàn)深拷貝，避免多個(gè) vector 共享同一內(nèi)存
先預(yù)分配足夠空間，然后逐個(gè)拷貝元素

賦值重載

/* 賦值重載 */
vector<T>& operator=(const vector<T>& v)
{
        if (this != &v)        // 防止自己賦值給自己
        {
                delete[] _start;
                _start = new T[v.capacity()];
                memcpy(_start, v._start, sizeof(T) * v.size());
                _finish = _start + v.size();
                _endofstorage = _start + v.capacity();
        }
        return *this;
}

賦值重載更簡(jiǎn)潔的寫法：

/* 賦值重載更簡(jiǎn)潔的寫法(現(xiàn)代寫法) */
vector<T>& operator=(vector<T> v)
{
        swap(v);
        return *this;
}

使用"拷貝-交換"技術(shù)實(shí)現(xiàn)賦值運(yùn)算符
參數(shù)通過值傳遞自動(dòng)調(diào)用拷貝構(gòu)造函數(shù)
交換內(nèi)容后，臨時(shí)對(duì)象 v 在函數(shù)結(jié)束時(shí)自動(dòng)析構(gòu)

深淺拷貝問題

為什么我們需要深拷貝？

/* 深淺拷貝問題 */
void test_vector4()
{
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);

        // 如果我們自己沒有實(shí)現(xiàn)深拷貝的拷貝構(gòu)造，就會(huì)發(fā)生和string類一樣的淺拷貝問題
        // 兩個(gè)vector對(duì)象的指針指向同一塊空間，最后析構(gòu)時(shí)同一塊空間被重復(fù)釋放，發(fā)生了錯(cuò)誤
        // 所以我們需要自己實(shí)現(xiàn)深拷貝
        vector<int> v2(v1);
        for (size_t i = 0; i < v1.size(); ++i)
        {
                cout << v2[i] << " ";
        }
        cout << endl;

        // 賦值同理
        vector<int> v3;
        v3.push_back(10);
        v3.push_back(20);
        v3.push_back(30);
        v3.push_back(40);

        v1 = v3;
        print_vector(v1);
        for (auto e : v1)
        {
                cout << e << " ";
        }
        cout << endl;
}

1.5 memcpy導(dǎo)致的更深一層次的深淺拷貝問題

受篇幅限制，這里給出文章鏈接：C++ memcpy導(dǎo)致的深拷貝問題

1.6 使用示例

遍歷與修改

void test_vector1()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    // 使用迭代器遍歷和修改
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        *it += 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 范圍for循環(huán)
    for (auto& e : v)
    {
        e -= 1;
        cout << e << " ";
    }
    cout << endl;

    // 下標(biāo)訪問
    for (size_t i = 0; i < v.size(); ++i)
    {
        cout << v[i] << " ";
    }
    cout << endl;
}

插入與刪除

void test_vector2()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);

    v.insert(v.begin(), 0);  // 在開頭插入0

    // 刪除所有偶數(shù)
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        if (*it % 2 == 0)
        {
            it = v.erase(it);  // 刪除元素并更新迭代器
        }
        else
        {
            ++it;
        }
    }
}