vector内存与效率

丛旭东拉西扯

vector就是一个动态数组，地址是连续的，可以通过下表快速访问其中元素。

插、删这类操作涉及到buffer搬运，是比较耗资源的。

vector本质是copy，所以参数是类对象时，需要关心拷贝构造函数的实现。

为了避免不必要的copy，建议实现移动构造函数，利用右值引用或完美转发做push_back。

引用自https://blog.csdn.net/u012658346/article/details/50725933

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_base ，所以我们首先来看一下这个基类的实现：

  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;

无参构造为什么没有申请动态内存呢，这里涉及到节约资源的原则，假设这里申请了一块动态内存，但是你后面却没有使用这个vector，那这个申请和释放这块动态内存的动作无形中就产生了时间和空间的浪费，这个不符合stl性能优先的原则。

但同时我们也可以看出来，如果vector在构造的时候给基类传入元素大小n，这个时候就会调用成员函数_M_create_storage，申请动态内存和给成员变量赋值。

到这里我们至少get到了基类的两个作用：

保存容器开始位置、结束位置以及所申请内存空间的的下一个位置；
申请动态内存空间

vector::push_back

对空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必定会被使用且有数据时，我们应该在声明的时候指定元素个数，避免最开始的时候多次申请动态内存消耗资源，进而影响性能。

vector当前内存用完时插入

那么如果内存用完时是怎样的呢，实际上，现有内存空间用完的情况其实跟最开始插入第一个元素的调用路线一致，也就是说，如果现有空间用完了，会在当前空间基础上乘以2，然后把原来内存空间中所有数据拷贝到新的内存中，最后把当前要插入的数据插入到最后一个元素的下一个位置。

push_back与emplace_back

vector<A> vec;
A a(10);
vec.push_back(a);
//输出结果为：
constructor
copy constructor

从输出结果看，push_back过程中除了调用一次 构造函数 ，还额外调用了一次 拷贝构造函数 ，额外调用复制构造函数甚是浪费时间。

vector<A> vec;
A a(10);
vec.emplace_back(std::move(a));
//输出结果为：
constructor
move constructor

从输出结果看，此时调用了一次 构造函数 ，和一次 移动构造函数 ，而移动构造函数基本是不耗时的。很明显，使用emplace_back比push_back效率更高。

另外，C++11中，上面的代码可以简化为：

vector<A> vec;
vec.emplace_back(10);
//输出结果为:
constructor

从输出结果看，此时只调用了一次构造函数，连移动构造函数都省掉了，这是因为emplace_back把参数10完美转发给A的构造函数，直接构造了一个元素，而这个元素是直接存放在vector容器中的。

emplace_back的实现

public:
    template<class... _Valty>
        decltype(auto) emplace_back(_Valty&&... _Val)
        {   // insert by perfectly forwarding into element at end, provide strong guarantee
        if (_Has_unused_capacity())
            _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
            {   // reallocate
            const size_type _Oldsize = size();
            if (_Oldsize == max_size())
                _Xlength();
            const size_type _Newsize = _Oldsize + 1;
            const size_type _Newcapacity = _Calculate_growth(_Newsize);
            bool _Emplaced = false;
            const pointer _Newvec = this->_Getal().allocate(_Newcapacity);
            _Alty& _Al = this->_Getal();
            _TRY_BEGIN
            _Alty_traits::construct(_Al, _Unfancy(_Newvec + _Oldsize), _STD forward<_Valty>(_Val)...);
            _Emplaced = true;
            _Umove_if_noexcept(this->_Myfirst(), this->_Mylast(), _Newvec);
            _CATCH_ALL
            if (_Emplaced)
                _Alty_traits::destroy(_Al, _Unfancy(_Newvec + _Oldsize));
            _Al.deallocate(_Newvec, _Newcapacity);
            _RERAISE;
            _CATCH_END
            _Change_array(_Newvec, _Newsize, _Newcapacity);
#if _HAS_CXX17
        return (this->_Mylast()[-1]);
#endif /* _HAS_CXX17 */
        }

通过上述代码可以看到，emplace_back的流程逻辑很简单。先检查vector的容量，不够的话就扩容，之后便通过 _Alty_traits::construct 来创建对象。而最终利用强制类似装换的指针来指向容器类之中对应类的构造函数，并且利用 可变长模板 将构造函数所需要的内容传递过去构造新的对象。

template<class _Objty,
        class... _Types>
        static void construct(_Alloc&, _Objty * const _Ptr, _Types&&... _Args)
        {   // construct _Objty(_Types...) at _Ptr
        ::new (const_cast<void *>(static_cast<const volatile void *>(_Ptr)))
            _Objty(_STD forward<_Types>(_Args)...);
        }

emplace_back这里最为巧妙的部分就是利用 可变长模板 实现了，任意传参的对象构造。

总结：

调用emplace_back时需要注意，不要把vec.emplace_back(std::move(a))，错误的写成vec.emplace_back(a)，看下面的例子：

vector<A> vec;
A a(10);
vec.emplace_back(a);
//输出的结果为：
constructor
copy constructor

从输出结果看，此时调用的是复制构造函数而不是移动构造函数， 因为传入的参数a不是右值引用，需要先调用a的复制构造函数生成一个副本，然后把副本的右值引用传递给emplace_back ，最终造成vec.emplace_back(a)等效与vec.push_back(a)。

2.当自定义类A没有移动构造函数时，vec.emplace_back(std::move(a))也等效与vec.push_back(a)。

vector::insert

中间插入元素就要使用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

看代码可知，其实就是把当前要插入元素的位置后面的元素向后移动，然后把待插入元素插入到相应的位置。

vector移除元素

从容器最后删除

从容器最后删除，是调用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);

这个就比较简单了，直接把最后一个元素位置向前移一位，然后把最后一个元素销毁掉即可。

从容器中间删除

从容器中间删除，其实就是删除一个指定位置的元素，这个动作是由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;

这个函数在不是删除最后一个元素的情况下，把这个元素后面的所有元素向前移动一位，且这是一个拷贝的动作，然后把容器结束位置向前移动一位，并返回指向当前位置的迭代器。

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

vector修改元素值

vector是否可以直接修改某个位置的元素，不可以的只能先删除，然后再插入

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