[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的优点，而完美的避开了其缺陷。 

原文地址：https://blog.csdn.net/weixin_62196764/article/details/142466526

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！