MSVC2019的deque源码分析

本文主要是介绍MSVC2019的deque源码分析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

先贴上源码的部分实现，如下，可以看到跟vector类似的模式，还是以deque<int>为例，

template <class _Ty, class _Alloc = allocator<_Ty>>
class deque {
private:
    friend _Tidy_guard<deque>;
    static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<_Ty, typename _Alloc::value_type>,
        _MISMATCHED_ALLOCATOR_MESSAGE("deque<T, Allocator>", "T"));

    using _Alty           = _Rebind_alloc_t<_Alloc, _Ty>;//std::allocator<int>,这些与vector类似，具体可参考vector一文
    using _Alty_traits    = allocator_traits<_Alty>;
    using _Alpty          = _Rebind_alloc_t<_Alloc, typename _Alty_traits::pointer>;
    using _Alpty_traits   = allocator_traits<_Alpty>;
    using _Mapptr         = typename _Alpty_traits::pointer;
    using _Alproxy_ty     = _Rebind_alloc_t<_Alty, _Container_proxy>;
    using _Alproxy_traits = allocator_traits<_Alproxy_ty>;

//这个类型同样熟悉，代表数据的容器。
    using _Scary_val = _Deque_val<conditional_t<_Is_simple_alloc_v<_Alty>, _Deque_simple_types<_Ty>,
        _Deque_iter_types<_Ty, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
            typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, _Ty&, const _Ty&, _Mapptr>>>;

    static constexpr int _Minimum_map_size = 8;
    static constexpr int _Block_size       = _Scary_val::_Block_size;

public:
    using allocator_type  = _Alloc;
    using value_type      = _Ty;
    using size_type       = typename _Alty_traits::size_type;
    using difference_type = typename _Alty_traits::difference_type;
    using pointer         = typename _Alty_traits::pointer;
    using const_pointer   = typename _Alty_traits::const_pointer;
    using reference       = _Ty&;
    using const_reference = const _Ty&;

    using iterator                  = _Deque_iterator<_Scary_val>;
    using const_iterator            = _Deque_const_iterator<_Scary_val>;
    using _Unchecked_iterator       = _Deque_unchecked_iterator<_Scary_val>;
    using _Unchecked_const_iterator = _Deque_unchecked_const_iterator<_Scary_val>;

    using reverse_iterator       = _STD reverse_iterator<iterator>;
    using const_reverse_iterator = _STD reverse_iterator<const_iterator>;
    enum { _EEN_DS = _Block_size }; // helper for expression evaluator

    deque() : _Mypair(_Zero_then_variadic_args_t{}) {
        _Get_data()._Alloc_proxy(static_cast<_Alproxy_ty>(_Getal()));//首先为container分配一个proxy，同样是后续管理迭代器的
    }
.....
     _Compressed_pair<_Alty, _Scary_val> _Mypair;

其实每个不同容器，关键在于这个_Scary_val,真正的数据结构，负责管理整个数据的生命周期。如下贴出相关代码：

template <class _Val_types>
class _Deque_val : public _Container_base12 {
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&;
    using _Mapptr         = typename _Val_types::_Mapptr;

private:
    static constexpr size_t _Bytes = sizeof(value_type);

public:
    static constexpr int _Block_size = _Bytes <= 1 ? 16 //根据数据类型的大小，确定块的大小，可以看到如果sizeof 大于8 ，则只有一个block。
                                     : _Bytes <= 2 ? 8
                                     : _Bytes <= 4 ? 4
                                     : _Bytes <= 8 ? 2
                                                   : 1; // elements per block (a power of 2)

    _Deque_val() noexcept : _Map(), _Mapsize(0), _Myoff(0), _Mysize(0) {}

    size_type _Getblock(size_type _Off) const noexcept {
        // NB: _Mapsize and _Block_size are guaranteed to be powers of 2
        return (_Off / _Block_size) & (_Mapsize - 1);
    }

    _Mapptr _Map; // pointer to array of pointers to blocks 二级指针，缓存指针的列表，每一个指针指向一个block
    size_type _Mapsize; // size of map array, zero or 2^N
    size_type _Myoff; // offset of initial element//相对初始元素的偏移，(push_front,是放在缓存的最后位置)
    size_type _Mysize; // current length of sequence
};

 再来看两个经典操作，push_front和push_back.首先看下push_front.可以看出是放在最后的位置，逐次向前偏移, _Myoff只对push_front有意义

template <class... _Valty>
    decltype(auto) emplace_front(_Valty&&... _Val) {
        _Orphan_all();//首先让所有的迭代器失效

        if (_Myoff() % _Block_size == 0/*(要到一个新的block上分配数据了)*/ && _Mapsize() <= (_Mysize() + _Block_size) / _Block_size) {
            _Growmap(1);//初始情况，或者当前元素即将扩充到最后的一个残余block，并不一定是第一个，因为第一个有可能push_back过。
        }
        _Myoff() &= _Mapsize() * _Block_size - 1;//与全1相与，没看出啥意义。
        size_type _Newoff = _Myoff() != 0 ? _Myoff() : _Mapsize() * _Block_size;//每次push_front到头时，即off等于0，则重新从后面push_front
        size_type _Block  = _Getblock(--_Newoff);//当前数据应该存贮在哪个block
        if (_Map()[_Block] == nullptr) {//是否已分配内存
            _Map()[_Block] = _Getal().allocate(_Block_size);
        }

        _Alty_traits::construct(//调用构造函数
            _Getal(), _Unfancy(_Map()[_Block] + _Newoff % _Block_size), _STD forward<_Valty>(_Val)...);

        _Myoff() = _Newoff;//记录更新数据
        ++_Mysize();
    }

_Growmap:

void _Growmap(size_type _Count) { // grow map by at least _Count pointers, _Mapsize() a power of 2
        static_assert(1 < _Minimum_map_size, "The _Xlen() test should always be performed.");

        _Alpty _Almap(_Getal());
        size_type _Newsize = 0 < _Mapsize() ? _Mapsize() : 1;
        while (_Newsize - _Mapsize() < _Count || _Newsize < _Minimum_map_size) {//保证其不小于最小map_size
            // scale _Newsize to 2^N >= _Mapsize() + _Count
            if (max_size() / _Block_size - _Newsize < _Newsize) {
                _Xlen(); // result too long
            }

            _Newsize *= 2;//以后每次增长，起码2倍扩张。
        }
        _Count = _Newsize - _Mapsize();//较上次增长多少个

        size_type _Myboff = _Myoff() / _Block_size;
        _Mapptr _Newmap   = _Almap.allocate(_Mapsize() + _Count);
        _Mapptr _Myptr    = _Newmap + _Myboff;//新的map 空间，注意额外把offblock 也加上去了。

        _Myptr = _STD uninitialized_copy(_Map() + _Myboff, _Map() + _Mapsize(), _Myptr); // copy initial to end, 拷贝末尾含有值 block对应的指针
        if (_Myboff <= _Count) { // increment greater than offset of initial block
            _Myptr = _STD uninitialized_copy(_Map(), _Map() + _Myboff, _Myptr); // copy rest of old 
            _Uninitialized_value_construct_n_unchecked1(_Myptr, _Count - _Myboff); // clear suffix of new
            _Uninitialized_value_construct_n_unchecked1(_Newmap, _Myboff); // clear prefix of new
        } else { // increment not greater than offset of initial block
            _STD uninitialized_copy(_Map(), _Map() + _Count, _Myptr); // copy more old 这段代码似乎不会被执行到
            _Myptr = _STD uninitialized_copy(_Map() + _Count, _Map() + _Myboff, _Newmap); // copy rest of old
            _Uninitialized_value_construct_n_unchecked1(_Myptr, _Count); // clear rest to initial block
        }

        _Destroy_range(_Map() + _Myboff, _Map() + _Mapsize());
        if (_Map() != _Mapptr()) {
            _Almap.deallocate(_Map(), _Mapsize()); // free storage for old
        }

        _Map() = _Newmap; // point at new
        _Mapsize() += _Count;
    }

 看看push_back，

template <class... _Tys>
    void _Emplace_back_internal(_Tys&&... _Vals) {
        if ((_Myoff() + _Mysize()) % _Block_size == 0/*(off在block的起始位置，意味着中间空着完整没被使用的block数量倍数，至少含有一个block) */&& _Mapsize() <= (_Mysize() + _Block_size) / _Block_size) {
            _Growmap(1);//同样是在初始时，以及快用完残余的最后一个block
        }
        _Myoff() &= _Mapsize() * _Block_size - 1;
        size_type _Newoff = _Myoff() + _Mysize();
        size_type _Block  = _Getblock(_Newoff);
        if (_Map()[_Block] == nullptr) {
            _Map()[_Block] = _Getal().allocate(_Block_size);
        }

        _Alty_traits::construct(
            _Getal(), _Unfancy(_Map()[_Block] + _Newoff % _Block_size), _STD forward<_Tys>(_Vals)...);

        ++_Mysize();
    }

 具体示意图如下：

 大致就是如上所述的过程，后面有空再看它的迭代器是什么样的机制，待续。。。

这篇关于MSVC2019的deque源码分析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！