C++ STL的vector扩容比例

2021-09-12 本文已影响0人 MaloFleur

在vs下，vector 在插入新的元素时，如果容量已满的时候需要扩容为原容量的1.5倍
如果扩容是个常量（M），即下次扩容的容量为上次的M+K，若共有N个元素需要添加进vector(push_back)
则共需要N/M次扩容，若第一次容量为1，下一次1+M时需要复制1次，再下一次1+M```,1+KM(>=N)
则添加N个元素需要时间复杂度：
$\sum_{i=0}^{N/M}{(1+iM)}=O(N^2)$
平均时间复杂度为O(N)

如果扩容量是倍数（M），级下次扩容的容量为上次的MK，同理，共需要 $\log_MN$ 次，若第一次容量为1，下一次扩容为M时需要复制1次，再下一次M次···，M^K(>=N)
则添加N个元素需要时间复杂度：
$\sum_{i=0}^{\log_MN}{M^i}=\frac{1-MN}{1-M}=O(N)$
平均时间复杂度为O(1)

对于增长的倍数，一般不大于2，因为若倍数为2，参考如下分配：

由于两倍扩容，因此每次都是正好比上一次分配的空间大，因此之前分配的空间无法再复用
而若是1.5倍，同样的例子：

0
 01
   012
      01234
           01234567
                   0123456789ABC
012345···

可知，经历了几次扩容，之前的空间可以复用

C++ STL的vector扩容比例

猜你喜欢

热点阅读