市面上有无数vector的教程，但它们大多告诉你‘怎么用’，很少告诉你‘为什么这样设计’，他们一上来就摆术语，讲概念，如果你和我一样听得云里雾里，但是自己愿意深入探究技术概念的底层奥秘，那么这篇文章，我将带你以尽量轻松幽默的方式，做一件看似多余但极有价值的事：重新发明vector。我们将从一个最简单的固定数组开始，一步步解决遇到的所有问题，最终‘发明’出一个动态数组。
——前言
0 引子
这是一行邪恶的代码：
int employeesID[10000];
它的问题很明显，数组大小居然是硬编码在代码里的！这意味着一旦要输入第10001个数据的时候，就会因为数组没有这么长，地方不够用了！
注：这就叫缓冲区溢出
至于始作俑者写下这行代码的契机，一旁的注释写得很清楚：
//等到员工数量超过了10000个，我早就挣大钱跑路了，哈哈哈哈哈嗝
多年以后，我因为公司招了第10001名员工焦头烂额地调试员工系统时，始作俑者究竟有没有挣大钱我们不得而知，但可以肯定的是，TA一定已经跑路了…
1 “发明”vector
1.0 数组
首先我们得知道，当你写下int a[10]这一个数组的时候，是在告诉计算机：我要借10块内存，每一块的大小是一个int！
至于怎么向计算机借内存，我们可以写：
malloc(10*sizeof(int));
意思是：我要申请借(10块(int大小的));内存
计算机会告诉你：申请好了！我把这块内存的开头位置给你：
int* data = (int*)malloc(10 * sizeof(int));//用int指针存储内存的开头
如果这款内存我们不用了，不能一直占着，要把它还给计算机：
free(data);//将data的内存释放（还给计算机）
那为什么我们在写数字的时候不想考虑这么多？那是因为编译器自动帮你把这些事干了
1.0.0 数组操作
其实，在出问题之前这个数组一直是这样运作的：
int* data = (int*)malloc(10000 * sizeof(int));
分配了一块大小为10000的连续的内存，用data储存这块内存开头的地址。因为指针太麻烦，所以有好事者想出了“索引访问”的语法糖：
employeesID[n] 等效于 *(data+n)
所以，所谓索引访问，不过是将内存开头的地址向后移动若干位罢了。
注：很多初学者都会奇怪数组索引为什么是从零开始的，实际上只要你知道索引的真实意义是“从数组开头开始向后移动若干个地址”，那么我们想要表示数组的第1个数据，也就是数组开头的数据，自然就是“从数组开头开始向后移动0个地址”了
那么如果我们想获取当前员工总数该怎么办呢？于是我们又添加了一个size计数器：
int size=0;
每次我们在尾部添加的时候，只需要在size+1的索引下写入，然后再将size增加1即可：
employeesID[size+1]=num;//在最后一个数据后面添加
size++;//增加size计数器
因为这个操作很常用，所以我们把它封装成一个函数，就叫做push_back(num);
1.0.1 越界访问
当问题发生时，这个数组的状态是这样的：
//size=10000;
employeesID[size+1]=num;
//实际上是这样的：*(data+size+1)=num
//因为在初始化时data+size+1这块内存根本就没有借给我们，我们“偷”了不该用的内存，缓冲区就溢出了！
1.1 动态数组
1.1.0 复制数组
既然问题来源于数组的大小是定死的，那么解决方案也就很简单了，直接建立一块大小够用的数组，把原先的数据复制过去：
data2 = (int*)malloc((size+1) * sizeof(int));
for(…){…}//逐个把原先的数据复制到新数组
free(…);//原来的数组不用了，释放它的内存
这样每次添加都复制一个更大的数组，再也不会出现缓冲区溢出了！这下好了，万事大吉了…吗？
1.1.1 预分配策略
“这个员工系统怎么回事？”红温的老板夺门而入，说：“为什么每一次添加这么慢？”
我这才想到，原来每一次添加数据，都要经过“重新分配+复制”，时间复杂度是O(n)，自然是奇慢无比！
这时候，一旁的John提醒我：“既然我们需要频繁的重新分配，那为什么不干脆一开始就分配多一点呢？”
原来如此！于是我设计了一个capacity计数器，代表分配多少内存：
capacity*=2;
int* data = (int*)malloc(capacity * sizeof(int));//每一次需要重新分配内存时都倍增capacity，这样既不会频繁添加，又不会一次添加的太多
注：其实有的语言并不是2倍增（比如java Arraylist是1.5倍，python list增长大小不固定（大约1.125倍）），std::vector也并不是明文规定要2倍增，只是主流实现是2倍增，于是约定俗成了
在每一次需要复制的时候，就判断需要的size是否大于capacity：
if(size>capacity){
//倍增capacity
//重新分配内存
//复制原来数组
}else{
//直接push_back()
}
这样时间复杂度就变成了：扩容时O(n)，正常情况下O(1)
看着我的解决方案，老板说：“有时候我知道要招1000个新员工，能不能提前分配好内存，别到时候临时分配耗时间？”
又加新需求！于是我又添加了reserve(num)函数：
if(num>capacity){//预分配的内存大于当前已经分配的内存
capacity=num;
}
//如果预分配的内存小于或等于当前已经分配的内存，那么就什么也不干（不会缩小分配的内存）
如果我们要判断数组是否为空，于是我又添加了empty()函数，这也很好实现：直接判断size是否为0。
注：实际上编译器不是这么实现的，而是判断数组开头和数组结尾的指针是不是同一个，但是和判断size是否为0完全等价
这时候，老板对我说：“你分配这么多内存，万一不用不就浪费了吗？还是得有方法把它们释放了，你知道内存条涨价了…”
没办法，我只好一边吐槽老板抠门，一边实现了一个shrink_to_fit()函数：
if (capacity() > size()) {
// 创建新的、容量等于size的数组
// 复制数据到新数组
// 释放旧数组
// 更新指针和容量
}
这样就能保证capacity=size，不会有多余的内存了
1.1.2 下标访问
“不好了，程序又崩溃了！”我闻声看去，只看到一只在风中凌乱的John。报出异常的代码很简单：
int* id1=data();
//省略一大堆代码
*id1=114514;
凡事总须研究，才会明白。古来时常报错，我也还记得，可是不甚清楚。
我翻开代码库一查，这代码库没有fork日期，歪歪斜斜的每行注释上都写着"祖传代码"几个字。我横竖睡不着，仔细review了半夜，才从行间距里看出字来，满屏幕都写着四个字是——
"数组扩容"！
一道皮卡丘（10万伏特）从我大脑中闪过，在这两行代码中间，数组已经经过了扩容！
int* id1=data();
//数组经过了扩容，data指向了一个新的地址
*id1=114514;//原来的id1已经被释放了！不能再用了！
注：这就叫指针悬挂问题
一旦数组经过扩容，就意味着原来的指针、迭代器，全都失效了！
为什么指针会失效？
回忆一下扩容过程：
1.申请一块新内存
2.把旧数据复制过去
3.释放旧内存
扩容后， employeesID 内部的 data 指针已经指向了新地址，但外部的id1仍然指着已经被释放了的旧地址。
这怎么办呢？还是用回数组的老法子？
employeesID[0];//下标访问
虽然这样也可行，但是我不想再review一个晚上找不到错误了，于是我添加了一个安全访问的方法：
try{
employeesID.at(0);
}catch(…){…}
这样立刻就能捕获越界访问带来的异常
经常要访问首尾元素，每次都写[0]和[size-1]太麻烦，于是我还添加了便捷的访问第一个和最后一个数据的语法糖给程序员吃：
employeesID.front();//第一个数据
employeesID.back();//最后一个数据
但有时候我们需要记住某个位置，之后还要多次访问怎么办？指针会失效，下标也不够直观。于是我设计了迭代器：
employeesID.begin();//指向第一个数据
employeesID.end();//指向最后一个数据
迭代器在失效的时候会抛出异常，而不是像指针一样仍然会访问原先的内存，这样能做到更加安全的访问。
注：指针和迭代器是两个容易混淆的概念，但实际上是两种不同的数据类型，指针在迭代的时候只对连续的内存有效，他指向的是内存，但是迭代器可以作用于内存不连续的数据结构，它指向的是数据结构里的元素，迭代器本来设计的目的就是为了给各种STL容器（vector，链表…）提供统一的接口，初学者只需要记住两点：
1.与指针相似
2.便于遍历（范围for循环等等）和函数调用
1.1.3 删除
最近，公司又启动了“广进计划”：“裁员”广进，employeesID自然是一删一大把，主打就是你不干，有的是牛马干。为了我不在被删除之列，我先是实现了一个从尾部删除的pop_back()函数：
employeesID.back()=0;//清空最后一个数据
size--;//减少size
后来，John看到了我的函数实现，说：“你这清空最后一个数据根本就没必要啊！size减少了，这个数据根本就不会访问到，添加新数据的时候这个位置的数据又会被新数据覆盖。”
有道理啊，于是我干脆就把函数实现改成了：
size--;//没错，就是这么简单
由此总结出了一个经验：在实现删除时，覆盖比做空标记更加高效！
注意：为了简化，我们先以 int 为例。实际上，如果数组存储的是复杂对象（比如字符串、自定义类），在删除（比如这里的pop_back(),erase()和clear()）时需要调用这些对象的析构函数来正确清理资源。但因为我们目前只处理 int 这样的基本类型，所以暂时忽略这一点。这一章节我所写的所有示例实际上都是“错误的”（省略了析构的过程）。等我们讲到“模板”和“自定义类”时，再回头完善这个细节（哎呀，不小心又给自己挖了个坑）。
这时候老板又说：“我不光要在末尾删除，还要在数组中间删除，把这个功能也给我实现了。”补豪，这不是要对老员工下手吗？没办法，我想想如何实现一个erase()函数
首先，erase函数需要两种模式：没有删除指定位置元素和删除某个范围的元素。用什么数据类型的参数好呢？索引不够直观，指针又容易出问题，还是用迭代器吧，所以调用的时候应该写成这样：
employeesID.erase(employeesID.begin()+1); //删除第2个元素
employeesID.erase(employeesID.begin()+1,employeesID.end()-5);//删除第2个元素到倒数第6个元素的所有元素
那么我们怎么实现呢？有了上次的经验，我就知道了：不用管删除的数据，下一个数据开始，挨个儿把后续所有的元素向前复制，删多少个数据就复制到多少格之前，直接把要删除的数据覆盖掉：
这是初始数组:
A|B|C|D|E|F…
假如我们要删除第2-3个数据BC:
A|D|C|D|E|F…
直接将D复制到两格之前，覆盖掉B
A|D|E|D|E|F…
E复制到两格之前覆盖掉C
A|D|E|F|E|F…
F复制到两格之前，以此类推，一直到数组最后一个数据
size-=2;//最后数组删除了多少个数据就减少多少大小
因此你每次删除数据，后面的数据都会挨个复制一次，速度依旧奇慢，时间复杂度仍然是O(n)，但似乎没有什么好方法解决这个问题，先凑合用吧？
注：链表就可以解决这个问题！这个我们先挖个坑，以后再讲
最后，如果我们要清空数组的话，使用employeesID.erase(employeesID.begin(),employeesID.end())实在是太不直观了，因此我们要发明一个clear()函数：
employeesID.clear();
我们该怎么设计这个函数呢？我们只是清空这个数组，而不是销毁这个数组，所以我们没有必要把那些内存释放掉，万一这个数组清空后还要存东西呢？所以我们只需要写：
size=0;//没错，还是这么简单
再次强调，清空之后内存没有被释放，所以capacity不变
1.1.4 .resize()
老板又有了新需求：“有时候我们批量裁员，一次裁掉后50个员工。你这 pop_back() 一次只能删一个，太麻烦了！能不能一次性把数组缩到指定大小？”
这是裁员裁到大动脉了吗？裁这么多？
我只好实现一个resize()函数。这函数参数怎么设计呢？干脆就设计成一个表示改变之后的数组大小吧：
employeesID.resize(size_t newSize);
因为现在只能缩小，所以实现也是很简单的：
size=newSize;
可是好景不长，老板又要添加扩大数字的功能。现在这个写法也能实现扩大呀，只要newSize比原本的size大就行了，是不是不用改了呢？
“怎么又bug了？”John一声哀嚎，我差点把咖啡喷在我刚买的键盘上。
//capacity=10086
employeesID.resize(114514);
//size变成了114514！
我一看代码就发现了不对劲：newSize比capacity还要大，又尝试访问了不该访问的内存，缓冲区又溢出了！
这怎么解决呢？借鉴之前push_back()的扩容思路，我们可以将capacity倍增到两倍，不过要是newSize大于capacity的两倍怎么办？再倍增一次？不行，这样不优雅，而且可能造成浪费。遇到这种情况就直接把capacity改成newSize吧。
因此，我们可以这样写：
if(newSize<=capacity){
size=newSize;//size小于capacity，这是安全的，capacity保持不变
}else{
capacity=max(capacity*2,newSize);//两者取最大值
size=newSize;
//申请一块新内存
//把旧数组的数据复制到新数组
//释放旧数组的内存
}
老板又问：“有时候新员工有默认工号，比如9999，能自定义填充值吗？”
真烦！原来的那个函数还实现不了，我还要重载加上一个默认值参数：
employeesID.resize(size_t newSize,int defaultNum=0);
然后在函数实现中添加一个for循环：
// 在尾部默认构造新元素
for (size_type i = 0; i < add_count; ++i) {
employeesID[i]=defaultNum;
}
因此现在这个resize()函数终于完成了
注：作者在这一章中又省略了构造和析构
1.15 .insert()
“待会儿我要有一批新员工进来”老板晃悠悠地进来：“但是员工顺序要靠前，赶紧把这个功能实现了，明天就要上线。”
裁员的时候招人，ID比我们还靠前？这是走了什么关系进来的？
既然要插入，就要实现一个insert()函数，又到了设计函数参数的时候，既然insert()和erase()都是从中间操作数组，那么就把他们的参数设计成一样的迭代器吧：
employeesID.insert(要插入的位置的迭代器,要插入的值);
那么这该怎么实现呢？是不是需要把原先在这个位置上的数据给向后挪，才能给插入的数据腾出地方？
于是我实现了第1个版本的insert：
void insert(size_t index, int value) {
// 1. 从index开始，所有元素往后移
for (int i = index; i < size; i++) {
data[i+1] = data[i];
}
// 2. 在index位置放入新值
data[index] = value;
// 3. 大小增加
size++;
}
看起来没有什么问题？运行一下试试：
这是初始数组:
A|B|C|D|E|F…
假如我们要在第2个位置插入数据T:
A|B|B|D|E|F…
直接将B复制到下一格，覆盖掉C
A|B|B|B|E|F…
注意从这里开始就出现问题了！B覆盖了C，本来应该是C的位置现在是B，因此B复制到下一格覆盖掉D
A|T|B|B|B|B…
以此类推，一直到数组最后一个数据，全部都被换成了B！
那么我们怎么解决呢？问题的关键就出在“前面的数据污染了后面的数据”，因此我们为什么不像华容道一样先挪后面的数据再挪前面的数据呢？于是我写出了第2版：
void insert(int index, int value) {
//大小增加
size++;
//从size开始，所有元素往后移
for (int i = size; i > index; i--) {
data[i] = data[i-1];
}
//在index位置放入新值
data[index] = value;
}
好了，这样就没有问题了…吗？
流水的代码，铁打的扩容：如果size又超过了capacity，我们又要处理扩容了。
好啊，我们加一个逻辑判断：
if(++size<=capacity){
//正常插入
}else{
//扩容，逻辑与前面相同
//在扩容后的新数组内插入
}
John看了我的实现，说：“这个写法比erase还要更慢啊！先扩容入组已经一个个数据复制一次了，再插入，还要再一个个挪动一次。为什么不直接在复制的过程中插入呢？”
对呀，我现在的流程是这样的：
这是初始数组（size=capacity=6）:
A|B|C|D|E|F|
假如我们要在第2个位置插入数据T:
A|B|C|D|E|F|
A|B|C|D|E|F…
复制一个新数组（复制了6个数据）
A|B|C|D|E|F…
销毁旧数组
A|T|B|C|D|E|F…
执行插入操作（挪动了5个数据，复制了1个数据）
总计12个操作
这样插入非常麻烦
于是我们发明一种三段复制：
这是初始数组（size=capacity=6）:
A|B|C|D|E|F|
假如我们要在第2个位置插入数据T:
A|B|C|D|E|F|
A| | | | | …
先把插入位置前的复制过来（复制1个数据）
A|T| | | | …
再复制要插入的数据（复制1个数据）
A|T|B|C|D|E|F…
把剩下的其他数据复制过来（复制5个数据）
总计7个操作
这样插入简单快速很多
尽管确实更快了，但时间复杂度仍然是O(n)，充分体现了动态数组再插入删除方面的效率低下。
2 总结
这一篇文章带大家以重新发明vector的方式，深入浅出的讲解了vector的底层原理，也是帮助初学者避开一些常见的坑点，理清一些容易混淆的概念。光说不练假把式，我们留一道课后思考题，涉及了本文提到的一些函数，做完了把答案发到评论区：
std::vector<int> v(5,0);//初始化size=5,capacity=5
v.push_back(1);
v.shrink_to_fit();
v.reserve(v.size()-2);
v.insert(v.begin()+1,2);
v.erase(v.begin()+2,v.end()-2);
v.resize(25);
已知扩容增长因子为2，求当前数组的size()，capacity()，和数组存储的所有值
最后的最后，如果这篇文章真的对你有帮助，点个赞和收藏吧喵～
