Effective STL 学习笔记14： Use reserve to avoid unnecessary reallocations.

时间：2022-05-25 13:18:32

vector 和 string 容器在动态插入一个新的对象时，如果容器内空间不够，该容器会：

  1. 重新分配空间
    通常的做法是分配当前 Capacity 大小两倍的空间。
  2. 将旧空间中的所有元素拷贝进新的空间中。
  3. 销毁原有空间中存储的对象。
  4. 销毁原有的空间。

可见一个简单的操作背后实际可能会有许多动作。

例如如果想创建一个容器让其存放 1 ～ 1000 这 1000 个 int 值，如果用下面的方法：

vector<int> v;

for (int i = 1; i < 1001; ++i)

{

    v.push_back(i)

}

典型情况下该过程将会导致约 2 ～ 10 次内存的重新分配 （前面提过，容器内存分配时，典型的方式是空间加倍，则内存从 \(1*sizeof(int)\) 增长倒 \(1000*sizeof(int)\) 约需要 10 次 (\(2^{10} = 1024\))。）

我们可以在容器创建之后通过 Reserve 来显式地让容器预先分配好足够的空间来减少频繁的 reallocation，形如：

vector<int> v;

v.reserve(1000);

for (int i = 1; i < 1001; ++i)

{

    v.push_back(i)

}

另外，简单总结一下 vector 和 string 提供的 size 相关函数：

  • size()
    告之容器内 存放了 多少元素。它并不告之容量。
  • capacity()
    告之该容器 可以 存放多少元素。我们可以通过 \(capacity() - size()\) 来计算剩余的空间。
  • resize(size_t n)
    该函数强制让容器将保存的元素数量从当前数量变成 n 。
    • 如果 n 比当前的容纳的元素数量小，则 Capacity 不变，但 n 以后的元素被销毁。
    • 如果 n 更大，则先重新分配内存 (改变了 Capacity)，然后调用元素的 Default
      Constructer 来初始化需要填充的内存。
  • reserve(size_t n)
    该函数让容器至少可以容纳 n 个元素：
    • n > 当前 capacity： 重新分配空间，改变 Capacity，但不影响 size。
    • n < 当前 capacity: nothing is changed.

相关文章