文章目录引入一、三指针框架哪些位置必须保持一致1.1 三个边界分别负责什么1.2 模板决定元素类型二、扩容和尾插旧数据什么时候释放2.1 reserve 预开辟空间2.2 push_back 尾部插入元素2.3 pop_back 删除尾部元素三、插入与删除偏移、方向和引用别名3.1 插入位置为何先变成偏移量3.2 erase 的返回值是继续遍历的入口四、对象复制为什么不能一律 memcpy4.1 容器复制与元素复制不是同一层4.2 用一个动态整数把问题看清楚4.3 拷贝构造4.4 赋值重载五、扩展练习5.1 LeetCode 118「杨辉三角」六、小结续接上篇vector 的基本使用大小、容量和位置的详细阐述上代码仓库《vector测试与模拟实现》引入上篇已经详细回答了vector“ 怎样用 ” 。这一篇将介绍我们自己如何根据已知的机制与知识来模拟实现一个我们自己的vector在此篇中我更建议把此次模拟实现当成是检验我们对于标准库vector理解的方法而不是自己实现一遍后就断定标准库也是同一份代码。具体源码可自行查找参照一、三指针框架哪些位置必须保持一致1.1 三个边界分别负责什么namespaceby{templateclassTclassvector{public:typedefT*iterator;typedefconstT*const_iterator;//....private:iterator _startnullptr;iterator _finishnullptr;iterator _end_of_storagenullptr;};}成员含义非空存储时的关系_start存储起始位置对应 begin_finish有效元素的尾后位置对应 end_end_of_storage存储容量的尾后位置不是可解引用元素有存储时_start _finish _end_of_storage有效区间是[_start,_finish)容量区间是[_start,_end_of_storage)。指针差以T元素为单位不是字节数。默认对象中三个成员都是nullptr有容量但size为 0 时_finish _start但起始位置不必是nullptr。1.2 模板决定元素类型templateclass T中的 T 是元素类型参数by::vectorint使用 intby::vectordouble使用doubletypedef T* iterator给指针起别名typedef const T* const_iteratorconst成员函数中的begin/end返回后者所以通过const容器不能改元素。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_end_of_storage-_start;}boolempty()const{return_start_finish;}iterator begin() { return _start; }iterator end() { return _finish; }普通对象调用返回可修改迭代器。const_iterator begin() const { return _start; }const_iterator end() const { return _finish; }const修饰的vector对象调用这一组返回const_iterator不能修改元素。size_t size() const { return _finish - _start; }size 有效元素个数连续内存指针相减得到元素数量。size_t capacity() const { return _end_of_storage - _start; }capacity 总容量内存可容纳的最大元素数。bool empty() const { return _start _finish; }有效元素区间起点等于终点代表容器为空。二、扩容和尾插旧数据什么时候释放2.1 reserve 预开辟空间//预开辟空间voidreserve(size_t n){if(ncapacity())return;size_t old_sizesize();T*tmpnewT[n];//浅拷贝对于普通内置类型可行但对于类类型会出错//memcpy(tmp, _start, old_size * sizeof(T));//深拷贝逐个赋值对于内置类型与自定义类型均适用for(size_t i0;iold_size;i){tmp[i]_start[i];}delete[]_start;_starttmp;_finishtmpold_size;_end_of_storage_startn;}如果n capacity不做任何操作。挪动空间前先保存旧size再申请新数组逐个复制有效元素成功后才能销毁旧数组并更新边界。为什么必须先保存old_size因为_finish - _start要用属于同一块存储的两个位置计算不能先改其中一个再拿新旧指针求差。2.2 push_back 尾部插入元素//追加单个元素voidpush_back(constTx){//检查容量if(_finish_end_of_storage){reserve(capacity()0?INIT_NUM:2*capacity());}*_finishx;_finish;}当size小于capacity时_finish指向数组中一个尚未计入有效区间的对象赋值完成后再递增_finish新的元素才进入逻辑序列。这里不能先递增_finish再赋值如果赋值失败size就会把尚未成功加入的元素算进去。2.3 pop_back 删除尾部元素//删除单个元素voidpop_back(){assert(!empty());--_finish;}assert(!empty())断言禁止对空 vector 调用 pop_back空的时候直接报错。--_finish只把结束指针向前挪一格。内置类型基本够用三、插入与删除偏移、方向和引用别名3.1 插入位置为何先变成偏移量//指定位置前插入元素iteratorinsert(iterator pos,constTx){assert(pos_start);assert(pos_finish);//检查容量if(_finish_end_of_storage){size_t lenpos-_start;reserve(capacity()0?INIT_NUM:2*capacity());pos_startlen;}//挪动数据iterator end_finish-1;while(endpos){*(end1)*(end);--end;}*posx;_finish;returnpos;}例如pos指向第三个元素它与旧_start相距 2。扩容后旧pos失效但数字 2 可以保留新的_start 2就得到新存储中的插入位置。对于尚未分配存储的空对象偏移直接记为 0不依赖空指针求差来表达位置。扩容成功后_start指向真实数组才按数组模型恢复位置。3.2 erase 的返回值是继续遍历的入口//删除指定位置元素voiderase(iterator pos){assert(pos_start);assert(pos_finish);iterator curpos1;while(cur!end()){*(cur-1)*cur;cur;}--_finish;}删除pos的元素后后续值从前向后补位最后缩小有效区间。前提条件必须是pos _finish不能允许单元素删除end。删最后一个元素时不需要搬移递减finish后pos恰好等于新的end。四、对象复制为什么不能一律 memcpy4.1 容器复制与元素复制不是同一层vector对象拥有自己的元素存储。若只把三个指针复制给新容器两个对象会指向同一个数组一方销毁后另一方悬空随后还可能重复delete[]。所以复制容器需要申请独立存储再按 T 的复制语义复制每个有效元素。对int就是复制数值对拥有资源的类需要该类自己定义正确的复制行为。4.2 用一个动态整数把问题看清楚下面的IntBox类中只有一个int*对象拥有它指向的动态整数。resources则用来观察资源数量不参与功能逻辑。#includeiostream#includestringclassIntBox{public:staticintresources;IntBox(intvalue0):_value(newint(value)){resources;}IntBox(constIntBoxother):_value(newint(*other._value)){resources;}IntBoxoperator(constIntBoxother){if(this!other)*_value*other._value;return*this;}~IntBox(){delete_value;--resources;}intvalue(){return*_value;}constintvalue()const{return*_value;}private:int*_value;};intIntBox::resources0;intmain(){IntBoxi(1);std::coutIntBox::resourcesstd::endl;IntBox ni;std::coutIntBox::resourcesstd::endl;return0;}运行示例构造时申请一个整数拷贝构造时申请另一个整数并复制值。赋值对象已经有自己的整数直接修改它的值就足够不需要先释放再申请。对于非平凡对象用memcpy覆盖整个对象并不能替代复制操作。除了没有调用拷贝构造或赋值复制出的指针也会指向同一资源若随后删除旧数组旧对象的析构会释放资源新对象中复制来的指针随即悬空以后再使用、再次析构都有风险。4.3 拷贝构造//拷贝构造vector(constvectorTv){reserve(v.size());for(autoe:v){push_back(e);}}reserve(v.size())提前开好足够空间避免push_back循环里频繁扩容提升效率。范围 for 遍历源vpush_back(e)把每个元素拷贝进新对象调用元素的拷贝构造。v的capacity中可能有大量备用位置它们不是有效元素没有理由作为内容复制。拷贝构造出来的新vectorsize v.size()capacity至少等于v.size()不一定和原vector的capacity相等标准库vector拷贝构造只保证容量≥ size不会拷贝原容器多余的备用空间。4.4 赋值重载//拷贝交换voidswap(constvectorTv){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_end_of_storage,v._end_of_storage);}//赋值深拷贝//现代写法vectorToperator(vectorTv){swap(v);return*this;}此处仍然采用现代写法安全有效。以a b为例先用b构造参数v得到独立副本交换后a持有新内容v持有a的旧数组离开函数后other析构旧数组被释放。a a时同样先构造独立副本再交换所以不会先清空自己再发现“源也被清空了”。五、扩展练习5.1 LeetCode 118「杨辉三角」LeetCode 118「杨辉三角」生成前numRows行每行首尾是 1中间元素等于上一行相邻两个元素之和。思路先创建外层的行对象再把第i行resize到i 1个元素并填 1。只计算内部列避免边界访问上一行不存在的位置。参考答案std::vectorstd::vectorintpascal(intnumRows){if(numRows0)return{};std::vectorstd::vectorintresult(numRows);for(size_t i0;iresult.size();i){result[i].resize(i1,1);for(size_t j1;ji;j)result[i][j]result[i-1][j-1]result[i-1][j];}returnresult;}pascal(5)得到[1]、[1,1]、[1,2,1]、[1,3,3,1]、[1,4,6,4,1]。i为 0、1 时没有内部列内循环自然不执行i为 2、j为 1 时第一次计算1 1。六、小结这次模拟实现最重要的进步不只是让实现的接口更多而是能把一个操作拆成有顺序的责任保存旧信息、保护来源值、取得新存储、转移有效元素、释放旧资源、更新边界。回到标准库使用时也应该保留两个区分连续存储不等于位置永远有效容器管理存储不等于可以无视元素自身的复制与析构。对照资料vector 总览与接口reserve容量与失效规则erase返回值、失效与复杂度resize增加和移除元素