【C++】vector的模拟实现

vector模拟实现最坚实的数据结构恰恰长着最简单的模样——用指针织一片连续的内存便装下了万物的来去1. 什么是vector想必大家都学过顺序表这个数据结构。顺序表通过开辟一块连续的内存空间来存储数据在C语言中如果要自己实现一个顺序表需要先定义一个动态数组然后还要实现增删改查相关的操作函数。但是C语言实现顺序表有一个很大的局限如果程序涉及到多种数据类型的顺序表就得为每种数据类型写一份重复的代码导致代码冗余且难以维护。C的vector正是为了解决这个问题而生——它是一个模板类内部维护的是一个动态数组增删改查等操作都封装好了并且会自动扩容。编译器会根据创建的对象类型实例化出对应数据类型的vector类我们只需要放心使用即可。2. vector的核心设计2.1 成员变量的设计不同于string用_str、_size、_capacity三个独立变量vector在成员变量的设计上采用了三个迭代器指针来维护数组templateclassTclassvector{private:iterator _startnullptr;// 指向数组起始位置iterator _finishnullptr;// 指向有效元素末尾的下一个位置iterator _endofstoragenullptr;// 指向已分配空间的末尾};这种设计的好处很明显_finish - _start直接得到元素个数size_endofstorage - _start直接得到当前容量capacity用指针的差值来表示大小和容量省去了单独维护size和capacity的烦恼这是仿照SGI版本STL源码的设计思路。2.2 迭代器的实现在vector中迭代器就是原始指针的别名typedefT*iterator;typedefconstT*const_iterator;因为vector的底层是一段连续的内存空间指针天然的就能移动到下一个元素所以在vector中迭代器的实现就这么简洁直接。四个迭代器函数分别返回_start和_finish并通过const版本来支持const对象的只读访问。2.3 基本接口size、capacity、empty、clear、operator[]size_tsize()const{return_finish-_start;}size_tcapacity()const{return_endofstorage-_start;}boolempty()const{return_start_finish;}voidclear(){_finish_start;}Toperator[](size_t n){assert(nsize());return_start[n];}constToperator[](size_t n)const{assert(nsize());return_start[n];}size()和capacity()利用指针差值直接计算时间复杂度O(1)。empty()判断起始和结束指针是否重合。clear()只需将_finish指向_start逻辑上清空所有元素内存并未释放。operator[]提供下标访问内部带断言检查越界。3. 构造函数与析构函数3.1 迭代器区间构造与SFINAE技巧向量不仅可以通过无参构造和初始化列表构造还可以通过迭代器区间构造。这里包含了一个很有意思的细节templateclassInputiterator,classtypenamestd::enable_if!std::is_integralInputiterator::value::typevector(Inputiterator first,Inputiterator last){while(first!last){push_back(*first);first;}}为什么要用enable_if加上is_integral呢这是因为vector还有两个构造函数的重载vector(size_t n,T valT());// 用n个val初始化vector(intn,T valT());// 为了兼容int类型的n如果不加限制当调用vectorint v(5, 1)时编译器会纠结(5, 1)到底该匹配迭代器区间构造把5和1当作两个迭代器还是匹配n个val构造5是元素个数1是元素值通过enable_if检查Inputiterator是否为整型如果是整型就排除这个重载确保编译器能够正确选择n个val构造。这就是C中SFINAESubstitution Failure Is Not An Error原则的应用——当一个模板重载在类型推导时失败编译器不会报错只是把这个重载从候选集中移除然后尝试下一个候选函数。⚠️ 温馨提示enable_if必须出现在函数签名中才能参与重载解析不能放在函数体内。而且C20提供了concepts机制可以用更清晰的方式来写这类约束。3.2 拷贝构造与赋值操作拷贝构造的实现思路很简单根据被拷贝对象的容量先开辟好足够大的空间然后逐个元素进行赋值。需要注意的细节是reserve的参数应该传被拷贝对象的capacity()而不是size()。如果传的是size()虽然也能运行但下一次push_back会立即触发扩容效率会打折扣。提前预留足够的容量可以避免多次扩容带来的性能损耗。vector(constvectorTv){reserve(v.capacity());for(autoe:v){push_back(e);}}赋值操作则巧妙地利用了拷贝交换copy-and-swap惯用法voidswap(vectorTtmp){std::swap(_start,tmp._start);std::swap(_finish,tmp._finish);std::swap(_endofstorage,tmp._endofstorage);}vectorToperator(vectorTv)// 传值调用自动生成了副本{swap(v);// 交换副本与当前对象的内容return*this;}先通过传值调用生成一份副本再通过交换成员变量完成赋值最后副本在函数结束时自动析构——简洁且异常安全。3.3 析构函数~vector(){if(_start){delete[]_start;_start_finish_endofstoragenullptr;}}析构函数负责释放动态分配的内存并将三个指针置空防止悬空指针。4. 容量管理与动态扩容4.1 reserve预留空间reserve是vector扩容的核心函数它保证容器能够容纳n个元素而不需要重新分配内存voidreserve(size_t n){if(ncapacity()){size_t old_sizesize();T*tmpnewT[n];if(_start){for(size_t i0;iold_size;i){tmp[i]_start[i];}delete[]_start;}_starttmp;_finish_startold_size;_endofstorage_startn;}}有几个关键点值得注意关键点一为什么要提前记录old_size_finish和_start都是指针size() _finish - _start在扩容过程中。如果先更新_start再计算_finish等式右边会算错。所以必须在_start被覆盖之前把size()保存下来。关键点二为什么不直接用memcpy拷贝如果T是string等自定义类型memcpy只是按字节复制浅拷贝会导致两个对象指向同一块资源析构时会double free。用赋值运算符逐个赋值才能调用自定义类型的拷贝逻辑实现深拷贝。4.2 push_back与pop_back有了reserve尾插操作变得简洁voidpush_back(constTval){if(_finish_endofstorage){reserve(capacity()0?4:2*capacity());}*_finishval;_finish;}当空间满了就用reserve扩容扩容因子是2倍g下是2倍扩容VS下是1.5倍。然后直接在_finish指向的位置放入新元素即可。尾删的逻辑更直接voidpop_back(){assert(!empty());--_finish;}只需要确保容器非空然后让_finish指针前移一位即可——这就是顺序表删除操作的简洁之处。5. 插入与删除5.1 insert在指定位置插入insert操作的实现思路分为三步判断是否需要扩容、将pos及之后的元素后移、在pos位置放入新元素。iteratorinsert(iterator pos,constTx){assert(pos_startpos_finish);if(_finish_endofstorage){size_t lenpos-_start;reserve(capacity()0?4:2*capacity());pos_startlen;// 关键重新定位pos}iterator end_finish-1;while(endpos){*(end1)*end;--end;}*posx;_finish;returnpos;}这里有一个非常隐蔽的问题如果在扩容前保存了pos扩容后新空间来了pos指向的还是旧空间的地址——此时旧空间已被释放pos变成了野指针解决方法是在扩容前记录pos相对于_start的偏移量len扩容后让pos重新指向新空间中对应的位置。5.2 erase删除指定位置erase的实现思路是将pos位置之后的元素逐个向前覆盖一位然后将_finish指针前移。iteratorerase(iterator pos){assert(pos_startpos_finish);iterator itpos1;while(it!_finish){*(it-1)*it;it;}--_finish;returnpos;}5.3 迭代器失效问题剖析迭代器本质上就是指针迭代器失效意味着这个指针指向的内存已经被释放了如果继续使用就会产生未定义行为程序可能会崩溃。在vector中有以下几种情况会导致迭代器失效扩容类操作reserve、resize、push_back、insert等。当触发扩容时容器会重新分配一块新内存将旧空间的元素逐个拷贝过去然后释放旧空间。此时任何指向旧空间的迭代器都会失效变成野指针。erase删除操作。当删除pos位置的元素时pos位置之后的元素会向前覆盖。虽然底层空间没有变化但VS等编译器认为该位置的迭代器已经失效尤其是删除最后一个元素时pos会变成end位置而end位置没有元素因此pos失效。5.4 resize调整容器大小resize函数根据n的不同取值分两种情况处理voidresize(size_t n,T valT()){if(nsize()){reserve(n);while(_finish!_startn){*_finishval;_finish;}}else{_finish_startn;}}当n大于当前size时扩容后用val填充多出的位置。当n小于当前size时只需将_finish指针调整到_start n位置即可相当于截断处理。6. 总结从成员变量的设计三个迭代器、迭代器的简单实现原生指针到自动扩容机制2倍扩容因子再到插入删除时对迭代器失效的处理记录偏移量重新定位每一个细节都体现了C顺序表这一核心数据结构的设计精髓。正如我们在本文开头所说的那样——最坚实的数据结构恰恰长着最简单的模样。希望这次模拟实现的讲解能帮助大家更深入地理解vector的底层原理在实际开发中写出更健壮的代码。7. vector.h完整代码#pragmaonce#includeiostream#includeassert.h#includevector#includetype_traitsusingnamespacestd;namespaceray{templateclassTclassvector{public:typedefT*iterator;typedefconstT*const_iterator;iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorbegin()const{return_start;}const_iteratorend()const{return_finish;}vector()default;vector(initializer_listTil){reserve(il.size());for(autoe:il)push_back(e);}vector(constvectorTv){reserve(v.capacity());for(autoe:v)push_back(e);}voidswap(vectorTtmp){std::swap(_start,tmp._start);std::swap(_finish,tmp._finish);std::swap(_endofstorage,tmp._endofstorage);}vectorToperator(vectorTv){swap(v);return*this;}templateclassInputiterator,classtypenamestd::enable_if!std::is_integralInputiterator::value::typevector(Inputiterator first,Inputiterator last){while(first!last)push_back(*first);}vector(size_t n,T valT()){resize(n,val);}vector(intn,T valT()){resize(n,val);}~vector(){if(_start)delete[]_start;_start_finish_endofstoragenullptr;}voidresize(size_t n,T valT()){if(nsize()){reserve(n);while(_finish!_startn)*_finishval;}else_finish_startn;}size_tsize()const{return_finish-_start;}size_tcapacity()const{return_endofstorage-_start;}Toperator[](size_t n){assert(nsize());return_start[n];}constToperator[](size_t n)const{assert(nsize());return_start[n];}voidreserve(size_t n){if(ncapacity()){size_t old_sizesize();T*tmpnewT[n];if(_start){for(size_t i0;iold_size;i)tmp[i]_start[i];delete[]_start;}_starttmp;_finish_startold_size;_endofstorage_startn;}}voidpush_back(constTval){if(_finish_endofstorage)reserve(capacity()0?4:2*capacity());*_finishval;}voidclear(){_finish_start;}boolempty()const{return_start_finish;}voidpop_back(){assert(!empty());--_finish;}iteratorinsert(iterator pos,constTx){assert(pos_startpos_finish);if(_finish_endofstorage){size_t lenpos-_start;reserve(capacity()0?4:2*capacity());pos_startlen;}iterator end_finish-1;while(endpos)*(end1)*end--;*posx;_finish;returnpos;}iteratorerase(iterator pos){assert(pos_startpos_finish);iterator itpos1;while(it!_finish)*(it-1)*it;--_finish;returnpos;}private:iterator _startnullptr;iterator _finishnullptr;iterator _endofstoragenullptr;};}