【C++】deque的实现原理简单介绍

前言

deque被称为双端队列，它的出现主要是为了结合vector和list的优点并减小它们的缺点，实际上deque确实结合了vector和list的优点减小了它们的缺点，但是它的结合也让它自己的优点没有原始的vector和list那么极致，导致deque变得很中庸，所以deque的应用场景也并没有那么多，它经常被用来作为stack和queue的底层容器

本篇文章我们来一起简单探讨一下deque的实现原理

一、deque的原理介绍

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

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

当中控数组满了，我们也只需要对中控数组进行扩容，然后拷贝指针就行了，并不需要对真正存储数据的小数组做改动，这大大减少了拷贝数据的个数。

二、deque的一些基本特性

1、deque的随机访问

deque的随机访问有两种情况: 这与deque中的小数组的大小是否固定有关。

• 假设我们deque中的小数组是固定大小，不能进行扩容，那么我们就可以使用除模运算进行随机访问，假设想要访问的位置是$x$,第一个数组中的元素个数是$y$,数组的大小固定为$n$，想要访问的小数组是从第二个数组开始第$row$个,想要访问的位置在对应小数组的第$col$个。
  
  我们就可以通过$$row=(x-y)/n$$ $$col=(x-y)\%n$$从而确定我们想要访问的位置。时间复杂度是$O(1)$
  
  
• 假设我们deque的小数组可以扩容，我们的中控数组可以存放一个自定义类型，自定义类型里面有指针也有对应小数组中数据的个数。那么我们就要用从第一个数组的个数 +第二个数组的个数 +第三个数组的长度 + …直到加到某个数组时大于我们想要访问的位置，我们才能确定对应是第几个数组，然后在小数组中进行访问该元素，这样的话时间复杂度就是遍历中控数组，时间复杂度是$O(n)$

2、deque的中间插入与删除

deque的中间插入也有两种情况: 这也与deque中的小数组的大小是否固定有关。

• 假设我们deque中的小数组是固定大小，不能进行扩容，那么我们在中间位置进行插入或者删除时，就要移动数据，也就是说可能要把一个小数组中的数据移动到另一个小数组里。
• 假设我们deque中的小数组是不是固定大小的。
  那么我们在中间位置进行插入就可以只对当前的小数组进行扩容然后再进行插入，这样我们就不必对其他小数组中的数据进行移动了
  如果我们对中间的数据进行删除，我们也只需要对当前的小数组进行缩容就进行了，如果小数组中的数据全部被删除了，那可以直接释放掉空间，然后调整中控数组就行了。

总结：deque的随机访问与deque的中间插入与删除之间有负相关的作用。当小数组固定时，随机访问效率会变高但是中间位置的插入与删除效率会变低；当小数组不固定大小时，随机访问效率会变低但是中间位置的插入与删除效率会变高。

在STL的SGI版本中对于deque的小数组选择了固定大小，且小数组中可以存储数据的个数是8(这个大小可以通过模板参数进行调整)

三、deque的迭代器

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

deque的迭代器有四个指针，第一个cur指向小数组中要指向的数据，第二个first指向小数组中的第一个位置，第三个last指向小数组中最后一个数据的下一个，第四个node反向指向中控数组，方便遍历完一个小数组后跳到下一个小数组。

四、deque的优缺点分析

1、优点：

1. 与vector比较，deque的优势是：
   • 头部插入和删除时，不需要搬移元素，效率特别高。
   • 在扩容时，也不需要搬移大量的元素，只需要搬移中控数组中的指针就行了。
2. 与list比较，deque的优势是：
   • 其底层是连续空间，空间利用率比较高，不需要存储额外字段。
   • 支持随机访问

2、缺点:

1. 中间的插入删除与随机访问不好抉择，难以两全其美。

2. 优点没有vector和list极致，随机访问的速度没有vector快，(vector是真正的连续空间，在计算机硬件中缓存利用率极高，在排序方面这点很重要！！！)，中间位置的插入与删除没有list快（list的中间位置的插入与删除是$O(1)$），deque需要进行扩容，而list根本不需要扩容

3. deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

五、为什么选择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不仅效率高，而且内存使用率高。两个适配器都结合了deque的优点，而完美的避开了其缺陷。