【c++篇】：深入剖析vector--模拟实现属于自己的c++动态数组

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–ZEEKLOG博客
✨文章所属专栏：c++篇–ZEEKLOG博客

文章目录

• 前言
• 一.`vector`类的默认成员函数
  • 整体框架
  • 构造函数
  • 析构函数
  • 拷贝构造函数
  • 赋值运算符重载函数
  • 测试
• 二.`vector`类的访问和迭代器相关函数
  • 访问函数
  • 迭代器函数
  • 测试
• 三.`vector`类的容量相关函数
  • 容量大小函数
  • 扩容函数
  • 测试
• 四.`vector`类的修改相关函数
  • 插入函数
  • 删除函数
  • 测试
• 五.迭代器失效问题
  • 迭代器失效的原因
  • 避免迭代器失效的方法
  • 示例代码分析
  • 总结
• 六.完整代码文件
  • `vector.h`文件
  • `test.cpp`文件

前言

在C++的世界中，标准模板库（STL）的vector容器因其灵活性和效率而广受欢迎。vector以其动态数组的形式，提供了快速访问和插入元素的能力，是许多程序员的得力工具。然而，当我们深入探究其内部机制时，会发现实现一个高效、健壮的vector并非易事。在这篇博客中，我们将一起踏上模拟实现vector的旅程。我们将从零开始，一步步构建一个属于我们自己的vector类。我们将探索vector的内部结构，理解其内存管理策略，并实现其核心功能，如push_back、pop_back、insert和erase等操作。

本次模拟实现需要用到两个文件：

test.cpp测试文件用来进行测试检验

vector.h头文件用来声明和定义

一.vector类的默认成员函数

整体框架

和之前模拟实现string一样，为了和库里面的std::vector进行区分，要定义一个命名空间用来封装我们自己模拟实现的vector，整体框架如下：

namespace Myvector{template<classT>classvector{public:typedef T* iterator;//成员函数private://成员变量 iterator _start; iterator _finish; iterator _endofstorage;};}

实现原理：

• 和string类不同的是，vector是模版类，vector中不仅可以存储内置类型的数据，对于我们自己设置的自定义类型数据也可以存储，因此需要使用模版。
• 用typedef 关键字重定义T类型，因为vector中不管是成员变量还是之后需要用到的迭代器都是T类型（就是指针类型），所以直接重定义为迭代器类型名iterator。
• _start指针指向的是数组的首元素位置，_finish指针指向的是数组最后一个元素的下一个位置，而_endofstorage指针指向的是数组空间最后的位置。
• 如图所示：

构造函数

vector类中用多种构造函数的重载，这里我们主要实现三种常用的构造函数：

• n表示指定数量大小需要存储多少个元素，val表示需要存储的数据
• 直接调用resize()函数（该函数在后面讲解），对空数组开辟空间的同时，将数据val填充到新的空间。
• 这里使用函数模版是因为对于迭代器的类型我们并不确定，可能是一个数组，也可能是string类型的迭代器所以这里使用函数模版来代替具体的类型，调用函数时，编译器会根据具体的类型来推演具体的函数。
• _first表示迭代器的起始位置，_last表示迭代器的终止位置。
• 调用push_back()函数直接将需要存储的数据插入到vector对象中。
• 如图所示：

迭代器区间构造函数：1.代码实现：

template<classinputiterator>vector(inputiterator first,inputiterator last):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){while(first!=last){push_back(*first); first++;}}

2.实现原理：

T()是匿名对象缺省值，如果T是自定义类型会调用对应的构造函数创建匿名对象，而c++对内置类型进行了升级，也可以使用构造函数初始化，比如：

int i=0;int j=int();int k=int(1);

带参构造函数：1.代码实现：

vector(int n,const T& val =T()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){resize(n, val);}

2.实现原理：

无参构造函数：代码实现：

vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){ cout<<"vector()"<<endl;}

析构函数

析构函数比较简单，如果_start指针不为空指针，表示有空间需要释放，直接调用delete函数释放空间，再将三个指针置为空即可，没有什么需要注意的地方，这里直接展示代码实现：

~vector(){ cout<<"~vector()"<<endl;if(_start){delete[] _start; _start=_finish=_endofstorage=nullptr;}}

拷贝构造函数

• 实现原理：
  • 拷贝构造是用一个已经存在的对象拷贝创建一个新的对象，所以首先是调用new函数开辟新的空间，空间大小是被拷贝对象容量。
  • 接下来就是拷贝数据，这里和模拟实现stirng类不同的是，string类可以使用memcpy函数直接拷贝所有数据，而vector类这里有所不同，如果vector数组中存储的是string类型的对象，直接使用memcpy会完成浅拷贝，而string类型是自定义类型，拷贝数据需要完成深拷贝，否则会产生一系列错误（具体可以看string模拟实现那篇文章，有详细的讲解深拷贝），所以这里需要一个一个拷贝数据，实现拷贝构造。
  • 拷贝完数据后，_finish指针指向最后一个元素的位置，_endofstorage指针指向数组空间最后的位置。
  • 如图所示：

代码实现：

vector(const vector<T>& v){ _start=new T[v.capacity()];for(size_t i=0;i<v.size();i++){ _start[i]=v._start[i];} _finish=_start+v.size(); _endofstorage=_start+v.capacity();}

赋值运算符重载函数

• 实现原理：
  • 赋值拷贝是用一个已经存在的对象赋值给另一个已经存在的对象。
  • 使用现代写法直接交换两个对象的三个指针，让他们分别指向另一个空间

代码实现：

//现代写法voidSwap(vector<T>& v){swap(_start,v._start);swap(_finish,v._finish);swap(_endofstorage,v._endofstorage);}//赋值运算符重载函数 vector<T>&operator=(vector<T> v){Swap(v);return*this;}

测试

测试代码：

voidtest1(){//指定数量和数值构造v1对象 Myvector::vector<int>v1(10,1);for(auto e:v1){ cout<<e<<" ";} cout<<endl;//用区间进行构造v2对象int array[]={1,2,3,4,5}; Myvector::vector<int>v2(array,array+5);for(auto e:v2){ cout<<e<<" ";} cout<<endl;//用v2对象拷贝构造v3对象 Myvector::vector<int>v3(v2);for(auto e:v3){ cout<<e<<" ";} cout<<endl;//构造空对象v4，并将对象v1赋值给v4 Myvector::vector<int> v4=v1;for(auto e:v4){ cout<<e<<" ";} cout<<endl;}

测试结果：

二.vector类的访问和迭代器相关函数

访问函数

访问函数operator[]:

• 实现原理：
  • 断言判断pos位置是否符合范围。
  • 符合范围后直接返回数组中对应位置元素即可

代码实现：

//普通对象访问函数 T&operator[](size_t pos){assert(pos<size());return _start[pos];}//const对象访问函数const T&operator[](size_t pos)const{assert(pos<size());return _start[pos];}

迭代器函数

vector类的迭代器模拟实现较为简单，begin()函数直接返回_start指针，end()函数直接返回_finish指针即可。

类型定义：

//普通对象迭代器类型typedef T* iterator;//const对象迭代器类型typedefconst T* const_iterator;

begin()函数:

代码实现：

iterator begin(){return _start;} const_iterator begin()const{return _start;}

end()函数：

代码实现：

iterator end(){return _finish;} const_iterator end()const{return _finish;}

测试

测试代码：

voidtest2(){ Myvector::vector<int>v(5,100);//下标+[]方式访问遍历for(size_t i=0;i<v.size();i++){ cout<<v[i]<<" ";} cout<<endl;//迭代器遍历 Myvector::vector<int>::iterator it=v.begin();while(it!=v.end()){ cout<<*it<<" "; it++;} cout<<endl;}

测试结果：

三.vector类的容量相关函数

容量大小函数

size()函数：

• 实现原理：_finsih指针指向的是数组做后一个元素，直接减去_start指针，就是数组实际存储的元素个数

代码实现：

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

capacity()函数：

• 实现原理：_endofstorage指针指向的是数组空间最后的位置，直接减去_start指针，就是整个数组的容量

代码实现：

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

扩容函数

reserve()函数：

• 实现原理：
  • 首先判断需要扩容的大小n是否大于原数组的容量，如果大于就进行扩容，小于则保持不变。
  • 扩容时，开辟新的空间，空间大小为参数n，设置一个新的指针tmp指向新的空间。
  • 开辟新空间后判断原数组的_start指针是否为空，如果为空，表示原数组是空，不需要拷贝数据，不为空则需要进行拷贝数据。这里的拷贝数据和拷贝构造函数那里一样，如果T是自定义类型时，直接使用memcpy函数会完成数据的浅拷贝，而自定义类型必须是深拷贝，所以这里也需要一个一个的拷贝每个数据元素。拷贝完后释放原来的数组空间。
  • _start指针指向新的空间，_finish指针加上最开始保存的size(),如果没有保存，直接调用size()函数，会发生错误，因为原空间中的_start指针已经指向新的空间。_endofstorage指针加上新的容量大小n

代码实现：

voidreserve(size_t n){if(n>capacity()){//先保存 size_t sz=size();//开新空间 iterator tmp=new T[n];//判断是否需要拷贝数据if(_start){for(size_t i=0;i<sz;i++){ tmp[i]=_start[i];}delete[] _start;}//更改指针，指向新的空间 _start=tmp; _finish=_start+sz; _endofstorage=_start+n;}}

resize()函数：

• 实现原理：
  • 如果n小于原数组的大小则发生截断。
  • 如果n大于原数组的大小进行扩容，扩容直接调用reserve()函数，扩容后，从_finish指针当前位置开始遍历，将val数据填充到新空间中，同时更改_finish指针的位置，指向新的位置。
  • 图片：

代码实现：

voidresize(size_t n,const T& val=T()){if(n<size()){ _finish=_start+n;}else{reserve(n);while(_finish!=_start+n){*_finish=val; _finish++;}}}

测试

测试代码：

voidtest3(){//创建对象v,依次插入5个字符串"vector" Myvector::vector<string> v;for(size_t i=0;i<5;i++){ v.push_back("vector");}//输出当前的大小和容量并遍历打印 cout<<v.size()<<" "<<v.capacity()<<endl;for(auto e:v){ cout<<e<<" ";} cout<<endl;//调用reserve()函数扩容到8 v.reserve(10);//输出当前的大小和容量 cout<<v.size()<<" "<<v.capacity()<<endl;//调用resize()函数扩容到10,并将新空间中插入字符串"string"//输出当前的大小和容量并遍历打印 v.resize(12,"string"); cout<<v.size()<<" "<<v.capacity()<<endl;for(auto e:v){ cout<<e<<" ";} cout<<endl;//调用resize()函数缩容到4，发生截断//输出当前的大小和容量并遍历打印 v.resize(6); cout<<v.size()<<" "<<v.capacity()<<endl;for(auto e:v){ cout<<e<<" ";} cout<<endl;}

测试结果：

四.vector类的修改相关函数

插入函数

insert()函数：

• 实现原理：
  • 首先断言判断pos指针是否符合范围，pos指针指向的位置需要在_start指针和_finish指针中间
  • 然后判断是否需要扩容，扩容前需要先计算并保存pos指针到_start指针的大小，然后调用reserve()函数进行扩容，扩容后从新更改pos指针，让它指向新空间中的位置（这里是涉及到迭代器失效问题，在本文的后面会重点讲解）
  • 扩容后就是开始移动数据，将pos位置后面的数据都往后移动一位，具体过程看代码实现
  • 移动数据后，将需要插入的数据插入到pos位置，然后_finish指针后移一位，最后返回pos指针，相当于返回当前插入的位置。

代码实现：

iterator insert(iterator pos,const T& x){assert(pos>=_start&&pos<=_finish);if(_finish==_endofstorage){ size_t len=pos-_start; size_t newcapacity=capacity()==0?4:2*capacity();reverse(newcapacity); pos=_start+len;} iterator end=_finish-1;while(end>=pos){*(end+1)=*end; end--;}*pos=x; _finish++;return pos;}

push_back()函数：

• 实现原理：直接调用insert()函数，相当于在数组的最后位置也就是end()位置插入数据。

代码实现：

voidpush_back(const T& x){insert(end(),x);}

删除函数

erase()函数：

• 实现原理：
  • 首先断言判断pos指针是否符合范围，pos指针指向的位置需要在_start指针和_finish指针中间
  • 然后设置一个新的指针it用来遍历数组，将pos位置后面的数据依次往前移动一位
  • _finish–，表示删除一个元素，最后返回pos指针，相当于返回当前删除的位置。

代码实现：

iterator erase(iterator pos){assert(pos>=_start&&pos<=_finish); iterator it=pos+1;while(it!=_finish){*(it-1)=*it; it++;} _finish--;return pos;}

pop_back()函数：

• 实现原理：直接调用erase()函数，相当于删除数组最后一个位置的元素，也就是end()前一个位置

代码实现：

voidpop_back(){erase(end()--);}

测试

测试代码：

voidtest4(){//创建对象v,依次插入5个字符串"vector" Myvector::vector<string> v;for(size_t i=0;i<5;i++){ v.push_back("vector");}for(auto e:v){ cout<<e<<" ";} cout<<endl; v.insert(v.begin()+2,"string");for(auto e:v){ cout<<e<<" ";} cout<<endl; v.erase(v.begin()+4);for(auto e:v){ cout<<e<<" ";} cout<<endl;}

测试结果：

五.迭代器失效问题

在C++的vector中，迭代器失效是一个需要注意的重要问题。迭代器失效主要发生在vector的底层空间发生改变的情况下，这通常是由于vector的扩容或者指定位置的元素插入或者删除操作引起的。

迭代器失效的原因

• 当vector需要增加元素，而当前分配的空间不足以容纳新元素时，vector会进行扩容。扩容通常涉及分配一个新的、更大的数组，并将原数组中的元素复制到新数组中。
• 由于底层空间的改变，之前获取的迭代器将不再指向vector中的有效元素，因此迭代器会失效。
1. 指定位置的插入和删除：

删除vector中指定位置的元素时，虽然不会总是导致扩容，但删除操作会使得被删除元素之后的元素向前移动一个位置。如果删除的是最后一个元素，那么指向该元素的迭代器在删除后会变为指向end()的迭代器，而end()迭代器并不指向有效元素，因此也可以认为迭代器失效。

vector<int> v={1,2,3,4,5}; vector<int>::iterator it=v.begin()+2;//删除前迭代器it指向2 it=erase(it);//删除后迭代器it指向3，因为2已经被删除//v:1,3,4,5 vector<int>::iteraot rit=v.begin()+4;//删除前迭代器rit指向5 rit=erase(rit);//删除后rit指向的是end()迭代器，此时迭代器rit失效

在vector的指定位置插入元素时，如果插入位置不是vector的末尾，且插入后导致vector需要扩容，那么迭代器会失效。

vector<int> v={1,2,3,4,5}; vector<int>::iterator it=v.begin()+3;//在3之前插入100//插入前迭代器it指向3 it=insert(it,100);//插入后迭代器it不再指向3,而是插入的100//v:1,2,100,3,4,5

扩容操作：这就是为什么在insert函数中，扩容前需要先计算pos位置指针到_start指针的大小，扩容后再从新更新pos指针，因为扩容导致底层空间的改变，之前获取的迭代器pos指针没有指向新空间对应的位置。

避免迭代器失效的方法

• 对于扩容引起的失效：在调用可能导致扩容的函数（如push_back、insert等）后，应重新获取迭代器。
• 对于插入和删除引起的失效：使用insert函数时，应接收其返回的迭代器作为新的有效迭代器；在使用erase函数删除元素后，同样应接收其返回的迭代器作为继续遍历的起点。

示例代码分析

以下是一个简单的示例，展示了在vector中插入元素后迭代器失效的情况：

voidtest5(){ Myvector::vector<int> vec; vec.push_back(0); vec.push_back(1); vec.push_back(2); vec.push_back(3); vec.push_back(4); Myvector::vector<int>::iterator it = vec.begin();while(it != vec.end()){if(*it %2==0){ vec.insert(it,5);// 在迭代器it指向的位置插入元素5++it;// 由于insert可能改变底层空间，需要重新更新迭代器}++it;}for(auto e:vec){ cout<<e<<" ";} cout<<endl;}

在上面的代码中，如果在insert操作后没有重新更新迭代器it，那么it可能会指向一个已经失效的位置，从而导致未定义的行为。

总结

在使用vector的迭代器时，需要注意扩容和指定位置插入/删除操作可能导致的迭代器失效问题。为了避免这些问题，应在这些操作后重新获取迭代器。同时，在编写涉及vector迭代器的代码时，应谨慎处理迭代器的有效性，以避免程序崩溃或未定义行为的发生。

六.完整代码文件

vector.h文件

#include<iostream>#include<string>#include<algorithm>#include<assert.h>usingnamespace std;namespace Myvector {template<classT>classvector{public:typedef T* iterator;typedefconst T* const_iterator; iterator begin(){return _start;} iterator end(){return _finish;} const_iterator begin()const{return _start;} const_iterator end()const{return _finish;}//只要是构造函数一定要用初始化列表给成员变量初始化，自定义类型用初始化列表初始化，内置类型可以在声明中给缺省值//普通构造函数vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){ cout<<"vector()"<<endl;}//n个val的构造函数vector(size_t n,const T& val =T()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){resize(n, val);}vector(int n,const T& val =T()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){resize(n, val);}template<classinputiterator>vector(inputiterator first,inputiterator last):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){while(first!=last){push_back(*first); first++;}}//析构函数~vector(){ cout<<"~vector()"<<endl;if(_start){delete[] _start; _start=_finish=_endofstorage=nullptr;}}//拷贝构造函数vector(const vector<T>& v){ _start=new T[v.capacity()];for(size_t i=0;i<v.size();i++){ _start[i]=v._start[i];} _finish=_start+v.size(); _endofstorage=_start+v.capacity();}voidSwap(vector<T>& v){swap(_start,v._start);swap(_finish,v._finish);swap(_endofstorage,v._endofstorage);}//赋值运算符重载函数 vector<T>&operator=(vector<T> v){Swap(v);return*this;} size_t size()const{return _finish-_start;} size_t capacity()const{return _endofstorage-_start;} T&operator[](size_t pos){assert(pos<size());return _start[pos];}const T&operator[](size_t pos)const{assert(pos<size());return _start[pos];}voidreserve(size_t n){if(n>capacity()){ size_t sz=size(); T* tmp=new T[n];if(_start){//这里拷贝数据时，如果T是自定义类型，比如sring，直接使用memcpy会是浅拷贝，所以要用赋值深拷贝for(size_t i=0;i<sz;i++){ tmp[i]=_start[i];}delete[] _start;} _start=tmp; _finish=_start+sz; _endofstorage=_start+n;}}//T()是匿名对象缺省值，如果T是自定义类型会调用对应的构造函数创建匿名对象//c++对内置类型进行了升级，也可以使用构造函数初始化//int i=0; int j=int(); int k=int(1);voidresize(size_t n,const T& val=T()){if(n<size()){ _finish=_start+n;}else{reserve(n);while(_finish!=_start+n){*_finish=val; _finish++;}}}voidpush_back(const T& x){/*if(_finish==_endofstorage){ size_t newcpacity=capacity()==0?4:2*capacity(); reserve(newcpacity); } *_finish=x; _finish++;*/insert(end(),x);} iterator insert(iterator pos,const T& x){assert(pos >= _start && pos <= _finish);//先记录pos的位置，防止扩容后迭代器失效if(_finish==_endofstorage){ size_t len=pos-_start; size_t newcapacity=capacity()==0?4:2*capacity();reserve(newcapacity); pos=_start+len;}//扩容后，更新pos的位置，让po指向新的空间中的位置 iterator end=_finish-1;while(end>=pos){*(end+1)=*end; end--;}*pos=x;++_finish;return pos;} iterator erase(iterator pos){assert(pos>=_start&&pos<=_finish); iterator it=pos+1;while(it!=_finish){*(it-1)=*it; it++;} _finish--;return pos;}voidpop_back(){erase(end()-1);}private: iterator _start; iterator _finish; iterator _endofstorage;};}

test.cpp文件

#include"vector.h"voidtest1(){//指定数量和数值构造v1对象 Myvector::vector<int>v1(10,1);for(auto e:v1){ cout<<e<<" ";} cout<<endl;//用区间进行构造v2对象int array[]={1,2,3,4,5}; Myvector::vector<int>v2(array,array+5);for(auto e:v2){ cout<<e<<" ";} cout<<endl;//用v2对象拷贝构造v3对象 Myvector::vector<int>v3(v2);for(auto e:v3){ cout<<e<<" ";} cout<<endl;//构造空对象v4，并将对象v1赋值给v4 Myvector::vector<int> v4=v1;for(auto e:v4){ cout<<e<<" ";} cout<<endl;}voidtest2(){ Myvector::vector<int>v(5,100);//下标+[]方式访问遍历for(size_t i=0;i<v.size();i++){ cout<<v[i]<<" ";} cout<<endl;//迭代器遍历 Myvector::vector<int>::iterator it=v.begin();while(it!=v.end()){ cout<<*it<<" "; it++;} cout<<endl;}voidtest3(){//创建对象v,依次插入5个字符串"vector" Myvector::vector<string> v;for(size_t i=0;i<5;i++){ v.push_back("vector");}//输出当前的大小和容量并遍历打印 cout<<v.size()<<" "<<v.capacity()<<endl;for(auto e:v){ cout<<e<<" ";} cout<<endl;//调用reserve()函数扩容到8 v.reserve(10);//输出当前的大小和容量 cout<<v.size()<<" "<<v.capacity()<<endl;//调用resize()函数扩容到10,并将新空间中插入字符串"string"//输出当前的大小和容量并遍历打印 v.resize(12,"string"); cout<<v.size()<<" "<<v.capacity()<<endl;for(auto e:v){ cout<<e<<" ";} cout<<endl;//调用resize()函数缩容到4，发生截断//输出当前的大小和容量并遍历打印 v.resize(6); cout<<v.size()<<" "<<v.capacity()<<endl;for(auto e:v){ cout<<e<<" ";} cout<<endl;}voidtest4(){//创建对象v,依次插入5个字符串"vector" Myvector::vector<string> v;for(size_t i=0;i<5;i++){ v.push_back("vector");}for(auto e:v){ cout<<e<<" ";} cout<<endl; v.insert(v.begin()+2,"string");for(auto e:v){ cout<<e<<" ";} cout<<endl; v.erase(v.begin()+4);for(auto e:v){ cout<<e<<" ";} cout<<endl;}voidtest5(){ Myvector::vector<int> vec; vec.push_back(0); vec.push_back(1); vec.push_back(2); vec.push_back(3); vec.push_back(4); Myvector::vector<int>::iterator it = vec.begin();while(it != vec.end()){if(*it %2==0){ vec.insert(it,5);// 在迭代器it指向的位置插入元素5++it;// 由于insert可能改变底层空间，需要重新更新迭代器}++it;}for(auto e:vec){ cout<<e<<" ";} cout<<endl;}intmain(){//test1();//test2();//test3();//test4();test5();return0;}

以上就是关于如何模拟实现vector类的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！