AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

STL源码分析--deque

2022-06-10 140
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： STL源码分析--deque



  • 1 deque相关头文件


  • 2 deque的数据结构


  • 3 deque的迭代器


  • 3.1 构造


  • 3.2 operator++


  • 3.3 operator--


  • 3.4 operator+=


  • 4 deque的扩缩策略


  • 4.1 push_front和push_back


  • 4.2 pop_front和pop_back


  • 4.3 insert


  • 4.4 erase


  • 5 deque的适用场景


  • 6 queue/stack/queue的关系



1 deque相关头文件

deque
deque.h
stl_deque.h



2 deque的数据结构

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


  1. 连续缓冲区_M_map, 元素类型为——Tp*。如果元素值不为NULL，则指向某个内存块；deque中使用__nstart(二级指针类型__Tp**)指向第一个内存块对应的数组元素;__nfinish指向最后一个内存块对应的数组元素


  1. 一系列定长(512 Byte)的内存块，又可称为节点(node)。

3b39fb482b656ad266c8d605f40e5800.png


代码如下，_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是对称操作，区别只在于方向不同。流程如下

dc500a7fd0f8acc79a60fabba04b3d99.png


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


  1. 头部/尾部node中是否有可用空间，如果是，则直接用于容纳新值，否则走2.


  1. deque map头部/尾部是否有可用空间，如果是，则创建新node容纳新值，否则走3.


  1. deque map中剩余空间是否超过一半，如果是，则右移/左移所有node, 给deque map头部/尾部腾出空间，然后走2.; 否则走4.


  1. 重新申请更大的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的复制。


  1. 对随机读写的支持较好，但是效率上不如vector, 因为索引到值的映射需要基于deque map进行计算。


  1. 对中间插入和删除不友好，因为可造成多次_Tp对象的copy操作。因为insert和erase使用了push(pop)_front(back)``, 因此极端条件下，也会出现1.`中的情况。




6 queue/stack/queue的关系

queue和stack中缺省底层数据结构是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_front和pop_back的deque, 而stack等效于隐藏了接口push_front和pop_front的deque。仅此而已，所以要研究queue和stack的实现，最关键的还是弄清楚deque



文章标签：
C++
容器
r3ya7mqz6iacc
目录
相关文章
r3ya7mqz6iacc
|
编译器 C++ 容器
STL源码分析--bitset
STL源码分析--bitset
r3ya7mqz6iacc
196 0
r3ya7mqz6iacc
|
安全 API C++
STL源码分析--vector
STL源码分析--vector
r3ya7mqz6iacc
192 0
STL源码分析--vector
r3ya7mqz6iacc
|
算法 C++
STL源码分析--hashtable
STL源码分析--hashtable
r3ya7mqz6iacc
213 0
STL源码分析--hashtable
r3ya7mqz6iacc
|
算法 C++
STL源码分析--rbtree
STL源码分析--rbtree
r3ya7mqz6iacc
358 0
陈童学哦
|
存储 C++ 容器
C++中deque的用法（超详细，入门必看）
⭐一、deque的简介 deque是一个双向队列（double-ended queue），可以在队列的两端进行元素的插入和删除操作。deque的全称是double-ended queue，翻译过来就是双端队列，也有人称之为双向队列，这两个名称都可以表示该数据结构。deque是C++STL（标准模板库）中的一种容器，可以用于存储各种类型的元素。deque的特点是可以在队列的两端进行元素的操作，并且可以高效地在队列的任意位置进行元素的插入和删除操作。 可以说deque几乎涵盖了queue（队列）、stack（堆栈）、vector（向量 ）等的全部用法，功能非常的强大。
陈童学哦
1053 0
龙盛国际
|
C++ 容器
STL之三：deque用法详解
龙盛国际
1676 0
r3ya7mqz6iacc
|
算法 C++ 容器
STL源码分析--list
STL源码分析--list
r3ya7mqz6iacc
146 0
yum9193-41641
|
算法 搜索推荐 C++
【C++ STL】 --- deque
【C++ STL】 --- deque
yum9193-41641
84 0
JKXQJ
|
容器
STL---deque
1 #include &lt;iostream&gt; 2 #include &lt;deque&gt; 3 using namespace std; 4 typedef deque&lt;int&gt; INTDEQUE; 5 //从前向后显示deque队列的全部元素 6 void put_deque(INTDEQUE deque, char *name) 7
JKXQJ
971 0
稻草人敲代码
|
9月前
|
编译器 C++ 容器
【STL】stack与queue的底层原理及其实现
【STL】stack与queue的底层原理及其实现
稻草人敲代码
89 0