基于STL源码分析deque容器整体实现及内存结构

//这里_Tp是模板类型
#if __cplusplus < 201103L
      typedef _Deque_iterator<_Tp, _Tp&, _Tp*>         iterator;
      typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
      typedef _Tp*                     _Elt_pointer;
      typedef _Tp**                    _Map_pointer;
#else
    private:
      template<typename _Up>
    using __ptr_to = typename pointer_traits<_Ptr>::template rebind<_Up>;
      template<typename _CvTp>
    using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_to<_CvTp>>;
    public:
      typedef __iter<_Tp>        iterator;
      typedef __iter<const _Tp>        const_iterator;
      typedef __ptr_to<_Tp>        _Elt_pointer;
      typedef __ptr_to<_Elt_pointer>    _Map_pointer;
#endif

//构造一个大小为n的deque容器，容器中所有元素的值为value，__a是默认分配器
deque(size_type __n, const value_type& __value, const allocator_type& __a = allocator_type())
      : _Base(__a, __n)
      { _M_fill_initialize(__value); }

//deque容器初始化元素个数
template<typename _Tp, typename _Alloc>
    void _Deque_base<_Tp, _Alloc>::_M_initialize_map(size_t __num_elements)
    {
     //如果sizeof(_Tp)<512，那么__deque_buf_size返回512/sizeof(_Tp)，否则返回1，_Tp是容器的元素类型，所以这里返回的是一个默认块内存的元素数量，也就是一个buffer里面包含的元素个数，后续以buffer代指一块内存
     //__num_nodes = 元素个数/块内存元素数量 + 1，得到的是总共有多少个buffer，为什么要加1，防止有余数，所以需要加1
      const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
                  + 1);
     //_S_initial_map_size默认为8，根据max调用得到最终的块内存个数
      this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
                       size_t(__num_nodes + 2));
     //这里根据buffer类型和buffer个数申请动态内存，说白了这里申请节点的动态内存，并没有申请真正保存元素的块内存的动态空间
      this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
     //根据以下两行可知，_M_map的第一个和最后一个节点其实是保留的，暂时不会使用
      _Map_pointer __nstart = (this->_M_impl._M_map
                   + (this->_M_impl._M_map_size - __num_nodes) / 2);
      _Map_pointer __nfinish = __nstart + __num_nodes;
      __try
    { 
        //该函数根据节点循环对每一块buffer申请动态空间，一个节点指向一个buffer
          _M_create_nodes(__nstart, __nfinish); }
      __catch(...)
    {
      _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
      this->_M_impl._M_map = _Map_pointer();
      this->_M_impl._M_map_size = 0;
      __throw_exception_again;
    }
    //_M_set_node对节点所对应的位置和迭代器位置进行初始化，并使用成员变量保存节点开始和结束位置
      this->_M_impl._M_start._M_set_node(__nstart);
      this->_M_impl._M_finish._M_set_node(__nfinish - 1);
      this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
      this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
                    + __num_elements
                    % __deque_buf_size(sizeof(_Tp)));
    }

template <typename _Tp, typename _Alloc>
    void
    deque<_Tp, _Alloc>::
    _M_fill_initialize(const value_type& __value)
    {
      _Map_pointer __cur;
      __try
        {
          //循环填充容器每一个元素的值为__value
          for (__cur = this->_M_impl._M_start._M_node;
           __cur < this->_M_impl._M_finish._M_node;
           ++__cur)
           //__uninitialized_fill_a函数会根据值对每一个元素进行构造，它其实相当于一个placement new的作用
            std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
                    __value, _M_get_Tp_allocator());
          std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
                      this->_M_impl._M_finish._M_cur,
                      __value, _M_get_Tp_allocator());
        }
      __catch(...)
        {
          std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
            _M_get_Tp_allocator());
          __throw_exception_again;
        }
    }

#include <deque>

int main()
{
    std::deque<int> deq(1024, 100);
    return 0;
}