STL deque容器

一、deque概述

deque在使用层面上，可以看成是vector的进化版，因为vector在头部插入，其实是将所有元素后移，然后空出一个头部位置插入的。而deque则是直接在头部插入的。所以的确在使用层面可以看成是如下连续的结构。

但是在源码层面，deque实现方法要比vector复杂很多，所以书上有这样一段话：

注意：其实deque的sort也是使用STL的sort算法，只是deque在移位时非常麻烦，所以最好先复制到vector中再sort。

二、deque数据结构

首先看一下deque的内存结构设计图：

其实deque并不是连续的，而是一段段的缓冲区，然后依靠map指针数组连起来的，这样在使用过程中给人一种连续的错觉。真正的数据放在缓冲区中，每一个缓冲区的大小确定源码如下：

  _Tp* _M_allocate_node()//分配一个缓冲区，返回该缓冲区首地址，这个缓冲区的大小是缓冲区512字节下，能够容纳的最大数量*sizeof(_Tp)
  //如果一个sizeof(_Tp)大于512，那一个缓冲区的大小就是sizeof(_Tp)
    { return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }
    //allocate会分配sizeof(_Tp)*__deque_buf_size(sizeof(_Tp))大小的内存给缓冲区，其实缓冲区大小如下：
    //如果sizeof(_Tp)小于512，那么一个缓冲区的大小就是512/__size*__size,
	//如果sizeof(_Tp)大于512，那么一个缓冲区的大小就是__size*1
	//也就是sizeof(_Tp)的整数倍

inline size_t __deque_buf_size(size_t __size) {//这个函数返回的是一个缓冲区可以容纳多少个__size大小的对象
//如果size小于512，那么一个缓冲区可以容纳512 / __size个对象
//如果大于512，那么一个缓冲区只能容纳一个对象
  return __size < 512 ? size_t(512 / __size) : size_t(1);
}

这种存储结构，具体的类成员变量如下：

  _Tp** _M_map; //指向一个Map数组，注意这是一个_Tp**类型
  size_t _M_map_size;  //Map的大小，也就是有多少个缓冲区
  iterator _M_start;  //指向deque所有元素中的第一个元素（即第一个缓冲区的第一个元素）
  iterator _M_finish; //指向deque所有元素中的最后一个元素的后面一个空间（即最后一个缓冲区的最后一个元素的下一位置）

其中_M_map是_Tp**类型，似乎map中每一个节点都指向一个_Tp对象而不是一个缓冲区，但因为缓冲区的大小以及sizeof(_Tp)大小都是固定的，所以只需要知道缓冲区的首地址就可以得到整个缓冲区中的任意一个数据。

三、deque的迭代器

①deque的迭代器属于Random access iterator迭代器。
②迭代器中存储的数据如下：

	_Tp* _M_cur;  //此迭代器所指缓冲区中的元素
	_Tp* _M_first;//此迭代器所指缓冲区的首地址
	_Tp* _M_last;//此迭代器所指缓冲区的最后一个元素的地址（含备用空间）
	_Map_pointer _M_node;//指向Map中的元素，即指向当前缓冲区的地址

用此图来展示：

③所以这时回到上面deque数据结构中，deque类成员变量中，就有两个迭代器，现在来看看这两个迭代器中的具体含义：

注意：不是所有的map中的节点都指向一个缓冲区的，只有在需要使用的时候才会在对应节点建立缓冲区。
④迭代器中的运算符
由于这样的结构，所以在++，–或者-运算符都需要加上一层判断，以前置++运算符为例：

_Self& operator++() {//如果当前元素为当前缓冲区中倒数第二个元素，那么再++就需要跳向下一个缓冲区了
    ++_M_cur;
    if (_M_cur == _M_last) {//如果下一个元素为当前缓冲区最后一个元素的末尾
      _M_set_node(_M_node + 1);//让first、last指向下一个缓冲区的首尾元素，_M_node指向下一个缓冲区
      _M_cur = _M_first;
    }
    return *this; 
  }

四、deque的关键算法

①deque封装了两个内存配置函数，源码如下：

_Tp* _M_allocate_node()//创建一个缓冲区大小的内存空间
    { return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }
_Tp** _M_allocate_map(size_t __n) //为map分配__n个指针空间
    { return _Map_alloc_type::allocate(__n); }

②在初始化创建节点时，map指针数组中至少会创建八个节点，但是并不是每个节点都是指向一块缓冲区的，map指针数组最多会创建所需缓冲区数+2个节点，多两个节点是为了提供一前一各预留一个，以便扩充。
并且有用的缓冲区会被放在map数组的*，给前后都预留差不多的空间。如上图所示，指向缓冲区的指针都在map数组中间。
③在erase函数中，当清除一个元素以后，比较该元素前后元素数量，数量少的就整体移动填充被删除的那个元素
④insert函数中还是比较插入点前后元素数量，移动数量比较少的那一方腾出空间来插入该元素。

五、指针相减

在deque源码中看到有指针的相减运算，虽然能猜到就是计算这两个指针之间差了多少个指针类型对象，但是不敢肯定，所以写个测试用例验证一下：

#include <iostream>                // std::cout
using namespace std;
int main()
{
	int c[] = { 12, 13, 14, 15 };
	int *b = &c[2];
	int *a = &c[0];
	cout << &a << endl;
	cout << &b << endl;
	cout << b - a << endl;
	cout << a - b << endl;
	system("pause");
}

结果如下：

所以确实是这样，但是注意，一下的程序结果明显不对：

#include <iostream>                // std::cout
using namespace std;
int main()
{
	int *b = new int(5);//指向堆上的指针
	int *a = new int(6);
	cout << &a << endl;
	cout << &b << endl;
	cout << b - a << endl;
	cout << a - b << endl;
	cout << "-------------" << endl;
	int e = 10;//指向栈上的指针
	int f = 20;
	int *c = &e;
	int *d = &f;
	cout << &c << endl;
	cout << &d << endl;
	cout << c - d << endl;
	cout << d - c << endl;
	delete a, b;
	delete b;
	system("pause");
}

结果如图所示

可以看到，指向堆上的指针相减结果是不对的，而指向栈上的指针结果是对的。

---

？？？我也不是很理解这个是为什么

---

不过一般这种没有任何关系的指针减法在实际中很少用到，一般都是我第一个程序所展示的那样，先分配一块连续内存，无论是在堆上还是在栈上，然后进行指向这块内存中元素的指针相减。