【C++】STL的百宝箱—全能deque的简单讲解
✨ 坚持用清晰易懂的图解+代码语言， 让每个知识点都简单直观！
🚀 个人主页 ：不呆头 · ZEEKLOG
🌱 代码仓库 ：不呆头 · Gitee
📌 专栏系列 ：📖 《C语言》🧩 《数据结构》💡 《C++》🐧 《Linux》💬 座右铭 ：“不患无位，患所以立。”
【C++】STL的百宝箱—全能deque讲解
摘要
在 STL 的容器家族里，deque（双端队列）就像一个“全能型选手”。它既能像 vector 一样支持随机访问，又能像 list 一样在两端高效插入删除。虽然它并不是完美的存在，但凭借灵活的底层结构和均衡的性能，deque 成为了 stack 和 queue 的首选底层容器。本文将带你全面认识 deque，从设计动机到底层实现，再到应用场景，一网打尽。
📌 编程箴言：
“好的C++代码就像好酒，需要时间沉淀。”
目录
一、deque的简单介绍
1. 为什么需要deque？
我们知道，vector 的优点是能够随机访问下标，尾插尾删效率高，且 CPU 缓存命中率高；但它的不足在于头插头删效率低下，因为插入或删除时需要整体数据前移或后移，复杂度为 O(n)，并且在内存不足时需要扩容，可能造成空间浪费。
而 list 的优点是按需分配空间，不存在额外浪费，并且能够在任意位置进行插入和删除，复杂度为 O(1)；但缺点是当空间不足时需要频繁申请内存，且不支持下标随机访问。
因此，人们希望同时结合二者的优点、互补缺点，于是便创造出了 deque。
2. 了解deque
std::deque（double-ended queue，双端队列）是 C++ STL 提供的一种 序列式容器，它和 vector 有点像，都能动态扩容并支持随机访问。但它的最大特点是：可以在容器的头尾两端高效地插入和删除元素，而不仅仅是尾部。你可以把它想象成一个“带前后两个门的房间”，不管是从前门塞进去，还是从后门塞进去，都很方便。因为底层采用分段数组（而不是连续内存），所以插入删除更灵活，但随机访问速度略逊于 vector。与list比较，空间利用率比较高，不需要存储额外字段。
但deque并不是真正的连续空间（空间连续了但没完全连续），而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
- 入图所示，我们在buffer1的位置满了之后需要头插数据的话，就开一个buffer0，在buffer0的最后一个空间插入7；同理buffer1的位置满了之后需要尾插一个数据的话，就开一个buffer2，在buffer2的第一个空间开始插入8。
- 我们用一个指针数组维护这块空间，例如buffer1存在这块数组的中间，当空间满了之后就可以向前（buffer0）以及向后扩容（buffer1）。
二、deque的迭代器
当然为了能够支持随机访问，deque的iterator迭代器就设计的十分复杂了deque的迭代器封装了四个指针，first和last用来指向buffer的头尾，cur用来遍历buffer，然后将node指向中控数组对应位置：
同时还有指向头尾buffer的start和first：
map是一个二级指针，因为中控数组是一个指针数组，而map存放的中控数组的地址。
三、为什么选择 deque？
- 对比 vector
deque在头部插入和删除时不需要整体搬移元素，效率远高于vector。- 扩容时，
deque只需新开 buffer，并在必要时扩容中控数组，而不像vector那样搬移大量元素，因此效率更高。
- 对比 list
deque的底层是分段连续空间，整体空间利用率高，不需要像list那样为每个节点存储额外的prev和next指针。
- 与 stack / queue 的关系
stack是后进先出结构，只需要push_back和pop_back就能实现，因此vector、list、deque都能作为其底层容器。queue需要一端插入、另一端删除，deque的双端操作正好契合。stack和queue本身不需要迭代器，因此完全避开了deque在遍历上的劣势。
- 效率与内存
- 在
stack中，deque的扩容效率比vector高（无需整体搬移）。 - 在
queue中，deque既保证了高效扩容，又具有良好的缓存命中率和内存利用率，不易产生大量内存碎片。
- 在
总结：deque 结合了 vector 和 list 的优点：既支持双端高效操作，又具备较好的空间局部性和扩容效率。因此，作为 stack 和 queue 的底层容器，是一个更优的选择。
四、为什么deque无法完全替代vector和list？
vector的随机访问和list的任意位置插入删除O(1)的时间复杂度做到了极致，而deque的中间位置的插入删除和随机访问的效率都差强人意，所以deque是无法替代vector和list的.而且deque有一个致命的缺点：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，还不如直接拷贝到vector中再遍历，但是对stack和queue来说恰好是不需要遍历，所以STL将deque用其作为stack和queue的底层数据结构
五、deque的简单使用
voidtest_deque(){ deque<int> dq; dq.push_back(1); dq.push_back(2); dq.push_back(3); dq.push_back(4); deque<int>::iterator it = dq.begin();while(it != dq.end()){ cout <<*it <<' '; it++;} cout << endl;}结尾总结
deque 并不是为了替代 vector 或 list 而存在，而是作为一种 折中与平衡 的选择：
- 它弥补了
vector头部操作的低效， - 也避免了
list节点式存储带来的空间开销， - 并凭借双端操作的优势，成为
stack与queue的最佳搭档。
所以，理解 deque，不仅能帮助我们选对容器，还能更好地体会 STL 设计中“权衡与取舍”的智慧。
不是呆头将一直坚持用清晰易懂的图解+代码语言，让每个知识点变得简单！
👁️ 【关注】 看一个非典型程序员如何用野路子解决正经问题
👍 【点赞】 给“不写八股文”的技术分享一点鼓励
🔖 【收藏】 把这些“奇怪但有用”的代码技巧打包带走
💬 【评论】 来聊聊——你遇到过最“呆头”的 Bug 是啥？
🗳️ 【投票】 您的投票是支持我前行的动力
技术没有标准答案，让我们一起用最有趣的方式，写出最靠谱的代码！ 🎮💻
