先贴上源码的部分实现,如下,可以看到跟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(); }
具体示意图如下:
大致就是如上所述的过程,后面有空再看它的迭代器是什么样的机制,待续。。。