本篇文章基于源码来分析规范模板库中vector容器的实现原理及一些非凡注意事项。

阐明一下，我用的是gcc7.1.0编译器，规范库源代码也是这个版本的。

多年以前面试的时候第一次被问到stl中vector的底层实现，那个时候的我真的很low，基本答复不上来，起初面试回来，在网络上搜寻了一些vector底层实现，晓得了它的底层是动静数组，但光晓得动静数组是不够的，进一步的，动静数组写满了怎么办，它的实现用了c++的什么技术，一些非凡场景下怎么应用vector更有效率等等，这些极少有人讲清楚，明天我基于gcc外面的源码来分析一下这些比拟深刻的问题。

先来看一下本篇文章思维导图，如下：

一. vector的实现原理

1. vector的基类介绍

先看一下class vector的申明，截取头文件stl_vector.h中局部代码，如下：

//两个模板参数，第一个是数据类型，第二个std::allocator是规范库中动态内存分配器，最终其实是调用了new运算符template<typename _Tp, typename _Alloc = std::allocator<_Tp> >    class vector : protected _Vector_base<_Tp, _Alloc>    {...};

从源码的实现来看，其实vector是一个模板派生类，也就是说，它首先是一个模板类，这一点咱们应该都猜得到，毕竟咱们应用的时候都是应用形如vector<int>这样的模式来进行申明一个vector对象的，其次它是一个派生类，它的基类是_Vector_base，所以咱们首先来看一下这个基类的实现。

能够看到这里vector继承基类时是protected，这个过程咱们称为爱护继承，爱护继承的特点是：基类的私有成员在派生类中也成为了爱护成员，基类的爱护成员和公有成员在派生类中应用权限与基类统一，放弃不变。

还是头文件stl_vector.h，截取这个基类的一段实现代码，如下：

  template<typename _Tp, typename _Alloc>    struct _Vector_base    {      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template    rebind<_Tp>::other _Tp_alloc_type;      typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer           pointer;      struct _Vector_impl      : public _Tp_alloc_type      {    pointer _M_start;//容器开始地位    pointer _M_finish;//容器完结地位    pointer _M_end_of_storage;//容器所申请的动态内存最初一个地位的下一个地位    _Vector_impl()    : _Tp_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage()    { }    ...  //局部代码没截取的以省略号代替，后续同理      };    public:      typedef _Alloc allocator_type;      ...//此处省略局部源代码      _Vector_base()      : _M_impl() { }        _Vector_base(size_t __n)      : _M_impl()      { _M_create_storage(__n); }      ...//此处省略局部源代码    public:      _Vector_impl _M_impl;          pointer      _M_allocate(size_t __n)      {    typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;    return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();      }      void      _M_deallocate(pointer __p, size_t __n)      {    typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;    if (__p)      _Tr::deallocate(_M_impl, __p, __n);      }    private:      void      _M_create_storage(size_t __n)      {    this->_M_impl._M_start = this->_M_allocate(__n);    this->_M_impl._M_finish = this->_M_impl._M_start;    this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;      }    };

这样看，这个基类的性能就很清晰了，它申明了一个构造体struct _Vector_impl，同时以这个构造体申明了一个私有成员变量_M_impl，对于基类的无参构造函数，它也只是调用了struct _Vector_impl的构造函数，进而调用了struct _Vector_impl的各个成员变量的构造函数。

这里有一点须要留神，就是构造体_Vector_impl的三个成员变量是比拟重要的，在vector的实现中它们会屡次呈现，对于它们的作用正文中也曾经写明了，这三个成员变量保留了vector容器的开始地位、完结地位以及所申请内存空间的的下一个地位。

到这里为止，其实咱们还是很纳闷，这个基类啥也没干啊，它有什么作用呢，事实上，对于形如vector<int> vec;这样的申明，vector其实就是调用了这个基类的无参结构，它就是什么也没干，此时也并没有申请动态内存，具体它的作用咱们前面再阐明。

无参结构为什么没有申请动态内存呢，这里波及到节约资源的准则，假如这里申请了一块动态内存，然而你前面却没有应用这个vector，那这个申请和开释这块动态内存的动作无形中就产生了工夫和空间的节约，这个不合乎stl性能优先的准则。

stl性能优先是指什么呢，就是c++规范中规定，stl要优先思考性能，为此，其余的容错性以及更多的性能都能够被舍弃掉。

但同时咱们也能够看进去，如果vector在结构的时候给基类传入元素大小n，这个时候就会调用成员函数_M_create_storage，申请动态内存和给成员变量赋值。

到这里咱们至多get到了基类的两个作用：

  • 保留容器开始地位、完结地位以及所申请内存空间的的下一个地位；
  • 申请动态内存空间。
2. vector从最初面插入元素时产生了什么
2.1 对空vector插入一个元素

上一大节说到，如果vector在结构的时候指定容器大小，那么申明时就会申请动态内存，但如果结构是默认结构，并不会申请动态内存，那么此时对一个无空间的vector插入一个元素会产生什么事呢？

咱们找到vector的push_back函数实现，如下：

voidpush_back(const value_type& __x){    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)    {        _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,             __x);        ++this->_M_impl._M_finish;    }    else        _M_realloc_insert(end(), __x);}

这个函数在内存还没有写满时，把元素直接插入成员变量_M_finish所指向的地位，如果曾经写满了，会调用vector的成员函数_M_realloc_insert，很显然对一个无空间的vector插入一个元素会调用_M_realloc_insert函数，该函数实现如下：

#if __cplusplus >= 201103L  template<typename _Tp, typename _Alloc>    template<typename... _Args>      void      vector<_Tp, _Alloc>::      _M_realloc_insert(iterator __position, _Args&&... __args)#else  template<typename _Tp, typename _Alloc>    void    vector<_Tp, _Alloc>::    _M_realloc_insert(iterator __position, const _Tp& __x)#endif{      //这里调用了_M_check_len，_M_check_len在传入参数为1的状况下，只有没有超出stl规定的最大内存大小，每次返回以后容器大小的双倍，首次返回1      const size_type __len = _M_check_len(size_type(1), "vector::_M_realloc_insert");      const size_type __elems_before = __position - begin();      //依据后面第1节说的，_M_allocate依据传入长度申请内存空间      pointer __new_start(this->_M_allocate(__len));      pointer __new_finish(__new_start);      __try    {      //把x写入相应的地位      _Alloc_traits::construct(this->_M_impl,                   __new_start + __elems_before,#if __cplusplus >= 201103L                   std::forward<_Args>(__args)...);#else                   __x);#endif      __new_finish = pointer();      //这里其实就是把原来数据拷贝到新的内存中来      __new_finish        = std::__uninitialized_move_if_noexcept_a        (this->_M_impl._M_start, __position.base(),         __new_start, _M_get_Tp_allocator());      ++__new_finish;      //这里为什么要再调用一次呢，是针对往vector两头插入元素的状况来的      __new_finish        = std::__uninitialized_move_if_noexcept_a        (__position.base(), this->_M_impl._M_finish,         __new_finish, _M_get_Tp_allocator());    }      __catch(...)    {        ...;    }        //这里销毁原来的内存并给成员变量赋新值        std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,            _M_get_Tp_allocator());      _M_deallocate(this->_M_impl._M_start,            this->_M_impl._M_end_of_storage            - this->_M_impl._M_start);      this->_M_impl._M_start = __new_start;      this->_M_impl._M_finish = __new_finish;      this->_M_impl._M_end_of_storage = __new_start + __len;};

依据以上代码，咱们能够晓得对一个无空间的vector插入一个元素的流程如下：

  • 失去一个长度，这个长度第一次插入时为1，后续如果超出容器所申请的空间，则在之前根底上乘以2，而后申请新的内存空间；
  • 把待插入的元素插入到相应的地位；
  • 把原来旧内存中元素全副拷贝到新的内存中来；
  • 调用旧内存中所有元素的析构，并销毁旧的内存；

依据以上逻辑，也就是说，对一个无空间的vector插入一个元素实际上是会先申请1个元素的空间，并把这个元素插入到vector。

依据以上，其实如果咱们能确定vector必定会被应用且有数据时，咱们应该在申明的时候指定元素个数，防止最开始的时候屡次申请动态内存耗费资源，进而影响性能。

2.2 vector以后内存用完时插入

那么如果内存用完时是怎么的呢，实际上，现有内存空间用完的状况其实跟最开始插入第一个元素的调用路线统一，也就是说，如果现有空间用完了，会在以后空间根底上乘以2，而后把原来内存空间中所有数据拷贝到新的内存中，最初把以后要插入的数据插入到最初一个元素的下一个地位。

3. vector在两头插入一个元素会产生什么

两头插入元素就要应用vector的成员函数insert啦，insert的一个最根本的实现如下：

  template<typename _Tp, typename _Alloc>    typename vector<_Tp, _Alloc>::iterator    vector<_Tp, _Alloc>::#if __cplusplus >= 201103L    insert(const_iterator __position, const value_type& __x)#else    insert(iterator __position, const value_type& __x)#endif    {      const size_type __n = __position - begin();      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)    if (__position == end())      {        _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,                     __x);        ++this->_M_impl._M_finish;      }    else      {#if __cplusplus >= 201103L        const auto __pos = begin() + (__position - cbegin());        // __x could be an existing element of this vector, so make a        // copy of it before _M_insert_aux moves elements around.        _Temporary_value __x_copy(this, __x);        _M_insert_aux(__pos, std::move(__x_copy._M_val()));#else        _M_insert_aux(__position, __x);#endif      }      else#if __cplusplus >= 201103L    _M_realloc_insert(begin() + (__position - cbegin()), __x);#else    _M_realloc_insert(__position, __x);#endif      return iterator(this->_M_impl._M_start + __n);    }

insert函数在空间不够时，其实与push_back调用流程一样，大家能够在拉到第2大节看一下函数_M_realloc_insert的正文，在函数_M_realloc_insert中，第二次调用std::__uninitialized_move_if_noexcept_a函数其实就是针对于往两头插入元素的状况，如果是push_back函数，这个第二次调用其实是没有作用的。

那如果空间足够时往两头插入会产生什么呢？咱们看代码，在c++11以前是间接调用_M_insert_aux函数，咱们看一下这个函数的实现，如下：

#if __cplusplus >= 201103Ltemplate<typename _Tp, typename _Alloc>    template<typename _Arg>      void      vector<_Tp, _Alloc>::      _M_insert_aux(iterator __position, _Arg&& __arg)#else  template<typename _Tp, typename _Alloc>    void    vector<_Tp, _Alloc>::    _M_insert_aux(iterator __position, const _Tp& __x)#endif    {      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,                   _GLIBCXX_MOVE(*(this->_M_impl._M_finish                           - 1)));      ++this->_M_impl._M_finish;#if __cplusplus < 201103L      _Tp __x_copy = __x;#endif      _GLIBCXX_MOVE_BACKWARD3(__position.base(),                  this->_M_impl._M_finish - 2,                  this->_M_impl._M_finish - 1);#if __cplusplus < 201103L      *__position = __x_copy;#else      *__position = std::forward<_Arg>(__arg);#endif    }

看代码可知，其实就是把以后要插入元素的地位前面的元素向后挪动，而后把待插入元素插入到相应的地位。

4. vector删除元素内存会被开释吗
4.1 从容器最初删除

从容器最初删除，是调用pop_back函数，咱们看下这个函数的实现：

void      pop_back() _GLIBCXX_NOEXCEPT      {    __glibcxx_requires_nonempty();    --this->_M_impl._M_finish;    _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);      }

这个就比较简单了，间接把最初一个元素地位向前移一位，而后把最初一个元素销毁掉即可。

4.2 从容器两头删除

从容器两头删除，其实就是删除一个指定地位的元素，这个动作是由erase函数实现的，erase的一个最简略的重载实现如下：

iterator#if __cplusplus >= 201103L      erase(const_iterator __position)      { return _M_erase(begin() + (__position - cbegin())); }#else      erase(iterator __position)      { return _M_erase(__position); }#endif

是调用了_M_erase函数，咱们看看这个函数的实现：

template<typename _Alloc>    typename vector<bool, _Alloc>::iterator    vector<bool, _Alloc>::    _M_erase(iterator __position)    {      if (__position + 1 != end())        std::copy(__position + 1, end(), __position);      --this->_M_impl._M_finish;      return __position;    }

这个函数在不是删除最初一个元素的状况下，把这个元素前面的所有元素向前挪动一位，且这是一个拷贝的动作，而后把容器完结地位向前挪动一位，并返回指向以后地位的迭代器。

综上，删除元素不会开释现有曾经申请的动态内存。

5. vector如何批改某个地位的元素值

vector是否能够间接批改某个地位的元素，不能够的只能先删除，而后再插入，不过这样干，是不是傻，所以vector坚定不反对批改元素哈。

6. vector读取一个元素的值效率怎么样

间接拜访元素的话，vector提供了不少函数，如果是拜访指定地位的元素，那就能够应用operator[]和at函数，咱们别离看下这两个函数的实现，如下：

const_reference      operator[](size_type __n) const _GLIBCXX_NOEXCEPT      {    __glibcxx_requires_subscript(__n);    return *(this->_M_impl._M_start + __n);      }      const_reference      at(size_type __n) const      {    _M_range_check(__n);    return (*this)[__n];      }

能够看到实际上at函数就是调用的operator[]函数，只是多了一个查看是否越界的动作，而operator[]函数是间接跳转地位拜访元素，所以速度是很快的，从工夫复杂度看，是O(1)。

7. c++11给vector减少了什么内容

从下面的代码咱们能够看出，充斥了诸多形如#if __cplusplus >= 201103L这样的预编译选项，它其实代表了c++的版本，比方c++11规范是在2011年3月份公布的，那么这行代码意思就是说如果咱们在编译时指定了__cplusplus这个为201103，那么就开展它上面的代码，否则开展#else前面的代码。

那么c++11当前vector中减少了一些什么内容呢，咱们来看看：

  • 对于迭代器，减少cbegin系列函数，返回常量迭代器，就是只读迭代器；
  • 减少了挪动构造函数和挪动赋值函数，这一点基本上规范库外面所有类型都减少了；
  • 减少公共成员函数shrink_to_fit，容许开释未应用的内存；
  • 减少公共成员函数emplace和emplace_back，它反对在指定地位原味结构元素，因为它们是以右值援用的形式传递参数，所以它们相比于push_back这一类的函数，少了一个拷贝的动作；
8. vector底层实现总结

总的来说，vector是一个动静数组，它保护了一段间断的动态内存空间，而后有三个成员变量别离保留开始地位、以后已应用地位、申请的动态内存的最初一个地位的下一个地位，每当以后所申请的动态内存曾经应用完时，它依照原有空间大小双倍从新申请，并把原来的元素都拷贝过来。

依据后面几大节的内容，对于vector操作的工夫复杂度别离如下所示：

  • 拜访元素，工夫复杂度为O(1);
  • 在开端插入或者删除元素，工夫复杂度也为O(1);
  • 在两头插入或者删除元素，工夫复杂度为O(n)。

二、vector应用时注意事项

1. 在不确定的状况下应用at而不是operator[]

在后面拜访元素大节那里咱们说了，at会查看是否越界，假如不确定以后拜访动作是否会越界，那么咱们应该应用at函数。

2. 什么类型不能够作为vector的模板类型

对于vector模板特化类型，因为在vector的实现过程中，变量会常常被拷贝或者赋值，所以vector的模板类型应该具备私有的拷贝构造函数和重载的赋值操作符函数。

3. 什么状况下vector的迭代器会生效
  • 第一是在vector容器两头依据指定迭代器删除元素，也就是调用erase函数，此时因为以后地位会被前面的元素笼罩，所以该指定迭代器会生效，不过此时能够通过erase的返回值重新得到以后地位的正确迭代器；
  • 第二是在vector需从新申请内存的时候，比方扩容，比方开释未应用的内存等等这些过程中都会产生迭代器生效的问题，因为内存有了变动，此时就须要从新取得迭代器；

有人说往vector两头插入数据也会使迭代器生效，实际上依据源码是不会的，看下面的insert实现能够得悉，再插入实现当前给以后迭代器从新赋值了的。

4. vector怎么迅速的开释内存

有人说是不是能够调用reserve(0)来进行开释，毕竟reserve函数会依据咱们指定的大小从新申请的内存，那是行不通的哈，这个函数只有在传入大小比原有内存大时才会有动作，否则不进行任何动作。

至于通过resize或者clear等都是行不通的，这些函数都只会对以后已保留在容器中的所有元素进行析构，但对容器自身所在的内存空间是不会进行开释的。

4.1 通过swap函数

这时咱们能够想想，什么状况下vector大小为0呢，就是作为一个空容器的时候，所以要想疾速的开释内存，咱们能够参考swap函数机制，用一个空的vector与以后vector进行替换，应用形如vector<int>().swap(v)这样的代码，将v这个vector变量所代表的内存空间与一个空vector进行替换，这样v的内存空间等于被开释掉了，而这个空vector因为是一个长期变量，它在这行代码完结当前，会主动调用vector的析构函数开释动态内存空间，这样，一个vector的动态内存就被迅速的开释掉了。

4.2 应用shrink_to_fit函数

在c++11当前减少了这个函数，它的作用是开释掉未应用的内存，假如咱们先调用clear函数把所有元素清掉，这样是不是整块容器都变成未应用了，而后再调用shrink_to_fit函数把未应用的局部内存开释掉，那不就把这个vector内存开释掉了吗。

写文章不免有疏漏，如果不对之处，欢送增加作者微信进行斧正，微信可在公众号菜单中获取，谢谢！