更多精彩内容,请关注微信公众号:后端技术小屋

1 deque相关头文件

deque
deque.h
stl_deque.h

2 deque的数据结构

deque为双向队列,同时支持从队首和队尾插入和弹出值。其数据结构分为两部分,如下图所示:

  1. 连续缓冲区_M_map, 元素类型为——Tp*。如果元素值不为NULL,则指向某个内存块;deque中使用__nstart(二级指针类型__Tp**)指向第一个内存块对应的数组元素;__nfinish指向最后一个内存块对应的数组元素
  2. 一系列定长(512 Byte)的内存块,又可称为节点(node)。

deque的数据结构

代码如下,_Tp表示deque中元素类型,_Alloc为内存分配器类型。_M_map_size表示当前连续缓冲区_M_map的长度,即最多能容纳多少个node。迭代器_M_start指向deque的左确界,对应队首值。迭代器_M_finish指向deque的右虚界。

template <class _Tp, class _Alloc>
class _Deque_base {
  ...

protected:
  _Tp** _M_map;
  size_t _M_map_size;  
  iterator _M_start;
  iterator _M_finish;
  ...
}

3 deque的迭代器

deque的迭代器属于random_access_iterator, 支持随机访问
其中_M_cur指向当前内存块node中当前值的位置,_M_first指向当前内存块node的首地址,_M_last指向当前内存块的虚边界

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 _Tp** _Map_pointer;
  ... 
  
  _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) {}

3.1 构造

迭代器的构造函数中,传入queue中_M_map中元素地址__y,和指向内存块node中值的地址__x,初始化_M_cur, _M_first, _M_last_M_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 _Tp** _Map_pointer;
  ... 
  
  _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) {}

3.2 operator++

首先判断迭代器当前位置是否为node尾部,如果是,则跳转至右相邻node头部,否则_M_cur自增1

代码如下,其中_M_set_node重新指定iterator当前内存块为_M_node+1,重置_M_first_M_last

  _Self& operator++() {
    ++_M_cur;
    if (_M_cur == _M_last) {
      _M_set_node(_M_node + 1);
      _M_cur = _M_first;
    }
    return *this; 
  }  

  void _M_set_node(_Map_pointer __new_node) {
    _M_node = __new_node;
    _M_first = *__new_node;
    _M_last = _M_first + difference_type(_S_buffer_size());
  

3.3 operator–

首先判断迭代器当前位置是否在当前node头部,如果是,则跳转至左相邻node的头部,否则_M_curr自减1

  _Self& operator--() {
    if (_M_cur == _M_first) {
      _M_set_node(_M_node - 1);
      _M_cur = _M_last;
    }
    --_M_cur;
    return *this;
  }

3.4 operator+=

计算目标位置相对于本node头部的偏移量,判断:

  • 偏移量 < node大小,说明目标位置在本node内,_M_curr自增n
  • 偏移量 >= node大小,说明目标位置不在本node内,分别计算node偏移量和_M_curr偏移量,并更新iterator状态
  _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;
  }

4 deque的扩缩策略

4.1 push_front和push_back

pop_front在队列头部压入值, pop_back在队列尾部压入值。push_front和push_back是对称操作,区别只在于方向不同。流程如下

deque执行push_front或者push_back的过程

执行时分为以下几种情况:

  1. 头部/尾部node中是否有可用空间,如果是,则直接用于容纳新值,否则走2.
  2. deque map头部/尾部是否有可用空间,如果是,则创建新node容纳新值,否则走3.
  3. deque map中剩余空间是否超过一半,如果是,则右移/左移所有node, 给deque map头部/尾部腾出空间,然后走2.; 否则走4.
  4. 重新申请更大的deque map空间,复制旧map上的node到新map, 继续走2.
  
  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);
  }
  
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_back_aux()
{
  _M_reserve_map_at_back();
  *(_M_finish._M_node + 1) = _M_allocate_node();
  __STL_TRY {
    construct(_M_finish._M_cur);
    _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)));
}

4.2 pop_front和pop_back

pop_front在队列头部弹出值, pop_back在队列尾部弹出值。 分两种情况:

  • 更新_M_start或者_M_finish之后仍在原node内,析构对象即可。
  • 更新_M_start或者_M_finish之后不在原node内,不仅要析构对象,还要释放node
  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();
  }

// 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);

4.3 insert

分三种情况:

  • 插入位置在头部,等效于push_front
  • 插入位置在尾部,等效于push_back
  • 插入位置既非头部,又非尾部,判断插入位置在前半部分还是后半部分:
    • 前半部分: 执行push_front(front()), deque map前半部分左移,插入位置上构造对象。
    • 后半部分:执行push_back(back()), deque map后半部分右移,插入位置上构造对象
  iterator insert(iterator position, const value_type& __x) {
    if (position._M_cur == _M_start._M_cur) {
      push_front(__x);
      return _M_start;
    }
    else if (position._M_cur == _M_finish._M_cur) {
      push_back(__x);
      iterator __tmp = _M_finish;
      --__tmp;
      return __tmp;
    }
    else {
      return _M_insert_aux(position, __x);
    }
  }

4.4 erase

判断擦除位置pos在前半部分还是后半部分

  • 前半部分:pos之前部分右移,然后执行pop_front
  • 后半部分:pos之后部分左移,然后执行pop_back
  iterator erase(iterator __pos) {
    iterator __next = __pos;
    ++__next;
    difference_type __index = __pos - _M_start;
    if (size_type(__index) < (this->size() >> 1)) {
      copy_backward(_M_start, __pos, __next);
      pop_front();
    }
    else {
      copy(__next, _M_finish, __pos);
      pop_back();
    }
    return _M_start + __index;
  }

5 deque的适用场景

  1. 双端队列适合从两端增加和删除数据。不过在极端条件下,会产生节点申请和释放,以及deque map的复制。
  2. 对随机读写的支持较好,但是效率上不如vector, 因为索引到值的映射需要基于deque map进行计算。
  3. 对中间插入和删除不友好,因为可造成多次_Tp对象的copy操作。因为inserterase使用了push(pop)_front(back)``, 因此极端条件下,也会出现1.`中的情况。

6 queue/stack/queue的关系

queuestack中缺省底层数据结构是deque


template <class _Tp, 
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class queue;

template <class _Tp, 
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class stack;

当然你也可以自己实现支持front() back() push_front() pop_front() push_back() pop_back()等接口的_Sequence容器,不过建议还是用默认设置,除非能保证你实现的_Sequence在性能能够超过deque

queue等效于隐藏了接口push_frontpop_backdeque, 而stack等效于隐藏了接口push_frontpop_frontdeque。 仅此而已,所以要研究queuestack的实现,最关键的还是弄清楚deque

推荐阅读

更多精彩内容,请扫码关注微信公众号:后端技术小屋。如果觉得文章对你有帮助的话,请多多分享、转发、在看。
二维码