vector扩容原理说明

扩容原理概述

新增元素：Vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素
对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了
初始时刻vector的capacity为0，塞入第一个元素后capacity增加为1

不同的编译器实现的扩容方式不一样，VS2015中以1.5倍扩容，GCC以2倍扩容。

代码

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> vec;
    cout << vec.capacity() << endl;
    for (int i = 0; i<10; ++i)
    {
        vec.push_back(i);
        cout << "size: " << vec.size() << endl;
        cout << "capacity: " << vec.capacity() << endl;
    }
    system("pause");
    return 0;
}

输出：

GCC输出

VS2015输出

分析：

可以根据输出看到，vector是以2倍的方式扩容的。有两个疑问：
- 为什么要成倍的扩容而不是一次增加一个固定大小的容量呢？
- 为什么是以两倍的方式扩容而不是三倍四倍，或者其他方式呢？
第一个问题：
- 以成倍方式增长
  1. 假定有 n 个元素,倍增因子为 m；
  2. 完成这 n 个元素往一个 vector 中的 push_back操作，需要重新分配内存的次数大约为 logm(n)；
  3. 第 i 次重新分配将会导致复制 m^(i) (也就是当前的vector.size() 大小)个旧空间中元素;
  4. n 次 push_back 操作所花费的时间复制度为O(n): $\sum_{i=1}^{\log _{m}^{n}} m^{i} \approx \frac{n m}{m-1}$
  5. m / (m - 1)，这是一个常量，均摊下来vector中push_back操作的时间复杂度为常量时间.
- 一次增加固定值大小
  1. 假定有 n 个元素,每次增加k个；
  2. 第i次增加复制的数量为：k*i
  3. n 次 push_back 操作所花费的时间复杂度为O(n^2): $\sum_{i=1}^{n / k} k i$
  4. 均摊下来每次push_back 操作的时间复杂度为O(n)；
总结：对比可以发现采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此，使用成倍的方式扩容。
第二个问题：
1. 根据查阅的资料显示，考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2二倍的方式扩容，或者以1.5倍的方式扩容。
2. 以2倍的方式扩容，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为(1,2)之间:
  $k \sum_{i=0}^{n} 2^{i}=k\left(2^{n+1}-1\right)<k 2^{n+1}$
- 知乎上看到一个很好的解释：
  
  C++ STL中vector内存用尽后，为啥每次是两倍的增长，而不是3倍或其他数值
- 借用他的一张图来说明2倍与1.5倍的区别：