企业官网建设流程全解析

续接上篇：vector 的基本使用（大小、容量和位置）的详细阐述（上）

代码仓库：《vector测试与模拟实现》

引入

上篇已经详细回答了vector“ 怎样用 ” 。这一篇将介绍我们自己如何根据已知的机制与知识来模拟实现一个我们自己的vector，在此篇中，我更建议把此次模拟实现当成是检验我们对于标准库vector理解的方法，而不是自己实现一遍后，就断定标准库也是同一份代码。（具体源码可自行查找参照）

一、三指针框架：哪些位置必须保持一致

1.1 三个边界分别负责什么

namespaceby{template<classT>classvector{public:typedefT*iterator;typedefconstT*const_iterator;//....private:iterator _start=nullptr;iterator _finish=nullptr;iterator _end_of_storage=nullptr;};}

有存储时，_start < =_finish <= _end_of_storage；有效区间是[_start,_finish)，容量区间是[_start,_end_of_storage)。指针差以T元素为单位，不是字节数。

默认对象中三个成员都是nullptr；有容量但size为 0 时，_finish == _start，但起始位置不必是nullptr。

1.2 模板决定元素类型

template<class T>中的 T 是元素类型参数；by::vector<int>使用 int，by::vector<double>使用double

typedef 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(n<=capacity())return;size_t old_size=size();T*tmp=newT[n];//浅拷贝，对于普通内置类型可行，但对于类类型会出错//memcpy(tmp, _start, old_size * sizeof(T));//深拷贝，逐个赋值，对于内置类型与自定义类型均适用for(size_t i=0;i<old_size;i++){tmp[i]=_start[i];}delete[]_start;_start=tmp;_finish=tmp+old_size;_end_of_storage=_start+n;}

如果n <= capacity：不做任何操作。

挪动空间前，先保存旧size，再申请新数组，逐个复制有效元素，成功后才能销毁旧数组并更新边界。

为什么必须先保存old_size？因为_finish - _start要用属于同一块存储的两个位置计算，不能先改其中一个，再拿新旧指针求差。

2.2 push_back 尾部插入元素

//追加单个元素voidpush_back(constT&x){//检查容量if(_finish==_end_of_storage){reserve(capacity()==0?INIT_NUM:2*capacity());}*_finish=x;++_finish;}

当size小于capacity时，_finish指向数组中一个尚未计入有效区间的对象；赋值完成后再递增_finish，新的元素才进入逻辑序列。

这里不能先递增_finish再赋值：如果赋值失败，size就会把尚未成功加入的元素算进去。

2.3 pop_back 删除尾部元素

//删除单个元素voidpop_back(){assert(!empty());--_finish;}

1. assert(!empty())：断言，禁止对空 vector 调用 pop_back，空的时候直接报错。
2. --_finish：只把结束指针向前挪一格。（内置类型基本够用）

三、插入与删除：偏移、方向和引用别名

3.1 插入位置为何先变成偏移量

//指定位置前插入元素iteratorinsert(iterator pos,constT&x){assert(pos>=_start);assert(pos<=_finish);//检查容量if(_finish==_end_of_storage){size_t len=pos-_start;reserve(capacity()==0?INIT_NUM:2*capacity());pos=_start+len;}//挪动数据iterator end=_finish-1;while(end>=pos){*(end+1)=*(end);--end;}*pos=x;++_finish;returnpos;}

例如pos指向第三个元素，它与旧_start相距 2。扩容后旧pos失效，但数字 2 可以保留；新的_start + 2就得到新存储中的插入位置。

对于尚未分配存储的空对象，偏移直接记为 0，不依赖空指针求差来表达位置。扩容成功后_start指向真实数组，才按数组模型恢复位置。

3.2 erase 的返回值是继续遍历的入口

//删除指定位置元素voiderase(iterator pos){assert(pos>=_start);assert(pos<_finish);iterator cur=pos+1;while(cur!=end()){*(cur-1)=*cur;++cur;}--_finish;}

• 删除pos的元素后，后续值从前向后补位，最后缩小有效区间。前提条件必须是pos < _finish，不能允许单元素删除end。
• 删最后一个元素时不需要搬移，递减finish后，pos恰好等于新的end。

四、对象复制：为什么不能一律 memcpy

4.1 容器复制与元素复制不是同一层

vector对象拥有自己的元素存储。若只把三个指针复制给新容器，两个对象会指向同一个数组；一方销毁后另一方悬空，随后还可能重复delete[]。

所以复制容器需要申请独立存储，再按 T 的复制语义复制每个有效元素。对int就是复制数值；对拥有资源的类，需要该类自己定义正确的复制行为。

4.2 用一个动态整数把问题看清楚

下面的IntBox类中只有一个int*，对象拥有它指向的动态整数。resources则用来观察资源数量，不参与功能逻辑。

#include<iostream>#include<string>classIntBox{public:staticintresources;IntBox(intvalue=0):_value(newint(value)){++resources;}IntBox(constIntBox&other):_value(newint(*other._value)){++resources;}IntBox&operator=(constIntBox&other){if(this!=&other)*_value=*other._value;return*this;}~IntBox(){delete_value;--resources;}int&value(){return*_value;}constint&value()const{return*_value;}private:int*_value;};intIntBox::resources=0;intmain(){IntBoxi(1);std::cout<<IntBox::resources<<std::endl;IntBox n=i;std::cout<<IntBox::resources<<std::endl;return0;}

运行示例：

构造时申请一个整数，拷贝构造时申请另一个整数并复制值。赋值对象已经有自己的整数，直接修改它的值就足够，不需要先释放再申请。

对于非平凡对象，用memcpy覆盖整个对象并不能替代复制操作。除了没有调用拷贝构造或赋值，复制出的指针也会指向同一资源；

若随后删除旧数组，旧对象的析构会释放资源，新对象中复制来的指针随即悬空；以后再使用、再次析构都有风险。

4.3 拷贝构造

//拷贝构造vector(constvector<T>&v){reserve(v.size());for(auto&e:v){push_back(e);}}

1. reserve(v.size())：提前开好足够空间，避免push_back循环里频繁扩容，提升效率。
2. 范围 for 遍历源v，push_back(e)把每个元素拷贝进新对象，调用元素的拷贝构造。

v的capacity中可能有大量备用位置，它们不是有效元素，没有理由作为内容复制。

• 拷贝构造出来的新vector：size == v.size()；
• capacity至少等于v.size()，不一定和原vector的capacity相等，标准库vector拷贝构造只保证容量≥ size，不会拷贝原容器多余的备用空间。

4.4 赋值重载

//拷贝交换voidswap(constvector<T>&v){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_end_of_storage,v._end_of_storage);}//=赋值（深拷贝）//现代写法vector<T>operator=(vector<T>v){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::vector<std::vector<int>>pascal(intnumRows){if(numRows<=0)return{};std::vector<std::vector<int>>result(numRows);for(size_t i=0;i<result.size();++i){result[i].resize(i+1,1);for(size_t j=1;j<i;++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：增加和移除元素