Deque容器（双端队列）

Deque是一种双向开口的连续线性空间。

Deque容器和vector最大的差异是：一再与deque头端的插入删除是O(1)时间复杂度。二是deque没有容量的概念，因为它是动态的分段连续空间组合而成，随时可以增加一段新的空间并链接起来。反观vector容器的空间不足时需要重新配置一块更大的空间然后复制元素，再释旧空间。因此，deque没有必要提供所谓的空间保留reserver功能

虽然deque容器也提供了可以随机访问的迭代器，但是它的迭代器并不是普通的指针，其复杂度和vector不是一个量级，这当然影响各个运算的层面。因此，除非必要，我们应该尽可能使用vector而不是deque.对deque的排序操作，为了最高效率，可以将deque先完整复制到一个vector中，对vector进行排序再复制回deque。

Deque容器是连续的空间，至少逻辑上看是如此，连续线性空间总是令我们联想到array和vector。array无法成长，vector虽然可以成长但是只能向尾端成长，而且其成长是一个假象，事实上是：申请更大的空间 ->原数据复制到新空间->释放原空间。如果不是vector每次配置新的空间都留有余裕，其成长假象所带来的代价是非常昂贵的。

deque是由一段一段的定量的连续空间构成，一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间、赋值、释放的轮回，代价就是复杂的迭代器架构。

既然deque是分段连续内存空间，那么久必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。deque代码的实现远比vector或list多得多。

deque采取一块所谓的map（并不是STL的map容器）作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素（此处成为一个节点）都是一个指针，指向另一端连续内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。

无标题.png

API

双端插入和删除操作

push_back(T);  //尾部添加

push_front(T);   //头部插入

T pop_back()   //删除最后一个数据并返回

T pop_front();  //删除第一个数据并返回

数据存取

at(idx)   //返回索引idx所指的数据，如果idx越界抛出out_of_range

operator [] //同上，区别是不抛出异常

front(); //返回第一个数据

back(); //返回最后一个数据

插入操作

insert(pos,T) 在pos位置插入一个T元素的拷贝，并返回新数据的位置

insert(pos,n,T)  在pos位置插入n个T数据，无返回值

insert(pos,iterator beg,iterator end) 在pos位置插入(beg,end)器件的数据，无返回值

删除操作

clear(); //移除容器的所有数据

erase(iterator begin,iterator end) 删除区间内的数据 并返回下一个数据的位置

erase(pos) 删除pos位置的数据并返回下一个数据的位置