Vecotr扩容

                                                                           Vecotr扩容

1. 扩容原理

初始时刻vector的capacity为0，塞入第一个元素后capacity增加为1。

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

对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了 ；（vector迭代器失效问题）。

 新增元素：Vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素；

2. 为什么采用成倍的扩容方式

对比可以发现采用采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此，使用成倍的方式扩容。

考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2二倍的方式扩容，或者以1.5倍的方式扩容。1.5倍的增长方式可以更好的实现对内存的重复利用，因此更好。