STL源码剖析之vector

0.导语

vector的数据安排以及操作方式，与array非常相似。两者的唯一差别在于空间的运用的灵活性，array是静态的，一旦配置了就不能改变，而 vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。下面一起来看一下vector的"内部机制"，怎么来实现空间配置策略的。

1.vector

在_Vector_base中开头有两行比较难理解，下面一个一个分析：

1.1 _Tp_alloc_type

开头处定义：

  1.  typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;

在gnu_cxx::alloc_traits中：对应文件为：ext/alloc_traits.h

  1.  template<typename _Tp>
  2.       struct rebind
  3.       { typedef typename _Base_type::template rebind_alloc<_Tp> other; };

等价于

  1. typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other

等价于：

  1. typename _Base_type::template rebind_alloc<_Tp>

而_Base_type是：

  1. typedef std::allocator_traits<_Alloc>           _Base_type;

所以上述等价于：

  1. typename std::allocator_traits<_Alloc>::template rebind_alloc<_Tp>

继续到allocator_traits中寻找

找到了：

  1.   template<typename _Up>
  2.     using rebind_alloc = allocator<_Up>;

于是：

  1. std::allocator_traits<_Alloc>::template rebind_alloc<_Tp>

等价于：

  1. allocator<_Tp>

小结

  1.  typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;

等价于：

  1. typedef allocator<_Tp> _Tp_alloc_type

1.2 pointer

而pointer：

  1.  typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
  2.         pointer;

等价于：

  1.  typedef typename __gnu_cxx::__alloc_traits<allocator<_Tp>>::pointer
  2.         pointer;

根据下面两行：

  1. typedef std::allocator_traits<_Alloc>           _Base_type;
  2. typedef typename _Base_type::pointer            pointer;

又等价于：

  1.  typedef std::allocator_traits<_Alloc>::pointer
  2.         pointer;

在allocator_traits中找到下面：

  1.   /**
  2.    * @brief   The allocator's pointer type.
  3.    *
  4.    * @c Alloc::pointer if that type exists, otherwise @c value_type*
  5.   */
  6.   typedef __pointer pointer;

注释中说了如果存在就是Alloc::pointer，否则为value_type *。

小结

  1.  typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
  2.         pointer;
  3.  // 或者
  4.  typedef typename __gnu_cxx::__alloc_traits<allocator<_Tp>>::pointer
  5.         pointer;

等价于

  1. /**
  2. * @brief   The allocator's pointer type.
  3. *
  4. * @c Alloc::pointer if that type exists, otherwise @c value_type*
  5. */
  6. typedef __pointer pointer;

如果存在_Tp_alloc_type::pointer也就是allocator<_Tp>存在就是allocator<_Tp>::pointer，

这个看allocator.h源码：

  1. typedef _Tp*       pointer;

否则为value_type*。而value_type为：

  1. typedef typename _Alloc::value_type value_type;

所以value_type*推导出为：

  1. _Tp::value_type*

1.3 vector的内存管理

_Vector_base中有一个内存管理器_Vector_impl类，该结构体继承allocator(根据上述1.1等价条件得出)。

  1. template<typename _Tp, typename _Alloc>
  2. struct _Vector_base {
  3.     //__alloc_traits -> allocator_traits
  4.     // typedef allocator<_Tp> _Tp_alloc_type
  5.     typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
  6.     rebind<_Tp>::other _Tp_alloc_type;
  7.     //  _Tp::value_type* or _Tp*
  8.     typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
  9.             pointer;
  11.     struct _Vector_impl
  12.             : public _Tp_alloc_type {
  13.         pointer _M_start;       // 使用空间起始位置    
  14.         pointer _M_finish;      // 使用空间结束位置
  15.         pointer _M_end_of_storage;   // 可使用空间结束位置 
  17.         _Vector_impl()
  18.                 : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
  20.         _Vector_impl(_Tp_alloc_type const &__a)
  22.         // vector数据交换，只交换内存地址，不交换数据
  23.         void _M_swap_data(_Vector_impl &__x)
  25.         _GLIBCXX_NOEXCEPT
  26.         {
  27.             std::swap(_M_start, __x._M_start);
  28.             std::swap(_M_finish, __x._M_finish);
  29.             std::swap(_M_end_of_storage, __x._M_end_of_storage);
  30.         }
  31.     };
  33. public:
  34.     typedef _Alloc allocator_type;
  35.     // 前面我们知道_Vector_impl继承自allocator分配器，而这个又是_Tp_alloc_type，所以这里返回的就是_M_impl的基类。
  36.     _Tp_alloc_type &
  37.     _M_get_Tp_allocator()
  39.     _GLIBCXX_NOEXCEPT
  40.     { return *static_cast<_Tp_alloc_type *>(&this->_M_impl); }
  42.     const _Tp_alloc_type &
  43.     _M_get_Tp_allocator() const
  45.     _GLIBCXX_NOEXCEPT
  46.     { return *static_cast<const _Tp_alloc_type *>(&this->_M_impl); }
  48.     allocator_type    // 获取传递进来的分配器      
  49.     get_allocator() const
  51.     _GLIBCXX_NOEXCEPT
  52.     { return allocator_type(_M_get_Tp_allocator()); }
  54.     _Vector_base()
  55.             : _M_impl() {}
  57.     _Vector_base(const allocator_type &__a)
  59.     _GLIBCXX_NOEXCEPT
  60.             : _M_impl(__a) {}
  62.     _Vector_base(size_t __n)
  63.             : _M_impl() { _M_create_storage(__n); }
  65.     _Vector_base(size_t __n, const allocator_type &__a)
  66.             : _M_impl(__a) { _M_create_storage(__n); }
  68. #if __cplusplus >= 201103L
  69.     _Vector_base(_Tp_alloc_type&& __a) noexcept
  70.     : _M_impl(std::move(__a)) { }
  72.     // 移动构造函数，只交换3个指针，不copy数据
  73.     _Vector_base(_Vector_base&& __x) noexcept
  74.     : _M_impl(std::move(__x._M_get_Tp_allocator()))
  75.     { this->_M_impl._M_swap_data(__x._M_impl); }
  77.     _Vector_base(_Vector_base&& __x, const allocator_type& __a)
  78.     : _M_impl(__a)
  79.     {
  80.   if (__x.get_allocator() == __a)
  81.     this->_M_impl._M_swap_data(__x._M_impl);
  82.   else
  83.     {
  84.       size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
  85.       _M_create_storage(__n);
  86.     }
  87.     }
  88. #endif
  90.     ~_Vector_base()
  92.     _GLIBCXX_NOEXCEPT
  93.     {
  94.         _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
  95.                                               - this->_M_impl._M_start);
  96.     }
  98. public:
  99.     _Vector_impl _M_impl;
  101.     pointer _M_allocate(size_t __n) {
  102.         typedef __gnu_cxx::__alloc_traits <_Tp_alloc_type> _Tr;
  103.         return __n != 0 ? _Tr::allocate(_M_impl, __n) : 0;  // 同_M_deallocate，一直往后调用的就是malloc函数
  104.     }
  106.     void _M_deallocate(pointer __p, size_t __n) {
  107.         typedef __gnu_cxx::__alloc_traits <_Tp_alloc_type> _Tr; 
  108.         if (__p)
  109.             _Tr::deallocate(_M_impl, __p, __n); // 最后调用allocator_traits的deallocate,而该函数又是根据传递进来的_M_impl进行deallocate,一直往后，最后调用的就是free函数
  110.     }
  112. private:
  113.     void _M_create_storage(size_t __n) {
  114.         this->_M_impl._M_start = this->_M_allocate(__n);
  115.         this->_M_impl._M_finish = this->_M_impl._M_start;
  116.         this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
  117.     }
  118. };

小结：_Vector_base专门负责vector的内存管理，内部类_M_impl通过继承_Tp_alloc_type(也就是allocator)得到内存分配释放的功能，_M_allocate和_M_deallocate分别分配和释放vector所用内存，vector只需要负责元素构造和析构。

在vector中，默认内存分配器为std::allocator<_Tp>

  1. template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
  2. class vector : protected _Vector_base<_Tp, _Alloc> {
  3. }

vector代码中使用基类的内存函数及typedef等：

  1. template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
  2. class vector : protected _Vector_base<_Tp, _Alloc> {
  3.     typedef _Vector_base<_Tp, _Alloc> _Base;
  4.     typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
  5. public:
  6.     typedef typename _Base::pointer pointer;
  7. protected:
  8.     using _Base::_M_allocate;
  9.     using _Base::_M_deallocate;
  10.     using _Base::_M_impl;
  11.     using _Base::_M_get_Tp_allocator;
  12. }

2.vector迭代器

在vector中使用了两种迭代器，分别是正向__normal_iterator与反向迭代器reverse_iterator:

正向：

  1. typedef __gnu_cxx::__normal_iterator <pointer, vector> iterator;
  2. typedef __gnu_cxx::__normal_iterator <const_pointer, vector> const_iterator;

反向：

  1. typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  2. typedef std::reverse_iterator<iterator> reverse_iterator;

__normal_iterator与reverse_iterator都定义于stl_iterator.h，封装了vector元素的指针。

2.1 正向

  1. template<typename _Iterator, typename _Container>
  2. class __normal_iterator
  3. {
  4. protected:
  5.     _Iterator _M_current;
  7.     typedef iterator_traits<_Iterator>      __traits_type;
  9. public:
  10.     typedef _Iterator                   iterator_type;
  12.     // iterator必须包含的五种typedef
  13.     typedef typename __traits_type::iterator_category iterator_category;
  14.     typedef typename __traits_type::value_type      value_type;
  15.     typedef typename __traits_type::difference_type     difference_type;
  16.     typedef typename __traits_type::reference   reference;
  17.     typedef typename __traits_type::pointer     pointer;
  19.     _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
  20.     : _M_current(_Iterator()) { }
  22.     explicit
  23.     __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
  24.     : _M_current(__i) { }
  26.     // Allow iterator to const_iterator conversion
  27.     template<typename _Iter>
  28.     __normal_iterator(const __normal_iterator<_Iter,
  29.             typename __enable_if<
  30.             (std::__are_same<_Iter, typename _Container::pointer>::__value),
  31.             _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
  32.     : _M_current(__i.base()) { }
  34.     // Forward iterator requirements
  35.     reference
  36.     operator*() const _GLIBCXX_NOEXCEPT
  37.     { return *_M_current; }
  39.     pointer
  40.     operator->() const _GLIBCXX_NOEXCEPT
  41.     { return _M_current; }
  43.     // 前置++
  44.     __normal_iterator&
  45.     operator++() _GLIBCXX_NOEXCEPT
  46.     {
  47.         ++_M_current;
  48.         return *this;
  49.     }
  51.     // 后置++
  52.     __normal_iterator
  53.     operator++(int) _GLIBCXX_NOEXCEPT
  54.     { return __normal_iterator(_M_current++); }
  56.     // 前置--
  57.     // Bidirectional iterator requirements
  58.     __normal_iterator&
  59.     operator--() _GLIBCXX_NOEXCEPT
  60.     {
  61.         --_M_current;
  62.         return *this;
  63.     }
  65.     // 后置--
  66.     __normal_iterator
  67.     operator--(int) _GLIBCXX_NOEXCEPT
  68.     { return __normal_iterator(_M_current--); }
  70.     // 随机访问迭代器都要重载[]操作符
  71.     // Random access iterator requirements
  72.     reference
  73.     operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
  74.     { return _M_current[__n]; }
  76.     // +=操作符 跳跃n个difference_type
  77.     __normal_iterator&
  78.     operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
  79.     { _M_current += __n; return *this; }
  81.     // +操作符 跳跃n个difference_type
  82.     __normal_iterator
  83.     operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
  84.     { return __normal_iterator(_M_current + __n); }
  86.     // -=操作符 后退n个difference_type
  87.     __normal_iterator&
  88.     operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
  89.     { _M_current -= __n; return *this; }
  91.     // -操作符 后退n个difference_type
  92.     __normal_iterator
  93.     operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
  94.     { return __normal_iterator(_M_current - __n); }
  96.     const _Iterator&
  97.     base() const _GLIBCXX_NOEXCEPT
  98.     { return _M_current; }
  99. };

_M_current是指向迭代器位置的指针，这是一个随机访问型指针，operator+和operator-等移动操作可以直接移动到目的地，非随机访问型指针只能一步步移动。

2.2 反向

vector还会使用reverse_iterator，即逆序迭代器，顾名思义，其移动方向与普通迭代器相反

  1. template<typename _Iterator>
  2. class reverse_iterator
  3. : public iterator<typename iterator_traits<_Iterator>::iterator_category,
  4.             typename iterator_traits<_Iterator>::value_type,
  5.             typename iterator_traits<_Iterator>::difference_type,
  6.             typename iterator_traits<_Iterator>::pointer,
  7.                     typename iterator_traits<_Iterator>::reference>
  8. {
  9. protected:
  10.     _Iterator current;
  12.     typedef iterator_traits<_Iterator>      __traits_type;
  14. public:
  15.     typedef _Iterator                   iterator_type;
  16.     typedef typename __traits_type::difference_type difference_type;
  17.     typedef typename __traits_type::pointer     pointer;
  18.     typedef typename __traits_type::reference       reference;
  20.     // 省略不重要的代码
  23.     // 该迭代器是从后面end()开始，需要往前一步，才可以获取到有效的迭代器位置
  24.     reference
  25.     operator*() const
  26.     {
  27.         _Iterator __tmp = current;
  28.         return *--__tmp;
  29.     }
  31.     // 通过调用上述*操作符直接实现
  32.     pointer
  33.     operator->() const
  34.     { return &(operator*()); }
  37.     // 前置++操作符完成后退任务
  38.     reverse_iterator&
  39.     operator++()
  40.     {
  41.         --current;
  42.         return *this;
  43.     }
  45.     // 后置++
  46.     reverse_iterator
  47.     operator++(int)
  48.     {
  49.         reverse_iterator __tmp = *this;
  50.         --current;
  51.         return __tmp;
  52.     }
  54.     // 前置--操作符完成前进任务
  55.     reverse_iterator&
  56.     operator--()
  57.     {
  58.         ++current;
  59.         return *this;
  60.     }
  62.     // 后置--
  63.     reverse_iterator
  64.     operator--(int)
  65.     {
  66.         reverse_iterator __tmp = *this;
  67.         ++current;
  68.         return __tmp;
  69.     }
  71.     // +操作符
  72.     reverse_iterator
  73.     operator+(difference_type __n) const
  74.     { return reverse_iterator(current - __n); }
  76.     // +=操作符
  77.     reverse_iterator&
  78.     operator+=(difference_type __n)
  79.     {
  80.         current -= __n;
  81.         return *this;
  82.     }
  84.     // -操作符
  85.     reverse_iterator
  86.     operator-(difference_type __n) const
  87.     { return reverse_iterator(current + __n); }
  89.     // -=操作符
  90.     reverse_iterator&
  91.     operator-=(difference_type __n)
  92.     {
  93.         current += __n;
  94.         return *this;
  95.     }
  97.     // []操作符
  98.     reference
  99.     operator[](difference_type __n) const
  100.     { return *(*this + __n); }
  101. };

3.vector的数据结构

vector内存由_M_impl中的M_start，_M_finish，_M_end_of_storage三个指针管理，所有关于地址，容量大小等操作都需要用到这三个指针：

  1. iterator begin() _GLIBCXX_NOEXCEPT
  2.     { return iterator(this->_M_impl._M_start); }
  3. iterator end() _GLIBCXX_NOEXCEPT
  4.     { return iterator(this->_M_impl._M_finish); }
  5. reverse_iterator  rbegin() noexcept
  6.     { return reverse_iterator(end()); }
  7. reverse_iterator rend() noexcept
  8.     { return reverse_iterator(begin()); }
  9. size_type size() const _GLIBCXX_NOEXCEPT
  10.     { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
  11. size_type capacity() const _GLIBCXX_NOEXCEPT
  12.     { return size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_start); }
  13. bool empty() const _GLIBCXX_NOEXCEPT
  14.     { return begin() == end(); }

vector_1.png

_M_finish和_M_end_of_storage之间的空间没有数据，有时候这是一种浪费，c++11提供了一个很有用的函数shrink_to_fit()，将这段未使用空间释放，主要调用了下面代码，

  1. template<typename _Alloc>
  2. bool vector<bool, _Alloc>::
  3. _M_shrink_to_fit()
  4. {
  5.     if (capacity() - size() < int(_S_word_bit)) // 64位系统为64bytes
  6.         return false;
  7.     __try
  8.     {
  9.         _M_reallocate(size());
  10.         return true;
  11.     }
  12.     __catch(...)
  13.     { 
  14.         return false; 
  15.     }
  16. }
  1.  template<typename _Alloc>
  2. void vector<bool, _Alloc>::
  3. _M_reallocate(size_type __n)
  4. {
  5.     _Bit_type* __q = this->_M_allocate(__n);
  6.     this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
  7.                     iterator(__q, 0));
  8.     this->_M_deallocate();
  9.     this->_M_impl._M_start = iterator(__q, 0);
  10.     this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
  11. }

而_M_copy_aligned通过两个std::copy实现:

第一次swap把first的指针与last的指针之间的数据拷贝到result指针所指向的起始位置。第二次swap获得last的指针对应的迭代器。

  1. iterator
  2. _M_copy_aligned(const_iterator __first, const_iterator __last,
  3.         iterator __result)
  4. {
  5.     // _Bit_type * _M_p; _Bit_type为unsigned long类型
  6.     _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
  7.     return std::copy(const_iterator(__last._M_p, 0), __last,
  8.             iterator(__q, 0));
  9. }

先分配size()大小的内存空间，用于存储begin()与end()之间的数据，释放原来的vector空间，新的vector只包含size()数量的数据，并修改_M_start与_M_end_of_storage指向。

4.vector构造与析构

  1. //使用默认内存分配器
  2. vector() : _Base() { } 
  3. //指定内存分配器
  4. explicit vector(const allocator_type& __a) : _Base(__a) { }
  5. //初始化为n个__value值，如果没指定就使用该类型默认值
  6. explicit vector(size_type __n, const value_type& __value = value_type(),
  7.              const allocator_type& __a = allocator_type()): _Base(__n, __a)
  8. { _M_fill_initialize(__n, __value); }
  9. //拷贝构造函数
  10. vector(const vector& __x)
  11.     : _Base(__x.size(),
  12.     _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
  13. { this->_M_impl._M_finish =
  14.     std::__uninitialized_copy_a(__x.begin(), __x.end(),
  15.                                 this->_M_impl._M_start,
  16.                                 _M_get_Tp_allocator());
  17. }
  18. //c++11的移动构造函数，获取__x的M_start，_M_finish，_M_end_of_storage，并不需要数据拷贝
  19. vector(vector&& ) noexcept
  20.     : _Base(std::move(__x)) { }
  21. //从list中拷贝数据，也是c++11才有的
  22.  vector(initializer_list<value_type> __l,
  23.         const allocator_type& __a = allocator_type())
  24. : _Base(__a)
  25. {
  26.     _M_range_initialize(__l.begin(), __l.end(), random_access_iterator_tag());
  27. }
  28. //支持vector使用两个迭代器范围内的值初始化，除了stl的迭代器，也可以是数组地址
  29. template<typename _InputIterator,
  30.         typename = std::_RequireInputIter<_InputIterator>>
  31. vector(_InputIterator __first, _InputIterator __last,
  32.         const allocator_type& __a = allocator_type())
  33. : _Base(__a)
  34. { _M_initialize_dispatch(__first, __last, __false_type()); }
  35. //只析构所有元素，释放内存由vector_base完成
  36. ~vector() _GLIBCXX_NOEXCEPT
  37. { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,_M_get_Tp_allocator()); }

5.vector

插入涉及到内存分配，动态调整，与一开始提到的vector与array区别，就在下面体现出：

  1. typename vector<_Tp, _Alloc>::iterator
  2. vector<_Tp, _Alloc>::insert(iterator __position, const value_type& __x)
  3. {
  4.     const size_type __n = __position – begin();
  5.     //插入到最后一个位置，相当于push_back
  6.     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
  7.         && __position == end())
  8.     {
  9.         _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
  10.         ++this->_M_impl._M_finish;
  11.     }
  12.     else
  13.     {
  14.         _M_insert_aux(__position, __x);
  15.     }
  16.     return iterator(this->_M_impl._M_start + __n);
  17. }

其中_M_insert_aux实现：

  1. template<typename _Tp, typename _Alloc>
  2. void vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
  3. {   
  4.     //内存空间足够
  5.     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
  6.     { 
  7.         _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
  8.                                 _GLIBCXX_MOVE(*(this->_M_impl._M_finish
  9.                                                 - 1)));
  10.         ++this->_M_impl._M_finish;
  11.         //__position后的元素依次向后移动一个位置
  12.         _GLIBCXX_MOVE_BACKWARD3(__position.base(),
  13.                                 this->_M_impl._M_finish - 2,
  14.                                 this->_M_impl._M_finish – 1);
  15.         //目标地址赋值
  16.         *__position = _Tp(std::forward<_Args>(__args)...);
  17.     }
  18.     else
  19.     {
  20.         //内存加倍
  21.         const size_type __len =
  22.         _M_check_len(size_type(1), "vector::_M_insert_aux");
  23.         const size_type __elems_before = __position - begin();
  24.         pointer __new_start(this->_M_allocate(__len));
  25.         pointer __new_finish(__new_start);
  26.         __try
  27.         {
  28.             //给position位置赋值
  29.             _Alloc_traits::construct(this->_M_impl,
  30.                                     __new_start + __elems_before,
  31.                                     std::forward<_Args>(__args)...);
  32.                                     __x);
  33.             __new_finish = 0;
  34.             //拷贝position位置前元素
  35.             __new_finish = std::__uninitialized_move_if_noexcept_a
  36.             (this->_M_impl._M_start, __position.base(),
  37.                 __new_start, _M_get_Tp_allocator());
  39.             ++__new_finish;
  40.             //拷贝position位置后元素
  41.             __new_finish
  42.             = std::__uninitialized_move_if_noexcept_a
  43.             (__position.base(), this->_M_impl._M_finish,
  44.                 __new_finish, _M_get_Tp_allocator());
  45.             }
  46.         __catch(...)
  47.         {
  48.             if (!__new_finish)
  49.             _Alloc_traits::destroy(this->_M_impl,
  50.                                     __new_start + __elems_before);
  51.             else
  52.             std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
  53.             _M_deallocate(__new_start, __len);
  54.             __throw_exception_again;
  55.         }
  57.         //析构原vector所有元素
  58.         std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
  59.                     _M_get_Tp_allocator());
  60.         //释放原vector内存空间
  61.         _M_deallocate(this->_M_impl._M_start,
  62.                     this->_M_impl._M_end_of_storage，this->_M_impl._M_start);
  63.         //vector内存地址指向新空间
  64.         this->_M_impl._M_start = __new_start;
  65.         this->_M_impl._M_finish = __new_finish;
  66.         this->_M_impl._M_end_of_storage = __new_start + __len;
  67.     }
  68. }

其中_M_check_len：

  1. size_type
  2. _M_check_len(size_type __n, const char* __s) const
  3. {
  4.     if (max_size() - size() < __n)
  5.         __throw_length_error(__N(__s));
  7.     const size_type __len = size() + std::max(size(), __n); //如果n小于当前size，内存加倍，否则内存增长n。
  8.     return (__len < size() || __len > max_size()) ? max_size() : __len;
  9. }

内存分配策略并不是简单的加倍，如果n小于当前size，内存加倍，否则内存增长n。

学习资料：

侯捷《STL源码剖析》

https://www.cnblogs.com/coderkian/p/3888429.html