本文代码已同步Github一、为什么STL使用三个迭代器1、SGI STL中的vector设计通过之前模拟实现的string我们知道string的底层有str,size,capacity_str指向字符串的起始位置:_size表示字符串的有效元素个数_capacity表示字符串容量那么vector中是否也是这样的结构呢我们通过g中SGI版本的vector来观察在说明文档中发现vector是通过一些头文件进行了封装核心文件便是stl_vector.h2、vector核心成员变量首先发现vector实际上是一个模板这也就解释了为什么vector不仅能存储内置类型也能存储自定义类型其次发现类里面typedef了许多类型名包括把模板参数T称为value_type等下面我们来看一下protected中的成员变量里面有三个迭代器内存池相关内容先不管并不是我们想象的一个指针加两个变量对于iterator的定义则是value_type*即T*也就是说这三个迭代器其实是三个指针通过名字我们猜测start指向有效数据的起始位置end指向有效数据最后一个元素的下一个位置;end_of_storage指向这块存储空间的末尾的下一个位置;那猜测究竟对不对呢我们来看看实现的迭代器成员函数begin()返回的是start表明start指向起始位置end()返回的是finish表明finish指向最后一个有效位置的下一个位置size()返回的是end() - begin()说明start和finish两个指针相减得到元素个数;capacity()返回的的是end_of_storage - begin()说明end_of_storage指向的就是这块空间的末尾的下一个位置经过对vector底层的简单观察发现vector有着自己独特的结构那么我们就根据底层结构来模拟实现vector二、vector类模板框架搭建vector本质上是一个存储任意类型对象的容器因此需要使用类模板实现。注意⚠️vector采用的是模板参数由于模板导致变量和声明不能分离因此我们使用vector.h文件来实现下面我们来完成模拟实现的前置工作//vector.h#pragmaonce#includeiostreamnamespacestl{//模板参数templateclassTclassvector{typedefT*iterator;private:iterator _startnullptr;iterator _finishnullptr;iterator _end_of_storagenullptr;};}三、基础接口实现注意⚠️文档中的顺序并不适合模拟实现各个接口之间有一定的依赖我们先来看库里面的构造函数的参数类型default(1)explicitvector(constallocator_typeallocallocator_type());fill(2)explicitvector(size_type n,constvalue_typevalvalue_type(),constallocator_typeallocallocator_type());range(3)templateclassInputIteratorvector(InputIterator first,InputIterator last,constallocator_typeallocallocator_type());copy(4)vector(constvectorx);总结一下1、无参的默认构造函数2、用n个val来初始化的构造函数3、用迭代器区间初始化的构造函数4、拷贝构造函数我们先实现无参的默认构造函数剩下的在后续实现(便于复用代码)对于无参的默认构造函数我们直接给出成员变量的缺省值直接走初始化列表即可//无参的默认构造函数//即使什么都不写成员变量也会走初始化列表使用缺省值vector(){}接下来我们实现一些简单接口iteratorbegin(){return_start;}iteratorend(){return_finish;}size_tsize()const{return_finish-_start;}size_tcapacity()const{return_end_of_storage-_start;}boolempty(){return_start_finish;}这样就完成了前置工作这些函数都是一眼秒懂我们不再测试四、空间管理1、reserve()经过上一篇对vector的接口介绍以及string类的经验我们知道reserve本质上是用来开空间的先来看reserve的参数voidreserve(size_t n);分析逻辑如果 n capacity那么就需要扩容否则没有影响实现时选择声明和定义分离templateclassTvoidvectorT::reserve(size_t n){if(ncapacity()){//扩容iterator tmpnew[n]T;memcpy(tmp,_start,sizeof(size()*sizeof(T));delete[]_start;//更新_starttmp;_finish_startsize();_end_of_storage_startn;}}此时由于还未实现push_back等操作我们先不着急测试2、resize()接着来看resize的参数解读一下核心逻辑如果n size()就把数据减少到n个;如果n size()就把有效数据个数增加到n个同时使用val来填充如果n capacity()就会重新分配空间把有效数据个数增加到ntemplateclassTvoidvectorT::resize(size_t n,constTval){if(nsize()){_finish_startn;}else{reserve(n);//挪动数据for(size_t isize();in;i){_start[i]val;}_finish_startn;}}先不着急测试等修改操作实现完之后一起进行测试五、元素操作在实现修改操作之前我们先实现一个打印函数用来更方便的观察测试结果templateclassTvoidprint_vector(vectorTv){for(autoe:v){coute ;}coutendl;}1、operator[]operator[]就是返回pos位置的引用即可Toperator[](size_t pos){assert(possize());return_start[pos];}2、push_back()push_back就是尾插考虑扩容voidpush_back(constTval){if(_finish_end_of_storage){reserve(T);}*_finishval;_finish;}测试 debug程序没有正常运行我们调试来看此时当程序运行到69行时发现_finish是空指针说明上面的reserve并没有正常扩容此时我们着重来看reserve在更新时正常来说_finish _start n应该能使得_finish更新说明问题就在这里我们画图来分析一下此时_start已经指向了新空间的起始位置而_finish还在指向旧空间size() _finish - _start其中_start已经更新而_finish却还没有代入到_finish _start _finish - _start竟然成了自赋值导致一直为空指针找到了问题该怎么解决呢方法一先更新_finish再更新_startvoidvectorT::reserve(size_t n){if(ncapacity()){//扩容iterator tmpnewT[n];memcpy(tmp,_start,size()*sizeof(T));delete[]_start;//方法一_finishtmpsize();_starttmp;_end_of_storage_startn;}}我们先来看一下结果是否正确没有问题方法二提前记录size()大小voidvectorT::reserve(size_t n){if(ncapacity()){size_t old_sizesize();//扩容iterator tmpnewT[n];memcpy(tmp,_start,old_size*sizeof(T));delete[]_start;//方法一//_finish _tmp size();//_start _tmp;//_end_of_storage _tmp n;//方法二_starttmp;_finish_startold_size;_end_of_storage_startn;}}用old_size来记录有效数据个数即可正常更新来看运行结果没有问题我们顺便来测一下resize3、 pop_back()pop_back就是尾删直接改变_finish即可voidpop_back(){assert(!empty());--_finish;}来测试一下再删一次看是否会触发断言4、 insert()vector底层是连续空间因此插入删除可能需要移动大量元素降低效率尽量少用发现参数全部都是迭代器因此我们也要采用迭代器参数我们选择实现第一个参数类型的函数vectorT::iteratorvectorT::insert(iterator pos,constTval){assert(pos_start);assert(pos_finish);if(_finish_end_of_storage){reserve(capacity()0?4:2*capacity());}iterator end_finish-1;while(endpos){*(end1)*end;--end;}*posval;_finish;returnpos;}我们来测试一下5、erase()我们先来看参数显然参数扔是迭代器类型的在pos位置删除当前元素挪动数据并更新_finish即可vectorT::iteratorvectorT::erase(iterator pos){assert(pos_start);assert(pos_finish);autobeginpos1;while(begin!_finish){*(begin-1)*begin;begin;}--_finish;returnpos;}来测试一下六、迭代器失效我们再来测试一下insert和erase1、野指针我想在末尾插入一个5但最终打印出来却是随机值我们通过调试来看程序执行到这时应该已经完成了赋值但却并没有正确赋值我们来画个图原因就是扩容后未更新pos的指向导致pos成了类似野指针的迭代器怎么解决呢先记录距离初始位置的相对大小接着在扩容之后更新posvectorT::iteratorvectorT::insert(iterator pos,constTval){assert(pos_start);assert(pos_finish);if(_finish_end_of_storage){//更新possize_t old_pospos-_start;reserve(capacity()0?4:2*capacity());posold_pos_start;}iterator end_finish-1;while(endpos){*(end1)*end;--end;}*posval;_finish;returnpos;}没有问题2、位置失效即使是没有扩容在pos位置插入值之后数据挪动pos指向的位置发生改变同样认为迭代器失效如果要访问那就需要更新迭代器之后再进行访问七、对象构造与资源管理1. n个val构造下面我们来看构造函数的其他重载fill(2)explicitvector(size_type n,constvalue_typevalvalue_type(),constallocator_typeallocallocator_type());分析逻辑先开大小为n的空间然后依次填入val即可//2.n个val构造vector(size_t n,constTvalT()){reserve(n);for(size_t i0;in;i){push_back(val);}}我们来测试一下2. 迭代器区间构造我们先来看库里面是怎么设计的range(3)templateclassInputIteratorvector(InputIterator first,InputIterator last,constallocator_typeallocallocator_type());显然是把迭代器区间构造函数设计成了函数模板那我们也仿照这样的设计按照函数模板形式来实现templateclassInputIteratorvector(InputIterator first,InputIterator last){//[first,last]size_t nlast-first;reserve(n);InputIterator beginfirst;while(first!last){push_back(*first);}}来测试一下编译报错了1------ 已启动生成: 项目: vector, 配置: Debug x64 ------ 1 Test.cpp 1D:\DailyCode\09_cpp_vector\vector\vector\vector.h(47,15): error C2100: 无法取消引用类型为“InputIterator”的操作数 1D:\DailyCode\09_cpp_vector\vector\vector\vector.h(47,15): error C2100: with 1D:\DailyCode\09_cpp_vector\vector\vector\vector.h(47,15): error C2100: [ 1D:\DailyCode\09_cpp_vector\vector\vector\vector.h(47,15): error C2100: InputIteratorint 1D:\DailyCode\09_cpp_vector\vector\vector\vector.h(47,15): error C2100: ] 1 (编译源文件“Test.cpp”) 1 D:\DailyCode\09_cpp_vector\vector\vector\vector.h(47,15): 1 模板实例化上下文(最早的实例化上下文)为 1 D:\DailyCode\09_cpp_vector\vector\vector\Test.cpp(366,17): 1 查看对正在编译的函数 模板 实例化“stl::vectorint::vectorint(InputIterator,InputIterator)”的引用 1 with 1 [ 1 InputIteratorint 1 ] 1 D:\DailyCode\09_cpp_vector\vector\vector\Test.cpp(366,17): 1 请参阅 stl::test_constructor 中对 stl::vectorint::vector 的第一个引用这个报错让人抓不到头脑我们直接说结论答案是测试代码的vectorint v1(10,1)的两个参数匹配上了迭代器区间构造为什么会匹配上呢对于n个val的构造函数第一个参数需要从int-size_t,第二个参数需要从int-const int而对于迭代器区间构造直接将InputIterator推导为int,无需类型转换由于函数模板不需要类型准换因此直接匹配到迭代器区间构造上了我们加上重载函数即可解决//3.迭代器区间构造templateclassInputIteratorvector(InputIterator first,InputIterator last){//[first,last]size_t nlast-first;reserve(n);while(first!last){push_back(*first);first;}}vector(intn,constTvalT()){reserve(n);for(size_t i0;in;i){push_back(val);}}3. 拷贝构造copy(4)vector(constvectorval);有了上面两个构造函数的经验我们直接遍历范围for即可提前开好空间避免多次扩容//4.拷贝构造vector(constvectorval){reserve(val.size());for(autoe:val){push_back(e);}}来测试一下4. 析构函数释放_start指向的空间即可delete[]会依次调用T的析构函数~vector(){if(_start){delete[]_start;_start_finish_end_of_storagenullptr;}}5. 赋值运算符重载首先清空原有内容接着开空间最后依次填入即可voidclear(){_finish_start;}Toperator(constTval){clear();reserve(val.size());for(autoe:val){push_back(e);}}我们不妨来试一下现代写法//现代写法voidswap(vectorTv){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_end_of_storage,v._end_of_storage);}vectorToperator(vectorTval){swap(val);return*this;}来测试一下八、经典再现前面的实现对于int等内置类型没有问题但是当vector存储自定义类型时问题才真正出现代码出现了随机值我们调试来看显然是reserve出了问题我们还是来画图分析:首先来看原始内存分布图接着来看扩容后的内存分布图注意memepy是浅拷贝由于memcpy是浅拷贝导致新空间的每个_str指向的还是原来的位置而此时原来空间均已被销毁导致最终打印成随机值并且程序结束时会调用两次string的析构函数关键在于memcpy是浅拷贝导致拷贝后的数据如果是自定义类型那么仍会指向被释放的空间该怎么解决呢我们选择不用memcpy而是直接采用赋值运算符把新空间的每个对象都用原空间的对象来完成对象复制同时也会开好新空间**这样对于自定义类型析构时就会调用其析构函数对于内置类型则不做处理templateclassTvoidvectorT::reserve(size_t n){if(ncapacity()){size_t old_sizesize();//扩容iterator tmpnewT[n];//memcpy(tmp, _start, old_size * sizeof(T));//赋值重载for(size_t i0;iold_size;i){tmp[i]_start[i];}delete[]_start;//方法一//_finish _tmp size();//_start _tmp;//_end_of_storage _tmp n;//方法二_starttmp;_finish_startold_size;_end_of_storage_startn;}}此时我们再来看运行结果程序正常运行九、从vector模拟实现理解STL设计思想通过对vector的模拟实现我们不仅了解了一个动态数组容器的底层结构也进一步理解了 C STL 容器设计背后的思想。在实现过程中我们首先认识到vector的核心并不是简单的数组封装而是通过三个迭代器_start、_finish、_end_of_storage管理一段连续空间通过空间大小与有效元素数量的分离实现动态扩容的能力。在空间管理方面vector需要在容量不足时重新申请空间并将原有元素迁移到新的空间中。这一过程看似简单但其中涉及指针更新、数据拷贝以及迭代器失效等问题。通过这些问题我们更加深入地理解了连续空间容器在效率和使用限制之间的权衡。同时在实现vector存储自定义类型时我们发现简单的内存拷贝并不能保证对象的正确性。对于像string这样的类对象其内部可能管理着动态资源如果只复制对象本身的内存会导致资源重复释放等问题。因此容器不能直接操作对象内部资源而应该依赖对象自身提供的构造、拷贝、赋值和析构等接口完成生命周期管理。这也体现了 C STL 的重要设计思想容器负责管理元素的位置和存储方式而元素类型负责管理自身的资源和生命周期。通过模拟实现vector我们不仅学习了一个 STL 容器的实现方式更重要的是理解了 C 中面向对象、泛型编程以及资源管理之间的联系。从最初的类和对象到内存管理再到 STL 容器设计C 的核心思想始终围绕着让对象管理自己的资源让代码拥有更好的复用性、安全性和扩展性。这也是 STL 能够成为 C 标准库核心组成部分的重要原因。下一篇将继续通过 list 模拟实现进一步学习链式结构、迭代器设计以及 STL 容器的抽象思想。img-YRdjfFGT-1785832729716)]程序正常运行我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code2tjljf0sxdj如果觉得有帮助可以关注Github项目持续更新
)
