背景

vector里的内存已经满了后，在插入新的元素时就需要扩容，在 VS 下是 1.5倍，在 GCC 下是 2 倍。那么会产生两个问题：
（1）为什么是成倍增长，而不是每次增长一个固定大小的容量呢？
（2）为什么是以 2 倍或者 1.5 倍增长，而不是以 3 倍或者 4 倍等增长呢？

扩容机制

机制一

扩容以成倍方式增长：假设从1开始，扩容到100个大小，每次扩容2倍，vector的push_back的操作次数可以是logmN，也就是log2(100)，换算下来大概是需要进行7次扩容，这样的话，数据需要拷贝7次。

扩容以倍数方式增长：假设需要扩容到100个，每次扩容10个值，则需要扩容10次，但是如果要扩容到1000个，扩容的次数就需要更多，如果需要扩容到5个，则倍数为10又太大了。

总结：以倍数方式增长的扩容方式扩容的次数比成倍方式更多，而且倍数的值也不好确定。

机制二

在 VS 下是1.5倍，在 GCC 下是2倍方式增长。

使用 k=2 增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和：
$$
c\sum_{i=1}^{n}2^i=c(2^{n+1}-1) < c2^{n+1}
$$
也就是说，之前分配的内存空间不可能被使用。这样对于缓存并不友好。最好把增长因子设为 1 < k < 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
k = 2,c = 4
0123
	01234567
			0123456789ABCDEF
							0123456789.......
k = 1.5,c = 4
0123
	012345
		  012345678
		  		   0123456789ABCD
		  		   				 0123456789ABCDEF0123
0123456789ABCDEF0123456789ABCD
							  0123.....

总结：如上图所示，当 k =1.5 时，在几次扩展以后，可以重用之前的内存空间了。