使用reserve来避免不必要的内存重新分配

STL容器的内存分配策略是，他们会自动增长以便容纳下你放入其中的数据，只要没有超过它的最大限制就可以（要查看最大限制可调用名为max_size的成员函数）。对于vector和string，增长过程是这样来实现的： 每当需要更多空间时，就调用与realloc类似的操作。这一类似realloc的操作分为如下四个步骤：

1.分配一块大小为当前容量的每个倍数的新内存。在大多数实现中，vector和string的容量每次以2的倍数增长，即每当扩容时，他们的容量加倍。

2.把容器的所有元素从旧的内存复制到新的内存中。

3.析构掉旧内存中的对象。

4释放旧内存。

每当发生内存的重新分配时，会带来以下两个问题：

1.效率问题。一系列的分配、释放、复制和析构步骤，必然会带来程序效率的下降。

2.迭代器失效。原来指向旧的容器的迭代器都将失效，因为那块内存已经被释放掉了。

下来我们介绍reserve成员函数。

reserve成员函数能使你把重新分配内存的次数减少到最低，从而避免了重新分配内存带来的问题。在介绍reserve怎么做到这些之前，先来看一下这四个相互关联、但有时会被混淆的成员函数。在标准容器中，只有vector和string提供了所有者四个函数：

1.size()。size()告诉你容器中有多少个元素。它不会告诉你该容器为自己所包含的元素分配了多少内存。

2.capacity()。capacity()告诉你该容器利用已经分配的内存可以容纳多少元素。这是容器所能容纳的元素总数，而不是它还能容纳多少元素。如果你想知道一个vector有多少未被使用的内存，就需要用capacity()-size()。如果capacity和size返回同样的值，就说明容器中不再有剩余空间了，因此下一个插入操作将导致上面讲过的重新分配过程。

3.resize(Container::size_type n)。resize()强迫容器把它的容量改变到包含n个元素的状态。在调用resize之后，size将返回n。如果n比当前的大小(size)要小，则容器尾部的元素将会被析构。如果n比当前的大小要大，则通过默认的构造函数创建的新元素将被添加到容器的尾部。如果n比当前的容量（capacity）要大，那么在添加元素之前，将先重新分配内存。

4.reserve(Container::size_type n)。reserve强迫容器把它的容量变为至少是n，前提是n不小于当前的大小。这通常会导致内存重新分配，因为容量需要增加。如果n比当前容量要小，则vector忽略该调用，什么也不做；而string则可能把自己的容量减为size和n中的最大值。

通过以上概括，应该清楚的是：当一个元素需要被插入容器而容量不够时，就会发生重新分配过程（包括原始内存的分配和释放，对象的拷贝和析构，迭代器、指针和引用的失效）。因此，避免重新分配的关键在于，今早地使用reserve，把容量设置为足够大的值，最好是在容器刚被构造出来之后就使用reserve。

例如，要创建一个包含1-1000之间的值得vector<int>。如果不使用reserve，可能这么写

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

对于大多数STL实现，该循环在执行过程中将会导致2到10次重新分配（2的十次方）。把这段改代码改为使用reserve，如下所示 

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

则在循环过程中，就不会发生内存重新分配。

大小（size）和容量（capacity）之间的关系使我们能够预知什么时候插入操作会导致vector或string执行重新分配的动作，进而又使我们有可能预知下一个插入操作什么时候回是容器中的迭代器、指针、和引用失效。例如，考虑下面的代码

string s;
if(s.size() < s.capacity()){
    s.push_back('x');
}

 对push_back的调用不会使string中的迭代器、指针和引用失效，因为string的容量肯定大于它的大小。

总结：通常有两种方式来使用reserve以避免不必要的内存重新分配。第一种方式是，若能确切知道或大致预计容器中最终会有多少元素，则此时可使用reserve。第二种方式是，先预留足够大的空间，然后，当把所有的数据都加入后，再去除多余的容量。如何去除多余的容量，这里有个诀窍，就是使用swap技巧。关于swap技巧的说明，以后会再更新一篇博文专门讲解。

参考：《Effective STL》 第14条