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

| 分类 C-Family  | 标签 c++  stl 

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.

上一篇     下一篇