STL之vector扩容机制

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

一、背景介绍

vector作为STL的常用容器之一，其特性和数组类似，拥有一段连续的内存空间。vector申请的是一段连续的内存，当插入新的元素内存不够时，通常会再重新申请更大的一块内存，将原来的元素拷贝过去，释放旧空间。因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为O(n)。

二、相关函数介绍

2.1 resize()

resize，即重置容器空间。当设置值小于当前容器空间时，会将目前容器中超出设置值的空间释放掉；当设置值大于当前容器空间时，会在当前空间的基础上增加容量。
举个例子，vector当前容量为10，若使用resize(20)设置容量为20，则需要再扩容增加10个；若使用resize(5)设置容量为5，则将6-10的空间进行释放。
空口无凭，咱直接上g++5.2源码：

      void      resize(size_type __new_size)      {if (__new_size > size())   _M_default_append(__new_size - size());else if (__new_size < size())  _M_erase_at_end(this->_M_impl._M_start + __new_size);      }

2.2 reserve()

reserve，即预留容器空间。当设置值大于当前容器空间时，会增加当前容器空间的大小，源码如下：

    void    reserve(size_type __n)    {      if (__n > max_size())__throw_length_error(__N("vector::reserve"));      if (capacity() < __n)_M_reallocate(__n);    }

三、扩容机制（1.5倍还是2.0倍？）

下面将在msvc编译器和gcc编译器上分别测试，直接上代码：

#include <iostream>#include <vector>using namespace std;int main(){    vector<int> dp;    int n = 100;    while (n--) { dp.push_back(n); cout << "size " << dp.size() << ", capacity " << dp.capacity() << endl;    }}

3.1 MSVC执行结果

3.2 GCC执行结果

3.3 总结

显然，不同编译器在vector的扩容策略上显然不太一致，在vector的size()(当前容器所用空间)等于capacity()(当前容器总空间)时会发生扩容，msvc编译器每次是以1.5倍且向下取整的策略进行扩容，gcc编译器则是每次以2.0倍的策略进行扩容。

无论如何，在vector的日常使用中，如果只是简单的push_back插入数据，显然会带来频繁的数据拷贝，这对程序执行效率来说影响很大，因此，在能提前考虑容量的情况下，提前使用**reserve()或resize()**调整容器空间对程序性能提升很有意义。