一、浅析vector源码对于编程来说学习初期进步最快的方式就是阅读别人优秀的代码理解其中的逻辑和细节后自己独立地去实现几次学习 STL 也是如此我们可以适当地去阅读 STL 的源码当然我们并不是要逐行地进行阅读因为这样太耗费时间况且其中很多 C 的语法我们也还没学。当前阶段我们阅读 STL 源码是为了学习 STL 库的核心框架然后根据这个框架自己模拟实现一个简易的vector只实现核心接口阅读源码与模拟实现能够让我们更好地了解底层对 STL 做到 能用并且 明理。可以看到vector.h仅仅是将几个头文件包含在一起vector的主要实现都在stl_vector.h里面。二、核心框架我们可以根据上面的vector源码来得出vector的核心框架namespaceljm{templateclassTclassvector{public:typedefT*iterator;typedefconstT*const_iterator;public://成员函数private:T*_start;T*_finish;T*_endofstorage;};}可以看到vector的底层和string一样都是一个指针指向一块动态开辟的数组但是二者不同的是string是用_size和_capacity两个size_t的成员变量来维护这块空间而vector是用_finish和_endofstorage两个指针来维护这块空间虽然vector使用指针看起来难了一些但本质上其实是一样的_size _finish - _start_capacity _endofstorage - _start。三、构造函数3.1 构造函数实现//无参构造vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}// 填充构造创建n个值为val的元素vector(size_t n,constTvalT()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){_startnewT[n];_finish_start;_endofstorage_startn;while(n--n!0){*_finishval;_finish;}}// 范围构造通过其他容器/序列的迭代器范围[first,last)初始化templateclassInputIteratorvector(InputIterator first,InputIterator last):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){size_t nlast-first;//这里计算链式存储结构的时候会有问题n不对我后续可以通过push-back来进行_startnewT[n];_finish_start;_endofstorage_startn;while(first!last){*_finish*first;_finish;first;}}3.2 问题在我们模拟实现了构造函数中的迭代器区间构造和n个val构造后我们会发现一个奇怪的问题我们使用n个val来构造其他类型的对象都没问题唯独构造int类型的对象时会编译出错如下这是由于编译器在进行模板实例化以及函数参数匹配时会调用最匹配的一个函数当我们将T实例化为int之后由于两个参数都是int它就走迭代器构造所以对于迭代器构造函数来说它会直接将InputIterator实例化为int但对于n个val的构造来说它不仅需要将T实例化为int还需要将第一个参数隐式转换为size_t所以编译器默认会调用迭代器构造同时由于迭代器构造内部会对first进行解引用所以这里报错 “非法的间接寻址”这个时候有两种办法解决这个问题方法 1将 10 显式指定为size_t类型写成10u这样编译器会优先匹配填充构造函数而非范围构造函数从而正常创建包含 10 个值为 1 的元素的vector。方法 2新增一个以int类型为参数的填充构造函数重载版本让vectorint v(10, 1)这类传入int型数值的场景能直接匹配该重载函数避免编译器误匹配范围构造函数。四、拷贝构造和赋值运算符重载深拷贝由于vector包含动态申请的资源因此不能使用浅拷贝浅拷贝仅复制指针地址会导致多个对象共用同一块内存引发析构时重复释放等问题必须实现深拷贝//swapvoidswap(vectorTv){std::swap(_start,v._start);//复用算法库的swap函数std::swap(_finish,v._finish);std::swap(_endofstorage,v._endofstorage);}//拷贝构造传统写法//vector(const vectorT v)// :_start(nullptr)// , _finish(nullptr)// , _endofstorage(nullptr)//{// size_t n v._start - v._finish;//这里计算链式存储结构的时候会有问题n不对我后续回来实现那一个方法的。// _start new T[n];// //浅拷贝 - 容器存储的是有动态资源的自定义类型使用memcpy就会造成浅拷贝// // 当 vector 里存的是带有动态资源的类比如含 char* 成员memcpy 会把同一块堆地址复制给两个对象结果双份析构 → 同一块内存被 free 两次 → 程序崩溃。// //memcpy(_start,v._start,sizeof(T)* v.size());// //深拷贝// for (size_t i 0; i v.size(); i)// {// _start[i] v._start[i];// }// _finish _start v.size();// _endofstorage _start v.capacity();//}//拷贝构造现代写法vector(constvectorTv):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){vectorTtmp(v.begin(),v.end());//复用构造函数和swap函数swap(tmp);//空手套白狼}//赋值重载传统写法//vectorT operator(vectorT v)//{// T* tmp new T[v.capacity()];// for (size_t i 0; i v.size(); i)// {// tmp[i] v._start[i];// }// delete[] _start;// _start tmp;// _finish _start v.size();// _endofstorage _start v.capacity();// return *this;//}//赋值重载现代// v1 v2vectorToperator(vectorTv){swap(v);return*this;}五、析构函数~vector(){if(_start){delete[]_start;_start_endofstorage_finishnullptr;}}六、迭代器由上面可得iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorbegin()const{return_start;}const_iteratorend()const{return_finish;}七、vector容量相关接口7.1 sizesize_tsize(){return_finish-_start;}7.2 capacitysize_tcapacity(){return_endofstorage-_start;}7.3 emptyboolempty(){returnsize()0;}7.4 reservevoidreserve(size_t n){if(ncapacity()){T*tmpnewT[n];//开空间size_t szsize();if(_start){for(size_t i0;isz;i)//拷数据{tmp[i]_start[i];}delete[]_start;}_starttmp;_finish_startsz;_endofstorage_startn;}else{return;}}该接口用于为vector预留至少n个元素的存储空间仅当n大于当前容器容量时才执行扩容操作扩容时先记录当前有效元素个数开辟n个大小的临时空间通过循环调用元素赋值重载完成深拷贝解决自定义类型动态资源的浅拷贝问题随后释放原空间更新容器的_start、_finish、_endofstorage指针使容器容量更新为n且保留原有全部有效元素有效避免频繁扩容带来的性能损耗。扩容接口有两个特殊问题1、自定义类型动态资源的浅拷贝问题当容器存储的是带动态资源的自定义类型时直接用memcpy拷贝会导致浅拷贝这一问题的解决思路在赋值运算符重载和拷贝构造的内容中已有说明此处不再赘述2、必须提前用sz记录当前有效元素个数因为扩容后原空间会被释放_start指针会指向新空间若此时再调用size()获取元素个数会因_start和_finish不再指向原空间而计算错误所以需要在扩容前先把当前元素个数存到sz变量中。7.5 resize先看是什么样的////1.ncapacity()nsize,不用扩容也不用加数据vectorintv1(5,6);for(autov:v1){coutv;}coutendl;cout1.开始v1.size() v1.capacity()endl;v1.resize(2,2);for(autov:v1){coutv;}coutendl;cout1.结束v1.size() v1.capacity()endl;//2.ncapacity()nsize,不用扩容加数据v1.resize(5,5);for(autov:v1){coutv;}coutendl;cout1.结束v1.size() v1.capacity()endl;v1.resize(10,2);for(autov:v1){coutv;}coutendl;cout1.结束v1.size() v1.capacity()endl;这段resize接口用于调整vector的有效元素个数第二个参数的缺省值是调用默认构造内置类型由于加入了模板也有了自己的默认构造当n小于当前元素数时直接截断仅调整_finish指针保留前n个元素当n更大时先调用reserve预留空间再将新增位置填充为指定值最终更新_finish指针既支持缩小容器也能安全扩容并填充元素。voidresize(size_t n,constTvalT()){if(nsize()){_finish_startn;// 缩小析构多余元素如有需要}elseif(nsize()){reserve(n);// reserve 内部会判断是否需要扩容size_t old_sizesize();for(size_t iold_size;in;i){_start[i]val;}_finish_startn;}}八、vector增删查改8.1 push_backvoidpush_back(constTx){if(_finish_endofstorage){size_t newcapacitycapacity()0?4:capacity()*2;reserve(newcapacity);}*_finishx;_finish;}8.2 insert//指定位置插入iteratorinsert(iterator pos,constTx){if(_finish_endofstorage){//记录相对位置size_t lenpos-_start;size_t newcapacitycapacity()0?4:capacity()*2;reserve(newcapacity);//之前的pos位置失效了之前的是基于没扩容前的pos_startlen;}iterator end_finish;while(posend){*end*(end-1);end--;}*posx;_finish;returnpos;}8.3 erase// 指定位置删除元素iteratorerase(iterator pos){// 断言确保pos迭代器合法在有效元素区间内且vector非空防止非法访问assert(pos_startpos_finishsize()0);// 定义迭代器it从pos的下一个元素开始遍历iterator itpos1;// 循环将pos之后的所有元素依次向前移动一位覆盖待删除元素实现逻辑删除while(it!_finish){*(it-1)*it;// 后一个元素的值赋给前一个元素完成前移覆盖it;// 迭代器后移处理下一个元素}// 尾指针前移一位缩小有效元素范围底层内存未释放仅标记该位置元素无效--_finish;// 返回原pos迭代器此时pos指向被删除元素的下一个有效元素避免外部迭代器失效returnpos;}8.4 pop_back//尾删voidpop_back(){erase(--end());}8.5 operator[]// 可读可写版本返回非const引用支持修改元素值Toperator[](size_t pos){assert(possize());// 断言确保访问的下标合法不越界return_start[pos];// 返回对应位置元素的引用支持读和写}// 仅读版本const成员函数返回const引用禁止修改元素值constToperator[](size_t pos)const{assert(possize());// 断言确保访问的下标合法不越界return_start[pos];// 返回对应位置元素的const引用仅支持读操作}8.6 findtemplateclassInputIterator,classTInputIteratorfind(InputIterator first,InputIterator last,constTval){while(first!last){if(*firstval){returnfirst;}first;}returnlast;}