Effective STL [14] | 使用reserve来避免不必要的重新分配

自动扩容

STL 容器只要存储的对象不超过「最大大小」，就可以自动增长到足以容纳放进去的数据。这个最大值，只要调用名叫max_size的成员函数就可以查询到。

对于vector和string，只要需要更多空间，就以realloc等价的思想来增长。

realloc的操作有4个部分：

1. 「分配新的内存块」。在大部分实现中，vector和string的容量每次以「2」为因数增长，即容量每次翻倍。
2. 「把所有元素从容器的旧内存拷贝到新内存」。
3. 「销毁旧内存中的对象」。
4. 「回收旧内存」。 这就是分配，回收，拷贝和析构4个步骤，这些步骤代价都很昂贵。

即便是简单地把一个元素插入vector或string的动作也可能因为需要更新其他使用了指向vector或string中的迭代器、指针或引用的数据结构而膨胀。

4个成员函数

这4个STL容器成员函数，只有vector和string提供了所有这些函数。

reserve成员函数允许你最小化必须进行的重新分配的次数，因而可以避免真分配的开销和迭代器/指针/引用失效。

「调用reserve不改变容器中对象的个数。」

提前 reserve

「只要有元素需要插入而且容器的容量不足时就会发生重新分配」（包括它们维护的「原始内存分配和回收」，「对象的拷贝和析构」和「迭代器、指针和引用的失效」）。

「避免重新分配的关键」是使用reserve尽快把容器的容量设置为足够大，最好在容器被构造之后立刻进行。

Example

假定你想建立一个容纳1-1000值的vector<int>。没有使用reserve：

1
2
3
4

vector<int> v;
for (int i = 1; i <= 1000; ++i) {
  v.push_back(i);
}

在大多数STL实现中，这段代码在循环过程中「将会导致2到10次重新分配」。（「vector在重新分配时一般把容量翻倍」，$1000 \approx 2^{10}$。） 把代码改为使用reserve：

1
2
3
4
5

vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i) {
  v.push_back(i);
}

「这在循环中不会发生重新分配。」

结论

通常有2种情况使用reserve来避免不必要的重新分配:

1. 可用的情况是「当你确切或者大约知道有多少元素将最后出现在容器中」。可以提前reserve适当数量的空间。

2.「保留可能需要的最大的空间」，然后，一旦添加完全部数据「修整掉任何多余的容量」。