deque

1. deque是什么？

1. deque(发音类似“deck”)，是双端队列不规则的首字母缩写，双端队列是动态大小的序列式容器，其可以像两端进行伸缩。
2. 特定的库可以以不同的方式实现deque，但通常都是一种动态数组。不论在何种情况下，它都允许通过随机访问迭代器直接访问单个元素，可以根据需要动态的伸缩。
3. 因此，deque提供了一些与vector相似的功能，但deque在头部和尾部进行数据插入和删除操作更加高效。与vector不同的是，deque不能保证所有的元素存储在连续的空间中，在deque中通过指针加偏移量方式访问元素可能会导致非法的操作。
4. vector与list提供了相似的接口，因此其具有类似的用途，但是内部的实现原理不同：vector使用使用了动态数组，该数组通常需要动态增长；deque中的元素可能分散在不同的存储块中，在deque中保存了
   一些必要的信息，通常用来在常数范围内直接访问deque中的任何一个元素，所以deque的内部实现比vector复杂，但是这些额外信息使得deque在某些情况下增长更加的高效，特别是在序列比较大，重新分
   配成本比较高的情况下。
5. 除了在频繁在头部或尾部进行插入和删除操作外，deque比list和forward_list的性能更差。

deque的详情解释

2. 既然deque与vector相似，那为什么还要有这个容器呢？

vector、list和deque对比：

vector：

优点：可以随机访问。

缺点：在头插和头删的时候效率不高，并且当预设的空间用完时需要增容。

list：

优点：插入删除效率高。

缺点：不能随机访问，还会造成内存碎片。

所以deque就是vector和list比较折中的方法。

deque：物理不连续，逻辑连续的vector。

优点：随机访问、插入删除效率高、无较大增容代价。

实现方法：中控+缓冲的方式。

中控：指针数组。

双端队列（deque）的底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”的假象，落在了deque的迭代器身上。

本篇博客的图片均来自《STL源码剖析》

我们可以从这张图中看到deque的结构，它是由一个中控（map）来控制一段一段缓冲区（buffer）。这些buffer并不是连续的，而是当目前我们要进行插入时，存储空间不够时再开辟一段buffer。这样就改进了vector扩容的问题。（vector扩容时，会开辟当前所有数据+需要插入的数据的空间再进行拷贝，效率非常低）

3. 那么我们到底怎么知道当前该在哪里插入删除呢？

这些工作是由deque的迭代器来完成的。

下面对迭代器需求描述来自《STL源码剖析》

让我们思考一下，deque迭代器应该具备什么结构。首先，它必须能够指出分段连续空间（亦缓冲区）在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃至下一个或上一个 缓冲区。为了能够正确跳跃，deque必须随时掌握管控中心（map）

这是一个迭代器能达到的基本需求：cur表示当前可以插入的位置，first表示当前缓冲区的第一个结点的位置，last表示最后一个结点的位置，node表示该缓冲区在map中的位置。

比如我们现在定义一个deque对象，并且令每个缓冲区可以存8个元素。然后存20个元素进去。

第一个缓冲区因为存满了所以它指向第一个元素，最后一个缓冲区因为还有空间所以cur指向最后一个元素的下一个元素。

4. deque接口

5.deque的应用场景

deque在序列式容器中比较鸡肋，因为如果只是简单的存储元素，使用vector即可，如果对元素任意位置进行插入或者删除操作比较多，使用vector即可，所以一般很少去使用deque。deque最大的应用，就是用其
作为标准库中stack和queue的底层结构。

还记得C语言里面队列和栈是怎么实现的吗？就是用了数组或链表但是我们在接口里面手动把他插入和删除的方式更改了规则。这里deque也是一样，它作为了C语言里面数组或链表的作用，作为deque的底层容器，然后再根据需要改变了插入和删除的规则而已。