C++ STL容器(四) —— vector底层剖析

这篇讲解vector，不说废话，直接开始！

文章目录

原理
UML类图
代码实现
- 构造函数
- 插入元素
- 删除元素
- 清空容器
- 析构函数
- 赋值运算符
案例分析

原理

这里简单说一下 vector 的大致思想，动态数组，即它的长度会随着我们插入元素而产生变化，这里由两个量，一个是容量(capacity) 表示动态数组可容纳的元素数量上限，一个 size 表示动态数组当前的元素数量。

比如下面的情况，capacity = 4, size = 3，具体实现里使用三个指针来体现状态，因为也需要考虑插入，删除的便利，后面代码分析里会详细介绍。如果我们插入了两个元素，那么就会触发扩容，我们会重新分配一块更大的内存块，把之前的内存块的元素移动到新分配的内存块，然后释放掉之前的内存块，之后的操作就会在新的内存块上进行，具体分配多大的空间会由不同的库实现决定。

UML类图

照例看下 vector 相关的 UML 类图，这里把 _Compressed_pair 省略掉了，最终的 UML 类图还是挺简单的。

代码实现

构造函数

无参构造函数，就是进行 _Vector_val 的无参构造，而 _Vector_val 的无参构造就是把三个指针置空，也就是初始 size 和 capacity 都是 0。

    _CONSTEXPR20 vector() noexcept(is_nothrow_default_constructible_v<_Alty>) : _Mypair(_Zero_then_variadic_args_t{}) {_Mypair._Myval2._Alloc_proxy(_GET_PROXY_ALLOCATOR(_Alty, _Getal()));}_CONSTEXPR20 _Vector_val() noexcept : _Myfirst(), _Mylast(), _Myend() {}

有参构造，这里主要看传入数量 _Count 和初始化值的有参构造，本质上都是先 _Vector_val 无参构造，再调用 _Construct_n 初始化。

    _CONSTEXPR20 explicit vector(_CRT_GUARDOVERFLOW const size_type _Count, const _Alloc& _Al = _Alloc()): _Mypair(_One_then_variadic_args_t{}, _Al) {_Construct_n(_Count);}_CONSTEXPR20 vector(_CRT_GUARDOVERFLOW const size_type _Count, const _Ty& _Val, const _Alloc& _Al = _Alloc()): _Mypair(_One_then_variadic_args_t{}, _Al) {_Construct_n(_Count, _Val);}template <class... _Valty>_CONSTEXPR20 void _Construct_n(_CRT_GUARDOVERFLOW const size_type _Count, _Valty&&... _Val) {// Dispatches between the three sized constructions.// 1-arg -> value-construction, e.g. vector(5)// 2-arg -> fill, e.g. vector(5, "meow")// 3-arg -> sized range construction, e.g. vector{"Hello", "Fluffy", "World"}auto& _Al       = _Getal();auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alty, _Al);auto& _My_data  = _Mypair._Myval2;_Container_proxy_ptr<_Alty> _Proxy(_Alproxy, _My_data);if (_Count != 0) {_Buy_nonzero(_Count);_Tidy_guard<vector> _Guard{this};if constexpr (sizeof...(_Val) == 0) {_My_data._Mylast = _STD _Uninitialized_value_construct_n(_My_data._Myfirst, _Count, _Al);} else if constexpr (sizeof...(_Val) == 1) {_STL_INTERNAL_STATIC_ASSERT(is_same_v<_Valty..., const _Ty&>);_My_data._Mylast = _STD _Uninitialized_fill_n(_My_data._Myfirst, _Count, _Val..., _Al);} else if constexpr (sizeof...(_Val) == 2) {_My_data._Mylast = _STD _Uninitialized_copy(_STD forward<_Valty>(_Val)..., _My_data._Myfirst, _Al);} else {_STL_INTERNAL_STATIC_ASSERT(false); // unexpected number of arguments}_ASAN_VECTOR_CREATE;_Guard._Target = nullptr;}_Proxy._Release();}

首先如果 _Count!=0 会进行内存的分配，一个是看是否超过了最大可分配长度，如果超过报错，反之，调用分配器分配 _Count 大小的空间，然后将 _Myfirst 和 _Mylast 调到初始位置，_Myend 调到末尾处，这里的 _Count 就是动态数组的容量大小。

    _CONSTEXPR20 void _Buy_nonzero(const size_type _Newcapacity) {// allocate array with _Newcapacity elementsif (_Newcapacity > max_size()) {_Xlength();}_Buy_raw(_Newcapacity);}_CONSTEXPR20 void _Buy_raw(size_type _Newcapacity) {// allocate array with _Newcapacity elementsauto& _My_data    = _Mypair._Myval2;pointer& _Myfirst = _My_data._Myfirst;pointer& _Mylast  = _My_data._Mylast;pointer& _Myend   = _My_data._Myend;_STL_INTERNAL_CHECK(!_Myfirst && !_Mylast && !_Myend); // check that *this is tidy_STL_INTERNAL_CHECK(0 < _Newcapacity && _Newcapacity <= max_size());const pointer _Newvec = _STD _Allocate_at_least_helper(_Getal(), _Newcapacity);_Myfirst              = _Newvec;_Mylast               = _Newvec;_Myend                = _Newvec + _Newcapacity;}

然后会根据 _Count 后参数的数量条件编译不同的代码，如果 _Val 的数量为 0，调用 _Unintialized_value_construct_n，这里两个条件编译的条件 _Use_memset_value_construct_v 和 _Uses_default_construct 分别表示可以使用 memset 快速初始化且可以使用默认构造函数，那么就可以进行 0 初始化。否则调用分配器里定义好的构造方法，挨个构造。

template <class _Alloc>
_CONSTEXPR20 _Alloc_ptr_t<_Alloc> _Uninitialized_value_construct_n(_Alloc_ptr_t<_Alloc> _First, _Alloc_size_t<_Alloc> _Count, _Alloc& _Al) {// value-initialize _Count objects to raw _First, using _Alusing _Ptrty = typename _Alloc::value_type*;if constexpr (_Use_memset_value_construct_v<_Ptrty> && _Uses_default_construct<_Alloc, _Ptrty>::value) {{auto _PFirst = _Unfancy(_First);_Zero_range(_PFirst, _PFirst + _Count);return _First + _Count;}}_Uninitialized_backout_al<_Alloc> _Backout{_First, _Al};for (; 0 < _Count; --_Count) {_Backout._Emplace_back();}return _Backout._Release();
}template <class _Ptr>
_Ptr _Zero_range(const _Ptr _First, const _Ptr _Last) { // fill [_First, _Last) with zeroeschar* const _First_ch = reinterpret_cast<char*>(_STD _To_address(_First));char* const _Last_ch  = reinterpret_cast<char*>(_STD _To_address(_Last));_CSTD memset(_First_ch, 0, static_cast<size_t>(_Last_ch - _First_ch));return _Last;
}

如果 _Val 的数量是 1，即传入了要初始化的值，那么调用 _Uninitialized_fill_n，首先检查下能否直接使用 memset 填充，然后检查能否 0 填充，如果都不行，就挨个进行拷贝/移动构造。

template <class _Alloc>
_CONSTEXPR20 _Alloc_ptr_t<_Alloc> _Uninitialized_fill_n(_Alloc_ptr_t<_Alloc> _First, _Alloc_size_t<_Alloc> _Count, const typename _Alloc::value_type& _Val, _Alloc& _Al) {// copy _Count copies of _Val to raw _First, using _Alusing _Ty = typename _Alloc::value_type;if constexpr (_Fill_memset_is_safe<_Ty*, _Ty> && _Uses_default_construct<_Alloc, _Ty*, _Ty>::value) {{_Fill_memset(_Unfancy(_First), _Val, static_cast<size_t>(_Count));return _First + _Count;}} else if constexpr (_Fill_zero_memset_is_safe<_Ty*, _Ty> && _Uses_default_construct<_Alloc, _Ty*, _Ty>::value) {{if (_Is_all_bits_zero(_Val)) {_Fill_zero_memset(_Unfancy(_First), static_cast<size_t>(_Count));return _First + _Count;}}}_Uninitialized_backout_al<_Alloc> _Backout{_First, _Al};for (; 0 < _Count; --_Count) {_Backout._Emplace_back(_Val);}return _Backout._Release();
}

如果 _Val 的数量是 2，那么一般是通过传入迭代器，进行构造初始化。也是判断能不能安全地使用 memmove，如果是相同类型的指针可以直接计算距离并拷贝，如果是不同类型的指针，需要调用 _Copy_memmove_n 转成相同的指针类型再调用 _Copy_memmove。如果是不满足 memmove 的条件，挨个构造。

template <class _InIt, class _Se, class _Alloc>
_CONSTEXPR20 _Alloc_ptr_t<_Alloc> _Uninitialized_copy(_InIt _First, _Se _Last, _Alloc_ptr_t<_Alloc> _Dest, _Alloc& _Al) {// copy [_First, _Last) to raw _Dest, using _Al// note: only called internally from elsewhere in the STLusing _Ptrval = typename _Alloc::value_type*;// In pre-concepts world, _Uninitialized_copy should only ever be called with an iterator// and sentinel of the same type, so `_Get_unwrapped` is fine to call.auto _UFirst = _STD _Get_unwrapped(_STD move(_First));auto _ULast  = _STD _Get_unwrapped(_STD move(_Last));constexpr bool _Can_memmove = _Sent_copy_cat<decltype(_UFirst), decltype(_ULast), _Ptrval>::_Bitcopy_constructible&& _Uses_default_construct<_Alloc, _Ptrval, decltype(*_UFirst)>::value;if constexpr (_Can_memmove) {if constexpr (is_same_v<decltype(_UFirst), decltype(_ULast)>) {_STD _Copy_memmove(_STD _To_address(_UFirst), _STD _To_address(_ULast), _STD _Unfancy(_Dest));_Dest += _ULast - _UFirst;} else {const auto _Count = static_cast<size_t>(_ULast - _UFirst);_STD _Copy_memmove_n(_STD _To_address(_UFirst), _Count, _STD _Unfancy(_Dest));_Dest += _Count;}return _Dest;}_Uninitialized_backout_al<_Alloc> _Backout{_Dest, _Al};for (; _UFirst != _ULast; ++_UFirst) {_Backout._Emplace_back(*_UFirst);}return _Backout._Release();
}

拷贝构造，也是调用 _Construct_n 对应上面 _Val 的数量为 2 的情况

    _CONSTEXPR20 vector(const vector& _Right): _Mypair(_One_then_variadic_args_t{}, _Alty_traits::select_on_container_copy_construction(_Right._Getal())) {const auto& _Right_data = _Right._Mypair._Myval2;const auto _Count       = static_cast<size_type>(_Right_data._Mylast - _Right_data._Myfirst);_Construct_n(_Count, _Right_data._Myfirst, _Right_data._Mylast);}

移动构造，将当前 _Right 的三个指针通过 exchange 获取到之后置空，再用获取到的三个指针初始化当前 vector 的三个指针。

    _CONSTEXPR20 vector(vector&& _Right) noexcept: _Mypair(_One_then_variadic_args_t{}, _STD move(_Right._Getal()),_STD exchange(_Right._Mypair._Myval2._Myfirst, nullptr),_STD exchange(_Right._Mypair._Myval2._Mylast, nullptr),_STD exchange(_Right._Mypair._Myval2._Myend, nullptr)) {_Mypair._Myval2._Alloc_proxy(_GET_PROXY_ALLOCATOR(_Alty, _Getal()));_Mypair._Myval2._Swap_proxy_and_iterators(_Right._Mypair._Myval2);}

插入元素

push_back，内部调用 _Emplace_one_at_back，判断 _Mylast 是否和 _Myend 相等，如果相等，说明元素数量要超过容量了，需要扩容，调用 _Emplace_reallocate，否则不需要扩容，调用 _Emplace_back_with_unused_capacity。

    _CONSTEXPR20 void push_back(const _Ty& _Val) { // insert element at end, provide strong guarantee_Emplace_one_at_back(_Val);}_CONSTEXPR20 void push_back(_Ty&& _Val) {// insert by moving into element at end, provide strong guarantee_Emplace_one_at_back(_STD move(_Val));}template <class... _Valty>_CONSTEXPR20 _Ty& _Emplace_one_at_back(_Valty&&... _Val) {// insert by perfectly forwarding into element at end, provide strong guaranteeauto& _My_data   = _Mypair._Myval2;pointer& _Mylast = _My_data._Mylast;if (_Mylast != _My_data._Myend) {return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);}return *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);}

首先看下不需要扩容的情况，在 _Mylast 处构造，之后将 _Mylast 对应元素传给 _Result 返回，然后 ++_Mylast 向后移动 _Mylast 指针。

    template <class... _Valty>_CONSTEXPR20 _Ty& _Emplace_back_with_unused_capacity(_Valty&&... _Val) {// insert by perfectly forwarding into element at end, provide strong guaranteeauto& _My_data   = _Mypair._Myval2;pointer& _Mylast = _My_data._Mylast;_STL_INTERNAL_CHECK(_Mylast != _My_data._Myend); // check that we have unused capacityif constexpr (conjunction_v<is_nothrow_constructible<_Ty, _Valty...>,_Uses_default_construct<_Alloc, _Ty*, _Valty...>>) {_ASAN_VECTOR_MODIFY(1);_Construct_in_place(*_Mylast, _STD forward<_Valty>(_Val)...);} else {_ASAN_VECTOR_EXTEND_GUARD(static_cast<size_type>(_Mylast - _My_data._Myfirst) + 1);_Alty_traits::construct(_Getal(), _Unfancy(_Mylast), _STD forward<_Valty>(_Val)...);_ASAN_VECTOR_RELEASE_GUARD;}_Orphan_range(_Mylast, _Mylast);_Ty& _Result = *_Mylast;++_Mylast;return _Result;}

再看下需要扩容的情况，如果 _Oldsize 已经达到我们能分配元素的上限了，报错，反之，进行正常的扩容操作，首先 _Newsize = _Oldsize + 1 计算新的元素数量，然后 _Calculate_growth(_Newsize) 计算要扩容的大小，看 _Calculate_growth 内部实现，新的容量是原来的1.5倍。然后使用分配器分配这个大小的内存，在新分配的内存下构造我们要插入的对象，然后将之前内存的其他元素移动到新分配的内存，这里需要注意，如果我们类中有移动构造函数也有拷贝构造函数，那么如果移动构造函数不是 nothrow 的话，会调用拷贝构造函数。此外，这里还有 try catch 捕获拷贝构造的时候可能产生的异常，那么如果捕获到异常，会先把末尾新构造的对象析构掉，再把新分配的内存空间收回，然后抛出异常。如果没有异常，进入 _Change_array 方法，把原有内存里的对象都析构掉，然后收回原来的内存，最后将三个指针指向新分配空间的正确位置。

    template <class... _Valty>_CONSTEXPR20 pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val) {// reallocate and insert by perfectly forwarding _Val at _Whereptr_Alty& _Al        = _Getal();auto& _My_data    = _Mypair._Myval2;pointer& _Myfirst = _My_data._Myfirst;pointer& _Mylast  = _My_data._Mylast;_STL_INTERNAL_CHECK(_Mylast == _My_data._Myend); // check that we have no unused capacityconst auto _Whereoff = static_cast<size_type>(_Whereptr - _Myfirst);const auto _Oldsize  = static_cast<size_type>(_Mylast - _Myfirst);if (_Oldsize == max_size()) {_Xlength();}const size_type _Newsize = _Oldsize + 1;size_type _Newcapacity   = _Calculate_growth(_Newsize);const pointer _Newvec           = _Allocate_at_least_helper(_Al, _Newcapacity);const pointer _Constructed_last = _Newvec + _Whereoff + 1;pointer _Constructed_first      = _Constructed_last;_TRY_BEGIN_Alty_traits::construct(_Al, _Unfancy(_Newvec + _Whereoff), _STD forward<_Valty>(_Val)...);_Constructed_first = _Newvec + _Whereoff;if (_Whereptr == _Mylast) { // at back, provide strong guaranteeif constexpr (is_nothrow_move_constructible_v<_Ty> || !is_copy_constructible_v<_Ty>) {_Uninitialized_move(_Myfirst, _Mylast, _Newvec, _Al);} else {_Uninitialized_copy(_Myfirst, _Mylast, _Newvec, _Al);}} else { // provide basic guarantee_Uninitialized_move(_Myfirst, _Whereptr, _Newvec, _Al);_Constructed_first = _Newvec;_Uninitialized_move(_Whereptr, _Mylast, _Newvec + _Whereoff + 1, _Al);}_CATCH_ALL_Destroy_range(_Constructed_first, _Constructed_last, _Al);_Al.deallocate(_Newvec, _Newcapacity);_RERAISE;_CATCH_END_Change_array(_Newvec, _Newsize, _Newcapacity);return _Newvec + _Whereoff;}_CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {// given _Oldcapacity and _Newsize, calculate geometric growthconst size_type _Oldcapacity = capacity();const auto _Max              = max_size();if (_Oldcapacity > _Max - _Oldcapacity / 2) {return _Max; // geometric growth would overflow}const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;if (_Geometric < _Newsize) {return _Newsize; // geometric growth would be insufficient}return _Geometric; // geometric growth is sufficient}_CONSTEXPR20 void _Change_array(const pointer _Newvec, const size_type _Newsize, const size_type _Newcapacity) {// orphan all iterators, discard old array, acquire new arrayauto& _Al         = _Getal();auto& _My_data    = _Mypair._Myval2;pointer& _Myfirst = _My_data._Myfirst;pointer& _Mylast  = _My_data._Mylast;pointer& _Myend   = _My_data._Myend;_My_data._Orphan_all();if (_Myfirst) { // destroy and deallocate old array_Destroy_range(_Myfirst, _Mylast, _Al);_ASAN_VECTOR_REMOVE;_Al.deallocate(_Myfirst, static_cast<size_type>(_Myend - _Myfirst));}_Myfirst = _Newvec;_Mylast  = _Newvec + _Newsize;_Myend   = _Newvec + _Newcapacity;_ASAN_VECTOR_CREATE;}

emplace_back，除了 push_back vector容器还提供 emplace_back，看他的方法实现可以看到，我们可以传入需要的参数，最后调用有参构造函数即可，而不一定像 push_back 一样定义是调用拷贝构造/移动构造，在传入临时变量时，可以节省一次拷贝/移动 + 一次析构，内部也是调用 _Emplace_one_at_back 实现。此外，push_back 无返回值，而 emplace_back 返回我们插入元素的引用。

    template <class... _Valty>_CONSTEXPR20 decltype(auto) emplace_back(_Valty&&... _Val) {// insert by perfectly forwarding into element at end, provide strong guarantee_Ty& _Result = _Emplace_one_at_back(_STD forward<_Valty>(_Val)...);
#if _HAS_CXX17return _Result;
#else // ^^^ _HAS_CXX17 / !_HAS_CXX17 vvv(void) _Result;
#endif // ^^^ !_HAS_CXX17 ^^^}

insert 和 emplace，都是可以在任意位置插入元素(传入迭代器指定)，和 emplace_back 是 push_back 的进化版本一样，emplace 也可以看作是 insert 的进化版本，insert 内部实现也就是调用的 emplace，当然有一点不同，insert 本身还支持了插入多个元素。

    template <class... _Valty>_CONSTEXPR20 iterator emplace(const_iterator _Where, _Valty&&... _Val) {// insert by perfectly forwarding _Val at _Whereconst pointer _Whereptr = _Where._Ptr;auto& _My_data          = _Mypair._Myval2;const pointer _Oldlast  = _My_data._Mylast;if (_Oldlast != _My_data._Myend) {if (_Whereptr == _Oldlast) { // at back, provide strong guarantee_Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);} else {auto& _Al = _Getal();_Alloc_temporary2<_Alty> _Obj(_Al, _STD forward<_Valty>(_Val)...); // handle aliasing// after constructing _Obj, provide basic guarantee_Orphan_range(_Whereptr, _Oldlast);_ASAN_VECTOR_EXTEND_GUARD(static_cast<size_type>(_Oldlast - _My_data._Myfirst) + 1);_Alty_traits::construct(_Al, _Unfancy(_Oldlast), _STD move(_Oldlast[-1]));_ASAN_VECTOR_RELEASE_GUARD;++_My_data._Mylast;_Move_backward_unchecked(_Whereptr, _Oldlast - 1, _Oldlast);*_Whereptr = _STD move(_Obj._Get_value());}return _Make_iterator(_Whereptr);}return _Make_iterator(_Emplace_reallocate(_Whereptr, _STD forward<_Valty>(_Val)...));}_CONSTEXPR20 iterator insert(const_iterator _Where, const _Ty& _Val) { // insert _Val at _Wherereturn emplace(_Where, _Val);}_CONSTEXPR20 iterator insert(const_iterator _Where, _Ty&& _Val) { // insert by moving _Val at _Wherereturn emplace(_Where, _STD move(_Val));}

如果是要在 _Myend 插入说明需要扩容了，调用 _Emplace_reallocate，否则判断是否是在 _Mylast 插入，如果是就调用 _Emplace_back_with_unused_capacity 就行了，如果都不是，说明是在 [_Myfirst, _Mylast) 间插入，首先先构造出这个元素，然后用 _Oldlast[-1] 构造 _Oldlast，然后更新 _Mylast 指针，然后挨个向后移动元素，这里具体实现如下，最后将之前构造好的元素赋值给 *_Whereptr 即可。

template <class _BidIt1, class _BidIt2>
_CONSTEXPR20 _BidIt2 _Move_backward_unchecked(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest) {// move [_First, _Last) backwards to [..., _Dest)// note: _Move_backward_unchecked has callers other than the move_backward familyif constexpr (_Iter_move_cat<_BidIt1, _BidIt2>::_Bitcopy_assignable) {{return _STD _Copy_backward_memmove(_First, _Last, _Dest);}}while (_First != _Last) {*--_Dest = _STD move(*--_Last);}return _Dest;
}

因为我们已经将最后的元素向后移动过一次了，那么这里只需要 *--_Last 从前一个开始就行。

删除元素

pop_back 比较简单，析构最后一个元素，然后 --_Mylast 更新 _Mylast

    _CONSTEXPR20 void pop_back() noexcept /* strengthened */ {auto& _My_data   = _Mypair._Myval2;pointer& _Mylast = _My_data._Mylast;_Orphan_range(_Mylast - 1, _Mylast);_Alty_traits::destroy(_Getal(), _Unfancy(_Mylast - 1));_ASAN_VECTOR_MODIFY(-1);--_Mylast;}

erase 先将 [_Whereptr + 1, _Mylast) 的元素向前移动，然后析构掉最后一个元素(这里需要注意析构的是最后一个元素，而不是我们删除的那个)，然后 --_Mylast 更新 _Mylast，如果我们的类自定义了移动构造函数，那么必须提供相应的移动赋值运算符，否则会编译错误，否则会调用 memmove 直接进行字节层面的移动。

    _CONSTEXPR20 iterator erase(const_iterator _Where) noexcept(is_nothrow_move_assignable_v<value_type>) /* strengthened */ {const pointer _Whereptr = _Where._Ptr;auto& _My_data          = _Mypair._Myval2;pointer& _Mylast        = _My_data._Mylast;_Orphan_range(_Whereptr, _Mylast);_STD _Move_unchecked(_Whereptr + 1, _Mylast, _Whereptr);_Alty_traits::destroy(_Getal(), _Unfancy(_Mylast - 1));_ASAN_VECTOR_MODIFY(-1);--_Mylast;return iterator(_Whereptr, _STD addressof(_My_data));}template <class _InIt, class _OutIt>
_CONSTEXPR20 _OutIt _Move_unchecked(_InIt _First, _InIt _Last, _OutIt _Dest) {// move [_First, _Last) to [_Dest, ...)// note: _Move_unchecked has callers other than the move familyif constexpr (_Is_vb_iterator<_InIt> && _Is_vb_iterator<_OutIt, true>) {return _STD _Copy_vbool(_First, _Last, _Dest);} else {if constexpr (_Iter_move_cat<_InIt, _OutIt>::_Bitcopy_assignable) {{return _STD _Copy_memmove(_First, _Last, _Dest);}}for (; _First != _Last; ++_Dest, (void) ++_First) {*_Dest = _STD move(*_First);}return _Dest;}
}

清空容器

清空容器的话就是 clear，首先判断 _Myfirst 是否已经和 _Mylast 相等了，如果是，那么说明容器已经是空的了，直接返回。如果不是空的，就先把 [_Myfirst, _Mylast) 的对象都析构掉，然后把 _Mylast 调整到和 _Myfirst 一样，可见清空容器并不会让我们的内存释放掉，容量大小也就没变。

    _CONSTEXPR20 void clear() noexcept { // erase allauto& _My_data    = _Mypair._Myval2;pointer& _Myfirst = _My_data._Myfirst;pointer& _Mylast  = _My_data._Mylast;if (_Myfirst == _Mylast) { // already empty, nothing to do// This is an optimization for debug mode: we can avoid taking the debug lock to invalidate iterators.// Note that when clearing an empty vector, this will preserve past-the-end iterators, which is allowed by// N4950 [sequence.reqmts]/54 "a.clear() [...] may invalidate the past-the-end iterator".return;}_My_data._Orphan_all();_Destroy_range(_Myfirst, _Mylast, _Getal());_ASAN_VECTOR_MODIFY(static_cast<difference_type>(_Myfirst - _Mylast)); // negative when destroying elements_Mylast = _Myfirst;}

析构函数

析构函数内部直接调用的 _Tidy，_Tidy 内部也比较简单，如果 _Myfirst 非空，那么析构掉 [_Myfirst, _Mylast) 之间的元素，然后分配器回收内存，再把三个指针全部置空。

    _CONSTEXPR20 ~vector() noexcept {_Tidy();}_CONSTEXPR20 void _Tidy() noexcept { // free all storageauto& _Al         = _Getal();auto& _My_data    = _Mypair._Myval2;pointer& _Myfirst = _My_data._Myfirst;pointer& _Mylast  = _My_data._Mylast;pointer& _Myend   = _My_data._Myend;_My_data._Orphan_all();if (_Myfirst) { // destroy and deallocate old array_STD _Destroy_range(_Myfirst, _Mylast, _Al);_ASAN_VECTOR_REMOVE;_Al.deallocate(_Myfirst, static_cast<size_type>(_Myend - _Myfirst));_Myfirst = nullptr;_Mylast  = nullptr;_Myend   = nullptr;}}

赋值运算符

首先判断 _Right 是否就是当前容器，如果是的话直接返回，然后 _Tidy() 将当前容器清空，然后 _Pocma(_Al, _Right_al) 进行分配器的移动，最后 _Take_contents 将当前容器的指针赋为 _Right 容器的指针，最后将 _Right 容器指针清空。

    _CONSTEXPR20 vector& operator=(vector&& _Right) noexcept(_Choose_pocma_v<_Alty> != _Pocma_values::_No_propagate_allocators) {if (this == _STD addressof(_Right)) {return *this;}_Alty& _Al                = _Getal();_Alty& _Right_al          = _Right._Getal();constexpr auto _Pocma_val = _Choose_pocma_v<_Alty>;if constexpr (_Pocma_val == _Pocma_values::_No_propagate_allocators) {if (_Al != _Right_al) {_Move_assign_unequal_alloc(_Right);return *this;}}_Tidy();_Pocma(_Al, _Right_al);_Mypair._Myval2._Take_contents(_Right._Mypair._Myval2);return *this;}_CONSTEXPR20 void _Vector_val<_Val_types>::_Take_contents(_Vector_val& _Right) noexcept {this->_Swap_proxy_and_iterators(_Right);_Myfirst = _Right._Myfirst;_Mylast  = _Right._Mylast;_Myend   = _Right._Myend;_Right._Myfirst = nullptr;_Right._Mylast  = nullptr;_Right._Myend   = nullptr;}

案例分析

经过上面的代码洗礼，我们应该已经大致掌握了 MSVC 的 vector 实现，那么我们来看一个简单的例子作为练习：

class A {
public:int _a, _b;A(int a, int b) : _a(a), _b(b) {cout << "Constructor " << _a << endl;};A(const A& other) : _a(other._a), _b(other._b) {cout << "Copy Constructor " << _a << endl;};A(A&& other) : _a(other._a), _b(other._b) {cout << "Move Constructor " << _a << endl;}void operator=(A&& other)  {cout << "Move Assignment " << _a << endl;}~A() {cout << "Destructor" << _a << endl;}
};int main()
{vector<A> a;a.push_back(A(1, 2));cout << "---" << endl;a.push_back(A(2, 4));cout << "---" << endl;a.push_back(A(3, 6));cout << "---" << endl;a.erase(a.begin() + 1);cout << "---" << endl;a.clear();
}