【C++】deque双端队列
deque的原理介绍
1.deque(双端队列):是一种双开口的“连续”空间的数据结构,双开口的含义是:在头尾两端都可以进行插入和删除操作,且时间复杂度为O(1)。
需要注意的是deque并不是真正连续的空间,不是像vector那样底层是连续空间的数组,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,为了管理分段空间,deque容器引入了map,称之为中控器,map是一块连续的空间,其中每个元素是指向缓冲区buffer的指针,缓冲区才是deque存储数据的主体,其底层结构如下图所示:
2.双端队列底层是一段假象的连续空间,实际上是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器上,因此deque的迭代器就比较复杂,如下图所示:
中控器包含了map size,指向buffer的指针,deque的开始迭代器与结尾迭代器。
_Tp **_M_map;
size_t _M_map_size;
iterator _M_start;
iterator _M_finish;
deque的优点和缺陷
在了解deque双端队列的优缺点之前,我们先学习一下vector和list的优缺点,有助于更好的比对。
vector的优点:
- 尾插尾删效率很高
- 支持随机访问(利用下标访问)
- 相比链表结构。顺序表CPU高速缓存命中率更高(因为顺序表的底层由数组实现,物理地址是连续的)
vector的缺点:
- 头部和中部插入删除效率低(O(N))
- 扩容:存在性能消耗和空间上的浪费
list的优点:
- 任意位置插入删除效率很高。(O(1))
- 按需申请和释放,优化了vector在空间上的浪费
list的缺点:
- CPU高速缓存的命中率不高(物理地址空间不连续)
- 不支持随机访问
deque的优点:
与vector比较,deque的优势是:头部插入删除时,不需要搬移元素,效率高,而且在扩容时,也不需要搬移大量的元素。因为deque在头部插入删除的时候,是直接在前面开一块空间(缓冲区buffer)插入元素的,尾插同理,在后面开空间。
与list比较,deque的底层是连续空间,空间利用率比较高,不需要存储额外的字段。
deque的缺点:
-
不适合遍历及排序
因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下**,并且deque的迭代器非常复杂,deque维护了两个迭代器,start指向第一个缓冲区的第一个元素,finish指向最后一个缓冲区的最后一个元素的下一个位置,cur指向迭代器所指缓冲区的当前元素,first指向迭代器所指缓冲区第一个元素,last指向迭代器所指缓冲区的最后一个元素,node指向中控,当cur等于last,说明本段空间已被使用完毕,通过node++找到中控数组中下一段内存空间的地址(见下图)。而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用场景并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构。 -
中间插入删除数据不如list
从deque的底层结构图中可以看出,中间插入、删除数据仍会产生数据的挪动。 -
随机访问速度不如vector
由于deque的中控数组中指向的一段地址空间之间并不连续,所以随机访问时需要计算目标数据处于哪段buffer中的第几个数据。计算方式与磁盘定位扇区类似(LBA地址转化为CHS地址)。
为什么选择deque作为stack和queue的底层默认容器?
1.stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作;
2.在stack和queue中,元素增长时,deque和vector相比,deque效率更高(扩容时不需要搬移大量数据),内存使用率更高。
相关文章
- C++ 链表
- 托管C++线程锁实现 c++11线程池
- C++ 模板类相关问题
- [c++菜鸟]《Accelerate C++》读书笔记
- c++文件操作
- 【C++】auto关键字
- 【C++】从C到C++
- MFC匿名管道原理详解、函数总结、调用实例(用MFC的匿名管道读取CMD输出内容)(C++语言)
- 开源免费的C/C++网络库(c/c++ sockets library)补充
- C++中优先队列priority_queue的基础用法
- 《C++多线程编程实战》——1.9 链表、队列和栈示例
- 《C++入门经典(第5版•修订版)》——2.6 问与答
- 《C和C++程序员面试秘笈》——
- 《C和C++代码精粹》——2.4 传引用语义
- 《Imperfect C++中文版》——1.2 编译期契约:约束
- 基于C++实现(控制台)考试系统【100010312】
- 机房预约系统(C++)
- C/C++使用心得:enum与int的相互转换
- Linux环境下配置vscode的C/C++ 的make编译环境(编写makefile方式)
- 【C++:STL之栈和队列 | 模拟实现 | 优先级队列 】
- 蓝桥杯冲刺(C/C++)(二) 真题练习(持续更新...积极备赛)
- 203、【栈与队列】leetcode ——剑指 Offer II 040. 矩阵中最大的矩形 / 85. 最大矩形:暴力+单调栈(C++/Pyhont版本)
- 186、【栈与队列】leetcode ——503. 下一个更大元素 II(C++版本)
- 81、【栈与队列】leetcode ——232. 用栈实现队列(C++版本)
- 35、【栈和队列】二叉树的中序遍历(C++版)
- 34、【栈和队列】逆波兰表达式(C++版)
- C/C++ 编程计算2的100万次方(m的n次方),超长结果输出文件
- C/C++ Windows API——ICMP