面试题：C++ vector内存增长策略及影响

Question

vector在内存不足时会以何种策略增长其容量？这种增长策略对性能和内存使用有什么影响？如果需要处理大量数据，如何调整vector的初始容量以提高效率？

Answer 1

1. vector容量增长策略
   • 当vector的容量（capacity）不足以容纳新元素时，通常会以倍数增长的策略来重新分配内存。常见的实现是将当前容量翻倍，例如当前容量为n，则新的容量为2n。不同的标准库实现可能在具体倍数上有差异，但大多是类似的指数增长方式。
2. 对性能和内存使用的影响
   • 性能影响：
     • 优点：指数增长减少了重新分配内存的次数。因为如果每次只增加固定大小的内存，随着元素不断添加，重新分配内存会非常频繁，而重新分配内存涉及到内存的申请、旧数据的拷贝等操作，开销较大。指数增长使得这种开销发生的频率降低，从而提高了整体性能。
     • 缺点：每次重新分配内存时，需要将旧的元素拷贝到新的内存位置，这在元素数量较多时会有一定的性能开销。而且，如果提前知道元素数量很多，前期频繁的小幅度增长会导致不必要的拷贝操作。
   • 内存使用影响：
     • 优点：由于不是每次添加元素都重新分配内存，避免了零碎的小内存块的产生，提高了内存的利用率。
     • 缺点：指数增长可能导致内存的预分配过多。例如，如果最终需要存储的元素数量远小于翻倍增长后的容量，就会造成内存浪费。
3. 调整初始容量提高效率
   • 如果需要处理大量数据，在创建vector时可以通过构造函数指定初始容量。例如，在C++ 中，可以这样创建vector：

std::vector<int> v(10000); // 初始容量为10000

• 或者使用reserve函数预先分配足够的空间：

std::vector<int> v;
v.reserve(10000);

• 通过提前预估数据量并设置合适的初始容量或预先分配足够空间，可以避免在添加元素过程中频繁的内存重新分配和数据拷贝，从而显著提高效率。