vector对象在内存空间中是如何增长的

vector对象在内存空间中是如何增长的

我们都知道vector对象是动态存储的，从这一点看有点像链表，可以动态的增加或减少元素。我们也知道链表中是有指针变量，专门用于存储上一个和下一个元素的地址。正是因为这两个指针的存在，我们才能做到动态的存储数据，即不用像数组那样必须事先申请好空间。链表的缺点就是不能够快速的随机访问其中元素，必须通过指针层层查找。

但是，vector既可以实现动态存储数据，而且支持快速随机访问（用下标或者指针访问元素）。对于能够用下标查找的数据类型，其存储方式必定是连续的，即每个元素紧挨着前一个元素存储。

这样对于vector来说，就会出现一个问题，我在初始定义vector的时候该给其申请多少内存空间？如果申请的很小，那么我来了新的数据改存放在哪里？如果申请的很大，我用不完，那岂不是很浪费内存空间？

当然对于vector这种标准库类型，通常我们只关心如何使用它，而不关心其实如何实现的。不过对于其在存储空间的实现方式还是了解一下比较好。

我们知道容器中元素连续存储，且容器大小是可变的，考虑向vector中添加元素会发生什么？如果没有空间容纳新的元素，容器不可能简单的将其添加到内存的其他位置，因为vector的元素必须连续存储。因此容器必须分配新的空间来保存已用的元素和新的元素。将已有元素从旧位置移动到新空间，然后添加新元素，释放旧空间。如果说我们每添加一个新的元素就执行一次这样的操作，显然性能会慢到我们不可接受。

为了避免上面的代价，标准库采用了可以减少容器空间重新分配的策略。当不得不获取新的内存空间时，vector的实现通常会分配比新的空间需求更大的内存空间。容器预留这些空间作为备用，从而用来保存更多新的元素。这样，就不需要每次添加新的元素都重新分配容器的内存空间了。

vector类型提供了一些成员函数，允许我们与它的现实中内存分配部分互动。

c.capacity()     不重新分配内存空间的话，c可以保存多少元素

c.reserve(n)     分配至少能容纳n个元素的内存空间

c.shrink_to_fit()  将capacity()减少为size()相同大小。size()为vector已经保存元素个数。