deque

快来打我* 2022-05-17 10:12 171阅读 0赞

#### 写在前面 ####

> STL:deque总结

#### 主要内容 ####

> 为什么需要deque?  
> deque的作用是什么？

**问题1**：vector虽然可以动态的增容，但是只能在vector的尾部进行插入和删除的效率比较高，在vector的头部操作带来的开销太大，无法被接受，（伴随大量的元素移动）所以vector就是一个单端开口的数组。  
**问题2**：当vector容量满的时候需要扩容，这时候需要开辟一块更大的空间，并且将原始空间的元素一个一个移动到新的空间当中，移动的开销是线性开销。  
**解决方案**：deque就是双向开口的数组。允许常数时间对头部端进行插入或者删除。其次没有容量的概念，deque可以随时开辟空间将新的空间链进来，原始的空间不会被改变。

> 有好处必然有损失：deque解决了vector的扩容开销以及头部操作开销，与此同时带来的问题就是deque的迭代器并不是像vector里的原生指针，虽然也是随机访问迭代器但是效率上比vector的访问差。

deque的数据结构组成：

> 中控器：map (并非STL的map)。

deque维护一个假象：所以的内存空间都是连续的。对于vector来说所以的元素是存储在连续的空间之上的，所以其迭代器就是原始指针。deque的空间是一段一段的，每一段空间是一个小片的连续空间，这些空间分布在不同的内存空间之上，而deque通过一个叫做中控器的数据结构将这些分散的段式空间管理起来，维护整体连续的假象。

中控器map本身是一个数组，这个数组每个元素是一个指针，每个指针指向前面所说的一段一段的连续空间，这些段式空间叫做缓冲区（后面将介绍）。这样做的好处是，我们可以一开始分配一个大小适中的map，在map的中间开始存放需要的缓冲区地址，当往deque尾部存放元素超过当前的大小时，分配新的一个缓冲区将地址放在map当前管理的最后一个有效地址的下一个位置，当往deque头部插入元素时也只需要再开辟一个缓冲区将地址放在当前map管理的第一个有效的地址的前面一个位置。当map某一端到头的时候，并且缓冲区也满了此时还需要像这端插入元素的时候，只需要新建一个更大的map数组，将当前map当中的内容拷贝至新的数组当中（放到中间的位置，两端有富余位置），再释放原来的map的空间。这样所有的拷贝也只是对于地址的拷贝相比于一个一个移动每一个元素来说简直可以忽略不计（除非你缓冲区的大小设置的比指针的大小还小。。。。。）。

> 缓冲区

deque的存储主体，deque的第三个模板参数就是设定缓冲区大小的参数，默认是0表示缓冲区的大小为512个字节。deque的数据结构当中管理着map。

> deque的迭代器

每一个迭代器管理着map当中的一个node，也就是一个单独的缓冲区。迭代器当中有三个重要的指针。  
cur:指向当前node当中的当前指向的元素  
first:指向当前node的头  
last:指向当前node的尾。  
整个迭代器通过一系列的操作和计算维护着整体连续的假象，实现所有随机访问迭代器的所有接口。