C++模拟实现vector的方法(C++,vector,开发技术)

1. 模拟实现vector

我们模拟实现是为了加深对这个容器的理解，不是为了造更好的轮子。

快速搭一个vector的架子

//vector.h#pragmaonce#include<assert.h>//模拟实现--加深对这个容器理解，不是为了造更好的轮子namespaceYuucho{ template<classT> classvector { public: typedefT*iterator; typedefconstT*const_iterator; vector() :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) {}//迭代器区间来构造，用模板的原因是存储的类型多种多样template<classInputIterator> vector(InputIteratorfirst,InputIteratorlast) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { while(first!=last) { push_back(*first); ++first; } }//用n个T去构造，但是会隐藏匹配问题vector(size_tn,constT&val=T()) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { reserve(n); for(size_ti=0;i<n;++i) { push_back(val); } }voidswap(vector<T>&v) { std::swap(_start,v._start); std::swap(_finish,v._finish); std::swap(_endofstorage,v._endofstorage); }//拷贝构造函数vector(constvector<T>&v) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { vector<T>tmp(v.begin(),v.end()); swap(tmp); } //拷贝赋值函数 vector<T>&operator=(vector<T>v) { swap(v); return*this; }//资源管理~vector(){if(_start){delete[]_start;_start=_finish=_endofstorage=nullptr;}} iteratorbegin() { return_start; } iteratorend() { return_finish; } const_iteratorbegin()const { return_start; } const_iteratorend()const { return_finish; } //默认是内联，频繁调用不用担心栈帧消耗 size_tsize()const { return_finish-_start; } size_tcapacity()const { return_endofstorage-_start; } voidreserve(size_tn) { } //voidresize(size_tn,constT&val=T()) voidresize(size_tn,Tval=T()) { } voidpush_back(constT&x) { } voidpop_back() { } T&operator[](size_tpos) { assert(pos<size()); return_start[pos]; } constT&operator[](size_tpos)const { assert(pos<size()); return_start[pos]; } iteratorinsert(iteratorpos,constT&x) { }voidclear(){_finish=_start;} private: iterator_start; iterator_finish; iterator_endofstorage; };}

2. vector常用接口

2.1 reserve

跟string的扩容思路一样。一般不考虑缩容(n<capacity)，因为这是时间换空间的做法，我们要的是效率。

错误代码:

voidreserve(size_tn){//一般不考虑缩容(n<capacity)if(n>capacity()){T*tmp=newT[n]; //capacity为0,n就是4(_endofstorage、_start都为nuptr)//有数据才拷贝if(_start){memcpy(tmp,_start,size()*sizeof(T)); delete[]_start;}_start=tmp;//注意,这里start位置变了}//更新_finish、_endofstorage_finish=_start+size();//size():_finish-_start,_finish还是空指针_endofstorage=_start+capacity;//capacity起始为0,也不对}

修正后的代码:

voidreserve(size_tn){//记录sizesize_tsz=size();if(n>capacity()){T*tmp=newT[n];if(_start){//memcpy还会隐藏更深层次的深浅拷贝问题，讲解在最后memcpy(tmp,_start,size()*sizeof(T)); delete[]_start;}_start=tmp;//注意,这里start位置变了}//更新_finish、_endofstorage_finish=_start+sz;_endofstorage=_start+n;}

2.2 resize

resize是开空间+初始化，size_type就是size_t，value_type就是T。

C++模板出来了语法就必须支持内置类型的默认构造、析构函数。

int() // 默认构造是0
double() // 默认构造是0.0
int*() // 默认构造是nullptr

思路与string一样

//voidresize(size_tn,constT&val=T())严格的编译器编不过,它认为T是临时对象//按照库里的写法voidresize(size_tn,Tval=T())//T类型的匿名对象，默认构造函数很重要,内置类型咋办？{if(n>capacity()) { reserve(n); } if(n>size()){ while(_finish<_start+n) { *_finish=val; ++_finish; } }//n<capacity就是删除数据 else { _finish=_start+n; }}

2.3 push_back

voidpush_back(constT&x){//满了先扩容if(_finish==_endofstorage){size_tnewCapacity=capacity()==0?4:capacity()*2;reserve(newCapacity);}//插入数据*_finish=x;++_finish;}

复用insert:

voidpush_back(constT&x){insert(end(),x);}

2.4 pop_back()

voidpop_back(){//如果不为空if(_finish>_start){--_finish;}}

复用erase:

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

2.5 insert

库里面的insert是带返回值的，我们先不管，先写一个没有返回值的看看。

voidinsert(iteratorpos,constT&x){ //检查参数 assert(pos>=_start&&pos<=_finish); //扩容 if(_finish==_endofstorage) { size_tnewCapacity=capacity()==0?4:capacity()*2; reserve(newCapacity); } //挪动数据 iteratorend=_finish-1; while(end>=pos) { *(end+1)=*end; --end; } *pos=x; ++_finish;}

(1) 迭代器失效第一种场景

yeahbaby，现在我们就可以来讲讲迭代器失效的问题了，嘿嘿嘿。

如果插入时没有扩容，ok，那还好说，没有问题。

如果扩容了，reserve会去更新_start和_finish，而不会去更新pos(pos还是会指向旧空间，迭代器发生了野指针问题)。在VS环境下，会用断言暴力检查出来的。在Linux环境下，检查不出来这种情况，甚至对原来的it仍然可读可写。

ok，那我们在扩容时更新一下pos：

if(_finish==_endofstorage){ size_tn=pos-_start; size_tnewCapacity=capacity()==0?4:capacity()*2; reserve(newCapacity); pos=_start+n;}

(2)另一种场景

 voidtest_vector1() { //在所有的偶数的前面插入2 vector<int>v; //v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); vector<int>::iteratorit=v.begin(); while(it!=v.end()) { if(*it%2==0) { it=v.insert(it,20); ++it; } ++it; } for(autoe:v) { cout<<e<<""; } cout<<endl; }}

运行结果

导致断言错误的原因是啥？为什么不能在2的前面插入20？

同样的道理，虽然我们修正了pos，但是我们是值传递，形参不会改变实参。所以it仍然是野指针。在VS环境下，会用断言暴力检查出来的。在Linux环境下，检查不出来这种情况，甚至对原来的it仍然可读可写。

有小伙伴就会说了，传引用不就行了吗？

我们是不会用引用的，官方库也没有用引用。因为我要传的是像v.begin()这样的临时对象怎么办。

更悲伤的是就算我提前把空间给你开好，保证插入时不需要扩容还是会出现问题。因为insert是在2之前插入20，++it后it仍指向2，这样就导致不断地在2之前插入20。这也是迭代器失效的一种场景。

修正后的代码:

用返回值解决，官方库里返回的是指向新插入的第一个元素的迭代器。 那我们也这样返回。

iteratorinsert(iteratorpos,constT&x){ //检查参数 assert(pos>=_start&&pos<=_finish); //扩容 //扩容以后pos就失效了,需要更新一下 if(_finish==_endofstorage) { size_tn=pos-_start; size_tnewCapacity=capacity()==0?4:capacity()*2; reserve(newCapacity); pos=_start+n; } //挪动数据 iteratorend=_finish-1; while(end>=pos) { *(end+1)=*end; --end; } *pos=x; ++_finish; returnpos;}

此时我们这样使用就行：

while(it!=v.end()){if(*it%2==0){//返回新插入的第一个元素的迭代器it=v.insert(it,20);//还是指向2++it;}//指向2的后一位++it;}

运行结果

2.6 erase

一般vector删除数据，都不考虑缩容的方案。

缩容方案：size() < capacity()/2时，可以考虑开一个size()大小的空间，拷贝数据，释放旧空间。

缩容方案本质是时间换空间。一般设计都不会考虑缩容，因为实际比较关注时间效率，不关注空间效率，因为现在硬件设备空间都比较大，空间存储也比较便宜。

我们这里不考虑缩容方案。

erase返回最后一个被释放元素的后一个元素的新位置。

iteratorerase(iteratorpos){ assert(pos>=_start&&pos<_finish); iteratorit=pos+1; while(it!=_finish) { *(it-1)=*it; ++it; } //erase最后一个数据，则pos==_finish，pos真失效了，但仍然属于这个容器 --_finish; returnpos;}

VS中的vector也没有考虑缩容方案，但是它对pos(如果缩容，pos就是野指针)进行了断言检查，不允许访问和写入。

(1)erase迭代器的失效都是意义变了，或者不在有效访问数据的范围。

(2)一般不会使用缩容的方案，那么erase的失效，一般也不存在野指针的失效。

erase(pos)以后pos失效了，pos的意义变了，但是不同平台下面对访问pos的反应不一样。VS会强制检查，Linux则没有严格的检查机制。我们用的时候一定要小心，统一以失效角度去看待。

erase迭代器意义变了的场景(假设我们要删除容器中的偶数)：

2.7 构造函数的匹配问题

迭代器区间的构造函数的参数要求是同类型的，而第一个构造函数的第一个参数是size_t，int会涉及隐式类型转换。所以参数为(10,2)的会匹配迭代器区间的构造函数，而参数为(10, &lsquo;x&rsquo;)的会匹配第一个构造函数。

这里就会导致int类型被当作迭代器解引用，本质上是发生了构造函数的错配问题。

解决方法：

源码是通过再写一个第一个参数为int类型的构造函数来解决的。

vector(intn,constT&val=T()) :_start(nullptr) ,_finish(nullptr) ,_endofstoage(nullptr) { reserve(n); for(inti=0;i<n;++i) { push_back(val); } }

3. 更深层次的深浅拷贝问题

以杨辉三角为例：

classSolution{public:vector<vector<int>>generate(intnumRows){vector<vector<int>>vv;//先开辟杨辉三角的空间vv.resize(numRows);//初始化每一行for(size_ti=0;i<numRows;++i){//每行个数依次递增vv[i].resize(i+1,0);//每一行的第一个和最后一个都是1vv[i][0]=1;vv[i][vv[i].size()-1]=1;}for(size_ti=0;i<vv.size();++i){for(size_tj=0;j<vv[i].size();++j){if(vv[i][j]==0){//之间位置等于上一行j-1和j个相加vv[i][j]=vv[i-1][j-1]+vv[i-1][j];}}}returnvv;}};

我们自己写的vector去跑这里的杨辉三角会出现问题。

voidtest_vector2(){ vector<vector<int>>ret=Solution().generate(5); for(size_ti=0;i<ret.size();++i) { for(size_tj=0;j<ret[i].size();++j) { cout<<ret[i][j]<<""; } cout<<endl; } cout<<endl;}

为了方便大家理解，我们把扩容的代码拿下来。

voidreserve(size_tn){//记录sizesize_tsz=size();if(n>capacity()){T*tmp=newT[n];if(_start){memcpy(tmp,_start,size()*sizeof(T)); delete[]_start;}_start=tmp;//注意,这里start位置变了}//更新_finish、_endofstorage_finish=_start+sz;_endofstorage=_start+n;}

vector<vector<int>> ret = Solution().generate(5);会去调用拷贝构造，拷贝构造又去调用了迭代器的区间构造函数，迭代器区间构造函数又去调用了push_back，push_back又去调用了reserve。

因为push_back我们第一次开的空间是4，所以前4次的push_back都不会有问题，第5次push_back去调用reserve时就会出现问题。

因为扩容的时候tmp会把前4组的vector<int>数据memcpy下来，而memcpy是浅拷贝，拷贝下来的数据和原来的数据指向的是同一块空间。关键是memcpy后又delete了旧空间，导致插入第5个vector<int>时前4组的数据被释放了，成了野指针。

解决方法:

拷贝的时候不要用memcpy，使用拷贝赋值函数来完成，因为赋值函数会帮我们完成深拷贝。

voidreserve(size_tn){//记录sizesize_tsz=size();if(n>capacity()){T*tmp=newT[n];if(_start){//防止浅拷贝问题3for(size_ti=0;i<size();++i) { tmp[i]=_start[i]; } delete[]_start;}_start=tmp;//注意,这里start位置变了}//更新_finish、_endofstorage_finish=_start+sz;_endofstorage=_start+n;}