【C++】---STL容器适配器之底层deque浅析

一、deque的使用

1、什么是deque？

deque(双端队列)：是一种双开口的"连续"空间的数据结构 双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

2、C++库中有三个队列：queue(FIFO)、deque(双端队列)、priority_queue(优先级队列)只有FIFO才是“真队列”！

3、如何理解deque？

虽然deque是vector和list的结合体！但是deque并不是万能的，也是有缺点的！

二、deque的原理

1、deque的结构

deque作为双端队列，是一种双开口的，拥有连续储存空间的数据结构。双开口意思就是说既可以在头部进行插入删除元素，又可以在尾部进行插入删除元素。它结合了vector和list的优点。

（1）与vector相比：vector没有头插头删的操作，而deque有！

（2）与list相比：list没有连续的存储空间，而deque有！

2、deque的底层结构

（1）deque的底层空间

（1）实际上来说，deque并不是真正意义上拥有连续的储存空间，而是由一个个小的数组一段段拼接而成。
实际deque类似于一个动态的二维数组，其底层结构如下：

（2）如何访问deque里面的元素？找到是第几个值？

如果要计算要访问的元素在第几个buff里面，每个buff固定大小：N，i/N +1算出在第几个buff中，i%N算出是buff中的第几个元素

（2）deque如何支持随机访问、deque迭代器

（1）双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

3、deque的优缺点

（1）deque的优势

deque结合了vector和list的优势：

①： deque在头部插入删除数据的时候不需要挪动后面的元素在进行扩容时也不需要大量的迁移，挪动元素。效率肯定比vector高。

②：除去了list的缺陷，它拥有相对连续的储存空间。空间利用率比较高。

（2）deque的致命缺陷

deque不适合进行遍历，因为deque的迭代器在进行遍历的时候，需要频繁的不断的去检测其有没有移动到某段小空间的边界，导致效率大大降低。

因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，不适合大量的头部和中间插入删除，也不适合大量的随机访问。而目前能看到的一个应用就是，STL用deque作为stack和queue的底层数据结构。

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

好了，今天的分享就到这里了
如果对你有帮助，记得点赞👍+关注哦！
我的主页还有其他文章，欢迎学习指点。关注我，让我们一起学习，一起成长吧！