关于 vector 的扩容机制

往 vector 中添加元素时，如果空间不够将会导致扩容。 vector 有两个属性：size 和 capacity 。 size 表示已经使用的数据容量，capacity 表示数组的实际容量，包含已使用的和未使用的。

vector 扩容规则：

1. 当数组大小不够容纳新增元素时，开辟更大的内存空间，把旧空间上的数据复制过来，然后在新空间中继续增加。
2. 新的更大的内存空间，一般是当前空间的 1.5 倍或者 2 倍，这个 1.5 或者 2 被称为扩容因子，不同系统实现扩容因子也不同。

注意，扩容会导致迭代器失效。

在 VS2017 中，vector 的扩容因子是 1.5 。可以追踪 push_back 的实现：

函数中先通过_Has_unused_capacity 函数判断是否有还有未使用的空间，如果有未使用的空间，直接在未使用的空间上新增。如果没有未使用的空间了，就需要执行_Emplace_reallocate 重新扩容：

函数中先判断新长度，然后继续调用_Calculate_growth 扩容，这个函数才是真正用来扩容的函数。

忽略过其他判断逻辑，_Calculate_growth 的实现为：

新的扩容大小等于当前容量再加上当前容量的一半，即按照 1.5 倍扩容。

在 GCC 的实现中，vector 扩容是 2 倍扩容的。

1.5 倍扩容和 2 倍扩容的区别

1. 扩容因子越大，需要分配的新内存空间越多，越耗时。空闲空间较多，内存利用率低。
2. 扩容因子越小，需要再分配的可能性就更高，多次扩容耗时。空闲空间较少，内存利用率高。

因此，小规模数组，添加元素不频繁的，建议使用扩容因子更小的。当数据规模越大，插入更频繁，大扩容因子更适合。

示例代码

以上代码通过循环插入了十个元素，并打印出每次插入后 vector 的容量：

能看出的增长规律为：0 -> 1 -> 2 -> 3 -> 4 -> 6 -> 9 -> 13，而同样的代码通过 G++编译后的输出结果为：