介绍
deque是一种结合了list和vector两者优势的一种容器,它既可以支持下标的随机访问,并且头插头删的效率都不低,但相对也存在一定的缺陷,在中间插入和遍历上,消耗相对较大。
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂
deque的迭代器设计结构封装了四个指针,first、last、cur、node
cur:用于遍历和随机访问数据
first:记录每一小段数组的开头位置
last:记录每一小段数组的结束位置
node:指向中控数组中当前小数组的地址
因此每一次遍历都需要判断是否到达了每一小段空间的末端,消耗相对较大
由于其头插头删效率高,相比于链表而言,其底层是连续空间,空间利用率比较高,不需要存储额外字段。因此常作为栈和队列的默认容器去使用,以及对头插头删大部分应用的场景下也可以使用
其他情况下,更多的是根据具体场景,选择list或vector。