STL源码剖析之vector

    1.vector

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

    开头处定义：

    在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

    而pointer：

    1.  typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::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*

    _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. }

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

    正向：

    2. typedef std::reverse_iterator<iterator> reverse_iterator;

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

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

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

    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.     }
    96.     // []操作符
    97.     reference
    98.     operator[](difference_type __n) const
    99.     { return *(*this + __n); }
    100. };

    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(); }

    _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指向。

    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。
    9. }

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

    学习资料：