STL的deque读书笔记

今天看到了deque，个人觉得deque应该是STL容器中的一个精华了，设计很巧妙，同时也很复杂，要花不少时间把这块硬骨头啃下来。

deque的逻辑模型

deque的逻辑模型和数组一样，连续的线性空间。使用上和vector一样支持随机存取。但和vector的区别很大，deque几乎以O(1)时间完成元素的头插入和移除，vector的话需要做元素移动处理；同时deque不会出现vector那样空间增长的时，元素”整体搬家”的情况，所以呢deque不会像vector那样用过的空间都留着用的情况，而是有条件的保留一些空间。

deque的实际数据结构

上面说到deque用起来好像全方面吊打（其实也未必）vector，要得益于deque的数据结构设计的太巧妙了。下面放张截图：

deque是由一块块长度固定且相等的连续空间组成的一个map，也可以说是一个hash结构，这里说的”map”不是STL中那个基于红黑树实现的map，而是一块连续线性空间只不过元素是一个指针的指针，指向一块大小固定的连续空间的头（这一块连续空间才是真正存放元素的地方）。所以deque的连续实际上是一种伪连续。因此deque的结构更准确的说是分段的连续空间。

迭代器的设计

为了维护deque连续的假象，迭代器就设计的比较复杂了。
如下：

注意！！！普通迭代器和两个特殊迭代器的区别

deque的普通迭代器有四个成员其意义分别是：
cur：指向当前迭代器所指的实际元素位置
first:指向当前迭代器所在段的第一个元素的位置
last：指向当前迭代器所在段的最后一个元素的位置
node：指向当前段在map中的位置（指示了这一段区间，是整个deque结构中的哪一块）

在此基础上，维护了两个特别的迭代器：
start：指向当前map已用空间的第一段
finish:指向当前map已用空间的最后一段

start的last指向了已用空间的第一段的最后一个元素的下一位置!!!下一位置！！！下一位置！！！；cur则指向了第一个元素。
finish的last指向了的已用空间的最后一段的段尾元素的下一位置；cur则指向了最后一个元素的下一位置（段尾和最后一个元素并不一定是相同的，参考上图）。
虽然话有点多，但上图的每个箭头指示位置这个细节是很重要，很多人会忽略，甚至以为图错了。指向下一位置这样设计，不为别的，就是为了兼容STL区间遍历时左闭右开的规范。
所以pop_back()操作中：

这诡异的先自减前进一位，然后在析构的逻辑就能解释的通了。
———疑问
那为什么start不指向整体空间的第一段，finish为什么不指向整体空间的最后一段，这里就是STL设计的高明之处了，可以让deque高效的双向增长，在此先放下这个问题，后面慢慢再说，先谈谈每一段的内存策略。

这里我大部分搬《STL源码剖析》的说明结合自己的一下理解。
deque的模板声明如下：
源码截图

书上的截图

和书上给出的不一样啊，估计是书上的STL版本真的过时了，那么那个制定缓冲区大小发生了什么改变呢？

通过源码分析：

可以发现新的STL是不再暴露可以设置缓冲区可装元素数量的方法了，取而代之的是，直接根据构造类型的大小来自动计算一个缓冲区应该装多少个元素，以便后面分配每个段的空间的大小。STL里面设计的逻辑是如果一个对象大小小于512字节的话，每个段就装载（int）(512/sz)个元素，反之，每个段只装一个元素。

//比如我们声明如下deque
deque<int> dque;
//那么每一段可以装(512/4)=128个int对象。

//再举个例子，构造一个有200个值为9的元素的deque对象。
deque<int> dque(200,9);
//因为一段只能放128个对象,那么这个dque中只使用了两段空间，即两个map节点

deque内存管理策略

上面为什么说只使用两段空间而不是只有呢？这就是接下来deque内存管理要说的事，同时补上前面放下的话题。

为了做到能够高效率双向扩展，deque在初始化map时，map的最小长度为8，最大长度为”所需要的段数（节点）+2”。对象在构造的时候就至少保证前后要各预留一段空间，用来为以后扩充使用。

也就是说初始的时候使用的第一个map节点并不是真正的第一个map节点，而是尽可能的靠中间的节点。
关于计算尽可能靠中间的节点的位置，可能上面计算的__nstart和__nfinish的方法不太直观。
我下面放张图从几何角度来直观呈现如何计算尽可能靠中间的节点:

因此当我们要在头/尾插入一个元素，恰好已使用的第一段/最后一段需要使用新的map节点的时候，只需要对前一个/后一个节点申请一个连续空间就可以愉快的扩展啦，不用元素搬家哦。如果往极端的地步想，map节点全部用完了，且每个段也装满了，再插入元素会怎么样。书上也很直接的说了，map空间进行重新分配空间，移动map元素，析构回收旧空间的操作，而存放元素的段则整体上不变，只有map节点整体搬家而元素依然不动，由两个函数reserve_map_at_back()和reserve_map_at_front()来通过调用reallocate_map()来实现map节点的重新分配。具体的是代码就不贴出来了。

insert()，和erase()方法

这两个方法很有意思，插入/擦除的手法其实和vecor的手法差不多（移动n各元素来让位/覆盖达到插入/擦除特定位置的效果），有意思的是为了尽可能的提高效率，会比较你要插入/擦除的位置的左右端的元素数量来使得移动元素的数量尽量少，下面我就直接放截图了。

erase()方法

insert()方法

insert中调用的insert_aux()

好了，deque篇目前就记录到这里了，日后有新的见解，我会在补充。同时因为deque比较复杂，如果存在表述有误的地方，欢迎指正。