MSVC2019的vector标准库实现源码分析

template <class _Ty, class _Alloc = allocator<_Ty>>
class vector { // varying size array of values
private:
    template <class>
    friend class _Vb_val;//？？？？
    friend _Tidy_guard<vector>;

    using _Alty        = _Rebind_alloc_t<_Alloc, _Ty>;//会区分是不是默认分配器_Default_allocator_Traits或自定义allocator，是默认的话，就是本身allocator<int>,否则。。。模板嵌套太多了。。
    using _Alty_Traits = allocator_Traits<_Alty>;

public:
    static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<_Ty, typename _Alloc::value_type>,
        _MIsmaTCHED_ALLOCATOR_messaGE("vector<T, Allocator>", "T"));

    using value_type      = _Ty;//int
    using allocator_type  = _Alloc;//
    using pointer         = typename _Alty_Traits::pointer;
    using const_pointer   = typename _Alty_Traits::const_pointer;
    using reference       = _Ty&;
    using const_reference = const _Ty&;
    using size_type       = typename _Alty_Traits::size_type;
    using difference_type = typename _Alty_Traits::difference_type;

private:
//template <class _Alloc> // tests if allocator has simple addressing

　　//_INLINE_VAR constexpr bool _Is_simple_alloc_v = is_same_v<typename allocator_Traits<_Alloc>::size_type, size_t>&&
　　//is_same_v<typename allocator_Traits<_Alloc>::difference_type, ptrdiff_t>&&
　　//is_same_v<typename allocator_Traits<_Alloc>::pointer, typename _Alloc::value_type*>&&
　　//is_same_v<typename allocator_Traits<_Alloc>::const_pointer, const typename _Alloc::value_type*>;

using _Scary_val = _Vector_val<conditional_t<_Is_simple_alloc_v<_Alty>, _Simple_types<_Ty>,
        _Vec_iter_types<_Ty, size_type, difference_type, pointer, const_pointer, _Ty&, const _Ty&>>>;//是否是simple类型，选择不同的types,
　　　　　　只要不是自定义类型，应该都是选择第一个，其实第二个无非也是用自定义的类型。

public:
    using iterator               = _Vector_iterator<_Scary_val>;
    using const_iterator         = _Vector_const_iterator<_Scary_val>;
    using reverse_iterator       = _STD reverse_iterator<iterator>;
    using const_reverse_iterator = _STD reverse_iterator<const_iterator>;

　　//两个构造函数同理，区分自定义分配器类型  #define _GET_PROXY_ALLOCATOR(_Alty, _Al) static_cast<_Rebind_alloc_t<_Alty, _Container_proxy>>(_Al) 这种写法第一次见，参数没有实际作用，构造一个新对象
    _CONSTEXPR20_CONTAINER vector() noexcept(is_nothrow_default_constructible_v<_Alty>)
        : _Mypair(_Zero_then_variaDic_args_t{}) {
        _Mypair._Myval2._Alloc_proxy(_GET_PROXY_ALLOCATOR(_Alty, _Getal()));//_GET_PROXY_ALLOCATOR(_Alty, _Getal()),构造一个allocator<_Container_proxy>
} 

_CONSTEXPR20_CONTAINER explicit vector(const _Alloc& _Al) noexcept : _Mypair(_One_then_variaDic_args_t{}, _Al) { _Mypair._Myval2._Alloc_proxy(_GET_PROXY_ALLOCATOR(_Alty, _Getal())); }

　　_Compressed_pair<_Alty, _Scary_val> _Mypair;//仅有的成员变量，实际继承第一个模板参数，负责分配数据内存，并持有一个_Scary_val的变量，负责管理数据
　　......
　　......

}

class _Vector_val : public _Container_base {// 基类里有个_Container_proxy* _Myproxy,维护迭代器的一个东西。
public:
    using value_type      = typename _Val_types::value_type;
    using size_type       = typename _Val_types::size_type;
    using difference_type = typename _Val_types::difference_type;
    using pointer         = typename _Val_types::pointer;
    using const_pointer   = typename _Val_types::const_pointer;
    using reference       = value_type&;
    using const_reference = const value_type&;

    _CONSTEXPR20_CONTAINER _Vector_val() noexcept : _Myfirst(), _Mylast(), _Myend() {}

    _CONSTEXPR20_CONTAINER _Vector_val(pointer _First, pointer _Last, pointer _End) noexcept
        : _Myfirst(_First), _Mylast(_Last), _Myend(_End) {}

    _CONSTEXPR20_CONTAINER void _Swap_val(_Vector_val& _Right) noexcept {
        this->_Swap_proxy_and_iterators(_Right);
        _Swap_adl(_Myfirst, _Right._Myfirst);
        _Swap_adl(_Mylast, _Right._Mylast);
        _Swap_adl(_Myend, _Right._Myend);
    }

    _CONSTEXPR20_CONTAINER void _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;
    }

    pointer _Myfirst; // pointer to beginning of array 指针维护数据结构
    pointer _Mylast; // pointer to current end of sequence
    pointer _Myend; // pointer to end of array
};

template <class _Ty1, class _Ty2, bool = is_empty_v<_Ty1> && !is_final_v<_Ty1>>
class _Compressed_pair final : private _Ty1 { // store a pair of values, deriving from empty first
public:
    _Ty2 _Myval2;

    using _Mybase = _Ty1; // for visualization

    template <class... _Other2>
    constexpr explicit _Compressed_pair(_Zero_then_variaDic_args_t, _Other2&&... _Val2) noexcept(//标签派发
        conjunction_v<is_nothrow_default_constructible<_Ty1>, is_nothrow_constructible<_Ty2, _Other2...>>)
        : _Ty1(), _Myval2(_STD forWARD<_Other2>(_Val2)...) {}
    template <class _Other1, class... _Other2>
    constexpr _Compressed_pair(_One_then_variaDic_args_t, _Other1&& _Val1, _Other2&&... _Val2) noexcept(
        conjunction_v<is_nothrow_constructible<_Ty1, _Other1>, is_nothrow_constructible<_Ty2, _Other2...>>)
        : _Ty1(_STD forWARD<_Other1>(_Val1)), _Myval2(_STD forWARD<_Other2>(_Val2)...) {}

    constexpr _Ty1& _Get_first() noexcept {
        return *this;//返回分配器，就是自身
    }

    constexpr const _Ty1& _Get_first() const noexcept {
        return *this;
    }
};

template <class _Alloc>
    _CONSTEXPR20_CONTAINER void _Alloc_proxy(_Alloc&& _Al) {//注意此时的_Al 是 allocator<container_proxy>,因为重新生成了一个allocator,具体看上面的_GET_PROXY_ALLOCATOR
_Container_proxy* const _New_proxy = _Unfancy(_Al.allocate(1));//分配一个container_proxy的内存16个字节，因为有两个指针，
 _Construct_in_place(*_New_proxy, this);//为刚才分配的内存，调用构造函数

 _Myproxy = _New_proxy; 
_New_proxy->_Mycont = this;//互相记录，container_base 记录一个proxy，这个proxy记录一个my_cont（container_base）
 }

template <class... _Valty>
    _CONSTEXPR20_CONTAINER decltype(auto) emplace_BACk(_Valty&&... _Val) {
        // insert by perfectly forWARDing into element at end, provide strong guarantee
        auto& _My_data   = _Mypair._Myval2;
        pointer& _Mylast = _My_data._Mylast;
        if (_Mylast != _My_data._Myend) {//last!=end 可以理解为capacity大于size，利用已有的多余内存构建数据。
            return _Emplace_BACk_with_unused_capacity(_STD forWARD<_Valty>(_Val)...);
        }
        _Ty& _Result = *_Emplace_reallocate(_Mylast, _STD forWARD<_Valty>(_Val)...);//新分配内存
#if _HAS_CXX17
        return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
        (void) _Result;
#endif // _HAS_CXX17
    }

template <class... _Valty>
    _CONSTEXPR20_CONTAINER 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 capacity

        const auto _Whereoff = static_cast<size_type>(_Whereptr - _Myfirst);//whereptr代表放入数据的位置
        const auto _Oldsize  = static_cast<size_type>(_Mylast - _Myfirst);//当前的size大小

        if (_Oldsize == max_size()) {
            _Xlength();//数据太大
        }

        const size_type _Newsize     = _Oldsize + 1;//已有的数据上新加一个
        const size_type _Newcapacity = _Calculate_growth(_NewsizE);
//////////////////////////////////////////////////////////////////
　　　　　　　　/*核心部分*/

_CONSTEXPR20_CONTAINER size_type _Calculate_growth(const size_type _NewsizE) const {
　　　　// given _Oldcapacity and _Newsize, calculate geometric growth
　　　　const 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;//在旧的大小基础上加一半，1 ， 2， 3 ，4，5， 7增长方式，前几个每次都会重新分配内存，

　　　　if (_Geometric < _NewsizE) {
　　　　　　return _Newsize; // geometric growth would be insufficient
　　　　}

　　　　return _Geometric; // geometric growth is sufficient 返回的大小一定大于等于newsize

}

////////////////////////////////////////////////////////////////////////
　　　　const pointer _Newvec   = _Al.allocate(_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 guarantee 
            _Umove_if_noexcept(_Myfirst, _Mylast, _Newvec);//将旧数据移动到新的内存里。
        } else { // provide basic guarantee
            _Umove(_Myfirst, _Whereptr, _Newvec);
            _Constructed_first = _Newvec;
            _Umove(_Whereptr, _Mylast, _Newvec + _Whereoff + 1);
        }
        _CATCH_ALL
        _Destroy(_Constructed_first, _Constructed_last);//异常捕捉
        _Al.deallocate(_Newvec, _Newcapacity);
        _RERAISE;
        _CATCH_END

        _Change_array(_Newvec, _Newsize, _Newcapacity);//因为容器重分配内存，需要重新调整，first,last,end指针，同时让所有的迭代器失效
        return _Newvec + _Whereoff;
    }

 template <class... _Valty>
    _CONSTEXPR20_CONTAINER decltype(auto) _Emplace_BACk_with_unused_capacity(_Valty&&... _Val) {
        // insert by perfectly forWARDing into element at end, provide strong guarantee
        auto& _My_data   = _Mypair._Myval2;
        pointer& _Mylast = _My_data._Mylast;
        _STL_INTERNAL_checK(_Mylast != _My_data._Myend); // check that we have unused capacity
        _Alty_Traits::construct(_Getal(), _Unfancy(_Mylast), _STD forWARD<_Valty>(_Val)...);
        _Orphan_range(_Mylast, _Mylast);//使迭代器失效
        _Ty& _Result = *_Mylast;
        ++_Mylast;
#if _HAS_CXX17
        return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
        (void) _Result;
#endif // _HAS_CXX17
    }

_CONSTEXPR20_CONTAINER void _Adopt_unlocked(const _Container_base12* _Parent) noexcept {
        if (!_Parent) {
            _Orphan_me_unlocked_v3();
            return;
        }

        _Container_proxy* _Parent_proxy = _Parent->_Myproxy;
        if (_Myproxy != _Parent_proxy) { // change parentage
            if (_Myproxy) { // adopted, remove self from list
                _Orphan_me_unlocked_v3();
            }
            _Mynextiter                 = _Parent_proxy->_Myfirstiter;//每次adopt,proxy记录的迭代器都会更新为当前，把上一个记录在_Mynextiter里，形成一个chain
            _Parent_proxy->_Myfirstiter = this;
            _Myproxy                    = _Parent_proxy;//当一个迭代器的_Myproxy为空时，即为失效，比如push_BACk后，end（）迭代器就会失效
        }
    }

template <class _Alloc>
struct _Default_allocator_Traits { // Traits for std::allocator
    using allocator_type = _Alloc;
    using value_type     = typename _Alloc::value_type;

    using pointer            = value_type*;
    using const_pointer      = const value_type*;
    using void_pointer       = void*;
    using const_void_pointer = const void*;

    using size_type       = size_t;//默认的size_t
    using difference_type = ptrdiff_t;

    using propagate_on_container_copy_assignment = false_type;
    using propagate_on_container_move_assignment = true_type;
    using propagate_on_container_swap            = false_type;
    using is_always_equal                        = true_type;

    template <class _Other>
    using rebind_alloc = allocator<_Other>;

    template <class _Other>
    using rebind_Traits = allocator_Traits<allocator<_Other>>;
....
}