超详细STL之基于源码剖析vector实现原理及注意事项

cpp加油站

发布于 2021-06-07 15:26:25

2.6K0

发布于 2021-06-07 15:26:25

文章被收录于专栏：cpp加油站

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

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;
    }
    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 >= 201103L
template<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的动态内存就被迅速的释放掉了。