deuqe STL容器深入解析------/deque简述/deque源码简单剖析/deque的数据结构/deque的应用

前言:deque （double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。而在STL中，deque的实现尤为精妙。而理解deque容器，对理解STL、提高C++技术有重要意义
而本文将详细介绍STL的deque容器

目录：

1、deque简述2、deque成员函数一览3、deque源码简单剖析

1）deque容器与vector容器的差异2）deque到底是不是连续的3）deque中配器4）再看看deque的迭代器 4、deque的数据结构5、deque的后插、后删、前插、前删的实现6、deque的应用

1）STL 栈的实现2）STL 队列的实现3）STL stack、queue是容器吗 7、后记

1)参考资料

1、deque简述

简单定义：deque双端队列，具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩，是兼具栈（stack）和队列(queue)性质的序列式容器。
生活中的deque:双端队列在现实生活中的例子：一个刚买了票的人如果只是还需要再问一些简单的信息，就可以直接回到队伍的头部。另外，在队伍末尾的人如果赶时间，他可以直接离开队伍。通过双端队列，对相应的问题可以做到较好的模拟.

——（图片取自网络）

2、deque成员函数一览

——（图表取自C语言中文网）

3、deque源码简单剖析 1）deque容器与vector容器的差异

在初学STL时，我们常常有一种自然的错觉：deque容器只是前端多开一个口的vector容器而当我们深入学习STL，从源码层面剖析时，我们会发现许多惊奇的差异
而最主要的两点差异在

deque允许 以常数时间O(1) 内对起头端进行元素的插入和移除操作,而 vector头部操作效果奇差————这是最显而易见的不同。deque没有所谓容量（capacity）的观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。

关于这第二点，其实从上面的"deque成员函数一览",就初见端倪
熟悉vector容器的朋友很容易发现：
vector容器关于容量操作的函数几乎没在deque中出现
像vector的：
resize() 改变实际元素的个数。
capacity() 返回当前容量。
reserve() 增加容器的容量。
都没有在deque容器的成员函数里出现

也正因此，deque没有所谓空间保留的
（reserve）函数！！！

---

第一点倒是好理解，但过于第二点，能再解释一下吗？
——要搞清第二点，我们必须要搞清deque的数据结构。


---

---

2）deque到底是不是连续的

在逻辑上、在实际操作中，deque都可以被视为连续空间。而由此可以类比 同样为线性连续空间的array/vector

array不可成长，固定大小，支持快速随机访问，不能添加/删除元素。vector只能向尾端延伸，一但vector容器空间已满，它将 1】开辟新的空间（这个空间大小常常是原来空间的两倍左右）2】将原来的数据拷贝到新空间中 3】释放原有空间。

关于deque容器，它是如何实现增长的呢？

实际上：deque容器由一段一段的定量连续空间（缓冲区）构成。一旦有必要在deque前端或后端增加新空间，便配置一段定量连续空间，串联在整个deque的头端或尾端deque最大的任务，就是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口，避开了vector“重新配置，拷贝，删除”的轮回，但代价则是复杂的迭代器架构和新增中配器的维护。

所以，严格意义上来说，deque容器不是连续的，它是由一段段连续空间串联起来的。不能把deque/vector混为一谈。
也这是这个原因，直接对deque STL sort排序往往十分低效。为提高效率，我们一般讲deque先完整复制一个vector容器身上，将vector用（STL sort 算法）排序后，再拷贝回deque容器
中配器

3）deque中配器

从上文，我们可以知道deque容器由一段一段的定量连续空间（缓冲区) 构成。
这一片片缓冲区才是deque存储元素的真正位置。而这些缓冲区是零散的，要管理好它们，就必须需要一个中央控制，这也就是我们所说的中配器

deque采用一块所谓的map（注意，不是STL的map容器，这里可以简单地理解为它是帮助程序找到各个缓冲区的地图）作为主控，这里所谓的map是一小块的连续空间，其中的每个元素（此处称为一个节点，node）都是指针，指向缓冲区。

要深入理解map，先看看map的源码

template //SGI STL允许我们指定缓冲区大小，默认值0将使用512 bytes缓冲区
class deque{
public:                        //基本类型
    typedef T value_type;
    typedef T value_type* pointer;
    ...
protected:                   //Internal typedefs
    //元素的指针的指针(pointer of pointer of T)
    typedef pointer* map_pointer;
protected:   //数据成员
    map_pointer map;//指向map,map是块连续空间，指向一块缓冲区。
    size_type map_size;  //map内可容纳多少指针
}

通过这 中配器 的源码 我们可以发现，map其实是个T** 的指针，所指之物又是一个指针，指向型别为T的一块空间。

4）再看看deque的迭代器

deque是分段连续空间，维持其“整体连续”假象的任务，就落在了迭代器operater++和operator–两个运算符身上。
deque的迭代器要求：

要能指出缓冲区在哪要能判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退就必须调到下一个或上一个缓冲区。

template 
struct _deque_iterator{//未继承std::iterator
    typedef _deque_iterator iterator;
    typedef _deque_iteratorconst_iterator;
    static size_t buffer_size(){return _deque_buf_size(BufSiz,sizeof(T));}
    //未继承标准库的iterator类，所以必须自行撰写五个必要的迭代器相应型别
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;   //（5）
    
    typedef T** map_pointer;
    typedef _deque_iterator self;
    //保持与容器的联结，维护下列指针
    T* cur;         //此迭代器指向缓冲区中的现行(current)元素
    T* first;       //此迭代器指向缓冲区的头
    T* last;        //此迭代器指向缓冲区的尾部
    map_pointer node;//指向管控中心 
    ...
}

inline size_t _deque_buf_size(size_t n,size_t sz){
return n!=0?n:(sz<512?size_t(512/sz):size_t(1));
}//如果n!=0,传回n,表示buffer size由用户自定义
//否则，表示buffer size 将使用默认值

这是deque容器的迭代器
竟具备了如此复杂的结构。对STL初学者来说，常常被告知：迭代器就可以当指针来用。而想成为C++大师，深入研究STL源码的话，只是会把迭代器当指针用是远远不够的。

类比下vector的迭代器

template
class vector{
      typedef T value_type;
      typedef value_type* iterator;//vector的迭代器就是普通指针
}

deque实现的代码分量远远比vector或list复杂得多

---

---

---

4、deque的数据结构

deque除了维护一个指向map的指针（map_pointer map，见中配器源码）外，还维护start、finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素（的下一个元素）。此外，它还必须记住目前的map大小，一旦map所提供的节点不足，就必须配置更大的一块map。

deque的元素储存在缓冲区中，由中控器指向各个缓冲区，其中中配器由（map_pointer map指向)
start、finish两个迭代器将它们完美地形成统一整体

这一部分的相关源码如下：

template 
class deque{
public:          //基础类型
     typedef T value_type;
     typedef value_type* pointer;
     typedef size_t  size_type;
public:
     typedef _deque_iteratoriterator;//迭代器
protected:
     //元素的指针的指针(pointer of pointer of T)
     typedef pointer* map_pointer;
protected:     //数据成员
     iterator start;  //表现第一个节点
     iterator finish;  //表现最后一个节点
     map_pointer map;//指向map,map是块连续空间（注意这里的重名，不要混淆),其每个元素都是个指针，指向一段缓冲区
     size_type map_size;//map内有多少指针

public:
   iterator begin(){return start;}
   iterator end(){return finish;}
   reference operator[](size_type n){
      return start[difference_type(n)]//调用_deque_iterator<>::operator[]
   }
   reference front(){return *start;}//调用_deque_iterator<>::operator*
   reference back(){
      iterator tmp=finish;
      --tmp;//调用_deque_iterator<>::operator--
      return *tmp;//调用_deque_iterator<>::operator*
      }//为什么不改成return *(finish-1)----因为_deque_iterator<>没有为(finish-1)定义运算子
      
   size_type size()cosnt {return finish-start;;}//两个；,但仍符合语法
               //调用iterator::operator-
  size_type max_size()const {return size_type(-1);}
  bool empty()const{return finish==start;}

5、deque的后插、后删、前插、前删的实现

public:                        //push_* and pop_*
  void push_back(const value_type& t){
     if(finish.cur!=finish.last-1){
         //最后缓冲区尚有两个或两个以上元素以上的备用空间
         construct(finish.cur,t);//直接在备用空间上构造函数
         ++finsh.cur;
     }else{//最后缓冲区只剩一个元素的备用空间
         push_back_aux(t);
     }
  }

//只有当finish.cur==finish.last-1时才会被调用
//也就是说，只有当最后一个缓冲区只剩一个备用元素空间时才会被调用
template 
void deque::push_back_aux(const values_type& t){
    value_type t_copy=t;
    reverse_map_at_back();//若符合条件，必须更换一个map
    *(finsh.node+1)=allocate_node();//配置一个新节点(缓冲区)
    _STL_TRY{
        construct(finish.cur,t_copy);//针对标的元素设值
        finish.set_node(finsh.node+1);//改变finish,令其指向新节点
        finish.cur=finish.first;//设定finish的状态
    }
    _STL_UNWIND(deallocate_node(*(finish.node+1)))；
}

finish迭代器移到新的缓冲区，cur、first指向此缓冲区的头部,last指向此缓冲区的尾部，node所指的位置后移动一格。实现push_back操作

---

---

---

6、deque的应用

deque虽然看起来高级，可以当vector用，可以当stack用，可以当queue用……
但其实我们平时做题目很少用到deque双端队列
虽然我们没怎么用，但STL还是利用了的，而且效果非一般重要

1）STL 栈的实现

2）STL 队列的实现

3）STL stack、queue是容器吗

这里就要复习一下：
配接器(adapters):一种用来修饰容器(containers)或仿函数（functors）或迭代器（iterator）的东西。
例如，STL所提供的queue、stack，虽然看起来像容器，实际上它们都只能算一种容器配接器。
因为它们的底部完全借助deque，所有的操作都由底层的deque供应
当然，用list实现stack/queue也是常见的，这就涉及到线性表线性描述和链式描述的区别
STL/queue 可以理解为类似容器，但不能和vector/deque/list之类的容器等同

7、后记 1)参考资料

书籍：《STL源码剖析》候捷 著
网站参考：C语言中文网](http://c.biancheng.net/view/6860.html)