當前位置:編程學習大全網 - 網站源碼 - C++ STL的vector擴容比例

C++ STL的vector擴容比例

在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次···,M K (>=N)

則添加N個元素需要時間復雜度:

平均時間復雜度為O(1)

對於增長的倍數,壹般不大於2,因為若倍數為2,參考如下分配:

由於兩倍擴容,因此每次都是正好比上壹次分配的空間大,因此之前分配的空間無法再復用

而若是1.5倍,同樣的例子:

可知,經歷了幾次擴容,之前的空間可以復用

  • 上一篇:java echarts
  • 下一篇:dubbo 2.8.3 支持jdk1.7麽
  • copyright 2024編程學習大全網