C++ vector容器底层深度剖析与模拟实现代码示例_C/C++

1 模板的使用说明

在c++中，模板是实现泛型编程的重要工具，它允许我们编写与数据类型无关的代码。vector容器正是通过模板技术实现的，可以存储任意类型的数据：

template<class t>
class vector
{
    // ... 实现细节
};

这里的t是类型参数，当我们创建vector对象时，需要指定具体的类型

vector<int> intvector;      // 存储int类型的vector
vector<string> strvector;   // 存储string类型的vector
vector<double> dblvector;   // 存储double类型的vector

模板的使用让vector具有了极强的通用性，可以容纳各种数据类型，从基本类型到自定义类类型。

2 vector深度剖析及模拟实现

2.1 vector的成员变量

vector底层使用动态数组实现，通过三个指针来管理内存：

private:
    iterator _start = nullptr;          // 指向数组的开始位置
    iterator _finish = nullptr;         // 指向最后一个元素的下一个位置
    iterator _end_of_storage = nullptr; // 指向分配内存的末尾

在这里，给了三个指针缺省值nullptr初始化。

2.2 构造函数

vector提供了多种构造函数来满足不同的初始化需求：、

2.2.1 指定大小和初始值的构造函数

vector(size_t n, const t& val = t())
{
    reserve(n);
    for (size_t i = 0; i < n; i++)
    {
        push_back(val);
    }
}

使用示例：

vector<int> v1(5);        // 包含5个0的vector
vector<int> v2(3, 10);    // 包含3个10的vector
vector<string> v3(2, "hello"); // 包含2个"hello"的vector

2.2.2 迭代器范围构造函数

template <class inputiterator>
vector(inputiterator first, inputiterator last)
{
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

这个构造函数是函数模板，可以接受任意类型的迭代器：

int arr[] = {1, 2, 3, 4, 5};
vector<int> v1(arr, arr + 5);           // 从数组构造
vector<int> v2(v1.begin(), v1.end());   // 从另一个vector构造

2.2.3 拷贝构造函数（现代写法）

vector(const vector<t>& v)
{
    vector<t> tmp(v.begin(), v.end());
    swap(tmp);
}

现代写法通过创建临时对象并交换资源，代码简洁且异常安全~

2.3 赋值运算符重载

vector<t>& operator=(vector<t> tmp)
{
    swap(tmp);
    return *this;
}

2.4 容量相关操作

2.4.1 reserve 开空间

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t sz = size();
        t* tmp = new t[n];
        if (_start)
        {
            for (size_t i = 0; i < sz; i++)
            {
                std::swap(tmp[i], _start[i]);
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + sz;
        _end_of_storage = _start + n;
    }
}

使用std::swap而不是直接赋值，这样可以高效地交换资源（）
如果直接使用memcpy，对于管理资源的类（如string）会导致浅拷贝问题！
重新计算_finish和_end_of_storage指针

2.4.2 用resize 调整大小

void resize(size_t n, t val = t())
{
    if (n < size())
    {
        // 缩小size，只是移动_finish指针
        _finish = _start + n;
    }
    else
    {
        reserve(n);  // 可能需要扩容
        while (_finish < _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
}

这里使用匿名对象做缺省参数。

使用示例：

vector<int> v = {1, 2, 3};
v.resize(5);      // 变为 {1, 2, 3, 0, 0}
v.resize(2);      // 变为 {1, 2}

2.4.3 size和capacity

size_t capacity() const
{
    return _end_of_storage - _start;
}

size_t size() const
{
    return _finish - _start;
}

2.5 元素访问操作

2.5.1 下标运算符

t& operator[](size_t i)
{
    assert(i < size());
    return _start[i];
}

const t& operator[](size_t i) const
{
    assert(i < size());
    return _start[i];
}

提供const和非const版本，支持读写访问和只读访问。

2.6 修改操作

2.6.1 push_back 尾部添加元素

void push_back(const t& x)
{
    if (_finish == _end_of_storage)
    {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
    }
    *_finish = x;
    ++_finish;
}

扩容策略：初始为0时分配4个元素空间，否则每次扩容为原来的2倍。

2.6.2 pop_back 尾部删除元素

void pop_back()
{
    assert(!empty());
    --_finish;
}

2.6.3 insert 在指定位置插入元素

iterator insert(iterator pos, const t& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);

    // 扩容
    if (_finish == _end_of_storage)
    {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
    }

    // 挪动数据
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }

    *pos = x;
    ++_finish;
    return pos;
}

扩容后需要重新计算pos的位置，因为_start可能改变了。

2.6.4 erase 删除指定位置元素

iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);

    iterator it = pos + 1;
    while (it != _finish)
    {
        *(it - 1) = *it;
        ++it;
    }

    --_finish;
    return pos;
}

3 vector迭代器失效问题

迭代器失效是使用vector时需要特别注意的问题，不当使用会导致未定义行为。

3.1 insert失效问题

当在vector中插入元素时，如果引起扩容，所有迭代器都会失效。

void test_vector2()
{
    bit::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    
    auto it = v.begin() + 3;
    v.insert(v.begin(), 0);  // 可能引起扩容
    
    // insert以后，it失效了，不能再使用
    // *it = 10;  // 错误！未定义行为
}

3.2 erase失效问题

erase操作会使被删除元素及其后面所有元素的迭代器失效。

void test_vector3()
{
    bit::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    
    auto it = v.begin() + 2;
    v.erase(v.begin());  // 删除第一个元素
    
    // it失效了，不能访问，访问结果未定义
    // cout << *it << endl;  // 错误！
}

3.3 删除所有的偶数

正确使用erase删除元素的模式：

void test_vector4()
{
    bit::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
    
    // 正确做法：接收erase的返回值
    auto it = v.begin();
    while (it != v.end())
    {
        if (*it % 2 == 0)
        {
            it = v.erase(it);  // erase返回下一个有效迭代器
        }
        else
        {
            ++it;
        }
    }
    
    // 错误做法：直接递增迭代器
    // auto it = v.begin();
    // while (it != v.end())
    // {
    //     if (*it % 2 == 0)
    //     {
    //         v.erase(it);  // erase后it失效
    //     }
    //     ++it;  // 错误：对失效迭代器递增
    // }
}

3.4 不同编译器对迭代器失效的检查

不同编译器对迭代器失效的检查严格程度不同：

debug模式下通常会进行严格的迭代器检查
release模式下可能没有检查，导致难以发现的bug
linux的gcc编译器检查就会比较宽松

3.5 扩容之后，迭代器已经失效了

vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);  // 可能引起扩容
// it已经失效，不能再使用

3.6 erase删除的迭代器如果是最后一个元素

vector<int> v = {1, 2, 3};
auto it = v.begin() + 2;  // 指向3
it = v.erase(it);         // 删除最后一个元素
// 此时it == v.end()，不能解引用

3.7 string的迭代器失效

与vector类似，string在插入、扩容操作、erase之后，迭代器也会失效。

4 本文代码完整展示

（一）vector.h

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

namespace bit
{
    template<class t>
    class vector
    {
    public:
        typedef t* iterator;
        typedef const t* const_iterator;

        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

        // 构造函数 - 指定大小和初始值
        vector(size_t n, const t& val = t())
        {
            reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                push_back(val);
            }
        }

        vector(int n, const t& val = t())
        {
            reserve(n);
            for (int i = 0; i < n; i++)
            {
                push_back(val);
            }
        }

        // 迭代器范围构造函数
        template <class inputiterator>
        vector(inputiterator first, inputiterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        // 默认构造函数
        vector() = default;

        // 拷贝构造函数（现代写法）
        vector(const vector<t>& v)
        {
            vector<t> tmp(v.begin(), v.end());
            swap(tmp);
        }

        // 赋值运算符（现代写法）
        vector<t>& operator=(vector<t> tmp)
        {
            swap(tmp);
            return *this;
        }

        // 交换两个vector
        void swap(vector<t>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_end_of_storage, v._end_of_storage);
        }

        // 清空元素
        void clear()
        {
            _finish = _start;
        }

        // 判断是否为空
        bool empty() const
        {
            return _start == _finish;
        }

        // 预留空间
        void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t sz = size();
                t* tmp = new t[n];
                if (_start)
                {
                    for (size_t i = 0; i < sz; i++)
                    {
                        std::swap(tmp[i], _start[i]);
                    }
                    delete[] _start;
                }
                _start = tmp;
                _finish = _start + sz;
                _end_of_storage = _start + n;
            }
        }

        // 调整大小
        void resize(size_t n, t val = t())
        {
            if (n < size())
            {
                _finish = _start + n;
            }
            else
            {
                reserve(n);
                while (_finish < _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
        }

        // 获取容量
        size_t capacity() const
        {
            return _end_of_storage - _start;
        }

        // 获取元素个数
        size_t size() const
        {
            return _finish - _start;
        }

        // 下标运算符
        t& operator[](size_t i)
        {
            assert(i < size());
            return _start[i];
        }

        const t& operator[](size_t i) const
        {
            assert(i < size());
            return _start[i];
        }

        // 尾部添加元素
        void push_back(const t& x)
        {
            if (_finish == _end_of_storage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            ++_finish;
        }

        // 尾部删除元素
        void pop_back()
        {
            assert(!empty());
            --_finish;
        }

        // 在指定位置插入元素
        iterator insert(iterator pos, const t& x)
        {
            assert(pos >= _start);
            assert(pos <= _finish);

            if (_finish == _end_of_storage)
            {
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2);
                pos = _start + len;
            }

            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }

            *pos = x;
            ++_finish;
            return pos;
        }

        // 删除指定位置元素
        iterator erase(iterator pos)
        {
            assert(pos >= _start);
            assert(pos < _finish);

            iterator it = pos + 1;
            while (it != _finish)
            {
                *(it - 1) = *it;
                ++it;
            }

            --_finish;
            return pos;
        }

        // 析构函数
        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _end_of_storage = nullptr;
            }
        }

    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };
}

（二）test.c

#include "vector.h"
#include <iostream>
using namespace std;

namespace bit
{
    // 打印vector内容
    void print(const vector<int>& v)
    {
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试基本操作
    void test_vector1()
    {
        cout << "测试基本操作:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        
        v[0]++;  // 修改第一个元素
        
        print(v);
        
        // 范围for遍历
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试insert操作
    void test_vector2()
    {
        cout << "\n测试insert操作:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        print(v);

        v.insert(v.begin(), 0);  // 头部插入
        print(v);

        // 注意：insert后迭代器可能失效
        auto it = v.begin() + 3;
        v.insert(it, 30);  // 指定位置插入
        print(v);
    }

    // 测试erase操作
    void test_vector3()
    {
        cout << "\n测试erase操作:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        print(v);

        v.erase(v.begin());  // 删除第一个元素
        print(v);

        auto it = v.begin() + 2;
        v.erase(it);  // 删除指定位置元素
        print(v);
    }

    // 测试删除特定元素（删除所有偶数）
    void test_vector4()
    {
        cout << "\n测试删除所有偶数:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        v.push_back(6);
        
        cout << "删除前: ";
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;

        // 正确删除方法
        auto it = v.begin();
        while (it != v.end())
        {
            if (*it % 2 == 0)
            {
                it = v.erase(it);  // 接收erase返回值
            }
            else
            {
                ++it;
            }
        }

        cout << "删除后: ";
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试resize操作
    void test_vector5()
    {
        cout << "\n测试resize操作:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        v.push_back(6);
        
        cout << "原始vector: ";
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;

        v.resize(3);  // 缩小
        cout << "resize(3): ";
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;

        v.resize(20, 5);  // 扩大并填充
        cout << "resize(20, 5): ";
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试拷贝构造和赋值
    void test_vector6()
    {
        cout << "\n测试拷贝构造和赋值:" << endl;
        bit::vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        v1.push_back(5);
        v1.push_back(6);
        
        cout << "v1: ";
        for (auto e : v1)
        {
            cout << e << " ";
        }
        cout << endl;

        // 拷贝构造
        bit::vector<int> v2(v1);
        cout << "v2(拷贝v1): ";
        for (auto e : v2)
        {
            cout << e << " ";
        }
        cout << endl;

        // 赋值操作
        bit::vector<int> v3 = {10, 20, 30, 40};
        v1 = v3;
        cout << "v1(赋值后): ";
        for (auto e : v1)
        {
            cout << e << " ";
        }
        cout << endl;

        // 指定大小构造
        bit::vector<int> v4(10, 1);
        cout << "v4(10个1): ";
        for (auto e : v4)
        {
            cout << e << " ";
        }
        cout << endl;

        bit::vector<char> v5(10, 'x');
        cout << "v5(10个x): ";
        for (auto e : v5)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试string类型vector
    void test_vector7()
    {
        cout << "\n测试string类型vector:" << endl;
        bit::vector<string> v1;
        v1.push_back("111111111111111111111111");
        v1.push_back("222222222222222222222222");
        v1.push_back("333333333333333333333333");
        v1.push_back("444444444444444444444444");
        v1.push_back("555555555555555555555555");
        
        for (auto& e : v1)
        {
            cout << e << " ";
        }
        cout << endl;
    }
}

int main()
{
    bit::test_vector1();
    bit::test_vector2();
    bit::test_vector3();
    bit::test_vector4();
    bit::test_vector5();
    bit::test_vector6();
    bit::test_vector7();

    return 0;
}

c++ vector基于动态数组实现，通过三个指针管理内存。核心风险是迭代器失效：insert可能扩容使所有迭代器失效；erase使被删位置后迭代器失效，必须通过it=erase(it)接收返回值。采用2倍扩容策略，现代写法通过swap实现安全拷贝。连续存储支持高效随机访问，但需警惕迭代器失效这一主要陷阱。

总结

到此这篇关于c++ vector容器底层深度剖析与模拟实现的文章就介绍到这了,更多相关c++ vector容器底层内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！

C++ vector容器底层深度剖析与模拟实现代码示例

2026年01月05日 • C/C++ •我要评论