[c++进阶(九)] STL之deque深度剖析
1.前言
本章重点
本章将会着重的介绍deque底层到底是如何实现它能够双向进出的，并且双向进出的消耗率还特别低，并且讲解deque的优缺点。
2.deque的使用
如果没有看我前面两篇文章的，请先看前面两篇文章再来看这篇文章，可以有助于理解。
[c++进阶(八)]STL容器适配器之queue-CSDN博客
[c++进阶(七)]STL容器适配器之stack-CSDN博客
deque在stack和queue里面使用的是deque作为底层容器，但是为何用的是deque呢？他有什么优势呢？又有什么缺点呢？
3.deque的原理
1.deque的结构
deque的底层结构是双端队列，这种队列可以实现双开口进出，并且进出的时间复杂度为0(1)。
与vector相比：头插的更加方便
与list相比：空间连续，空间利用率更高。
2.deque的底层结构
（1）deque的底层空间
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成，实际deque类似于一个动态的二维数组，其底层结构如下：
中控指针数组中存放的是指向缓冲区buffer的指针，是动态开辟的二维数组，先malloc一个指针数组，指针数组的每个位置存放一维数组buffer的地址。当deque不断开buffer时，map中控指针数组满了，那么会增容，不过map增容的代价非常低，因为只需要拷贝存储数据的buffer数组的指针，不需要拷贝buffer中的内容。
如果要计算要访问的元素在第几个buffer里面，每个buffer固定大小，i/buffer.size()+1算出在第几个buffer中，i%buffer.size()算出是buffer中的第几个元素。
（2）deque是如何支持随机访问
双端队列底层是一段假象的连续空间，实际是分段连续的，但是为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂：
first指向buffer的第一个位置，last指向最后一个位置，cur指向当前buffer中存在的数据，node则需要回指导中控指针数组。
为什么要指回呢？这是因为当迭代器遍历到当前为止时，如果需要++或者--，自己是无法找到下一个buffer在那个位置，必须根据中控指针的指向找到下一个需要遍历的位置，所以说需要一个node来回指中控指针，方便迭代器迭代。
（3）deque迭代器
那deque是如何借助其迭代器维护其假想连续的结构呢？ 如果一个buffer走完了，如何走到下一个buffer的位置呢？用node++来控制，node反向指向map当中当前buffer的位置，那么node++就指向下一个node的位置，解引用就是下一个buffer的位置。
node并不是从第一个位置就开始存放的，从中间开始存放，那么头插就还有空余位置。
而在buffer中存放位置一般都是从尾部开始存放的，这样就方便后续的头插头删，尾插尾删等相关操作了。
3.deque的缺陷
deque不适合随机访问，不适合中间插入和删除函数。可以说他结合了vector和list的相关特性。
可以说deque的优缺点也和vector和list的优缺点息息相关。
(1)deque的致命缺陷
不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，不适合大量的头部和中间插入删除，也不适合大量的随机访问。而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
（2）deque的优点
① 与vector比较：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
② 与list比较：其底层是连续空间，空间利用率比较高，不需要存储额外字段。
4.deque作为stack和queue底层容器的原因
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有 push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和 queue默认选择deque作为其底层容器，主要是因为：
（1）stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
（2）在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，使用deque作为底层默认容器，不仅效率高，而且内存使用率高。
stack和queue结合了deque的优点，而完美的避开了其缺陷。