在vs下，vector 在插入新的元素时，如果容量已满的时候需要扩容为原容量的1.5倍
如果扩容是个常量（M），即下次扩容的容量为上次的M+K，若共有N个元素需要添加进vector(push_back)
则共需要N/M次扩容，若第一次容量为1，下一次1+M时需要复制1次，再下一次1+M```,1+KM(>=N)
则添加N个元素需要时间复杂度：
平均时间复杂度为O(N)
如果扩容量是倍数（M），级下次扩容的容量为上次的MK，同理，共需要次，若第一次容量为1，下一次扩容为M时需要复制1次，再下一次M次···，MK(>=N)
则添加N个元素需要时间复杂度：
平均时间复杂度为O(1)
对于增长的倍数，一般不大于2，因为若倍数为2，参考如下分配：
0
01
0123
01234567
由于两倍扩容，因此每次都是正好比上一次分配的空间大，因此之前分配的空间无法再复用
而若是1.5倍，同样的例子：
0
01
012
01234
01234567
0123456789ABC
012345···
可知，经历了几次扩容，之前的空间可以复用
网友评论