[C++STL]从数组到vector：我发明了动态数组！

市面上有无数vector的教程但它们大多告诉你‘怎么用’很少告诉你‘为什么这样设计’他们一上来就摆术语讲概念如果你和我一样听得云里雾里但是自己愿意深入探究技术概念的底层奥秘那么这篇文章我将带你以尽量轻松幽默的方式做一件看似多余但极有价值的事重新发明vector。我们将从一个最简单的固定数组开始一步步解决遇到的所有问题最终‘发明’出一个动态数组。——前言0 引子这是一行邪恶的代码int employeesID[10000];它的问题很明显数组大小居然是硬编码在代码里的这意味着一旦要输入第10001个数据的时候就会因为数组没有这么长地方不够用了注这就叫缓冲区溢出至于始作俑者写下这行代码的契机一旁的注释写得很清楚//等到员工数量超过了10000个我早就挣大钱跑路了哈哈哈哈哈嗝多年以后我因为公司招了第10001名员工焦头烂额地调试员工系统时始作俑者究竟有没有挣大钱我们不得而知但可以肯定的是TA一定已经跑路了…1 “发明”vector1.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] 等效于 *(datan)所以所谓索引访问不过是将内存开头的地址向后移动若干位罢了。注很多初学者都会奇怪数组索引为什么是从零开始的实际上只要你知道索引的真实意义是“从数组开头开始向后移动若干个地址”那么我们想要表示数组的第1个数据也就是数组开头的数据自然就是“从数组开头开始向后移动0个地址”了那么如果我们想获取当前员工总数该怎么办呢于是我们又添加了一个size计数器int size0;每次我们在尾部添加的时候只需要在size1的索引下写入然后再将size增加1即可employeesID[size1]num;//在最后一个数据后面添加size;//增加size计数器因为这个操作很常用所以我们把它封装成一个函数就叫做push_back(num);1.0.1 越界访问当问题发生时这个数组的状态是这样的//size10000;employeesID[size1]num;//实际上是这样的*(datasize1)num//因为在初始化时datasize1这块内存根本就没有借给我们我们“偷”了不该用的内存缓冲区就溢出了1.1 动态数组1.1.0 复制数组既然问题来源于数组的大小是定死的那么解决方案也就很简单了直接建立一块大小够用的数组把原先的数据复制过去data2 (int*)malloc((size1) * 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是否大于capacityif(sizecapacity){//倍增capacity//重新分配内存//复制原来数组}else{//直接push_back()}这样时间复杂度就变成了扩容时O(n)正常情况下O(1)看着我的解决方案老板说“有时候我知道要招1000个新员工能不能提前分配好内存别到时候临时分配耗时间”又加新需求于是我又添加了reserve(num)函数if(numcapacity){//预分配的内存大于当前已经分配的内存capacitynum;}//如果预分配的内存小于或等于当前已经分配的内存那么就什么也不干不会缩小分配的内存如果我们要判断数组是否为空于是我又添加了empty()函数这也很好实现直接判断size是否为0。注实际上编译器不是这么实现的而是判断数组开头和数组结尾的指针是不是同一个但是和判断size是否为0完全等价这时候老板对我说“你分配这么多内存万一不用不就浪费了吗还是得有方法把它们释放了你知道内存条涨价了…”没办法我只好一边吐槽老板抠门一边实现了一个shrink_to_fit()函数if (capacity() size()) {// 创建新的、容量等于size的数组// 复制数据到新数组// 释放旧数组// 更新指针和容量}这样就能保证capacitysize不会有多余的内存了1.1.2 下标访问“不好了程序又崩溃了”我闻声看去只看到一只在风中凌乱的John。报出异常的代码很简单int* id1data();//省略一大堆代码*id1114514;凡事总须研究才会明白。古来时常报错我也还记得可是不甚清楚。我翻开代码库一查这代码库没有fork日期歪歪斜斜的每行注释上都写着祖传代码几个字。我横竖睡不着仔细review了半夜才从行间距里看出字来满屏幕都写着四个字是——数组扩容一道皮卡丘10万伏特从我大脑中闪过在这两行代码中间数组已经经过了扩容int* id1data();//数组经过了扩容data指向了一个新的地址*id1114514;//原来的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复制到两格之前覆盖掉BA|D|E|D|E|F…E复制到两格之前覆盖掉CA|D|E|F|E|F…F复制到两格之前以此类推一直到数组最后一个数据size-2;//最后数组删除了多少个数据就减少多少大小因此你每次删除数据后面的数据都会挨个复制一次速度依旧奇慢时间复杂度仍然是O(n)但似乎没有什么好方法解决这个问题先凑合用吧注链表就可以解决这个问题这个我们先挖个坑以后再讲最后如果我们要清空数组的话使用employeesID.erase(employeesID.begin(),employeesID.end())实在是太不直观了因此我们要发明一个clear()函数employeesID.clear();我们该怎么设计这个函数呢我们只是清空这个数组而不是销毁这个数组所以我们没有必要把那些内存释放掉万一这个数组清空后还要存东西呢所以我们只需要写size0;//没错还是这么简单再次强调清空之后内存没有被释放所以capacity不变1.1.4 .resize()老板又有了新需求“有时候我们批量裁员一次裁掉后50个员工。你这 pop_back() 一次只能删一个太麻烦了能不能一次性把数组缩到指定大小”这是裁员裁到大动脉了吗裁这么多我只好实现一个resize()函数。这函数参数怎么设计呢干脆就设计成一个表示改变之后的数组大小吧employeesID.resize(size_t newSize);因为现在只能缩小所以实现也是很简单的sizenewSize;可是好景不长老板又要添加扩大数字的功能。现在这个写法也能实现扩大呀只要newSize比原本的size大就行了是不是不用改了呢“怎么又bug了”John一声哀嚎我差点把咖啡喷在我刚买的键盘上。//capacity10086employeesID.resize(114514);//size变成了114514我一看代码就发现了不对劲newSize比capacity还要大又尝试访问了不该访问的内存缓冲区又溢出了这怎么解决呢借鉴之前push_back()的扩容思路我们可以将capacity倍增到两倍不过要是newSize大于capacity的两倍怎么办再倍增一次不行这样不优雅而且可能造成浪费。遇到这种情况就直接把capacity改成newSize吧。因此我们可以这样写if(newSizecapacity){sizenewSize;//size小于capacity这是安全的capacity保持不变}else{capacitymax(capacity*2,newSize);//两者取最大值sizenewSize;//申请一块新内存//把旧数组的数据复制到新数组//释放旧数组的内存}老板又问“有时候新员工有默认工号比如9999能自定义填充值吗”真烦原来的那个函数还实现不了我还要重载加上一个默认值参数employeesID.resize(size_t newSize,int defaultNum0);然后在函数实现中添加一个for循环// 在尾部默认构造新元素for (size_type i 0; i add_count; i) {employeesID[i]defaultNum;}因此现在这个resize()函数终于完成了注作者在这一章中又省略了构造和析构1.15 .insert()“待会儿我要有一批新员工进来”老板晃悠悠地进来“但是员工顺序要靠前赶紧把这个功能实现了明天就要上线。”裁员的时候招人ID比我们还靠前这是走了什么关系进来的既然要插入就要实现一个insert()函数又到了设计函数参数的时候既然insert()和erase()都是从中间操作数组那么就把他们的参数设计成一样的迭代器吧employeesID.insert(要插入的位置的迭代器,要插入的值);那么这该怎么实现呢是不是需要把原先在这个位置上的数据给向后挪才能给插入的数据腾出地方于是我实现了第1个版本的insertvoid insert(size_t index, int value) {// 1. 从index开始所有元素往后移for (int i index; i size; i) {data[i1] data[i];}// 2. 在index位置放入新值data[index] value;// 3. 大小增加size;}看起来没有什么问题运行一下试试这是初始数组:A|B|C|D|E|F…假如我们要在第2个位置插入数据T:A|B|B|D|E|F…直接将B复制到下一格覆盖掉CA|B|B|B|E|F…注意从这里开始就出现问题了B覆盖了C本来应该是C的位置现在是B因此B复制到下一格覆盖掉DA|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(sizecapacity){//正常插入}else{//扩容逻辑与前面相同//在扩容后的新数组内插入}John看了我的实现说“这个写法比erase还要更慢啊先扩容入组已经一个个数据复制一次了再插入还要再一个个挪动一次。为什么不直接在复制的过程中插入呢”对呀我现在的流程是这样的这是初始数组sizecapacity6: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个操作这样插入非常麻烦于是我们发明一种三段复制这是初始数组sizecapacity6: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::vectorint v(5,0);//初始化size5,capacity5v.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()和数组存储的所有值最后的最后如果这篇文章真的对你有帮助点个赞和收藏吧喵