deque可以看做是vector和list的折中容器，类似vector，它支持随机访问(其实是假象)，即支持[]以及at()，但是性能没有vector好。

deque和vector的区别：

1. 在头部插入删除元素的时间复杂度是O(1)
2. 没有容量的概念，所以没有reserve, capacity函数。因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，不像 vector 那样，当旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间

deque还是不如list的任何位置插入删除，它的中间部分插入和删除元素和vector一样，时间复杂度还是O(n)。所以没有list的reverse函数

底层机制

这下问题就来了，既然没有reserve和capacity，显然它和vector的底层机制不同。

deque采用类似索引的结构管理内存，采用一块所谓的map(不是数据结构的map )作为中控器，map是一块连续的内存空间，每个元素(称之为节点)都是指针，指向另一块连续的线性空间，称为缓冲区，map实际上是指针的指针T**。

deque的迭代器包含4个：

• cur：迭代器当前所指元素

• first：此迭代器所指的缓冲区的头

• last：缓冲区尾

• node：指向管控中心

deque的最初状态是有一个缓冲区，调用clear函数的作用就会清除整个deque，释放所有空间而只保留一个缓冲区。如果调用erase清楚某个元素，而这个元素是所在缓冲区唯一的元素，会将此缓冲区释放。

与vector不同，deque的内存大小是可缩减的。deque的内存区块不再被使用时，会被释放。

deque维护start和finish两个迭代器，分别指向第一缓冲区的第一个元素和最后一个缓冲区的最后元素的下一个位置。它还要记住当前map的大小，如果map的节点不足，就需要重新配置。

为了指定缓冲区的大小，必须指定 alloc 为空间配置器。比如指定数据int类型，缓冲区大小为4的deque: deque<int, alloc, 4>。 map的初始大小至少是8，最多是所需节点数+2，按刚才的例子，要存放50个元素，就需要13个节点，那么map的初始大小就是15。 如果插入的元素太多，map会不够大，需要扩充，和vector的内存扩充一样，先配置一块更大的，把原来的节点全拷贝过来，再释放原来的map。 对于平时的空间扩充，如果缓冲区中还有备用的空间，那么直接使用备用的空间；否则另外配置一个缓冲区，将其信息记录到缓冲区地址表里

在除了首尾两端的其他地方插入和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。

特点

• deque的元素存取和迭代器操作会比vector稍微慢一些，因为它的内部结构会多一个间接过程

• deque迭代器是特殊的指针，而不是vector那样的一般指针，它需要在不同的区块之间跳转

• 不支持对内存分配时机的控制，也就是没有reserve

• 缓冲区的内存地址是连续的，但不同缓冲区之间不是连续的

• 中间添加元素，会使迭代器、指针、引用失效

• 头尾添加元素，现有元素的内存地址不变，指针和引用不失效，但迭代器可能失效，因为可能分配新的内存块

最好采用deque的情形

• 需要在两端插入和删除元素

• 随机访问元素的情况较少，主要是访问两端元素

• 要求容器释放不再使用的元素

cartographer中的成员变量，凡是以queue结尾的，基本都是deque类型。 比如timed_pose_queue，它的使用只有back, front, pop_back, pop_front几个函数，根本没有用到遍历和随机访问

deque<std::unique_ptr<Constraint>>   constraints_;
constraints_.emplace_back();
auto* const constraint = &constraints_.back();

constraints_是个vector，可先添加一个空元素，然后再对最后一个元素进行赋值，其实为添加一个新元素（cartographer中很多都是如此做法，目的可减省一个变量空间和赋值时间）

queue

单向队列中的数据是先进先出，queue只是进一步封装别的数据结构，并提供自己的接口，如果不指定容器，默认是用deque来作为其底层数据结构的

单向队列一共6个常用函数front()、back()、push()、pop()、empty()、size()，不支持随机访问，所以没有[]运算符和at

#include <queue>

queue<int>  q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);

qDebug()<< q.size() << "  "<< q.empty();
qDebug() <<q.front() << "  " << q.back() ;
q.pop();
qDebug() <<q.front() << "  " << q.back() ;

4    false
1    4
2    4