本篇文章基于源码来剖析标准模板库中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();
      _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:
      _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函数实现，如下：

void
push_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;
        _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>
      vector<_Tp, _Alloc>::
      _M_realloc_insert(iterator __position, _Args&&... __args)
#else
  template<typename _Tp, typename _Alloc>
    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;
#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
#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 >= 201103L
template<typename _Tp, typename _Alloc>
    template<typename _Arg>
      vector<_Tp, _Alloc>::
      _M_insert_aux(iterator __position, _Arg&& __arg)
#else
  template<typename _Tp, typename _Alloc>
    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