STL源码分析--vector

一、简介

　　STL的容器分为序列式容器和关联式容器。vector作为序列式容器的一种，其内存模型与操作方式与数组类似，都是以一段连续的内存空间存储数据单元，区别在于数组的内存空间大小固定，不可变动，而vector可实现动态的内存迁移。当vector存储满后，会自动重新申请更大的内存空间作为新的存储容器，把旧的数据原样迁移到新的内存空间，此操作对用户层是无感知的。

　　用户层使用vector容器需包含头文件vector，方式为#include ，但vector的具体实现细节则在内。

　　STL对容器均使用模板类来实现，同时以空间分配器allocator作为内存管理者，管理着容器内存空间的申请和释放、数据对象的申请和回收，构造和析构。

　　vector的类图描述如下，其中的接口细节不完全展示出来。

allocator：空间分配器，管理内存的申请释放、数据对象的申请和回收，构造和析构。vector使用的空间分配器默认为std::new_alloctor；
_Vector_impl_data：维护容器的内存空间管理，三个指针_M_start指向内存的起始地址，_M_end_of_storage指向内存的末端地址，_M_finish指向容器最后一个元素的下一个地址空间。该类同时还提供了内存空间交换的接口，本质是交换指针。
_Vector_impl：继承自allocator和_Vector_Impl_data，同时该类内部还声明了_Asan模板类。
_Asan：GCC提供的一种内存错误检查器，这东西在编译和运行时使用，具体实现不在本博客说明。
_Vector_base：vector的基类。依赖_Vector_impl实现容器内存的构建、销毁。
vector：容器的具体实现，提供了插入、删除、定位等数据操作。

二、_Vector_impl_data的实现

 1 struct _Vector_impl_data
 2 {
 3     pointer _M_start;
 4     pointer _M_finish;
 5     pointer _M_end_of_storage;
 6 
 7     _GLIBCXX20_CONSTEXPR
 8     _Vector_impl_data() _GLIBCXX_NOEXCEPT
 9     : _M_start(), _M_finish(), _M_end_of_storage()
10     { }
11 
12 #if __cplusplus >= 201103L
13     // 移动构造函数
14     _GLIBCXX20_CONSTEXPR
15     _Vector_impl_data(_Vector_impl_data&& __x) noexcept
16     : _M_start(__x._M_start), _M_finish(__x._M_finish), _M_end_of_storage(__x._M_end_of_storage)
17     { __x._M_start = __x._M_finish = __x._M_end_of_storage = pointer(); }
18 #endif
19 
20     // 仅拷贝指针而不拷贝内存
21     _GLIBCXX20_CONSTEXPR
22     void _M_copy_data(_Vector_impl_data const& __x) _GLIBCXX_NOEXCEPT
23     {
24         _M_start = __x._M_start;
25         _M_finish = __x._M_finish;
26         _M_end_of_storage = __x._M_end_of_storage;
27     }
28 
29     // 交换的是指针，而不是内存数据
30     _GLIBCXX20_CONSTEXPR
31     void _M_swap_data(_Vector_impl_data& __x) _GLIBCXX_NOEXCEPT
32     {
33         _Vector_impl_data __tmp;
34         __tmp._M_copy_data(*this);
35         _M_copy_data(__x);
36         __x._M_copy_data(__tmp);
37     }
38 };

三、_Vector_impl的实现

 1 struct _Vector_impl : public _Tp_alloc_type, public _Vector_impl_data
 2 {
 3     _GLIBCXX20_CONSTEXPR
 4     _Vector_impl() _GLIBCXX_NOEXCEPT_IF(is_nothrow_default_constructible<_Tp_alloc_type>::value)
 5     : _Tp_alloc_type()
 6     { }
 7 
 8     _GLIBCXX20_CONSTEXPR
 9     _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT
10     : _Tp_alloc_type(__a)
11     { }
12 
13 #if __cplusplus >= 201103L
14     _GLIBCXX20_CONSTEXPR
15     _Vector_impl(_Vector_impl&& __x) noexcept
16     : _Tp_alloc_type(std::move(__x)), _Vector_impl_data(std::move(__x))
17     { }
18 
19     _GLIBCXX20_CONSTEXPR
20     _Vector_impl(_Tp_alloc_type&& __a) noexcept
21     : _Tp_alloc_type(std::move(__a))
22     { }
23 
24     _GLIBCXX20_CONSTEXPR
25     _Vector_impl(_Tp_alloc_type&& __a, _Vector_impl&& __rv) noexcept
26     : _Tp_alloc_type(std::move(__a)), _Vector_impl_data(std::move(__rv))
27     { }
28 #endif
29 
30 #if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
31     template
32     struct _Asan
33     {
34         ......
35     };
36 
37     template
38     struct _Asan >
39     {
40         ......
41     };
42 };

四、_Vector_base的实现

  1 template
  2 struct _Vector_base
  3 {
  4     typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
  5     typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer pointer;
  6 
  7     struct _Vector_impl_data
  8     {
  9         // _Vector_impl_data的定义见第二节
 10     };
 11 
 12     struct _Vector_impl
 13     : public _Tp_alloc_type, public _Vector_impl_data
 14     {
 15         // _Vector_impl的定义见第三节
 16     };
 17 
 18 public:
 19     typedef _Alloc allocator_type;
 20 
 21     // 获取空间分配器实例
 22     _GLIBCXX20_CONSTEXPR
 23     _Tp_alloc_type&
 24     _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
 25     { return this->_M_impl; }
 26 
 27     _GLIBCXX20_CONSTEXPR
 28     const _Tp_alloc_type&
 29     _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
 30     { return this->_M_impl; }
 31 
 32     _GLIBCXX20_CONSTEXPR
 33     allocator_type
 34     get_allocator() const _GLIBCXX_NOEXCEPT
 35     { return allocator_type(_M_get_Tp_allocator()); }
 36 
 37 #if __cplusplus >= 201103L
 38     _Vector_base() = default;
 39 #else
 40     _Vector_base() { }
 41 #endif
 42 
 43     _GLIBCXX20_CONSTEXPR
 44     _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT
 45     : _M_impl(__a) { }
 46 
 47 
 48 #if !_GLIBCXX_INLINE_VERSION
 49     _GLIBCXX20_CONSTEXPR
 50     _Vector_base(size_t __n)
 51     : _M_impl()
 52     { _M_create_storage(__n); }
 53 #endif
 54 
 55     _GLIBCXX20_CONSTEXPR
 56     _Vector_base(size_t __n, const allocator_type& __a)
 57     : _M_impl(__a)
 58     { _M_create_storage(__n); }
 59 
 60 #if __cplusplus >= 201103L
 61     _Vector_base(_Vector_base&&) = default;
 62 
 63 
 64 # if !_GLIBCXX_INLINE_VERSION
 65     // 移动构造函数
 66     _GLIBCXX20_CONSTEXPR
 67     _Vector_base(_Tp_alloc_type&& __a) noexcept
 68     : _M_impl(std::move(__a)) { }
 69 
 70     // __x为要移动的_Vector_base对象，__a为要拷贝的空间分配器
 71     _GLIBCXX20_CONSTEXPR
 72     _Vector_base(_Vector_base&& __x, const allocator_type& __a)
 73     : _M_impl(__a)
 74     {
 75         // 当指定的分配器__a与__x的分配器相等时，直接交换__x的指针指向即可，新的容器使用的内存空间仍为__x的内存空间；
 76         // 当指定的分配器__a与__x的分配器不相等时，重新申请新的内存空间给新容器使用。
 77         // 分配器的==运算符重载见allocator的实现，其始终返回true
 78         if (__x.get_allocator() == __a)
 79             this->_M_impl._M_swap_data(__x._M_impl);
 80         else
 81         {
 82             size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
 83             _M_create_storage(__n);
 84         }
 85     }
 86 # endif
 87 
 88     _GLIBCXX20_CONSTEXPR
 89     _Vector_base(const allocator_type& __a, _Vector_base&& __x)
 90     : _M_impl(_Tp_alloc_type(__a), std::move(__x._M_impl))
 91     { }
 92 #endif
 93 
 94     _GLIBCXX20_CONSTEXPR
 95     ~_Vector_base() _GLIBCXX_NOEXCEPT
 96     {
 97         _M_deallocate(_M_impl._M_start, _M_impl._M_end_of_storage - _M_impl._M_start);
 98     }
 99 
100 public:
101     _Vector_impl _M_impl;
102 
103     // 构建容器的内存空间，空间大小为__n * sizeof(_Tp)
104     _GLIBCXX20_CONSTEXPR
105     pointer
106     _M_allocate(size_t __n)
107     {
108         // 通过萃取机制取出空间分配器，再调用分配器提供的allocate接口申请内存空间
109         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
110         return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
111     }
112 
113     // 释放内存空间
114     _GLIBCXX20_CONSTEXPR
115     void
116     _M_deallocate(pointer __p, size_t __n)
117     {
118         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
119         if (__p)
120             _Tr::deallocate(_M_impl, __p, __n);
121     }
122 
123 protected:
124     // 构建容器的内存空间，空间大小为__n * sizeof(_Tp), 同时初始化三个指针
125     // _M_start指向内存首地址，_M_end_of_storage指向内存末端地址，_M_finish初始等于_M_start
126     _GLIBCXX20_CONSTEXPR
127     void
128     _M_create_storage(size_t __n)
129     {
130         this->_M_impl._M_start = this->_M_allocate(__n);
131         this->_M_impl._M_finish = this->_M_impl._M_start;
132         this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
133     }
134 };

五、vector的实现

1、vector内的定义的类型别名

 1 template >
 2 class vector : protected _Vector_base<_Tp, _Alloc>
 3 {
 4 #ifdef _GLIBCXX_CONCEPT_CHECKS
 5     // Concept requirements.
 6     typedef typename _Alloc::value_type        _Alloc_value_type;
 7 # if __cplusplus < 201103L
 8     __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 9 # endif
10     __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
11 #endif
12 
13 #if __cplusplus >= 201103L
14     static_assert(is_same::type, _Tp>::value,
15         "std::vector must have a non-const, non-volatile value_type");
16 # if __cplusplus > 201703L || defined __STRICT_ANSI__
17     static_assert(is_same::value,
18         "std::vector must have the same value_type as its allocator");
19 # endif
20 #endif
21 
22     typedef _Vector_base<_Tp, _Alloc>            _Base;
23     typedef typename _Base::_Tp_alloc_type        _Tp_alloc_type;
24     typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>    _Alloc_traits;
25 
26 public:
27     typedef _Tp                                                    value_type;
28     typedef typename _Base::pointer                                pointer;
29     typedef typename _Alloc_traits::const_pointer                const_pointer;
30     typedef typename _Alloc_traits::reference                    reference;
31     typedef typename _Alloc_traits::const_reference                const_reference;
32     typedef __gnu_cxx::__normal_iterator         iterator;
33     typedef __gnu_cxx::__normal_iterator const_iterator;
34     typedef std::reverse_iterator                const_reverse_iterator;
35     typedef std::reverse_iterator                        reverse_iterator;
36     typedef size_t                                                size_type;
37     typedef ptrdiff_t                                            difference_type;
38     typedef _Alloc                                                allocator_type;
39 
40 protected:
41     using _Base::_M_allocate;
42     using _Base::_M_deallocate;
43     using _Base::_M_impl;
44     using _Base::_M_get_Tp_allocator;
45     
46     ......
47 };

2、vector的构造和析构

  1 public: 
  2 
  3 #if __cplusplus >= 201103L
  4 vector() = default;
  5 #else
  6 vector() { }
  7 #endif
  8 
  9 explicit _GLIBCXX20_CONSTEXPR 
 10 vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT 
 11 : _Base(__a) { }
 12 
 13 #if __cplusplus >= 201103L
 14 
 15 // 初始化n个数据项，数据项的初始化采用默认构造。可指定空间分配器
 16 explicit _GLIBCXX20_CONSTEXPR
 17 vector(size_type __n, const allocator_type& __a = allocator_type()) 
 18 : _Base(_S_check_init_len(__n, __a), __a)
 19 { _M_default_initialize(__n); }
 20 
 21 // 初始化n个数据项，数据项的初始化为__value。可指定空间分配器
 22 _GLIBCXX20_CONSTEXPR
 23 vector(size_type __n, const value_type& __value, const allocator_type& __a = allocator_type())
 24 : _Base(_S_check_init_len(__n, __a), __a)
 25 { _M_fill_initialize(__n, __value); }
 26 
 27 #else
 28 
 29 // 初始化n个数据项，数据项的初始化为__value。可指定空间分配器
 30 explicit
 31 vector(size_type __n, const value_type& __value = value_type(), const allocator_type& __a = allocator_type())
 32 : _Base(_S_check_init_len(__n, __a), __a)
 33 { _M_fill_initialize(__n, __value); }
 34 
 35 #endif
 36 
 37 // 拷贝构造函数，将_x的所有数据项拷贝到新的容器内。_S_select_on_copy返回一份分配器的拷贝
 38 _GLIBCXX20_CONSTEXPR
 39 vector(const vector& __x) 
 40 : _Base(__x.size(), _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
 41 {
 42     this->_M_impl._M_finish = std::__uninitialized_copy_a(__x.begin(), __x.end(), 
 43         this->_M_impl._M_start, _M_get_Tp_allocator());
 44 }
 45 
 46 #if __cplusplus >= 201103L
 47 
 48 vector(vector&&) noexcept = default;
 49 
 50 // 拷贝构造函数，将_x的所有数据项拷贝到新的容器内。
 51 // __type_identity_t 能用于在模板实参推导中建立非推导语境：
 52 _GLIBCXX20_CONSTEXPR
 53 vector(const vector& __x, const __type_identity_t& __a)
 54 : _Base(__x.size(), __a)
 55 {
 56     this->_M_impl._M_finish = std::__uninitialized_copy_a(__x.begin(), __x.end(),
 57         this->_M_impl._M_start, _M_get_Tp_allocator());
 58 }
 59 
 60 private:
 61 
 62 // typename _Alloc_traits::is_always_equal{} 为true_type时
 63 _GLIBCXX20_CONSTEXPR
 64 vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
 65 : _Base(__m, std::move(__rv))
 66 { }
 67 
 68 // typename _Alloc_traits::is_always_equal{} 为false_type时
 69 _GLIBCXX20_CONSTEXPR
 70 vector(vector&& __rv, const allocator_type& __m, false_type)
 71 : _Base(__m)
 72 {
 73     // 当指定的分配器__m与__rv的分配器相等时，直接交换__rv的指针指向即可，新的容器使用的内存空间仍为__rv的内存空间；
 74     // 当指定的分配器__m与__rv的分配器不相等时，重新申请新的内存空间给新容器使用。
 75     // 分配器的==运算符重载见allocator的实现，其始终返回true
 76     if (__rv.get_allocator() == __m)
 77         this->_M_impl._M_swap_data(__rv._M_impl);
 78     else if (!__rv.empty())
 79     {
 80         this->_M_create_storage(__rv.size());
 81         this->_M_impl._M_finish = std::__uninitialized_move_a(__rv.begin(), __rv.end(),
 82             this->_M_impl._M_start, _M_get_Tp_allocator());
 83         __rv.clear();
 84     }
 85 }
 86 
 87 public:
 88 // 移动构造函数，采用C++11的委托构造方式，调用其他构造函数
 89 _GLIBCXX20_CONSTEXPR
 90 vector(vector&& __rv, const __type_identity_t& __m)
 91 noexcept( noexcept(vector(std::declval(), std::declval<const allocator_type&>(),
 92    std::declval())) )
 93 : vector(std::move(__rv), __m, typename _Alloc_traits::is_always_equal{})
 94 { }
 95 
 96 // 根据初始化列表创建容器，最终会调用数据项的n次拷贝构造函数来初始化对象。n为初始化列表的size大小
 97 _GLIBCXX20_CONSTEXPR
 98 vector(initializer_list __l, const allocator_type& __a = allocator_type())
 99 : _Base(__a)
100 {
101     _M_range_initialize(__l.begin(), __l.end(), random_access_iterator_tag());
102 }
103 #endif
104 
105 
106 // 根据迭代器范围初始化容器，会将[first,last)范围内的数据拷贝到新容器内。
107 // 如果迭代器类型是forward, bidirectional或random-access，将会调用数据项的N次拷贝构造，N为迭代器范围内的数据项数目。并且不会进行内存的重新分配（reallocate）
108 // 如果迭代器类型是input，会进行最多2N次的拷贝构造，和logN次的内存重新分配（reallocate）
109 #if __cplusplus >= 201103L
110 template>
111 _GLIBCXX20_CONSTEXPR
112 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type())
113 : _Base(__a)
114 {
115     _M_range_initialize(__first, __last, std::__iterator_category(__first));
116 }
117 #else
118 
119 // 根据迭代器范围初始化容器，会将[first,last)范围内的数据拷贝到新容器内。
120 // std::__is_integer模板用来判断类型是否为整型，
121 // 当为true时，会调用_M_fill_initialize()进行初始化，__first为数据项个数，__last为初始化的值；
122 // 当为false时，会调用_M_range_initialize进行初始化，__first、__last均为迭代器。
123 template
124 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type())
125 : _Base(__a)
126 {
127     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
128     _M_initialize_dispatch(__first, __last, _Integral());
129 }
130 #endif
131 
132 // 析构函数仅从容器内删除数据项，如果数据项是指针，析构函数不会释放指针所指的内存空间，用户层应该在析构前主动释放内存
133 _GLIBCXX20_CONSTEXPR
134 ~vector() _GLIBCXX_NOEXCEPT
135 {
136     std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator());
137     _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC;
138 }

构造函数调用的几个函数接口介绍：

 1 static _GLIBCXX20_CONSTEXPR size_type
 2 _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
 3 {
 4     // std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX,
 5     // and realistically we can't store more than PTRDIFF_MAX/sizeof(T)
 6     // (even if std::allocator_traits::max_size says we can).
 7     const size_t __diffmax = __gnu_cxx::__numeric_traits::__max / sizeof(_Tp);
 8     const size_t __allocmax = _Alloc_traits::max_size(__a);
 9     return (std::min)(__diffmax, __allocmax);
10 }
11 
12 static _GLIBCXX20_CONSTEXPR size_type
13 _S_check_init_len(size_type __n, const allocator_type& __a)
14 {
15     if (__n > _S_max_size(_Tp_alloc_type(__a)))
16         __throw_length_error(__N("cannot create std::vector larger than max_size()"));
17     return __n;
18 }
19 
20 #if __cplusplus >= 201103L
21 // 初始化n个数据项，调用的是数据项的默认构造函数
22 _GLIBCXX20_CONSTEXPR
23 void _M_default_initialize(size_type __n)
24 {
25     this->_M_impl._M_finish =
26         std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, _M_get_Tp_allocator());
27 }
28 #endif
29 
30 // 初始化n个数据项，值为__value，调用的是数据项的拷贝构造、赋值运算重载、或memset
31 _GLIBCXX20_CONSTEXPR
32 void _M_fill_initialize(size_type __n, const value_type& __value)
33 {
34     this->_M_impl._M_finish =
35         std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, _M_get_Tp_allocator());
36 }
37 
38  // 仅当迭代器类型为input时调用
39 template
40 _GLIBCXX20_CONSTEXPR
41 void _M_range_initialize(_InputIterator __first, _InputIterator __last,
42         std::input_iterator_tag)
43 {
44     __try {
45     for (; __first != __last; ++__first)
46 #if __cplusplus >= 201103L
47       emplace_back(*__first);
48 #else
49       push_back(*__first);
50 #endif
51     } __catch(...) {
52         clear();
53         __throw_exception_again;
54     }
55 }
56 
57 // 当迭代器类型为forward、bidirectional或random-access调用，会重新申请内存并进行数据项拷贝
58 template
59 _GLIBCXX20_CONSTEXPR
60 void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
61         std::forward_iterator_tag)
62 {
63     const size_type __n = std::distance(__first, __last);
64     this->_M_impl._M_start = this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
65     this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
66     this->_M_impl._M_finish =
67         std::__uninitialized_copy_a(__first, __last, this->_M_impl._M_start, _M_get_Tp_allocator());
68 }
69 
70 #if __cplusplus < 201103L
71 // _Integer 为整型类型
72 template
73 void _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
74 {
75     this->_M_impl._M_start = _M_allocate(_S_check_init_len(
76         static_cast(__n), _M_get_Tp_allocator()));
77     this->_M_impl._M_end_of_storage = this->_M_impl._M_start + static_cast(__n);
78     _M_fill_initialize(static_cast(__n), __value);
79 }
80 
81 // _InputIterator为迭代器类型
82 template
83 void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, __false_type)
84 {
85     _M_range_initialize(__first, __last, std::__iterator_category(__first));
86 }
87 #endif

其中__uninitialized_default_n_a、__uninitialized_fill_n_a、__uninitialized_copy_a、__uninitialized_move_a几个函数是全局的内存处理函数，用于填充、拷贝、移动元素等处理，详细介绍见

几个函数模板介绍：

__type_identity_t 能用于在模板实参推导中建立非推导语境，示例如下：

1 template<class T>
2 void f(T, T);
3  
4 template<class T>
5 void g(T, std::type_identity_t);
6  
7 f(4.2, 0); // 错误：对 'T' 推导出冲突的类型
8 g(4.2, 0); // OK ：调用 g

_Alloc_traits::is_always_equal 是用于得到空间分配器是否相等的特性，allocator的相等比较的意义是：一个allocator分配的空间，是否可以用另外一个allocator来释放。stl在定义了is_always_equal 模板始终为true_type。stl默认的空间分配器就是std::new_allocator，因为是new和delete的封装，一个std::allocator new的当然可以用另一个std::allocator来delete。

 1 // 定义在中的allocator类模板中
 2 using is_always_equal _GLIBCXX20_DEPRECATED_SUGGEST("std::allocator_traits::is_always_equal") = true_type;
 3 
 4 // 以下均定义在中
 5 struct __allocator_traits_base
 6 {
 7     template
 8     using __equal = typename _Tp::is_always_equal;
 9     ......
10 };
11 
12 template
13 struct allocator_traits : __allocator_traits_base
14 {
15     // __detected_or_t用来检查类型有效性，当__equal<_Alloc>，即 _Alloc::is_always_equal有效时，is_always_equal = _Alloc::is_always_equal
16     // 否则，is_always_equal = is_empty<_Alloc>::type
17     // is_empty 用来判断类型是否为空类型，空类型则返回true_type, 否则返回false_type
18     using is_always_equal = __detected_or_t::type, __equal, _Alloc>;
19     ......
20 };
21 
22 // 偏特化版本，分配器为allocator，即为std::new_allocator
23 template
24 struct allocator_traits>
25 {
26     using is_always_equal = true_type;
27     ......
28 };
29 
30 template<>
31 struct allocator_traitsvoid>>
32 {
33     using is_always_equal = true_type;
34     ......
35 };

is_empty：如果T是空类型（即，除大小为0的位字段外，没有非静态数据成员、没有虚拟函数、没有虚拟基类和非空基类的非并集类类型），则提供等于true的成员常量值。对于任何其他类型，值都为false。

std::declval的功能：返回某个类型T的右值引用，不管该类型是否有默认构造函数或者该类型是否可以创建对象。

3、vector的迭代器

1 typedef __gnu_cxx::__normal_iterator iterator;
2 typedef __gnu_cxx::__normal_iterator const_iterator;
3 typedef std::reverse_iterator    const_reverse_iterator;
4 typedef std::reverse_iterator        reverse_iterator;

vector定义了如上几种迭代器（其实为两种，每种各包含普通迭代器和常量迭代器），根据迭代器元素的遍历方向分为正向迭代器和反向迭代器。vector迭代器的本质为原生指针，属于Random Access Iterator，分别通过模板__normal_iterator和reverse_iterator做简单封装，实现指针的所有算数操作。__normal_iterator为正向迭代器，reverse_iterator为反向迭代器。关于迭代器的说明见

4、vector的定界操作

  1 // 返回指向容器第一个元素的迭代器（可读可写），迭代器是正向遍历的
  2 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
  3 iterator begin() _GLIBCXX_NOEXCEPT
  4 { return iterator(this->_M_impl._M_start); }
  5 
  6 // 返回指向容器第一个元素的迭代器（只读），迭代器是正向遍历的
  7 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
  8 const_iterator begin() const _GLIBCXX_NOEXCEPT
  9 { return const_iterator(this->_M_impl._M_start); }
 10 
 11 // 返回指向容器最后一个元素下一个位置的迭代器（可读可写），迭代器是正向遍历的
 12 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 13 iterator end() _GLIBCXX_NOEXCEPT
 14 { return iterator(this->_M_impl._M_finish); }
 15 
 16 // 返回指向容器最后一个元素下一个位置的迭代器（只读），迭代器是正向遍历的
 17 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 18 const_iterator end() const _GLIBCXX_NOEXCEPT
 19 { return const_iterator(this->_M_impl._M_finish); }
 20 
 21 // 返回指向容器最后一个元素的迭代器（可读可写），迭代器是反向遍历的
 22 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 23 reverse_iterator rbegin() _GLIBCXX_NOEXCEPT
 24 { return reverse_iterator(end()); }
 25 
 26 // 返回指向容器最后一个元素的迭代器（只读），迭代器是反向遍历的
 27 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 28 const_reverse_iterator rbegin() const _GLIBCXX_NOEXCEPT
 29 { return const_reverse_iterator(end()); }
 30 
 31 // 返回指向容器第一个元素前一个位置的迭代器（可读可写），迭代器是反向遍历的
 32 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 33 reverse_iterator rend() _GLIBCXX_NOEXCEPT
 34 { return reverse_iterator(begin()); }
 35 
 36 // 返回指向容器第一个元素前一个位置的迭代器（只读），迭代器是反向遍历的
 37 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 38 const_reverse_iterator rend() const _GLIBCXX_NOEXCEPT
 39 { return const_reverse_iterator(begin()); }
 40 
 41 #if __cplusplus >= 201103L
 42 
 43 // 返回指向容器第一个元素的迭代器（只读），迭代器是正向遍历的
 44 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
 45 const_iterator cbegin() const noexcept
 46 { return const_iterator(this->_M_impl._M_start); }
 47 
 48 // 返回指向容器最后一个元素下一个位置的迭代器（只读），迭代器是正向遍历的
 49 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
 50 const_iterator cend() const noexcept
 51 { return const_iterator(this->_M_impl._M_finish); }
 52 
 53 // 返回指向容器最后一个元素的迭代器（只读），迭代器是反向遍历的
 54 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
 55 const_reverse_iterator crbegin() const noexcept
 56 { return const_reverse_iterator(end()); }
 57 
 58 // 返回指向容器第一个元素前一个位置的迭代器（只读），迭代器是反向遍历的
 59 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
 60 const_reverse_iterator crend() const noexcept
 61 { return const_reverse_iterator(begin()); }
 62 #endif
 63 
 64 // 返回容器的第一个元素的引用
 65 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 66 reference front() _GLIBCXX_NOEXCEPT
 67 {
 68     __glibcxx_requires_nonempty();
 69     return *begin();
 70 }
 71 
 72 // 返回容器的第一个元素的常量引用
 73 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 74 const_reference front() const _GLIBCXX_NOEXCEPT
 75 {
 76     __glibcxx_requires_nonempty();
 77     return *begin();
 78 }
 79 
 80 // 返回容器最后一个元素的引用
 81 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 82 reference back() _GLIBCXX_NOEXCEPT
 83 {
 84     __glibcxx_requires_nonempty();
 85     return *(end() - 1);
 86 }
 87 
 88 // 返回容器最后一个元素的常量引用
 89 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 90 const_reference back() const _GLIBCXX_NOEXCEPT
 91 {
 92     __glibcxx_requires_nonempty();
 93     return *(end() - 1);
 94 }
 95 
 96 // 返回容器第一个元素的地址
 97 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 98 _Tp* data() _GLIBCXX_NOEXCEPT
 99 { return _M_data_ptr(this->_M_impl._M_start); }
100 
101 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
102 const _Tp* data() const _GLIBCXX_NOEXCEPT
103 { return _M_data_ptr(this->_M_impl._M_start); }

5、vector的插入和删除

先来看下删除，删除的方式有几种，erase、pop_back以及clear，对外提供的接口有：

 1 #if __cplusplus >= 201103L
 2 iterator erase(const_iterator __position);
 3 iterator erase(const_iterator __first, const_iterator __last);
 4 #else
 5 iterator erase(iterator __position);
 6 iterator erase(iterator __first, iterator __last);
 7 #endif
 8 
 9 void pop_back();
10 void clear();

接口的实现细节如下：

  1 // 删除__pos后的所有元素，含__pos。该函数私有，被erase(q1,q2), clear(), 
  2 // resize(), _M_fill_assign,_M_assign_aux调用
  3 _GLIBCXX20_CONSTEXPR
  4 void _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
  5 {
  6     if (size_type __n = this->_M_impl._M_finish - __pos)
  7     {
  8         std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
  9         this->_M_impl._M_finish = __pos;
 10         _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n);
 11     }
 12 }
 13 
 14 // 删除容器__position指向的元素，返回的迭代器指向__position的下一元素（或 end()）。__position删除后该迭代器失效
 15 GLIBCXX20_CONSTEXPR
 16 iterator
 17 #if __cplusplus >= 201103L
 18 erase(const_iterator __position)
 19 { return _M_erase(begin() + (__position - cbegin())); }
 20 #else
 21 erase(iterator __position)
 22 { return _M_erase(__position); }
 23 #endif
 24 
 25 // 删除容器[__first,__last)范围内的元素，返回的迭代器指向__last原先指向的元素（或end()）
 26 _GLIBCXX20_CONSTEXPR
 27 iterator
 28 #if __cplusplus >= 201103L
 29 erase(const_iterator __first, const_iterator __last)
 30 {
 31     const auto __beg = begin();
 32     const auto __cbeg = cbegin();
 33     return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
 34 }
 35 #else
 36 erase(iterator __first, iterator __last)
 37 { return _M_erase(__first, __last); }
 38 #endif
 39 
 40 // 清空容器
 41 _GLIBCXX20_CONSTEXPR
 42 void clear() _GLIBCXX_NOEXCEPT
 43 { _M_erase_at_end(this->_M_impl._M_start); }
 44 
 45 _GLIBCXX20_CONSTEXPR
 46 iterator _M_erase(iterator __position);
 47 
 48 _GLIBCXX20_CONSTEXPR
 49 iterator _M_erase(iterator __first, iterator __last);
 50 
 51 // 定义与bits/vector.tcc文件中
 52 template
 53 _GLIBCXX20_CONSTEXPR
 54 typename vector<_Tp, _Alloc>::iterator
 55 vector<_Tp, _Alloc>::
 56 _M_erase(iterator __position)
 57 {
 58     // 从__position + 1起，到end(), 每个元素往前挪一个单位（拷贝或移动）
 59     if (__position + 1 != end())
 60         _GLIBCXX_MOVE3(__position + 1, end(), __position);
 61     // 更新_M_finish，并删除最后一个元素
 62     --this->_M_impl._M_finish;
 63     _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
 64     _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
 65     return __position;
 66 }
 67 
 68 template
 69 _GLIBCXX20_CONSTEXPR
 70 typename vector<_Tp, _Alloc>::iterator
 71 vector<_Tp, _Alloc>::
 72 _M_erase(iterator __first, iterator __last)
 73 {
 74     if (__first != __last)
 75     {
 76         // 将[__last, end())范围内的数据拷到__first所指的内存空间上
 77         if (__last != end())
 78             _GLIBCXX_MOVE3(__last, end(), __first);
 79         // end() - __last 为拷贝或移动的数据项个数，所以__first.base() + (end() - __last)就是为最后要删除的起始地址
 80         _M_erase_at_end(__first.base() + (end() - __last));
 81     }
 82     return __first;
 83 }
 84 
 85 // 定义于
 86 #if __cplusplus >= 201103L
 87 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
 88 #else
 89 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
 90 #endif
 91 
 92 // 删除末端的一个元素
 93 _GLIBCXX20_CONSTEXPR
 94 void pop_back() _GLIBCXX_NOEXCEPT
 95 {
 96     __glibcxx_requires_nonempty();
 97     --this->_M_impl._M_finish;
 98     _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
 99     _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
100 }

iterator _M_erase(iterator __position); 操作的示例图如下：

iterator _M_erase(iterator __first, iterator __last);操作的示例图如下：

需要注意的是，当vector存储的数据是指针时，所有的删除操作（包括erase、pop_back和clear），都只会将数据项也就是指针从容器删除，而不会释放指针所指的内存空间。

vector插入数据的方式有几种，push_back、assign、insert等，对外提供的接口有：

 1 void push_back(const value_type& __x);
 2 void assign(size_type __n, const value_type& __val);
 3 #if __cplusplus >= 201103L
 4 void push_back(value_type&& __x);
 5 void emplace_back(_Args&&... __args);
 6 iterator emplace(const_iterator __position, _Args&&... __args);
 7 iterator insert(const_iterator __position, const value_type& __x);
 8 iterator insert(const_iterator __position, value_type&& __x);
 9 iterator insert(const_iterator __position, initializer_list __l);
10 iterator insert(const_iterator __position, size_type __n, const value_type& __x);
11 iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
12 void assign(_InputIterator __first, _InputIterator __last);
13 void assign(initializer_list __l);
14 #else
15 iterator insert(iterator __position, const value_type& __x);
16 void insert(iterator __position, size_type __n, const value_type& __x);
17 void insert(iterator __position, _InputIterator __first, _InputIterator __last);
18 void assign(_InputIterator __first, _InputIterator __last);
19 #endif
20 
21 #if __cplusplus > 201402L
22 reference emplace_back(_Args&&... __args);
23 #endif

assign函数

  1 _GLIBCXX20_CONSTEXPR
  2 void assign(size_type __n, const value_type& __val)
  3 { _M_fill_assign(__n, __val); }
  4 
  5 #if __cplusplus >= 201103L
  6 template<typename _InputIterator,
  7 typename = std::_RequireInputIter<_InputIterator>>
  8 _GLIBCXX20_CONSTEXPR
  9 void assign(_InputIterator __first, _InputIterator __last)
 10 { _M_assign_dispatch(__first, __last, __false_type()); }
 11 #else
 12 template
 13 void assign(_InputIterator __first, _InputIterator __last)
 14 {
 15     // 检查_InputIterator类型是否为整型，非整型时，为迭代器
 16     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 17     _M_assign_dispatch(__first, __last, _Integral());
 18 }
 19 #endif
 20 
 21 #if __cplusplus >= 201103L
 22 // 支持初始化列表作为参数赋值
 23 _GLIBCXX20_CONSTEXPR
 24 void assign(initializer_list __l)
 25 {
 26     this->_M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag());
 27 }
 28 #endif
 29 
 30 // 类型_Integer为整型时调用
 31 template
 32 _GLIBCXX20_CONSTEXPR
 33 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 34 { _M_fill_assign(__n, __val); }
 35 
 36 // 类型_InputIterator为迭代器类型时调用
 37 template
 38 _GLIBCXX20_CONSTEXPR
 39 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type)
 40 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
 41 
 42 // 定义于bits/vector.tcc文件
 43 template
 44 _GLIBCXX20_CONSTEXPR
 45 void vector<_Tp, _Alloc>::
 46 _M_fill_assign(size_t __n, const value_type& __val)
 47 {
 48     // 如果__n大于容器容量，则需重新申请内存空间，此处创建一个临时的容器，并将其与旧容器交换指针，即交换容器的内存空间所有权
 49     if (__n > capacity())
 50     {
 51         vector __tmp(__n, __val, _M_get_Tp_allocator());
 52         __tmp._M_impl._M_swap_data(this->_M_impl);
 53     }
 54     // 如果__n大于现有容器数据个数，但小于容器容量，则先将原有的数据项修改为__val，后构造剩余的数据项。
 55     else if (__n > size())
 56     {
 57         std::fill(begin(), end(), __val);
 58         const size_type __add = __n - size();
 59         _GLIBCXX_ASAN_ANNOTATE_GROW(__add);
 60         this->_M_impl._M_finish = std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 61                   __add, __val, _M_get_Tp_allocator());
 62         _GLIBCXX_ASAN_ANNOTATE_GREW(__add);
 63     }
 64     // 如果__n小于等于现有容器数据个数，则将容器前__n个数据项改为__val，后将多余的数据删除掉
 65     else
 66         _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
 67 }
 68 
 69 // 仅当迭代器类型为input时调用
 70 template
 71 template
 72 _GLIBCXX20_CONSTEXPR
 73 void vector<_Tp, _Alloc>::
 74 _M_assign_aux(_InputIterator __first, _InputIterator __last, std::input_iterator_tag)
 75 {
 76     pointer __cur(this->_M_impl._M_start);
 77     // 将[__first, __last)元素赋值到[_M_start, _M_finish)区间
 78     for (; __first != __last && __cur != this->_M_impl._M_finish; ++__cur, (void)++__first)
 79         *__cur = *__first;
 80     // 当[__first, __last)元素个数小于等于[_M_start, _M_finish)时，删除__cur及其后剩余的数据
 81     if (__first == __last)
 82         _M_erase_at_end(__cur);
 83     // 当[__first, __last)元素个数大于[_M_start, _M_finish)时，需要继续[__first, __last)未赋值的元素填充到容器末端
 84     else
 85         _M_range_insert(end(), __first, __last, std::__iterator_category(__first));
 86 }
 87 
 88 // 当迭代器类型为forward、bidirectional或random-access调用
 89 template
 90 template
 91 _GLIBCXX20_CONSTEXPR
 92 void vector<_Tp, _Alloc>::
 93 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, std::forward_iterator_tag)
 94 {
 95     const size_type __len = std::distance(__first, __last);
 96 
 97     // 当[__first, __last)元素个数大于原有容器容量，重新申请内存空间使用，并析构原容器内的所有元素、释放原容器内存空间
 98     if (__len > capacity())
 99     {
100         _S_check_init_len(__len, _M_get_Tp_allocator());
101         pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
102         std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator());
103         _GLIBCXX_ASAN_ANNOTATE_REINIT;
104         _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
105         this->_M_impl._M_start = __tmp;
106         this->_M_impl._M_finish = this->_M_impl._M_start + __len;
107         this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
108     }
109     // 当[__first, __last)元素个数小于等于容器容量，且小于容器数据项个数时，
110     // 将[__first, __last)元素赋值到容器内，并将剩余的旧数据项删除
111     else if (size() >= __len)
112         _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
113     // 当[__first, __last)元素个数小于等于容器容量，大于等于容器数据项个数时，
114     // 先将[__first, __last)前size()个元素赋值到容器内，再将剩余未赋值的元素拷贝到容器末端
115     else
116     {
117         _ForwardIterator __mid = __first;
118         std::advance(__mid, size()); // 相当于__mid += size()
119         std::copy(__first, __mid, this->_M_impl._M_start);
120         const size_type __attribute__((__unused__)) __n = __len - size();
121         _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
122         this->_M_impl._M_finish = std::__uninitialized_copy_a(__mid, __last, this->_M_impl._M_finish,
123             _M_get_Tp_allocator());
124         _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
125     }
126 }

assign操作将不再保留原容器的数据，而是完全根据assign函数指定的参数重新填充容器，原有数据被丢弃。

其中调用的子接口_M_range_insert()实现的细节如下：

  1 // 定义于bits/stl_iterator.h
  2 #if __cplusplus >= 201103L
  3 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
  4 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
  5     std::__make_move_if_noexcept_iterator(_Iter)
  6 #else
  7 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
  8 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
  9 #endif // C++11
 10 
 11 // 定义于bits/stl_algobase.h
 12 #if __cplusplus >= 201103L
 13 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
 14 #else
 15 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
 16 #endif
 17 
 18 // 仅当迭代器类型为input时调用当迭代器类型
 19 template
 20 template
 21 _GLIBCXX20_CONSTEXPR
 22 void vector<_Tp, _Alloc>::
 23 _M_range_insert(iterator __pos, _InputIterator __first, _InputIterator __last, std::input_iterator_tag)
 24 {
 25     // 如果是容器尾端插入，则遍历[__fitst,__last),依次插入到容器
 26     if (__pos == end())
 27     {
 28         for (; __first != __last; ++__first)
 29             insert(end(), *__first);
 30     }
 31     // 如果是在容器中间或首部插入，先构建临时的容器，再一次将[__fitst,__last)插入容器，
 32     // 此时只需对__pos后的元素做一次调整
 33     else if (__first != __last)
 34     {
 35         vector __tmp(__first, __last, _M_get_Tp_allocator());
 36         insert(__pos, _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()), 
 37             _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
 38     }
 39 }
 40 
 41 // 当迭代器类型为forward、bidirectional或random-access调用
 42 template
 43 template
 44 _GLIBCXX20_CONSTEXPR
 45 void vector<_Tp, _Alloc>::
 46 _M_range_insert(iterator __position, _ForwardIterator __first, _ForwardIterator __last, std::forward_iterator_tag)
 47 {
 48     if (__first != __last)
 49     {
 50         const size_type __n = std::distance(__first, __last);
 51         // 如果容器剩余空间足够插入
 52         if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n)
 53         {
 54             const size_type __elems_after = end() - __position;
 55             pointer __old_finish(this->_M_impl._M_finish);
 56             // __position到容器末端end，剩余元素个数__elems_after大于待插入的元素个数__n
 57             if (__elems_after > __n)
 58             {
 59                 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 60                 // 先将容器最后__n个元素移动到容器末端，中间腾出__n个位置出来
 61                 std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 62                     this->_M_impl._M_finish, this->_M_impl._M_finish, _M_get_Tp_allocator());
 63                 // 更新_M_finish指针
 64                 this->_M_impl._M_finish += __n;
 65                 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
 66                 // 移动或拷贝[__position, __old_finish - __n)到[__old_finish - (__elems_after - __n), __old_finish)
 67                 _GLIBCXX_MOVE_BACKWARD3(__position.base(), __old_finish - __n, __old_finish);
 68                 // 拷贝[__first, __last)到[__position, __position + __n)
 69                 std::copy(__first, __last, __position);
 70             }
 71             // __position到容器末端end，剩余元素个数__elems_after小于等于待插入的元素个数__n
 72             else
 73             {
 74                 _ForwardIterator __mid = __first;
 75                 // 等同于__mid += elems_after
 76                 std::advance(__mid, __elems_after);    
 77                 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 78                 // 先将[__first+elems_after, __last)区间的数据拷贝到容器末端
 79                 std::__uninitialized_copy_a(__mid, __last, this->_M_impl._M_finish, _M_get_Tp_allocator());
 80                 // 更新_M_finish指针
 81                 this->_M_impl._M_finish += __n - __elems_after;
 82                 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
 83                 // 移动[__position, __old_finish)到容器末端
 84                 std::__uninitialized_move_a(__position.base(), __old_finish,
 85                     this->_M_impl._M_finish, _M_get_Tp_allocator());
 86                 // 更新_M_finish指针
 87                 this->_M_impl._M_finish += __elems_after;
 88                 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
 89                 // 拷贝[__first, __first+elems_after)到[__position, __position+elems_after)
 90                 std::copy(__first, __mid, __position);
 91             }
 92         }
 93         // 容器剩余空间不足
 94         else
 95         {
 96             // 如果size() > __n，则容器新申请的空间大小为2倍size(), 否则为size()+__n
 97             const size_type __len = _M_check_len(__n, "vector::_M_range_insert");
 98             pointer __new_start(this->_M_allocate(__len));
 99             pointer __new_finish(__new_start);
100             __try
101             {
102                 // 移动[_M_start, __position)区间的数据到新的内存空间上
103                 __new_finish = std::__uninitialized_move_if_noexcept_a
104                     (this->_M_impl._M_start, __position.base(), __new_start, _M_get_Tp_allocator());
105                 // 拷贝[__first, __last)区间的数据到容器末端
106                 __new_finish = std::__uninitialized_copy_a(__first, __last,
107                     __new_finish, _M_get_Tp_allocator());
108                 // 移动[__position, _M_finish)区间的数据到容器末端
109                 __new_finish = std::__uninitialized_move_if_noexcept_a(__position.base(), 
110                     this->_M_impl._M_finish, __new_finish, _M_get_Tp_allocator());
111             }
112             __catch(...)
113             {
114                 // 若捕获异常，则析构所有元素，并释放申请的空间
115                 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
116                 _M_deallocate(__new_start, __len);
117                 __throw_exception_again;
118             }
119             // 析构原容器内存空间的所有对象，并释放原容器内存空间，更新容器指针指向使其指向新的地址空间
120             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
121                 _M_get_Tp_allocator());
122             _GLIBCXX_ASAN_ANNOTATE_REINIT;
123             _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
124                 - this->_M_impl._M_start);
125             this->_M_impl._M_start = __new_start;
126             this->_M_impl._M_finish = __new_finish;
127             this->_M_impl._M_end_of_storage = __new_start + __len;
128         }
129     }
130 }
131 
132 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
133 size_type max_size() const _GLIBCXX_NOEXCEPT
134 { return _S_max_size(_M_get_Tp_allocator()); }
135 
136 _GLIBCXX20_CONSTEXPR
137 size_type _M_check_len(size_type __n, const char* __s) const
138 {
139     if (max_size() - size() < __n)
140         __throw_length_error(__N(__s));
141 
142     const size_type __len = size() + (std::max)(size(), __n);
143     return (__len < size() || __len > max_size()) ? max_size() : __len;
144 }

_M_range_insert(iterator __position, _ForwardIterator __first, _ForwardIterator __last, std::forward_iterator_tag)负责将区间[__first, last)的数据插入到__position位置。

有如下几种情况：

1）容器剩余空间足够插入，从插入位置__position到容器末端end()的数据个数大于待插入的数据个数，操作步骤示意图如下：

　　假定，待插入个数__n = 2，__position到容器末端end()的数据个数__elems_after = 4

　　步骤1，先将容器末端最后__n个元素移动至末尾__M_finish处；

　　步骤2，将__position开始的__elems_after - _n个元素移动至原__M_finish前的__elems_after - _n个位置（std::move_back实现）;

　　步骤3，将待插入的__n个元素拷贝到__position开始处（步骤1和2已经将__position开始的__n个元素做了往后挪位的操作）。

2）容器剩余空间足够插入，从插入位置__position到容器末端end()的数据个数小于等于待插入的数据个数，操作步骤示意图如下：

　　假定，待插入个数__n = 5，__position到容器末端end()的数据个数__elems_after = 2

　　步骤1，将[__first + elems_after, __last)的数据拷贝到容器末端；

　　步骤2，将__position开始到原容器末端（old_finish）的数据拷贝到现在的容器末端；

　　步骤3，将[__first, __first + elems_after)的数据拷贝到__position开始的位置。

3）容器剩余空间不足插入新元素，操作步骤示意图如下：

　　假定，待插入个数__n = 2，__position到容器末端end()的数据个数__elems_after = 2，剩余空间为1

　　步骤1，为容器重新申请内存空间，并将[_M_start, __position)的元素移动到新内存空间地址上。申请大小根据容器的元素个数size和待插入元素个数__n决定，当size > __n时，为2倍size，否则为size+__n；

　　步骤2，将待插入元素[__first, __last)插入到新容器末尾；

　　步骤3，将原[__position, _M_finish)区间的元素插入到新容器末尾；

　　步骤4，将原容器[__M_start, _M_finish)区间的元素析构，并释放原内存空间，同时将 __M_start、_M_finish、_M_end_of_storage指针指向新的内存地址。

push_back函数

push_back函数用于在容器末端插入元素，当容器未满时直接在末端插入，当容器满时调用_M_realloc_insert()重新申请内存空间并将原容器数据迁移，再于尾端插入元素。

 1 _GLIBCXX20_CONSTEXPR
 2 void push_back(const value_type& __x)
 3 {
 4     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 5     {
 6         // 容器空间有剩余，直接在容器尾构造对象
 7         _GLIBCXX_ASAN_ANNOTATE_GROW(1);
 8         _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
 9         ++this->_M_impl._M_finish;
10         _GLIBCXX_ASAN_ANNOTATE_GREW(1);
11     }
12     else
13         // 容器空间不足
14         _M_realloc_insert(end(), __x);
15 }
16 
17 #if __cplusplus >= 201103L
18 _GLIBCXX20_CONSTEXPR
19 void push_back(value_type&& __x)
20 { emplace_back(std::move(__x)); }
21 
22 template
23 #if __cplusplus > 201402L
24     _GLIBCXX20_CONSTEXPR
25     reference
26 #else
27     void
28 #endif
29     emplace_back(_Args&&... __args);
30 
31 #endif

其中调用的子接口_M_realloc_insert()实现的细节如下：

 1 #if __cplusplus >= 201103L
 2 template
 3 template
 4 _GLIBCXX20_CONSTEXPR
 5 void vector<_Tp, _Alloc>::_M_realloc_insert(iterator __position, _Args&&... __args)
 6 #else
 7 template
 8 void vector<_Tp, _Alloc>::_M_realloc_insert(iterator __position, const _Tp& __x)
 9 #endif
10 {
11     // _M_check_len计算并返回新的内存空间大小
12     const size_type __len = _M_check_len(size_type(1), "vector::_M_realloc_insert");
13     pointer __old_start = this->_M_impl._M_start;
14     pointer __old_finish = this->_M_impl._M_finish;
15     const size_type __elems_before = __position - begin();
16     // 申请新的内存空间
17     pointer __new_start(this->_M_allocate(__len));
18     pointer __new_finish(__new_start);
19     __try
20     {
21         // 在新内存空间的__position位置先构造 待插入的对象
22         _Alloc_traits::construct(this->_M_impl, __new_start + __elems_before,
23 #if __cplusplus >= 201103L
24             std::forward<_Args>(__args)...);
25 #else
26             __x);
27 #endif
28         __new_finish = pointer();
29 
30         // 以下将原容器的数据移至新容器内部
31 #if __cplusplus >= 201103L
32         // _S_use_relocate判断_Alloc::value_type是否能移动插入（__is_move_insertable），std::__relocate_a调用是否会抛异常
33         // 如果支持移动插入，std::__relocate_a不抛异常，则返回true，最终通过std::__relocate_a移动元素
34         if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
35         {
36             __new_finish = _S_relocate(__old_start, __position.base(),
37                 __new_start, _M_get_Tp_allocator());
38 
39             ++__new_finish;
40 
41             __new_finish = _S_relocate(__position.base(), __old_finish,
42                 __new_finish, _M_get_Tp_allocator());
43         }
44         // 否则使用std::__uninitialized_move_if_noexcept_a移动元素
45         else
46 #endif
47         {
48             __new_finish = std::__uninitialized_move_if_noexcept_a(__old_start, __position.base(),
49                 __new_start, _M_get_Tp_allocator());
50 
51             ++__new_finish;
52 
53             __new_finish = std::__uninitialized_move_if_noexcept_a(__position.base(), __old_finish,
54                 __new_finish, _M_get_Tp_allocator());
55         }
56     }
57     __catch(...)
58     {
59         if (!__new_finish)
60             _Alloc_traits::destroy(this->_M_impl, __new_start + __elems_before);
61         else
62             std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
63         _M_deallocate(__new_start, __len);
64         __throw_exception_again;
65     }
66 #if __cplusplus >= 201103L
67     if _GLIBCXX17_CONSTEXPR (!_S_use_relocate())
68 #endif
69         std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
70 _GLIBCXX_ASAN_ANNOTATE_REINIT;
71     _M_deallocate(__old_start,this->_M_impl._M_end_of_storage - __old_start);
72     this->_M_impl._M_start = __new_start;
73     this->_M_impl._M_finish = __new_finish;
74     this->_M_impl._M_end_of_storage = __new_start + __len;
75 }

_S_use_relocate()函数用来判断是否可使用std::__relocate_a进行数据构造，它判断_Alloc::value_type是否能移动插入（__is_move_insertable），std::__relocate_a调用是否会抛异常；

_S_relocate()当满足_S_use_relocate()为常量表达式时（理解应该是函数的constexpr属性生效，_S_use_relocate()在编译期间计算结果，作为常量表达式），调用std::__relocate_a。

std::__relocate_a函数的具体实现在中，此处不予分析。

 1 #if __cplusplus >= 201103L
 2 static constexpr bool _S_nothrow_relocate(true_type)
 3 {
 4     return noexcept(std::__relocate_a(std::declval(),
 5         std::declval(),
 6         std::declval(),
 7         std::declval<_Tp_alloc_type&>()));
 8 }
 9 
10 static constexpr bool _S_nothrow_relocate(false_type)
11 { return false; }
12 
13 static constexpr bool _S_use_relocate()
14 {
15     // Instantiating std::__relocate_a might cause an error outside the
16     // immediate context (in __relocate_object_a's noexcept-specifier),
17     // so only do it if we know the type can be move-inserted into *this.
18     return _S_nothrow_relocate(__is_move_insertable<_Tp_alloc_type>{});
19 }
20 
21 static pointer _S_do_relocate(pointer __first, pointer __last, pointer __result,
22     _Tp_alloc_type& __alloc, true_type) noexcept
23 {
24     return std::__relocate_a(__first, __last, __result, __alloc);
25 }
26 
27 static pointer _S_do_relocate(pointer, pointer, pointer __result,
28     _Tp_alloc_type&, false_type) noexcept
29 { return __result; }
30 
31 static _GLIBCXX20_CONSTEXPR pointer
32 _S_relocate(pointer __first, pointer __last, pointer __result,
33     _Tp_alloc_type& __alloc) noexcept
34 {
35 #if __cpp_if_constexpr
36     // All callers have already checked _S_use_relocate() so just do it.
37     return std::__relocate_a(__first, __last, __result, __alloc);
38 #else
39     using __do_it = __bool_constant<_S_use_relocate()>;
40     return _S_do_relocate(__first, __last, __result, __alloc, __do_it{});
41 #endif
42 }
43 #endif // C++11

子接口emplace_back()的处理类同void push_back(const value_type& __x)

 1 // 在vector.tcc 定义
 2 #if __cplusplus >= 201103L
 3 template
 4 template
 5 
 6 #if __cplusplus > 201402L
 7 _GLIBCXX20_CONSTEXPR
 8 typename vector<_Tp, _Alloc>::reference
 9 #else
10 void
11 #endif
12 vector<_Tp, _Alloc>:: emplace_back(_Args&&... __args)
13 {
14     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
15     {
16         _GLIBCXX_ASAN_ANNOTATE_GROW(1);
17         _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
18              std::forward<_Args>(__args)...);
19         ++this->_M_impl._M_finish;
20         _GLIBCXX_ASAN_ANNOTATE_GREW(1);
21     }
22     else
23         _M_realloc_insert(end(), std::forward<_Args>(__args)...);
24 #if __cplusplus > 201402L
25     return back();
26 #endif
27 }
28 #endif

insert函数

1）insert(const_iterator __position, const value_type& __x)，在指定的__position位置插入元素__x

 1 // 在vector.tcc 定义
 2 template
 3 _GLIBCXX20_CONSTEXPR
 4 typename vector<_Tp, _Alloc>::iterator
 5 vector<_Tp, _Alloc>::
 6 #if __cplusplus >= 201103L
 7 insert(const_iterator __position, const value_type& __x)
 8 #else
 9 insert(iterator __position, const value_type& __x)
10 #endif
11 {
12     const size_type __n = __position - begin();
13     // 容器未满
14     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
15         // 插入位置在容器末端
16         if (__position == end())
17         {
18             _GLIBCXX_ASAN_ANNOTATE_GROW(1);
19             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
20             ++this->_M_impl._M_finish;
21             _GLIBCXX_ASAN_ANNOTATE_GREW(1);
22         }
23         // 插入位置不在容器末端，调用_M_insert_aux在指定位置插入元素
24         else
25         {
26 #if __cplusplus >= 201103L
27             const auto __pos = begin() + (__position - cbegin());
28             // __x 可以是当前容器的某个元素，所以这里不直接移动__x，而是移动__x的副本
29             _Temporary_value __x_copy(this, __x);
30             _M_insert_aux(__pos, std::move(__x_copy._M_val()));
31 #else
32             _M_insert_aux(__position, __x);
33 #endif
34         }
35     // 容器已满，调用_M_realloc_insert重新申请内存并插入元素
36     else
37 #if __cplusplus >= 201103L
38         _M_realloc_insert(begin() + (__position - cbegin()), __x);
39 #else
40         _M_realloc_insert(__position, __x);
41 #endif
42 
43     // 返回指向插入元素的迭代器
44     return iterator(this->_M_impl._M_start + __n);
45 }

其中子接口_M_insert_aux的实现细节如下：

 1 template
 2 template
 3 _GLIBCXX20_CONSTEXPR
 4 void vector<_Tp, _Alloc>::
 5 _M_insert_aux(iterator __position, _Arg&& __arg)
 6 #else
 7 template
 8 void vector<_Tp, _Alloc>::
 9 _M_insert_aux(iterator __position, const _Tp& __x)
10 #endif
11 {
12     _GLIBCXX_ASAN_ANNOTATE_GROW(1);
13     // 先拷贝构造最后一个元素，插入容器尾端，同时更新_M_finish指针
14     _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
15     ++this->_M_impl._M_finish;
16     _GLIBCXX_ASAN_ANNOTATE_GREW(1);
17 #if __cplusplus < 201103L
18     _Tp __x_copy = __x;
19 #endif
20     // [__position, _M_finish - 2)的所有元素往后挪一位，即移动到[__position + 1, _M_finish - 1)
21     _GLIBCXX_MOVE_BACKWARD3(__position.base(), this->_M_impl._M_finish - 2,    this->_M_impl._M_finish - 1);
22 #if __cplusplus < 201103L
23     *__position = __x_copy;
24 #else
25     *__position = std::forward<_Arg>(__arg);
26 #endif
27 }

_M_insert_aux操作步骤示意图如下：

2）iterator insert(const_iterator __position, value_type&& __x)；在指定的__position位置插入元素__x，__x为右值引用。该函数操作类同上面的常量左值引用参数的函数版本。

 1 #if __cplusplus >= 201103L
 2 _GLIBCXX20_CONSTEXPR
 3 iterator insert(const_iterator __position, value_type&& __x)
 4 { return _M_insert_rval(__position, std::move(__x)); }
 5 #endif
 6 
 7 #if __cplusplus >= 201103L
 8 template
 9 _GLIBCXX20_CONSTEXPR
10 auto vector<_Tp, _Alloc>::
11 _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
12 {
13     const auto __n = __position - cbegin();
14     // 容器未满
15     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
16         // 插入位置在容器末端
17         if (__position == cend())
18         {
19             _GLIBCXX_ASAN_ANNOTATE_GROW(1);
20             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, std::move(__v));
21             ++this->_M_impl._M_finish;
22             _GLIBCXX_ASAN_ANNOTATE_GREW(1);
23         }
24         // 插入位置不在容器末端，调用_M_insert_aux在指定位置插入元素
25         else
26             _M_insert_aux(begin() + __n, std::move(__v));
27     // 容器已满，调用_M_realloc_insert重新申请内存并插入元素
28     else
29         _M_realloc_insert(begin() + __n, std::move(__v));
30 
31     // 返回指向插入元素的迭代器
32     return iterator(this->_M_impl._M_start + __n);
33 }
34 #endif

3）iterator insert(const_iterator __position, initializer_list __l)；在指定位置，插入初始化列表。

1 #if __cplusplus >= 201103L
2 iterator insert(const_iterator __position, initializer_list __l)
3 {
4     auto __offset = __position - cbegin();
5     _M_range_insert(begin() + __offset, __l.begin(), __l.end(), std::random_access_iterator_tag());
6     return begin() + __offset;
7 }
8 #endif

调用的方式形如：

insert(begin(), {1,2,3});

4）iterator insert(const_iterator __position, size_type __n, const value_type& __x)；在指定位置，插入__n个值为__x的数据。

 1 #if __cplusplus >= 201103L
 2 _GLIBCXX20_CONSTEXPR
 3 iterator insert(const_iterator __position, size_type __n, const value_type& __x)
 4 {
 5     difference_type __offset = __position - cbegin();
 6     _M_fill_insert(begin() + __offset, __n, __x);
 7     return begin() + __offset;
 8 }
 9 #else
10 void insert(iterator __position, size_type __n, const value_type& __x)
11 { _M_fill_insert(__position, __n, __x); }
12 #endif

C++98和C++11及以上版本，该函数的返回值不同，C++98返回void，C++11返回指向插入的第一个元素的迭代器。

其中子接口_M_fill_insert的实现细节如下：

  1 template
  2 _GLIBCXX20_CONSTEXPR
  3 void vector<_Tp, _Alloc>::
  4 _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
  5 {
  6     if (__n != 0)
  7     {
  8         // 剩余空间足够
  9         if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n)
 10         {
 11 #if __cplusplus < 201103L
 12             value_type __x_copy = __x;
 13 #else
 14             _Temporary_value __tmp(this, __x);
 15             value_type& __x_copy = __tmp._M_val();
 16 #endif
 17             const size_type __elems_after = end() - __position;
 18             pointer __old_finish(this->_M_impl._M_finish);
 19             // __position到容器末端end，剩余元素个数__elems_after大于待插入的元素个数__n
 20             if (__elems_after > __n)
 21             {
 22                 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 23                 // 先将容器最后__n个元素移动到容器末端，中间腾出__n个位置出来
 24                 std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 25                     this->_M_impl._M_finish, this->_M_impl._M_finish, _M_get_Tp_allocator());
 26                 // 更新_M_finish指针
 27                 this->_M_impl._M_finish += __n;
 28                 _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
 29                 // 移动或拷贝[__position, __old_finish - __n)到[__old_finish - (__elems_after - __n), __old_finish)
 30                 _GLIBCXX_MOVE_BACKWARD3(__position.base(), __old_finish - __n, __old_finish);
 31                 // 以__x_copy填充[__position, __position + __n)
 32                 std::fill(__position.base(), __position.base() + __n, __x_copy);
 33             }
 34             // __position到容器末端end，剩余元素个数__elems_after小于等于待插入的元素个数__n
 35             else
 36             {
 37                 _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 38                 // 先填充__n - __elems_after个数据到容器末端
 39                 this->_M_impl._M_finish = std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 40                     __n - __elems_after, __x_copy, _M_get_Tp_allocator());
 41                 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
 42                 // 移动[__position, __old_finish)到容器末端
 43                 std::__uninitialized_move_a(__position.base(), __old_finish, 
 44                     this->_M_impl._M_finish, _M_get_Tp_allocator());
 45                 // 更新_M_finish指针
 46                 this->_M_impl._M_finish += __elems_after;
 47                 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
 48                 // 填充[__position,__old_finish)
 49                 std::fill(__position.base(), __old_finish, __x_copy);
 50             }
 51         }
 52         // 容器剩余空间不足
 53         else
 54         {
 55             // 如果size() > __n，则容器新申请的空间大小为2倍size(), 否则为size()+__n
 56             const size_type __len = _M_check_len(__n, "vector::_M_fill_insert");
 57             const size_type __elems_before = __position - begin();
 58             pointer __new_start(this->_M_allocate(__len));
 59             pointer __new_finish(__new_start);
 60             __try
 61             {
 62                 // 先在新的容器空间上填充[__position, __position + __n)
 63                 std::__uninitialized_fill_n_a(__new_start + __elems_before,
 64                     __n, __x, _M_get_Tp_allocator());
 65                 __new_finish = pointer();
 66 
 67                 // 移动[_M_start, __position)区间的数据到新的内存空间上
 68                 __new_finish = std::__uninitialized_move_if_noexcept_a
 69                     (this->_M_impl._M_start, __position.base(), __new_start, _M_get_Tp_allocator());
 70 
 71                 __new_finish += __n;
 72 
 73                 // 移动[__position, _M_finish)区间的数据到新的内存空间上
 74                 __new_finish = std::__uninitialized_move_if_noexcept_a(__position.base(), this->_M_impl._M_finish,
 75                     __new_finish, _M_get_Tp_allocator());
 76             }
 77             __catch(...)
 78             {
 79                 if (!__new_finish)
 80                     std::_Destroy(__new_start + __elems_before, __new_start + __elems_before + __n, _M_get_Tp_allocator());
 81                 else
 82                     std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
 83                 _M_deallocate(__new_start, __len);
 84                 __throw_exception_again;
 85             }
 86             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator());
 87             _GLIBCXX_ASAN_ANNOTATE_REINIT;
 88             _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
 89             this->_M_impl._M_start = __new_start;
 90             this->_M_impl._M_finish = __new_finish;
 91             this->_M_impl._M_end_of_storage = __new_start + __len;
 92         }
 93     }
 94 }
 95     
 96 // 类型为bool的特化版本
 97 template
 98 _GLIBCXX20_CONSTEXPR
 99 void vector<bool, _Alloc>::
100 _M_fill_insert(iterator __position, size_type __n, bool __x)
101 {
102     if (__n == 0)
103         return;
104     // 剩余空间充足
105     if (capacity() - size() >= __n)
106     {
107         std::copy_backward(__position, end(), this->_M_impl._M_finish + difference_type(__n));
108         std::fill(__position, __position + difference_type(__n), __x);
109         this->_M_impl._M_finish += difference_type(__n);
110     }
111     // 剩余空间不足
112     else
113     {
114         const size_type __len = _M_check_len(__n, "vector::_M_fill_insert");
115         _Bit_pointer __q = this->_M_allocate(__len);
116         iterator __start(std::__addressof(*__q), 0);
117         iterator __i = _M_copy_aligned(begin(), __position, __start);
118         std::fill(__i, __i + difference_type(__n), __x);
119         iterator __finish = std::copy(__position, end(), __i + difference_type(__n));
120         this->_M_deallocate();
121         this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
122         this->_M_impl._M_start = __start;
123         this->_M_impl._M_finish = __finish;
124     }
125 }

_M_fill_insert(iterator __position, size_type __n, const value_type& __x)用于在__position位置插入__n个值为__x的对象。当容器剩余空间充足时，插入步骤类同_M_range_insert；当容器剩余空间不足时，插入步骤类同_M_realloc_insert

5）iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)；在指定位置，插入[__first, __last)区间的数据。

 1 #if __cplusplus >= 201103L
 2 template>
 3 _GLIBCXX20_CONSTEXPR
 4 iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
 5 {
 6     difference_type __offset = __position - cbegin();
 7     _M_insert_dispatch(begin() + __offset, __first, __last, __false_type());
 8     
 9     // 返回指向插入位置的迭代器
10     return begin() + __offset;
11 }
12 #else
13       
14 template
15 void insert(iterator __position, _InputIterator __first, _InputIterator __last)
16 {
17     // 检查_InputIterator类型是否为整型，非整型时，为迭代器
18     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
19     _M_insert_dispatch(__position, __first, __last, _Integral());
20 }
21 #endif
22 
23 // 模板参数为整型数据时调用
24 template
25 _GLIBCXX20_CONSTEXPR
26 void
27 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type)
28 { _M_fill_insert(__pos, __n, __val); }
29 
30 // 模板参数为迭代器时调用
31 template
32 _GLIBCXX20_CONSTEXPR
33 void _M_insert_dispatch(iterator __pos, _InputIterator __first, _InputIterator __last, __false_type)
34 {
35     _M_range_insert(__pos, __first, __last, std::__iterator_category(__first));
36 }

C++98和C++11及以上版本，该函数的返回值不同，C++98返回void，C++11返回指向插入的第一个元素的迭代器。

6、vector的重载运算符

移动赋值运算符重载和初始化列表赋值

 1 #if __cplusplus >= 201103L
 2 // 移动赋值运算符重载
 3 _GLIBCXX20_CONSTEXPR vector& operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
 4 {
 5     constexpr bool __move_storage = _Alloc_traits::_S_propagate_on_move_assign() 
 6         || _Alloc_traits::_S_always_equal();
 7     _M_move_assign(std::move(__x), __bool_constant<__move_storage>());
 8     return *this;
 9 }
10 
11 // 赋值运算符重载，支持初始化列表的赋值方式，如vector vec = {1, 2, 3};
12 _GLIBCXX20_CONSTEXPR vector& operator=(initializer_list __l)
13 {
14     this->_M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag());
15     return *this;
16 }
17 
18 // 分配器支持移动赋值
19 _GLIBCXX20_CONSTEXPR
20 void _M_move_assign(vector&& __x, true_type) noexcept
21 {
22     // 交换两个容器指针
23     vector __tmp(get_allocator());
24     this->_M_impl._M_swap_data(__x._M_impl);
25     __tmp._M_impl._M_swap_data(__x._M_impl);
26     std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
27 }
28 
29 _GLIBCXX20_CONSTEXPR
30 void _M_move_assign(vector&& __x, false_type)
31 {
32     // 分配器支持移动赋值
33     if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
34         _M_move_assign(std::move(__x), true_type());
35     else
36     {
37         // 分配器不支持移动赋值，则调用_M_assign_aux赋值新容器，直接移动容器内的每个元素
38         this->_M_assign_aux(std::make_move_iterator(__x.begin()),
39             std::make_move_iterator(__x.end()), std::random_access_iterator_tag());
40         __x.clear();
41     }
42 }
43 #endif

赋值运算符重载

 1 template
 2 _GLIBCXX20_CONSTEXPR
 3 vector<_Tp, _Alloc>& vector<_Tp, _Alloc>::
 4 operator=(const vector<_Tp, _Alloc>& __x)
 5 {
 6     if (std::__addressof(__x) != this)
 7     {
 8         _GLIBCXX_ASAN_ANNOTATE_REINIT;
 9 #if __cplusplus >= 201103L
10         if (_Alloc_traits::_S_propagate_on_copy_assign())
11         {
12             // 分配器不支持移动赋值，即旧分配器申请的内存不能由新分配器来释放，
13             // 这种情况需要析构原容器内的数据对象，并释放内存空间。
14             if (!_Alloc_traits::_S_always_equal()
15                 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
16             {
17                 // replacement allocator cannot free existing storage
18                 this->clear();
19                 _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
20                     - this->_M_impl._M_start);
21                 this->_M_impl._M_start = nullptr;
22                 this->_M_impl._M_finish = nullptr;
23                 this->_M_impl._M_end_of_storage = nullptr;
24             }
25             std::__alloc_on_copy(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
26         }
27 #endif
28         const size_type __xlen = __x.size();
29         // 新容器容量大于原容器容量，重新申请内存并拷贝新容器数据，析构原容器对象，并释放原容器内存空间。
30         if (__xlen > capacity())
31         {
32             pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
33             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator());
34             _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
35             this->_M_impl._M_start = __tmp;
36             this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
37         }
38         // 原容器数据个数大于等于新容器数据个数，将新容器的数据拷贝至原容器首部，并析构尾部多余的旧数据对象
39         else if (size() >= __xlen)
40         {
41             std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), end(), _M_get_Tp_allocator());
42         }
43         // 原容器数据个数小于新容器数据个数，先拷贝size()个元素到新容器，再拷贝构造剩余的数据。
44         else
45         {
46             std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), this->_M_impl._M_start);
47             std::__uninitialized_copy_a(__x._M_impl._M_start + size(), 
48                 __x._M_impl._M_finish, this->_M_impl._M_finish, _M_get_Tp_allocator());
49         }
50         this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
51     }
52     return *this;
53 }

[]运算符重载

 1 // []运算符重载，使vector支持随机存取，返回容器第__n个对象的引用
 2 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 3 reference operator[](size_type __n) _GLIBCXX_NOEXCEPT
 4 {
 5     __glibcxx_requires_subscript(__n);
 6     return *(this->_M_impl._M_start + __n);
 7 }
 8 
 9 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
10 const_reference operator[](size_type __n) const _GLIBCXX_NOEXCEPT
11 {
12     __glibcxx_requires_subscript(__n);
13     return *(this->_M_impl._M_start + __n);
14 }

STL源码分析 STL

STL源码分析--vector

相关

集合相似度-easy-stl-set

依赖注入 Castle.Windsor入门

无法在web.xml或使用此应用程序部署的jar文件中解析绝对uri：[http://java.sun.com/jsp/

竞赛中用到的一些STL

STL中堆(heap)函数的使用

从零开始devops-fastlane配置

whistle工具

day41.EL&JSTL

C++ STL栈和队列

EL和JSTL核心技术

An exception was thrown while activating Castle.Proxies.NoticeApp ServiceProxy.

Whistle 实现原理 —— 从 0 开始实现一个抓包工具

标签