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

.💓 博客主页：倔强的石头的ZEEKLOG主页
📝Gitee主页：倔强的石头的gitee主页
⏩ 文章专栏：《C++指南》
期待您的关注

文章目录

• 一、引言
• 二、成员变量
• 三、默认成员函数
  • 2.1 默认构造函数
  • 2.2 析构函数
  • 2.3 拷贝构造函数
    • 传统写法
    • 现代写法
  • 2.4 赋值重载函数
    • 传统写法
    • 现代写法
• 四、元素访问相关
  • 3.1 `[]` 重载（非 `const` 版本）
  • 3.2 `[]` 重载（`const` 版本）
• 五、迭代器相关
  • 4.1 迭代器类型声明
  • 4.2 `begin` 函数
  • 4.3 `end` 函数
  • 4.4 `cbegin` 函数
  • 4.5 `cend` 函数
• 六、容量相关函数
  • 5.1 `size` 函数
  • 5.2 `capacity` 函数
  • 5.3 `empty` 函数
  • 5.4 `resize` 函数
  • 5.5 `reserve` 函数
• 七、修改相关操作
  • 6.1 `push_back` 函数
  • 6.2 `pop_back` 函数
  • 6.3 `insert` 函数
  • 6.4 `erase` 函数
• 八、其他函数
  • 7.1 `swap` 函数
• 九、实现亮点与注意事项
• 结尾总结

一、引言

在 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;typedefconst 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 函数

boolempty(){return _start == _finish;}

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

5.4 resize 函数

voidresize(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 函数

voidreserve(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 函数

voidpush_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 函数

voidpop_back()//尾删{assert(!empty());--_finish;}

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

6.3 insert 函数

voidinsert(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 函数

voidswap(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++ 对象生命周期管理规则，并通过单元测试验证关键功能。