capacity 扩容规则是什么？

Question

#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> vec = {1, 2, 3};
  vec.push_back(5);
  cout << vec.size() << endl;
  cout << vec.capacity() << endl;

  return 0;
}

此时输出是 4 4；
代码为

#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> vec = {1, 2, 3, 4};
  vec.push_back(5);
  cout << vec.size() << endl;
  cout << vec.capacity() << endl;

  return 0;
}

此时输出是 5 6；

感觉扩容好像是2的倍数这种，这是为什么？

Answer 1

quickzhao 2022-04-05 10:47:00

算法实现上乘以一个扩容因子很简单，方便；但要根据实际情况：

因子大，需要分配的新内存空间越多，越耗时，空闲空间较多，内存利用率低。因子越大，需要分配的新内存空间越多，越耗时。空闲空间较多，内存利用率低；

因子小，需要再分配的可能性就更高，多次扩容耗时。空闲空间较少，内存利用率高。

一般这个因子为1.5或2,不同版本可能会有差异。

• 提问者 学以致用over #1

  非常感谢！

Answer 2

易萧 2022-08-08 11:25:38

动态扩容其实本质上是内存回收再分配，原有的内存地址如果其后紧接别的数据，那么数组想要扩容只能另寻它处，将原来内存的数据全部搬到一个新的地方，这个过程是O(n)级别的，但你只不过是想做一次append操作，这样当然是不划算的，因此只能换一种策略，第一个就是链表，它就是因此而诞生，添加删除是O(1)的，但访问是O(i)的，你访问第i个元素，必须从头进行遍历。第二种策略就是使之摊销复杂度为O(1)，当你有4个元素时想扩容，那么我有理由认为以后也可能会增加8个元素，这样一次O(n)的操作分摊到n次O(1)的增加操作上，就实现了摊销复杂度为O(1)的扩容。删除稍微复杂一点，因为过多的删除却不缩减容量会导致内存浪费，所以到达临界值是会裁掉的，但这个临界值却不是最初扩容时的那个值，因为如果某一段操作一直在临界容量反复横跳，就会导致容器不断地扩容又裁剪，所以这个临界值会比扩容初值更低，称为防抖。

扩容策略我也只了解到这里，更多优化细节上没有太多了解，比如如果内存地址后面有可用的扩容空间是否会直接扩容而不搬移数据，这时扩容容量可能并非完全由扩容因子（扩容倍数）决定，但会趋于它，如果是我来设计vector的话，我会这样做。