C++ deque 双端队列

deque原理介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)。

与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的。

为了表面看起来上连续的，我们就需要迭代器来封装底层。

deque迭代器

成员函数中有两个迭代器start finish，中控数组map存储空间的起始地址

而迭代器中有3个一级指针，和1个二级指针node(用来找中控数组map中下一段内存空间的地址)

1.start finish迭代器中的first last都是指向这段连续小区间的起始和末尾。

2.start的cur是指向第一个元素，而finish的cur是指向最后一个元素后面的位置。

可以看到deque可以支持vector的[]下标的随机访问，链表的头删 头插。

1.push_back尾插。

如果最后一段区间没满，直接插入就行。反之，就需要重新开辟一块空间，并在map中记录起始地址，再插入。

2.push_front头插

头插的话也要开辟一块空间，但数据的存入顺序是在这一段空间的末尾倒着存入。

3.[]随机访问

虽然deque的底层空间并不是完全连续的，但每次开辟的空间buff大小是确定的。

对要访问的下标先除buff空间大小找到在第几个buff上，再取余找到在buff上的第几个元素。

 

我们知道头插数据是倒着存入的，如果第一段空间没有满又改怎么办呢？

我们可以假设第一段空间满了，让要访问的下标加上第一段空间空的元素个数（cur-first）。

4.迭代器遍历

当cur==last时说明当前buff数组已经遍历结束，set_node(node+1)根据map数组找到下一段空间的起始位置。first=*new_node new_node是二级指针解引用就是空间的起始地址。

vector list deque优劣势

vector

优势：1.尾删/插效率高

2.支持随机访问

3.顺序表CPU高速缓存命中率更高（物理地址是连续的）

劣势：
1.头或中间删/插效率低

2.空间利用效率不高

3.扩容费时间，还可能存在空间的浪费。

list

优势：1.插入删除效率高

2.按需申请空间避免空间的浪费。

劣势：1.不支持随机访问。

2.CPU高速缓存命中率低（物理地址是不连续的）

deque

优势：1.对比vector头插效率更高

2.对比list可以随机访问

劣势：1.虽然可以随机访问但效率是不如vector，毕竟空间不是完全连续的。

（可以少量访问，像排序，遍历还是用vector好）

2.在中间插入删除，还是需要移动数据的。