【c++篇】:深入剖析vector--模拟实现属于自己的c++动态数组
✨感谢您阅读本篇文章,文章内容是个人学习笔记的整理,如果哪里有误的话还请您指正噢✨
✨ 个人主页:余辉zmh–CSDN博客
✨文章所属专栏:c++篇–CSDN博客
文章目录
- 前言
- 一.`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<class T>class vector{public:typedef T* iterator;//成员函数private://成员变量iterator _start;iterator _finish;iterator _endofstorage;};
}
实现原理:
-
和
string
类不同的是,vector是模版类,vector中不仅可以存储内置类型的数据,对于我们自己设置的自定义类型数据也可以存储,因此需要使用模版。 -
用typedef 关键字重定义T类型,因为vector中不管是成员变量还是之后需要用到的迭代器都是T类型(就是指针类型),所以直接重定义为迭代器类型名iterator。
-
_start指针指向的是数组的首元素位置,_finish指针指向的是数组最后一个元素的下一个位置,而_endofstorage指针指向的是数组空间最后的位置。
-
如图所示:
构造函数
vector类中用多种构造函数的重载,这里我们主要实现三种常用的构造函数:
-
无参构造函数:
代码实现:
vector() :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) {cout<<"vector()"<<endl; }
-
带参构造函数:
1.代码实现:
vector(int n, const T& val = T()) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) {resize(n, val); }
2.实现原理:
-
n表示指定数量大小需要存储多少个元素,val表示需要存储的数据
-
T()是匿名对象缺省值,如果T是自定义类型会调用对应的构造函数创建匿名对象,而c++对内置类型进行了升级,也可以使用构造函数初始化,比如:
int i=0; int j=int(); int k=int(1);
-
直接调用resize()函数(该函数在后面讲解),对空数组开辟空间的同时,将数据val填充到新的空间。
-
-
迭代器区间构造函数:
1.代码实现:
template<class inputiterator> vector(inputiterator first,inputiterator last) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) {while(first!=last){push_back(*first);first++;} }
2.实现原理:
-
这里使用函数模版是因为对于迭代器的类型我们并不确定,可能是一个数组,也可能是string类型的迭代器所以这里使用函数模版来代替具体的类型,调用函数时,编译器会根据具体的类型来推演具体的函数。
-
_first表示迭代器的起始位置,_last表示迭代器的终止位置。
-
调用push_back()函数直接将需要存储的数据插入到vector对象中。
-
如图所示:
-
析构函数
析构函数比较简单,如果_start指针不为空指针,表示有空间需要释放,直接调用delete函数释放空间,再将三个指针置为空即可,没有什么需要注意的地方,这里直接展示代码实现:
~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(); }
-
实现原理:
-
拷贝构造是用一个已经存在的对象拷贝创建一个新的对象,所以首先是调用new函数开辟新的空间,空间大小是被拷贝对象容量。
-
接下来就是拷贝数据,这里和模拟实现stirng类不同的是,string类可以使用memcpy函数直接拷贝所有数据,而vector类这里有所不同,如果vector数组中存储的是string类型的对象,直接使用memcpy会完成浅拷贝,而string类型是自定义类型,拷贝数据需要完成深拷贝,否则会产生一系列错误(具体可以看string模拟实现那篇文章,有详细的讲解深拷贝),所以这里需要一个一个拷贝数据,实现拷贝构造。
-
拷贝完数据后,_finish指针指向最后一个元素的位置,_endofstorage指针指向数组空间最后的位置。
-
如图所示:
-
赋值运算符重载函数
-
代码实现:
//现代写法 void Swap(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; }
-
实现原理:
- 赋值拷贝是用一个已经存在的对象赋值给另一个已经存在的对象。
- 使用现代写法直接交换两个对象的三个指针,让他们分别指向另一个空间
测试
测试代码:
void test1()
{//指定数量和数值构造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赋值给v4Myvector::vector<int> v4=v1;for(auto e:v4){cout<<e<<" ";}cout<<endl;
}
测试结果:
二.vector
类的访问和迭代器相关函数
访问函数
访问函数operator[]
:
-
代码实现:
//普通对象访问函数 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]; }
-
实现原理:
- 断言判断pos位置是否符合范围。
- 符合范围后直接返回数组中对应位置元素即可
迭代器函数
vector类的迭代器模拟实现较为简单,begin()函数直接返回_start指针,end()函数直接返回_finish指针即可。
类型定义:
//普通对象迭代器类型
typedef T* iterator;
//const对象迭代器类型
typedef const 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; }
测试
测试代码:
void test2()
{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()函数:
-
代码实现:
size_t size()const {return _finish-_start; }
-
实现原理:
_finsih指针指向的是数组做后一个元素,直接减去_start指针,就是数组实际存储的元素个数
capacity()函数:
-
代码实现:
size_t capacity()const {return _endofstorage-_start; }
-
实现原理:
_endofstorage指针指向的是数组空间最后的位置,直接减去_start指针,就是整个数组的容量
扩容函数
reserve()函数:
-
代码实现:
void reserve(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;} }
-
实现原理:
- 首先判断需要扩容的大小n是否大于原数组的容量,如果大于就进行扩容,小于则保持不变。
- 扩容时,开辟新的空间,空间大小为参数n,设置一个新的指针tmp指向新的空间。
- 开辟新空间后判断原数组的_start指针是否为空,如果为空,表示原数组是空,不需要拷贝数据,不为空则需要进行拷贝数据。这里的拷贝数据和拷贝构造函数那里一样,如果T是自定义类型时,直接使用memcpy函数会完成数据的浅拷贝,而自定义类型必须是深拷贝,所以这里也需要一个一个的拷贝每个数据元素。拷贝完后释放原来的数组空间。
- _start指针指向新的空间,_finish指针加上最开始保存的size(),如果没有保存,直接调用size()函数,会发生错误,因为原空间中的_start指针已经指向新的空间。_endofstorage指针加上新的容量大小n
resize()函数:
-
代码实现:
void resize(size_t n,const T& val=T()){if(n<size()){_finish=_start+n;}else{reserve(n);while(_finish!=_start+n){*_finish=val;_finish++;}} }
-
实现原理:
- 如果n小于原数组的大小则发生截断。
- 如果n大于原数组的大小进行扩容,扩容直接调用reserve()函数,扩容后,从_finish指针当前位置开始遍历,将val数据填充到新空间中,同时更改_finish指针的位置,指向新的位置。
- 图片:
测试
测试代码:
void test3()
{//创建对象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()函数扩容到8v.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()函数:
-
代码实现:
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; }
-
实现原理:
- 首先断言判断pos指针是否符合范围,pos指针指向的位置需要在_start指针和_finish指针中间
- 然后判断是否需要扩容,扩容前需要先计算并保存pos指针到_start指针的大小,然后调用reserve()函数进行扩容,扩容后从新更改pos指针,让它指向新空间中的位置(这里是涉及到迭代器失效问题,在本文的后面会重点讲解)
- 扩容后就是开始移动数据,将pos位置后面的数据都往后移动一位,具体过程看代码实现
- 移动数据后,将需要插入的数据插入到pos位置,然后_finish指针后移一位,最后返回pos指针,相当于返回当前插入的位置。
push_back()函数:
-
代码实现:
void push_back(const T& x){insert(end(),x); }
-
实现原理:
直接调用insert()函数,相当于在数组的最后位置也就是end()位置插入数据。
删除函数
erase()函数:
-
代码实现:
iterator erase(iterator pos){assert(pos>=_start&&pos<=_finish);iterator it=pos+1;while(it!=_finish){*(it-1)=*it;it++;}_finish--;return pos; }
-
实现原理:
- 首先断言判断pos指针是否符合范围,pos指针指向的位置需要在_start指针和_finish指针中间
- 然后设置一个新的指针it用来遍历数组,将pos位置后面的数据依次往前移动一位
- _finish–,表示删除一个元素,最后返回pos指针,相当于返回当前删除的位置。
pop_back()函数:
-
代码实现:
void pop_back(){erase(end()--); }
-
实现原理:
直接调用erase()函数,相当于删除数组最后一个位置的元素,也就是end()前一个位置
测试
测试代码:
void test4()
{//创建对象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中的有效元素,因此迭代器会失效。
这就是为什么在insert函数中,扩容前需要先计算pos位置指针到_start指针的大小,扩容后再从新更新pos指针,因为扩容导致底层空间的改变,之前获取的迭代器pos指针没有指向新空间对应的位置。
-
指定位置的插入和删除:
-
在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
-
删除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,5vector<int>::iteraot rit=v.begin()+4; //删除前迭代器rit指向5 rit=erase(rit); //删除后rit指向的是end()迭代器,此时迭代器rit失效
-
避免迭代器失效的方法
- 对于扩容引起的失效:在调用可能导致扩容的函数(如push_back、insert等)后,应重新获取迭代器。
- 对于插入和删除引起的失效:使用insert函数时,应接收其返回的迭代器作为新的有效迭代器;在使用erase函数删除元素后,同样应接收其返回的迭代器作为继续遍历的起点。
示例代码分析
以下是一个简单的示例,展示了在vector中插入元素后迭代器失效的情况:
void test5() {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>
using namespace std;
namespace Myvector
{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():_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<class inputiterator>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();}void Swap(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];}void reserve(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);void resize(size_t n,const T& val=T()){if(n<size()){_finish=_start+n;}else{reserve(n);while(_finish!=_start+n){*_finish=val;_finish++;}}}void push_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;}void pop_back(){erase(end()-1);}private:iterator _start;iterator _finish;iterator _endofstorage;};
}
test.cpp
文件
#include"vector.h"void test1()
{//指定数量和数值构造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赋值给v4Myvector::vector<int> v4=v1;for(auto e:v4){cout<<e<<" ";}cout<<endl;
}void test2()
{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;
}void test3()
{//创建对象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()函数扩容到8v.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;}void test4()
{//创建对象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;}void test5() {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;
}int main()
{//test1();//test2();//test3();//test4();test5();return 0;
}
以上就是关于如何模拟实现vector类的讲解,如果哪里有错的话,可以在评论区指正,也欢迎大家一起讨论学习,如果对你的学习有帮助的话,点点赞关注支持一下吧!!!