STL — deque – 绿虫虫

本文原创

deque 的存储结构为块索引表映射其在堆上动态分配的多个不连续块，每个块内连续存储对象，deque 类内包含一个指向起始位置元素的迭代器和一个指向末尾位置元素位置之后的迭代器，以及指向索引表起始位置的二维指针。

/* 如果存储元素单个 size 超过了512，则一块就存一个元素，否则对其取商作为一块存储元素的数目，
   每一块的实际大小取决于单个元素的 size，譬如 size 为 80，那么单个块的大小为 512/80*80 = 480 */
inline size_t __deque_buf_size(size_t __size)
{
  return __size < 512 ? size_t(512 / __size) : size_t(1);
}

template <class _Tp, class _Alloc>
class _Deque_base
{
public:
  typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
  typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;

  typedef _Alloc allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }
  /* 定义 deque<T> 对象时调用的都是该构造函数 */
  _Deque_base(const allocator_type&, size_t __num_elements)
    : _M_map(0), _M_map_size(0),  _M_start(), _M_finish()
  {
    _M_initialize_map(__num_elements);
  }
  _Deque_base(const allocator_type&) : _M_map(0), _M_map_size(0),  _M_start(), _M_finish() {}
  ~_Deque_base();    

protected:
  void _M_initialize_map(size_t);
  void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
  void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
  enum { _S_initial_map_size = 8 }; // 索引表的初始结点数目

protected:
  _Tp** _M_map;       // 索引表的起始位置
  size_t _M_map_size; // 索引表的结点数目，也就是块的数目
  iterator _M_start;
  iterator _M_finish;

  typedef simple_alloc<_Tp, _Alloc>  _Node_alloc_type;
  typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type; // 索引表存储的都是指针

  _Tp* _M_allocate_node() { return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }
  void _M_deallocate_node(_Tp* __p) { _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
  _Tp** _M_allocate_map(size_t __n) { return _Map_alloc_type::allocate(__n); }
  void _M_deallocate_map(_Tp** __p, size_t __n) { _Map_alloc_type::deallocate(__p, __n); }
};

template <class _Tp, class _Alloc>
_Deque_base<_Tp,_Alloc>::~_Deque_base()
{
    if (_M_map)
    {
        _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1); // 区间前闭后开，所以+1
        _M_deallocate_map(_M_map, _M_map_size); // 释放索引表
    }
}

template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
  /* 得到需要分配的块数，+1是因为最后一块可能是不满的，应当向上取整 */
  size_t __num_nodes = __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
  /* 设置一个 _S_initial_map_size 的目的是提高效率，很多情况下索引表后续不用再扩展 */
  _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
  _M_map = _M_allocate_map(_M_map_size); // 分配索引表的内存空间
  /* 当 _M_map_size == _S_initial_map_size 时，[__nstart, __nfinish) 为索引表中间那一段；
     当 _M_map_size == __num_nodes + 2 时，__nstart = _M_map + 1 */
  _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
  _Tp** __nfinish = __nstart + __num_nodes;
    
  __STL_TRY {
    _M_create_nodes(__nstart, __nfinish); // 分配 [__nstart, __nfinish) 区间内块的内存
  }
  __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size), _M_map = 0, _M_map_size = 0));
  _M_start._M_set_node(__nstart);       // 设置起始迭代器所在块
  _M_finish._M_set_node(__nfinish - 1); // 设置末尾迭代器所在块，因为区间是后开的，需要-1
  _M_start._M_cur = _M_start._M_first;  // 设置起始迭代器游标
  _M_finish._M_cur = _M_finish._M_first + __num_elements % __deque_buf_size(sizeof(_Tp)); // 设置末尾迭代器游标，取余是因为中间可能跨越很多块
}

template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
{
    _Tp** __cur;
    __STL_TRY {
        for (__cur = __nstart; __cur < __nfinish; ++__cur)
            *__cur = _M_allocate_node(); // 分配单个块的内存空间
   }
    __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
}

template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
{
    for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
        _M_deallocate_node(*__n); // 释放单个块的内存空间
}

由于 deque 的存储结构在快间是不连续的，迭代器就需要具备在块间跳跃的能力，迭代器中 _M_cur 指向的是当前指向元素的起始地址，以下省略了一些无关紧要的成员函数：

/* Class invariants:
 *  For any nonsingular iterator i:
 *    i.node is the address of an element in the map array.  The
 *      contents of i.node is a pointer to the beginning of a node.
 *    i.first == *(i.node) 
 *    i.last  == i.first + node_size
 *    i.cur is a pointer in the range [i.first, i.last).  NOTE:
 *      the implication of this is that i.cur is always a dereferenceable
 *      pointer, even if i is a past-the-end iterator.
 *  Start and Finish are always nonsingular iterators.  NOTE: this means
 *    that an empty deque must have one node, and that a deque
 *    with N elements, where N is the buffer size, must have two nodes.
 *  For every node other than start.node and finish.node, every element
 *    in the node is an initialized object.  If start.node == finish.node,
 *    then [start.cur, finish.cur) are initialized objects, and
 *    the elements outside that range are uninitialized storage.  Otherwise,
 *    [start.cur, start.last) and [finish.first, finish.cur) are initialized
 *    objects, and [start.first, start.cur) and [finish.cur, finish.last)
 *    are uninitialized storage.
 *  [map, map + map_size) is a valid, non-empty range.  
 *  [start.node, finish.node] is a valid range contained within [map, map + map_size).  
 *  A pointer in the range [map, map + map_size) points to an allocated node
 *    if and only if the pointer is in the range [start.node, finish.node].
 */
template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator
{
  typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
  typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }

  typedef random_access_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Ptr pointer;
  typedef _Ref reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef _Tp** _Map_pointer;

  typedef _Deque_iterator _Self;

  _Tp* _M_cur;
  _Tp* _M_first;
  _Tp* _M_last;
  _Map_pointer _M_node;

  _Deque_iterator(_Tp* __x, _Map_pointer __y) : _M_cur(__x), _M_first(*__y), _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
  _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
  _Deque_iterator(const iterator& __x) : _M_cur(__x._M_cur), _M_first(__x._M_first), _M_last(__x._M_last), _M_node(__x._M_node) {}

  reference operator*() const { return *_M_cur; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return _M_cur; }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  void _M_set_node(_Map_pointer __new_node)
  {
    _M_node = __new_node;   // 跳到下一个块
    _M_first = *__new_node; // 更改 first 指针至该块起始位置
    _M_last = _M_first + difference_type(_S_buffer_size()); // 更改 last 指针至该块末尾位置
  }

  difference_type operator-(const _Self& __x) const
  {
    return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
      (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
  }

  _Self& operator++()
  {
    ++_M_cur; // 先加上游标所指的位置
    if (_M_cur == _M_last) // 下一个元素在下一个块当中
    {
      _M_set_node(_M_node + 1); // 迭代器跳到下一个块
      _M_cur = _M_first; // 游标设置为该块的起始位置
    }
    return *this; 
  }
  _Self operator++(int)
  {
    _Self __tmp = *this;
    ++*this; // 调用前缀形式，operator--(int) 也是一样调用前缀形式的 operator--()
    return __tmp;
  }

  _Self& operator--()
  {
    if (_M_cur == _M_first) // 前一个元素在上一块当中
    {
      _M_set_node(_M_node - 1); // 迭代器跳到上一个块
      _M_cur = _M_last; // 游标设置为该块末尾位置
    }
    --_M_cur; // 再减去游标的位置，从而指向前一个元素的起始位置
    return *this;
  }

  _Self& operator+=(difference_type __n)
  {
    difference_type __offset = __n + (_M_cur - _M_first); // 得到从该块起始位置需要跳几个元素
    if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) // 还在该块内，直接往后移动游标即可
      _M_cur += __n;
    else
    {
      /* 先得到需要跳多少个块，区分往后跳和往前跳的情况 */
      difference_type __node_offset = __offset > 0 ? __offset / difference_type(_S_buffer_size())
                                        : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
      _M_set_node(_M_node + __node_offset); // 跳到需要跳到位置所在的块
      _M_cur = _M_first + (__offset - __node_offset * difference_type(_S_buffer_size())); // 更新游标位置到目的元素起始位置
    }
    return *this;
  }

  _Self operator+(difference_type __n) const
  {
    _Self __tmp = *this;
    return __tmp += __n;
  }

  _Self& operator-=(difference_type __n) { return *this += -__n; }
  /* 需要间接调用 operator+=(difference_type __n)，因此对 deque 进行随机访问操作一定是比 vector 费时的 */
  reference operator[](difference_type __n) const { return *(*this + __n); }

  bool operator<(const _Self& __x) const
  {
    return (_M_node == __x._M_node) ? (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
  }
};

/* 解决加法运算符的交换律问题，因为该迭代器类未使用友元函数 */
template <class _Tp, class _Ref, class _Ptr>
inline _Deque_iterator<_Tp, _Ref, _Ptr>
operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
{
  return __x + __n;
}

上述迭代器的 operator++() 和 operator–() 可以参考下图，黑色是进行 operator++() 之前的指针，红色是之后的指针，该图中一个元素的 size 为 80 字节：

了解清楚迭代器的设计后，deque 类所做的不过是一些调用操作，相对比较简单：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc>
{
  typedef _Deque_base<_Tp, _Alloc> _Base;

public:                         // Basic types
  typedef _Tp value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

  typedef typename _Base::allocator_type allocator_type;
  allocator_type get_allocator() const { return _Base::get_allocator(); }

public:                         // Iterators
  typedef typename _Base::iterator       iterator;
  typedef typename _Base::const_iterator const_iterator;
  typedef reverse_iterator<iterator> reverse_iterator;
  typedef reverse_iterator<const_iterator> const_reverse_iterator;
protected:                      // Internal typedefs
  typedef pointer* _Map_pointer;
  static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }

protected:
#ifdef __STL_USE_NAMESPACES
  using _Base::_M_initialize_map;
  using _Base::_M_create_nodes;
  using _Base::_M_destroy_nodes;
  using _Base::_M_allocate_node;
  using _Base::_M_deallocate_node;
  using _Base::_M_allocate_map;
  using _Base::_M_deallocate_map;

  using _Base::_M_map;
  using _Base::_M_map_size;
  using _Base::_M_start;
  using _Base::_M_finish;
#endif /* __STL_USE_NAMESPACES */

public:                         // Basic accessors
  iterator begin() { return _M_start; }
  iterator end() { return _M_finish; }
  const_iterator begin() const { return _M_start; }
  const_iterator end() const { return _M_finish; }

  reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
  reverse_iterator rend() { return reverse_iterator(_M_start); }
  const_reverse_iterator rbegin() const { return const_reverse_iterator(_M_finish); }
  const_reverse_iterator rend() const { return const_reverse_iterator(_M_start); }

  reference operator[](size_type __n) { return _M_start[difference_type(__n)]; }
  const_reference operator[](size_type __n) const { return _M_start[difference_type(__n)]; }

#ifdef __STL_THROW_RANGE_ERRORS
  void _M_range_check(size_type __n) const
  {
    if (__n >= this->size())
      __stl_throw_range_error("deque");
  }

  reference at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
  const_reference at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; }
#endif /* __STL_THROW_RANGE_ERRORS */

  reference front() { return *_M_start; }
  reference back()
  {
    iterator __tmp = _M_finish;
    --__tmp;
    return *__tmp;
  }

  size_type size() const { return _M_finish - _M_start; } // 迭代器的 operator-()
  size_type max_size() const { return size_type(-1); }
  bool empty() const { return _M_finish == _M_start; } // 迭代器的 operator==()

public:                         // Constructor, destructor.
  explicit deque(const allocator_type& __a = allocator_type()) : _Base(__a, 0) {}
  deque(const deque& __x) : _Base(__x.get_allocator(), __x.size()) 
  { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
  deque(size_type __n, const value_type& __value,
        const allocator_type& __a = allocator_type()) : _Base(__a, __n)
  { _M_fill_initialize(__value); }
  explicit deque(size_type __n) : _Base(allocator_type(), __n)
  { _M_fill_initialize(value_type()); }
  deque(const value_type* __first, const value_type* __last,
        const allocator_type& __a = allocator_type()) : _Base(__a, __last - __first)
  { uninitialized_copy(__first, __last, _M_start); }
  deque(const_iterator __first, const_iterator __last,
        const allocator_type& __a = allocator_type()) : _Base(__a, __last - __first)
  { uninitialized_copy(__first, __last, _M_start); }

  ~deque() { destroy(_M_start, _M_finish); } // 析构存储元素对象

  void swap(deque& __x) // 调换指针和迭代器，几乎无开销
  {
    __STD::swap(_M_start, __x._M_start);
    __STD::swap(_M_finish, __x._M_finish);
    __STD::swap(_M_map, __x._M_map);
    __STD::swap(_M_map_size, __x._M_map_size);
  }

public: 
  void _M_fill_assign(size_type __n, const _Tp& __val)
  {
    if (__n > size())
    {
      fill(begin(), end(), __val);
      insert(end(), __n - size(), __val);
    }
    else
    {
      erase(begin() + __n, end());
      fill(begin(), end(), __val);
    }
  }
  void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }

public:                         // push_* and pop_*
  void push_back(const value_type& __t)
  {
    if (_M_finish._M_cur != _M_finish._M_last - 1) // 块内末尾处还剩余有位置
    {
      construct(_M_finish._M_cur, __t); // 调用存储元素的构造函数
      ++_M_finish._M_cur; // 游标直接移动就可以了
    }
    else
      _M_push_back_aux(__t);
  }

  void push_front(const value_type& __t)
  {
    if (_M_start._M_cur != _M_start._M_first) // 块内起始处还剩余有位置
    {
      construct(_M_start._M_cur - 1, __t); // 调用存储元素的构造函数
      --_M_start._M_cur; // 游标直接移动就可以了
    }
    else
      _M_push_front_aux(__t);
  }

  void pop_back()
  {
    if (_M_finish._M_cur != _M_finish._M_first) // 该块起始位置处有元素
    {
      --_M_finish._M_cur;
      destroy(_M_finish._M_cur);
    }
    else
      _M_pop_back_aux();
  }

  void pop_front()
  {
    if (_M_start._M_cur != _M_start._M_last - 1) // 该块末尾位置处有一个元素以上
    {
      destroy(_M_start._M_cur);
      ++_M_start._M_cur;
    }
    else 
      _M_pop_front_aux();
  }

protected:                        // Internal push_* and pop_*
  void _M_push_back_aux(const value_type&);
  void _M_push_front_aux(const value_type&);
  void _M_pop_back_aux();
  void _M_pop_front_aux();

protected:                      // Allocation of _M_map and nodes
  // Makes sure the _M_map has space for new nodes.  Does not actually
  //  add the nodes.  Can invalidate _M_map pointers.  (And consequently, 
  //  deque iterators.)

  void _M_reserve_map_at_back(size_type __nodes_to_add = 1)
  {
    if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
      _M_reallocate_map(__nodes_to_add, false);
  }

  void _M_reserve_map_at_front(size_type __nodes_to_add = 1)
  {
    if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
      _M_reallocate_map(__nodes_to_add, true);
  }

  void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
};

template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
{
  size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
  size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;

  _Map_pointer __new_nstart;
  if (_M_map_size > 2 * __new_num_nodes)
  {
    __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);
    if (__new_nstart < _M_start._M_node)
      copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
    else
      copy_backward(_M_start._M_node, _M_finish._M_node + 1, __new_nstart + __old_num_nodes);
  }
  else
  {
    size_type __new_map_size = _M_map_size + max(_M_map_size, __nodes_to_add) + 2;

    _Map_pointer __new_map = _M_allocate_map(__new_map_size);
    __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);
    copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
    _M_deallocate_map(_M_map, _M_map_size);
    _M_map = __new_map;
    _M_map_size = __new_map_size;
  }

  _M_start._M_set_node(__new_nstart);
  _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}

// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
{
  value_type __t_copy = __t;
  _M_reserve_map_at_back();
  *(_M_finish._M_node + 1) = _M_allocate_node();  // 当前最后一块后新开辟一块
  __STL_TRY {
    construct(_M_finish._M_cur, __t_copy);
    _M_finish._M_set_node(_M_finish._M_node + 1); // 跳到刚刚新开辟出来的块
    _M_finish._M_cur = _M_finish._M_first;        // 游标就是该块的起始位置
  }
  __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
}

// Called only if _M_start._M_cur == _M_start._M_first.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
{
  value_type __t_copy = __t;
  _M_reserve_map_at_front();
  *(_M_start._M_node - 1) = _M_allocate_node(); // 当前最前一块前新开辟一块
  __STL_TRY {
    _M_start._M_set_node(_M_start._M_node - 1); // 跳到刚刚新开辟出来的块
    _M_start._M_cur = _M_start._M_last - 1;     // 游标就是块的末尾位置往前一个元素的大小
    construct(_M_start._M_cur, __t_copy);
  }
  __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
}

// Called only if _M_finish._M_cur == _M_finish._M_first.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_back_aux()
{
  _M_deallocate_node(_M_finish._M_first); // 块中已经没有元素了，释放内存
  _M_finish._M_set_node(_M_finish._M_node - 1);
  _M_finish._M_cur = _M_finish._M_last - 1;
  destroy(_M_finish._M_cur);
}

// Called only if _M_start._M_cur == _M_start._M_last - 1.  Note that 
// if the deque has at least one element (a precondition for this member 
// function), and if _M_start._M_cur == _M_start._M_last, then the deque 
// must have at least two nodes.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_front_aux()
{
  destroy(_M_start._M_cur);
  _M_deallocate_node(_M_start._M_first); // 块中已经没有元素了，释放内存
  _M_start._M_set_node(_M_start._M_node + 1);
  _M_start._M_cur = _M_start._M_first;
}

上述 _M_pop_back_aux() 和 _M_pop_front_aux() 不同，_M_pop_back_aux() 释放的元素的末尾位置是迭代器所指位置，因为此时块中已经没有元素，所以先释放块的内存，随后析构前一块中的最后一个元素；_M_pop_front_aux() 释放的元素的起始位置是迭代器所指位置，因此先析构该块中最后一个元素，然后该块就没有元素了，可以释放掉内存。

Leave a comment 取消回复