十二、动态数组
本篇讨论C++中的动态数组，就是标准库的vector类(std::vector)。
我们之前讲的像常量、变量、指针、数组、类、结构体等都是C++的内置数据类型(built in)，从现在开始我们终于开始讲标准库的类型了。这些也是C++的基础。
标准库也叫标准模板库，本质上还是一个库，就是里面装的都是容器，容器类型(container type)。这些容器包含特定的数据，所以被称为标准模板库，因为它可以模板化任何东西。整个库模板化意味着容器的底层数据类型。也就是说，容器包含的数据类型，实际上是由你决定，所有东西由模板(template)组成。如果你还不了解模板，那也不妨碍你先学习如何使用标准模板库，你只要知道模板可以处理你提供的底层数据类型。也就是你不需要编写自己的数据结构。
此后我们会重写很多C++中存在的数据结构，会对它们进行优化，使其比标准模板库中的快很多，因为标准模板库优先考虑的不是速度。也所以我们在实际工作中，一般是要创建自己的容器库，一般都比标准模板库快得多。
1、静态数组
作为对比先写一个静态数组的两种用法：
这种创建数组的做法就是你提前要明确告诉程序你要创建多长的数组。数组存放的内存大小一旦定下就不能改变了。而现实情况是，我们也不知道用户要输入多少数据，只能边输入边看了。此时我们就需要更高层的解决方案——动态数组了。
2、什么是动态数组
C++给我们提供一个叫做Vector的类，这个Vector在std命名空间中。Vector不是向量的意思，更为准确的说是ArrayList，因为它的本质是一个动态数组。但与我们之前讲的数组类型不同的是，它可以调整数组的大小。意思就是当你创建一个vector时，它是没有固定大小的(当然你也可以初始化一个特定的大小，但一般我们不这样做)，我们也不需要care它的大小，只要把元素放进去就行。每次你放入一个元素，数组的大小就会增长。就是当你写入的内容超过了分配的大小，它会在内存中创建一个比第一个大的新数组，然后把所有东西都复制到新数组，并删除旧数组，这样就实现了动态。其实就是不断地分配一个个静态数组，以达到动态的效果。
3、动态数组的基本用法
（1）手写要包含vector头文件。
（2）创建动态数组
A处：<>里面写的是数组中的元素的类型，这里我们都放Book类类型。后面跟的bs就是你要创建的动态数组的名字，这里我取名bs。
在C++模板中，<>里面也可以传递原始类型，比如vector v1;或者vector v2;等等。
普通数组的底层都是存储的是一堆指针，比如上上图可以说就是一个二维数组了，那底层也是一个二维指针，有一步跨一个元素的，有一步走一个float的。
但是动态数组底层没有bs指针。实际上只是把bs存储在一条直线（一段内存）上, in line，这是普通数组和动态数组之间最大的区别。
有人会问，是否应该把指向堆分配的类对象的指针，存储在bs中？或者是否应该存储栈分配、一条线上分配的Book类或者结构体？答案是视情况而定。因为很难决定你是否应该使用Book指针还是Book对象。但是你要知道，存储Book对象比存储指针在技术上更优。因为如果是Book对象，你的内存分配将是一条线上的。
动态数组是内存连续的数组，也就是它在内存中不是碎片，而是在一条线上。如果你像这样将Book对象存储在一条直线上，xyzxyzxyz....,这种一个接一个的，这就是最优的。因为如果你要遍历、修改等操作，它们都在同一条高速缓存线上。所以如果可以的话，我们尽量要像这样(一条线上)分配。唯一的问题是，如果要调整bs的大小,就要复制所有的数据。如果你碰巧是一个字符串的Book,那你要调整bs,就要重新分配和复制所有的东西，这可能是一个非常缓慢的操作。
这里作者的原话是：moving instead of copying largerly solves this particular issue, but there is still some copying which is not ideal.
而指针就不同了，因为你的实际内存是保持不变的，你只要能正确的保存了指向内存的指针就可以了。到了调整大小的时候，只是调整下实际数据的内存地址，而实际数据仍然被存储在内存中的不同位置。
所以说这两种操作很难说哪种好，但是这里我想强调的是，尽量使用对象而不是指针，除非不得不选指针。
B处：给数组添加元素。使用.push_back()，也就是初始化每个Book类实例。
（3）遍历数组
遍历数组，上图的CDE三种方法都可以。
C处：因为vector是一个完整的类，所以我们是知道bs的大小的，用bs.size()即可。也所以我们也是可以使用索引[]操作符的。
D处：实际上是将bs中的每个Book实例都逐个复制到for循环中，然后打印出来。
E处：前面我们刚刚讲过，尽量不要copy,所以E处我们就是对bs中的每个Book类实例进行了引用。当然E处不要const也是可以的。
（4）动态数组被当作参数传递给一个函数
对复制 【C++】理解C++中的复制、复制构造函数-CSDN博客 这篇博文有感触的同学就一定会记得：一定一定要确保你是通过引用传递的。千万别把整个数组复制到函数中去。
（5）删除数组列表
F处：将数组大小设为0。
G处：erase会返回vector_iterator,返回的类型是Book。G处是erase的函数，可以看到参数是const iterator。所以erase的参数应该是个迭代器。
H处：如果我只想擦除第二个元素，也就是索引是1的元素，我就可以通过H代码实现。其中bs.begin()返回的是0。
4、vector使用优化
vector通常情况下是很慢的，所以我们需要想尽办法尽力榨出所有的性能。本部分讲如何优化，如何避免重新分配，如何避免复制等技巧。总之就是怎么以一种更优化的方式使用vector类，就是优化vector的使用。C++语言能很好的发挥优化的作用，但是前提是你要先清楚vector是如何工作的，你才能想办法改变它，使之更好的工作。
当我们创建一个vector，然后开始push_back元素，也就是向数组逐个添加元素。也就是我们现在存储的不是vector指针，存储的是vector对象。我们先看下面代码的运行结果：
上面代码都是非常普通的、写入数组元素的代码，但是不可思议的是，就仅仅写入了4个元素，就copy了1+2+3+4=10次之多！也销毁了同样多次！不断地复制再销毁这多浪费时间和性能啊！而且这个复制和销毁的次数是随着输入的元素增加而增加的，就是越往后存储越慢！下面我们分析一下为什么会出现这么多复制和销毁。
首先，我们从代码运行结果来看：
当代码运行到B处之前，也就是我们push_back第一个元素时，在push_back()之前，其实是先运行Book(1,2,3),就是先实例化一个x=1,y=2,z=3的Book类实例，所以就先调用了初始化构造函数a。而这个工作是在主函数main的当前栈帧中构造的，就是说是在main的栈上创建了Book(1,2,3)。然后push_back要做的就是把main函数中的Book(1,2,3)放到实际的vector分配的内存中，所以实例对象Book(1,2,3)被复制了一次，从main函数复制到vector类中。所以调用了一次复制构造函数b。当复制完毕，还得销毁main中的Book(1,2,3)，所以又调用了一次析构函数e。
可见，如果我们直接构建(创建)Book实例对象，在vector分配的内存中，是不是就省去了一次复制和销毁？这是优化的一个点。下面我们看看优化结果：
我们只要把push_back替换成emplace_back即可，此时emplace_back方法传递给vector的就不是已经实例化好的Book(1,2,3)了，而是传递的只是Book构造函数的参数列表。那创建Book(1,2,3)的工作就可以在vector内存中构造了。也就是直接在vector内存中初始化三个float：1,2,3，分别表示x,y,z。就算是在vector内存区域存储了第一个元素了。
也所以上图我们每个元素都减少了一次复制和销毁。
但是，代码运行中依然还有复制和销毁，那我们再打断点看看问题出在哪里：
发现，我们的动态数组bs创建时，长度竟然是0！我们前面说过，如果当vector的容量不够时，vector就开始分配新的、更大的内存，将当前的vector的内容，从内存中的旧位置复制到内存中的新位置，然后删除旧位置的内存。这也正好和上上图的运行结果对上了！输入第一个元素的时候就是直接创建，但输入第二个元素时，除了创建第二个元素外，还得复制第一个元素。同理输入第三个元素时，又复制了第一、二个元素！就是我们每输入一个元素，就要重新找一块连续的内存把之前的所有元素都copy到新位置，还得再删除旧位置上的元素。就是出现了不断分配、复制的操作了。如何避免？下面是我们的优化代码：
上面代码仅仅是增加了一行bs.reserve();表示一开始就给我留多少个元素的内存空间，因为我大概还是知道我要输入多少东西的。这里就是设置大致的容量，以防止没有意义的拷贝。
此时我们的代码要比之前快很多，这就是优化的过程，也就是先找到代码拖慢的原因，了解解决的工具，就可以逐个解决或避免了。