c++：vector

1.使用

1.1构造函数

常见的三种构造方式：空构造，拷贝构造，指定元素构造

1.2iterator

begin和end也分为正向和反向。

注意：反向迭代器可以反向遍历是因为在定义rbegin和rend函数的时候把尾地址给到了rbegin，而不是说改个reverse_iterator的名字就可以这么简单

1.3空间

（1）resize：可以用于确定元素个数的初始化，以及插入n个相同元素

（2）reserve：可以扩充数组容量

这是扩容前，我们看到它的空间容量是15

这扩容后，它的空间容量是30

1.4获取首尾数据

front:获取首数据，back获取尾元素

因为front取得是首元素，所以我们这里把首元素改成2，back取得是尾元素，所以这里我们把尾元素改成3

2.动态二维数组理解

静态的二维数组其实是先把划给数组的空间分为几大块，有几行就分几块，然后在每块里面再细分出来给具体的元素存储。

而动态的二维数组是先弄一个数组存每行的地址，这个地址是动态开辟的数组的地址，这个动态开辟的数组存的才是数据

3.迭代器的分类

1.单向迭代器：支持迭代器++

eg：单链表，哈希表

2.双向迭代器：支持++，--

eg：list，set，map

3.随机迭代器：支持++，--，=，-

eg：vector，string

4.底层部分实现

4.1基础结构搭建

（1）因为我们需要利用迭代器实现vector和算法的链接，所以先把迭代器typedef出来，对于数组结构，对应数据的指针就可以实现迭代器的功能

（2）之前的数组我们都是使用索引去访问数据，这里也是为了和算法接上，所以改成迭代器的形式，m_start表示首元素的迭代器位置，m_finish表示尾元素的下一个位置的迭代器位置。m_end_of_storage表示空间边界的下一个位置

4.2迭代器构建

首先是需要typedef出iterator，因为对于数组这个数据结构原生指针就可以充当迭代器实现访问。

然后我们把begin（）和end（）的值给上

4.3reserve实现

因为我们不实现缩容，所以这里我们需要知道capacity是多少，且后面的实现还需要知道有效数据个数，所以我们先把这两个功能实现一下

1.capacity

2.size

接下来实现reserve

首先判断是否满足指定的容量值大于当前容量值，若大于则开始进行扩容。

扩容：

1.根据val创建新的空间

2.拷贝对应值

3.释放旧空间

4.更新数组内置三个迭代器的值

但是这里会有个大问题：m_finish的指向会有问题

因为此时调用size，用的是旧的m_finish和新的m_start相减，m_start已经是指向新开辟的空间的迭代器，与m_finish八竿子打不着。我们有两种解决方式

方法一：换顺序

调换赋值顺序，我们把m_finish的赋值和m_start的赋值顺序换一下，这样就可以用旧的m_start和旧的m_finish相减，从而得到正确的size大小

方法二：变量存值

在扩容前，先用一个oldsize存储旧的size，后面赋值就不再调用size，而是直接使用oldsize。

方法二要比方法一更好，因为你无法保证其他程序员会不会去动你的代码顺序。

方法二实现

补充：由于实现模板需要考虑到各种数据类型，所以我们的reserve其实不能使用memcpy来实现数据拷贝，因为他是一个一个字节去拷贝的，实现的是浅拷贝。

对于需要深拷贝的我们应该实现深拷贝

这里对于内置类型则与之前没区别，但是对于自定义类型就可以调用赋值重载来实现深拷贝了

4.4尾插与尾删

尾插前判断容量是否足够，如果不足就reserve，不过也要考虑到capacity为0的情况，若为0就给四个字节空间，否则就按照原本空间两倍来开

插入数据就直接解引用给值即可。

4.5 任意位置插入

第一步：容量判断与扩容

第二步：挪动数据

第三步：插入数据并更新迭代器

注意：insert在需要扩容的情况下会出现pos迭代器失效的问题！！！

因为扩容后m_start和m_finish变位置了，而pos还是旧的位置，所以while循环会出问题。

我们应该在扩容完成前把旧的pos和start之间的距离保存下来，然后更新pos位置，用新的pos进行while判断

还有一个要注意的是，我们既然利用了迭代器去访问数据，就用上解引用符号来访问

一旦我们使用了insert或erase这些用了迭代器的方法之后，默认这个传入的迭代器就失效了，不能接着使用

4.6删除

第一步：挪动数据，从pos的下一个位置开始挪动，直到最后一个位置的元素也挪动完为止

第二步：更新迭代器

4.7resize实现

总共分两种情况：删除和插入

删除：需要的size大小比原来的size还小，所以删除，把m_finish更新一下即可

插入：需要的size大小比原来的size还大，所以插入，无论是否需要扩容，我们先reserve，对于需要扩容的reserve会自动扩，不用的则不会有任何操作。然后进行插入，直到到达目标size

4.8构造函数

（1）普通构造 注意：如果我们写了任意一个构造函数，系统就不会再给我们自动实现默认构造了

（2）拷贝构造

我们对于含有指针等类型的自定义类型需要实现深拷贝，而这里我们实现的是vector的模板，所以要考虑到这一点。

直接遍历然后尾插即可，不过因为尾插会涉及很多次扩容，效率较低，所以我们先提前用reserve开好空间

(3)数值直接传递的构造

在说这个构造之前我们先了解一下initializer_list这个类。

他和数组的使用很类似，不过他的类只支持begin，end和size三个方法。

和拷贝构造的实现方法类似，不再重复说明

使用：

这样我们就可以实现传递多个值的构造函数

（4）迭代器区间初始化

由于我们利用迭代器区间初始化的时候不仅仅是使用自己这个类的迭代器，而是适用于所有类型的迭代器，所以这里我们创建一个迭代器模板，以此兼容所有迭代器。

（5）n个数值构造

疑问：为什么我们要实现两个方法？

因为第一个方法在一种常见的情况下会出问题，导致匹配的构造方法是迭代器区间的构造方法。

这里我们的两个数据都是int型，而如果只实现第一个方法，在匹配度上就不如迭代器区间构造的匹配度，所以会调用迭代器区间初始化，造成非法间接寻址

所以我们多重载一个构造函数就可以解决这个问题