vector扩容面试题总结

vector

底层数据结构是一个动态数组。

默认构造的方式是0， 之后插入按照1 2 4 8 16 二倍扩容。注（GCC是二倍扩容，VS13是1.5倍扩容。原因可以考虑内存碎片和伙伴系统，内存的浪费）。扩容后是一片新的内存，需要把旧内存空间中的所有元素都拷贝进新内存空间中去，之后再在新内存空间中的原数据的后面继续进行插入构造新元素，并且同时释放旧内存空间，并且，由于vector 空间的重新配置，导致旧vector的所有迭代器都失效了。

GCC:

VS2013

从这里我认为vector的初始的扩容方式代价太大,初始扩容效率低， 需要频繁增长，不仅操作效率比较低，而且频繁的向操作系统申请内存容易造成过多的内存碎片，所以这个时候需要合理使用resize()和reserve()方法提高效率减少内存碎片的，需要

resize()

1、resize方法被用来改变vector中元素的数量，我们可以说，resize方法改变了容器的大小，且创建了容器中的对象；

2、如果resize中所指定的n小于vector中当前的元素数量，则会删除vector中多于n的元素，使vector得大小变为n；

3、如果所指定的n大于vector中当前的元素数量，则会在vector当前的尾部插入适量的元素，使得vector的大小变为n，在这里，如果为resize方法指定了第二个参数，则会把后插入的元素值初始化为该指定值，如果没有为resize指定第二个参数，则会把新插入的元素初始化为默认的初始值；

4、如果resize所指定的n不仅大于vector中当前的元素数量，还大于vector当前的capacity容量值时，则会自动为vector重新分配存储空间；

reserve():

1、reserve方法被用来重新分配vector的容量大小；

2、只有当所申请的容量大于vector的当前容量时才会重新为vector分配存储空间；小于当前容量则没有影响

3、reserve方法对于vector元素大小没有任何影响，不创建对象。

vector中数据的随机存取效率很高，O(1)的时间的复杂度，但是在vector 中随机插入元素，需要移动的元素数量较多，效率比较低。

vector中resize与reserve的区别（提高效率）
我们先看一下Cplusplus中对resize与reserve的表示吧：

reserve：（预留一定的空间）
reserve是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题，就可以提高效率，其次还可以减少多次要拷贝数据的问题。
reserve只是当要开辟空间大于其原空间会开辟至需要的空间，而小于就不会更改其空间。
reserve只是保证vector中的空间大小（capacity）最少达到参数所指定的大小n
在区间[0, n ]的范围内，如果下标是index，vector[index]有可能是合法的，也有可能是非法的，具体视情况而定。
resize：（重新分配大小）
若要开辟的空间的size大于其原来的size，那么resize之后要存放的数据就放在原size后的位置上。
若要开辟的空间小于原size则就保留前n个数据（之后的会自动的删除）
为了实现resize的语义，resize的接口做了两个保证：
1、保证区间[0, newsize]范围内的数据是有效的，下标index在这个区间内的话，那么vector[index]就是有效的。
2、保证区间[0, newsize]范围外的数据是无效的，下标index在这个区间外的话，那么vector[index]就是无效的。

reserve与resize的相同点：
就是它们都保证了vector空间的大小，至少达到它们参数所指定的大小。
下面给出reserve与resize的源码：
reserve：