【C++指南】vector（二）：手把手教你底层原理与模拟实现

@toc

一、引言

在 C++ 标准库中，vector 是最常用的动态数组容器，它提供了高效的元素存储和访问能力。

其底层实现涉及内存管理、迭代器维护、元素操作等复杂逻辑。

本文将基于自主实现的 xc::vector 类，深入探讨其设计原理与关键功能实现

vector系列关联文章：【C++指南】vector（一）：从入门到详解

二、成员变量

通过对stl库中vector的实现进行分析：

我们发现其成员变量与我们想象的不一致，并不是通过一个指针指向数据和两个size_t size和capacity

在这里插入图片描述

通过默认构造找到了其基于三个成员变量start、finish和endofstorage来实现vector

并通过size和capacity成员函数的实现可以明白:==STL库是通过指针做差来计算size和capacity==

接着往下深挖，可以找到:

==三个成员变量的数据类型，最终是基于模板类型的指针==

在这里插入图片描述

于是，我们通过模拟STL库的方式来实现vector

private:

    iterator \_start = nullptr;    // 指向数据存储起始位置

    iterator \_finish = nullptr;   // 指向有效数据尾部的下一个位置

    iterator \_endofstorage = nullptr; // 指向存储容量尾部

通过三个指针实现动态数组的核心控制：

• \_start：内存块的起始地址
• \_finish：当前有效元素的末尾的下一个位置
• \_endofstorage：内存块的总容量

三、默认成员函数

2.1 默认构造函数

vector()//默认构造

{}

**思路**：默认构造函数不进行任何初始化操作，将成员指针初始化为 nullptr，表示当前 vector 为空。

2.2 析构函数

~vector()

{

    delete[]\_start;

    \_start = \_finish = \_endofstorage = nullptr;

}

**思路**：析构函数负责释放 vector 所占用的内存。首先使用 delete[] 释放存储元素的数组，然后将三个成员指针都置为 nullptr，避免悬空指针。

2.3 拷贝构造函数

传统写法

//vector(const vector<T>& v)//老实人写法

//{

//    size\_t capacity = v.capacity();//开空间和初始化

//    \_start = new T[capacity];

//    \_endofstorage = \_start + capacity;

//    \_finish = \_start + v.size();



//    for (size\_t i = 0; i < size(); i++)//拷贝数据

//    {

//        \_start[i] = v.\_start[i];

//    }

//}

**思路**：传统的拷贝构造函数首先根据源 vector 的容量分配新的内存空间，然后将源 vector 的元素逐个复制到新的内存空间中。最后更新 \_finish 和 \_endofstorage 指针。

==注意==

拷贝数据不可用memcpy ，为了防止数据类型是自定义类型而引发的浅拷贝问题，而采用逐个位置赋值，这样就可以调用数据类型相应的构造函数了

在C++中所有容器相关的拷贝中，都要用深拷贝来代替浅拷贝

现代写法

vector(const vector<T>& v)//偷懒式写法

{

    reserve(v.capacity());



    for (auto i = v.cbegin(); i != v.cend(); ++i)

    {

        push\_back(\*i);

    }

}

**思路**：现代写法利用 reserve 函数预先分配足够的内存空间，然后通过 push\_back 函数将源 vector 的元素逐个添加到新的 vector 中。这种写法更加简洁，并且利用了已有的 push\_back 函数，减少了代码的重复。

2.4 赋值重载函数

传统写法

//vector<T>& operator=(const vector<int>& v)//老实人写法

//{

//    size\_t capacity = v.capacity();//开空间和初始化

//    \_start = new T[capacity];

//    \_endofstorage = \_start + capacity;

//    \_finish = \_start + v.size();



//    for (size\_t i = 0; i < size(); i++)//拷贝数据

//    {

//        \_start[i] = v.\_start[i];

//    }

//    return \*this;

//}

**思路**：传统的赋值重载函数首先释放当前 vector 所占用的内存，然后根据源 vector 的容量分配新的内存空间，将源 vector 的元素逐个复制到新的内存空间中。最后返回当前对象的引用。

现代写法

vector<T>& operator=(vector<int>v)//偷懒式写法

{

    swap(v);

    return \*this;

}

**思路**：现代写法采用了“拷贝 - 交换”技术。首先通过值传递的方式接收一个临时对象 v，然后调用 swap 函数将当前对象和临时对象的成员指针进行交换。这样就完成了赋值操作，并且保证了异常安全性。最后返回当前对象的引用。

四、元素访问相关

3.1 [] 重载（非 const 版本）

T& operator[](size\_t i)

{

    return \_start[i];

}

**思路**：非 const 版本的 [] 重载函数返回指定位置元素的引用，允许对元素进行修改。

3.2 [] 重载（const 版本）

const T& operator[](size\_t i)const

{

    return \_start[i];

}

**思路**：const 版本的 [] 重载函数返回指定位置元素的 const 引用，用于在 const 对象上访问元素，不允许对元素进行修改。

五、迭代器相关

4.1 迭代器类型声明

typedef T\* iterator;

typedef const T\* const\_iterator;

**思路**：定义了两种迭代器类型，iterator 用于非 const 对象的迭代，const\_iterator 用于 const 对象的迭代。

4.2 begin 函数

iterator begin()

{

    return \_start;

}

**思路**：begin 函数返回指向 vector 第一个元素的迭代器。

4.3 end 函数

iterator end()

{

    return \_finish;

}

**思路**：end 函数返回指向 vector 最后一个元素的下一个位置的迭代器。

4.4 cbegin 函数

const\_iterator cbegin() const

{

    return \_start;

}

**思路**：cbegin 函数返回指向 vector 第一个元素的 const 迭代器，用于在 const 对象上迭代。

4.5 cend 函数

const\_iterator cend() const

{

    return \_finish;

}

**思路**：cend 函数返回指向 vector 最后一个元素的下一个位置的 const 迭代器，用于在 const 对象上迭代。

六、容量相关函数

5.1 size 函数

size\_t size()const

{

    return \_finish - \_start;

}

**思路**：size 函数返回 vector 中当前元素的数量，通过 \_finish 和 \_start 指针的差值计算得到。

5.2 capacity 函数

size\_t capacity()const

{

    return \_endofstorage - \_start;

}

**思路**：capacity 函数返回 vector 当前分配的内存空间能够容纳的元素数量，通过 \_endofstorage 和 \_start 指针的差值计算得到。

5.3 empty 函数

bool empty()

{

    return \_start == \_finish;

}

**思路**：empty 函数判断 vector 是否为空，通过比较 \_start 和 \_finish 指针是否相等来实现。

5.4 resize 函数

void resize(size\_t n,const T& val=T())

{

    if (n <= size())

    {

        \_finish = \_start + n;

    }

    else

    {

        reserve(n);//该函数只有n大于capacity才会扩容

        for (size\_t i = size(); i < n; ++i)

        {

            push\_back(val);

        }

    }

}

**思路**：resize 函数用于调整 vector 的大小。如果 n 小于等于当前大小，则将 \_finish 指针移动到 \_start + n 的位置；如果 n 大于当前大小，则先调用 reserve 函数确保有足够的容量，然后使用 push\_back 函数将元素添加到 vector 中，直到大小达到 n。

==可参考下面两张图来理解resizeu对于不同的n所采取的不同处理方式==

当n小于等于size时

在这里插入图片描述

当n大于size时

包括两种情况，分别是size<n<capacity，以及n>capacity

两种处理结果稍有不同

在这里插入图片描述

5.5 reserve 函数

void reserve(size\_t n)

{

    if (n > capacity())

    {



        size\_t size = \_finish - \_start;//提前存下size防止迭代器失效

        T\* tmp = new T[n];



        if (\_start)//如果原空间不为空，则拷贝数据

        {

            for (size\_t i = 0; i < size; ++i)

            {

                tmp[i] = \_start[i];

            }

        }

        

        delete[]\_start;

        \_start = tmp;

        \_finish = \_start + size;

        \_endofstorage = \_start + n;

    }

}

**思路**：reserve 函数用于增加 vector 的容量。如果 n 大于当前容量，则分配一个新的内存空间，将原有的元素复制到新的内存空间中，然后释放原有的内存空间。在操作过程中，需要提前记录当前的大小，以避免迭代器失效。

==reserve、insert和erase的实现，涉及到迭代器失效的问题，限于本篇文章主题和篇幅限制，没法在此展开，故放到系列第三篇文章，单独来讲解==

如果对代码有不理解的地方可以直接点击链接跳转下一篇文章：

七、修改相关操作

6.1 push\_back 函数

void push\_back(const T& val)  //尾插

{

    if (\_finish == \_endofstorage)

    {

        reserve(capacity() == 0 ? 4 : 2 \* capacity());

    }

    \*(\_finish++) = val;



}

**思路**：push\_back 函数用于在 vector 的末尾添加一个元素。如果当前容量不足，则调用 reserve 函数进行扩容，然后将元素赋值给 \_finish 指针所指向的位置，并将 \_finish 指针向后移动一位。

6.2 pop\_back 函数

void pop\_back() //尾删

{

    assert(!empty());

    --\_finish;

}

**思路**：pop\_back 函数用于删除 vector 的最后一个元素。在删除之前，需要确保 vector 不为空，然后将 \_finish 指针向前移动一位。

6.3 insert 函数

void insert(iterator pos, const T& val) //插入  

{

    assert(pos >= begin()); //位置合法性判断

    assert(pos <= end());



    

    if (\_finish == \_endofstorage)//判断扩容

    {

        size\_t len = pos - begin();//提前存下pos相对位置，防止pos迭代器失效

        reserve(capacity() == 0 ? 4 : 2 \* capacity());

        pos = begin() + len;



    }



    iterator i = end();//挪动数据

    while (i != pos) 

    {

        \*i = \*(i - 1);

        --i;

    }



    \*pos = val;

    ++\_finish;

}

**思路**：insert 函数用于在指定位置插入一个元素。首先进行位置合法性检查，如果当前容量不足，则进行扩容操作。在扩容过程中，需要提前记录插入位置的相对位置，以避免迭代器失效。然后将插入位置之后的元素依次向后移动一位，最后将元素插入到指定位置，并将 \_finish 指针向后移动一位。

==可参考下面两张图来理解insert的过程==

1.首先判断是否需要扩容

2.然后需要判断和挪动数据（因为vector底层是基于顺序表的原理实现的）

3.最后将空出来的位置插入数据 ，修改finish的值

在这里插入图片描述

挪动数据和插入

在这里插入图片描述

6.4 erase 函数

iterator erase(iterator pos)

{

    assert(pos >= begin());

    assert(pos < end());

    assert(!empty());



    iterator i = pos + 1;

    while (i != end())

    {

        \*(i - 1) = \*i;

        ++i;

    }

    --\_finish;

    return pos;



}

**思路**：erase 函数用于删除指定位置的元素。首先进行位置合法性检查，然后将删除位置之后的元素依次向前移动一位，最后将 \_finish 指针向前移动一位。函数返回指向删除位置的迭代器。

==可借助下面两张图来理解erase的过程==

`1.挪动数据

2.修改finish`

在这里插入图片描述

在这里插入图片描述

八、其他函数

7.1 swap 函数

void swap(vector<T> v)//两个vector对象的交换

{

    std::swap(\_start, v.\_start);

    std::swap(\_finish, v.\_finish);

    std::swap(\_endofstorage, v.\_endofstorage);

}

**思路**：swap 函数用于交换两个 vector 对象的内容。通过交换三个成员指针，实现了两个 vector 对象的快速交换。

九、实现亮点与注意事项

1. **深拷贝实现**：通过逐个元素赋值确保自定义类型正确拷贝,再次重申一句在C++中所有容器相关的拷贝中，都要用深拷贝来代替浅拷贝。
2. **异常安全**：采用“拷贝 - 交换”模式保证赋值操作的原子性。
3. **迭代器安全**：在扩容时通过记录相对位置保持迭代器有效性（具体实现细节将在后续文章深入解析）。

结尾总结

本文通过自主实现的 xc::vector 类，展示了动态数组容器的核心实现技术。

需要特别注意的是，虽然当前实现通过记录相对位置等手段初步解决了迭代器失效问题，但不同操作（如 reserve、insert、erase）引发的迭代器失效机制与应对策略仍需深入探讨。建议读者持续关注后续文章《，我们将结合具体代码与测试用例，系统分析迭代器失效的根本原因及解决方案。

提示：在实际开发中，建议优先使用标准库 std::vector。若需自定义实现，务必严格遵循 C++ 对象生命周期管理规则，并通过单元测试验证关键功能。