小伙伴们大家好啊！

今天为大家带来vector的详解。那么因为vector和类似于数组。所以它的基本功能和数据是差不多的。所以今天我们将首先了解它的基本使用，其实了解对于vector而言，比较重要的几个内容，为了深刻理解它的实现，所以我们采用模拟实现，当然我们需要知道的是模拟实现并不是造出一个比源码更好地轮子，而是通过实现它的底层从而对它的功能更加了解。

好的，那么我们进入正题。

一，vector基本使用

1.1简介

那么对于第二个参数，本质上是一个空间配置器，也就是内存池，它的作用就是先将堆上的空间申请一部分出来，然后当vector使用空间的时候，效率就会比较高。仅此而已。

1.2基本使用

1.2.1构造函数

对于构造函数而言，主要关注图中标注出来的两个即可。分别是第一个无参构造，第四个拷贝构造。tips：函数前面的explict，是类中限制函数自动发生隐式类型转换。

1.2.2vector迭代器

那么可以看到vector的迭代器是随机迭代器。也就是说，它是支持随机访问的。同时，我们知道，所有的迭代器都是左闭右开的。

那么在vector中，我们需要关心的迭代器有以下四个，分别是正向和反向迭代器。

vector的迭代器可以理解为其底层是指针，这是因为vector::iterator是一个类似于指针的事物。而且也可以当做指针使用，可以通过解引用访问并修改值，如下图所示：?

对于语法糖范围for，其实它的本质是将迭代器进行了封装。然后才有了范围for的自动递增以及自动后移。

1.2.3vector空间有关

如上图所示，那么首先我们需要学习了解的有以上六个主要的函数。这里我们将其划分为三个部分。

其中第一部分是 size 和 capacity，size函数在vector中为计算元素个数，表示当前vector中有几个元素；capacity在很多地方都会用到，它表示容量大小，这里则表示vector一共能容纳的元素个数。

第二部分reserve 和 resize，他们两个都是为了扩容而来的（因为需要“防抖”，所以他们两都不能缩容）。而resize在增容的时候，还会在不改变原空间内容的情况下，将新增加的空间初始化为0，reserve则不会。

而当用户强制减小空间的时候，即时使用 resive，也是将原有容量空间的内容清空，但是容量不会减小。（在一些特殊的场合，需要“防抖”）

第三部分，empty 为检查空间是否为空，max_size 则表示空间的最大容量。

tips：不同编译器一次增容大下可能不一样，在vs2019下，每次都是1.5倍增容。而在linux，g++编译器下则是2倍增容。（具体的话，我们可以通过代码验证）?????????

总结来说，那么 reserve 只有扩容，而 resize 则是扩容 + 初始化。

1.3增删查改的基本认识

因为对于每个容器来说，他们的增删查改都比较重要，所以我们单独拎出来学习。

?那么首先，我们还是将其分为两个部分，首先就是元素访问。

1.3.1元素访问

那么在访问这一节是存在四个函数的。front 和 back 分别为访问首元素和尾元素。

而主要的则是operator[]，也就是下标访问。下标访问可以理解为数组，vector，string，顺序表等的一个最主要的特性，因为它支持随机访问，这样可以大大提供访问效率，减少空间浪费。

那么对于at函数来说，意义和下标操作符是一样的，不过at是一个函数，下标操作符是一个操作符，在本质上是不同的。

1.3.2增加，修改

首先，增加元素的函数有 push_back 尾插和 insert 指定位置的插入。

那么对于push_back来说，它只有值插入一个函数，没有其他的重载函数，这个需要注意。其次，对于 insert 来说，可以有很多种插入方式：

可以看到它是有三种不同的插入形式的，首先是指定位置的值插入。第二个是指定位置多个相等的值插入。第三个，是指定位置使用迭代器区间插入，就是将这一段迭代器区间的值插入到指定pios位置。

1.3.3删除

删除和增加是正好相反的动作。所以pop_back删除的也是值删除，而erase则有指定位置的删除和迭代器区间的删除。如下图所示：

1.3.4查找

对于查找，在vector中并没有提供接口实现，而是在算法库中实现了。可以看到它是通过一段迭代器区间查找指定的值的。?

1.3.5迭代器失效问题

因为对于当前vector的迭代器，底层就是一个 T* 的指针，那么也就是说，每当你通过该指针插入或者删除的时候，是会导致该指针指向的空间已经删除或者使用，那么就会导致该空间不属于该指针了，那么也就是出现了迭代器失效的问题，但是因为当我们了解了其底层实现以后，才能更好的了解他，所以我们将其放到后面模拟实现的时候去了解。?

那么对于迭代器失效的问题，在vector中，可以在使用前，首先将迭代器进行重新赋值。那么当迭代器使用后，就不会出现失效的问题了。

二，模拟实现vector

接下来我们通过一部分的模拟实现来更深层次的了解一下vector底层是如何实现的。

2.1构造析构

首先我们需要知道的是，vector它的底层是通过三个指针来限定的，也就是第一个元素位置的strat，最后一个数据后面位置的finish，还有表示容量大小的endofstorage。

那么需要注意的是析构的时候，new开辟的数组的析构是用 delete [ ] 。

2.2元素个数和容量

如下图所示，因为有三指针的存在，所以size大小和capacity大小就相对比较容易实现了，只需要用指针相减即可。因为指针的减法表示指针之间的距离大小，在vector中就可以表示为元素个数。

?

那么因为对于这些函数来说，并不会修改this对象的成员变量，也就是说，这些函数都不会修改this对象，那么在函数末尾加上const，可以有效的防止this对象被修改。虽然不是一个很重要的内容，但是养成一个良好的习惯，这样可能会避免很多错误。

2.3operator[]

在vector以及string等容易中，最有效的功能莫过于O(1)的访问效率了。所以下标操作符一定是不可或缺的。那么对于它的实现，因为_strat原先就是一个指针，所以可以使用下标，将i位置元素返回。但是同时需要注意的是要返回的元素的位置一定是存在的，那么直接暴力解题，用assert断言即可。

而他的返回值直接使用T&，就可以避免一次拷贝。而他可以使用引用的原因其实是 _strat[i]元素在该函数结束之后，并没有销毁，所以可以引用，否则使用引用就是内存泄漏了。

2.4 reserve 开空间

首先，reserve开空间，只能增容，不能缩容。这是为了“防抖”。

那么对于reserve而言，它是一个只开空间，其他任何事情不做的函数，所以我们只需要在空间满了之后，重新开辟出一个合适大小的空间，然后将原空间内容拷贝到新空间即可。

但是这里需要注意的有以下几个方面：

1.在拷贝的时候，不能直接用memcpy，因为mencpy是浅拷贝，也就是简单的值拷贝，那么就会导致在析构的时候，把新空间的内容释放了，因为他们的_strat都是指向同一个位置。

2.最后在计算_finish的时候，不要直接使用size()，因为size是原空间的元素个数，如果加上size，就会出错。

2.5resize开空间

不同于reserve，resize是一个可以扩容，可以缩容，而且在增容之后需要初始化新空间的函数。如下图所示：

首先，我们需要注意的是参数，第二个参数是一个模板参数，给了缺省值。缺省值是一个空值。其次，在函数实现中，有以下几个点：

1.如果是缩容，也就是给的n是小于原有元素个数的，那么我们直接将表示最后一个元素后面位置的 _finish 指针修正为 _strat+n 即可。因为我们不需要做其他操作。

2.如果是增容，则首先复用reserve开空间。然后将多余的空间初始化为val值。具体的操作为，因为开空间了之后 _finish的位置并没有发生变化，所以需要从 _finish 开始，依次将多开的空间赋初值为val。

2.6尾插push_back

在vector中，因为如果是头插或者中间插入，那么它的代价是很大的，因为需要移动元素，它的时间复杂度是O(N)。但是尾插的效率是很高的，所以在标准库中只提供了尾插，一般我们在使用的时候也是使用尾插。

三，迭代器

那么对于每个容器而言，迭代器基本都是必不可缺的。所以接下来的一部分我们在迭代器部分实现。

迭代器一般都被认为是一种类似于指针一样的事物，因为它的操作以及内容都和指针很相似。vector的迭代器基本可以认为就是原生指针，因为它的功能和指针基本没有区别。所以这里我们通过将原生指针封装为迭代器完成接下来的操作。

但是需要主要并不是所有的迭代器都是指针，比如list容器的迭代器就不是。

3.1begin() 和 end()

那么对于迭代器而言，首先需要认识的一定是第一个起始位置迭代器begin()，最后一个元素位置end()。因为是原生指针，所以起始和结束位置的迭代器是 _strat 和 _finish。那么const迭代器也是同样的。

3.2迭代器区间实现的构造函数

在1.2节我们将构造函数的所有重载结构都截图了，可以看到是有一个迭代器区间构造的构造函数的，所以接下来我们将其实现一下，如下图所示：所以为迭代器区间初始化，就是在一段迭代器区间中，将迭代器之间的值，依次尾插到 vector 中。

这里有个可能不太熟悉的InputIterator。那么对于迭代器而言，是分很多种的，那么这种是用在顺序容器中的一种迭代器，它对于每个元素都只会读取一次，然后依次往后迭带。所以它的等级基本是最低的。

3.3拷贝构造

刚刚在上面我们实现实现了迭代器区间的构造函数。接下来我们就可以通过现代写法实现拷贝构造了。如下图所示：首先用迭代器区间初始化了一个临时对象 tmp，然后接着通过交换函数，将vector 的三指针分别交换。然后在构造函数结束时，会调用析构函数将临时对象释放。这样就达到了“一石二鸟”的效果。

?

3.4赋值重载

对于赋值而言，在现代写法上基本和拷贝构造没有区别，因为他们的思路都是相同的，但是赋值重载的话，需要使用拷贝构造先构造出一个函数，然后再交换。?

但是这里，我们遇到了一个新问题，那就是赋值重载需不需要返回的问题，一般的想法就是，因为在交换之后，其实已经完成了赋值，那为什么还需要返回呢？

其实这里是为了防止出现链式访问。那么就需要返回值了，所以为了防止出现链式访问没法实现的情况，所以我们将返回值加上，是比较可靠的一种做法。而对于this而言，因为出了作用域并不会被销毁，所以一般情况下，返回值会用引用返回。

3.5insert插入

那么对于指定位置的插入。对于vector代价还是比较大的，因为需要移动元素。但是不管代价多大，依然还是要实现的。如下图所示：

首先需要迭代器位置时正确的，否则不能插入。

其次，因为有可能出现扩容的情况，而如果扩容了之后，那么原先pos位置的迭代器可能就不在原来的位置上了，那么就有可能导致出现迭代器失效的问题，所以在之前首先要记录下差值，然后在之后重新计算pos迭代器的值。

然后我们需要做的就是将 pos 位置到 _finish的所有元素后移一位。然后将x元素插入pos位置。