vector扩容2倍与1.5倍

如果按2倍扩容,第n次扩容需要的空间恰好比前n-1扩容要求的空间总和要大,那么即使在前n-1次分配空间都是连续排列的最好情况下,他们留下的空间也不足以分配给此次扩容。


理想分配方案是是在第N次resize()的时候能复用之前N-1次释放的内存,但选择两倍的增长比如像这样:

1,2,4,8,16,32,...

可以看到到第三次resize(4)的时候,前面释放的总和只有1+2=3,到第四次resize(8)的时候前面释放的总和只有1+2+4=7,每次需要申请的空间都无法用到前面释放的内存。

这样对cache和MMU都不够友好。