Deque源码

下图左边是容器deque的实际结构，右边是抽象结构，实际上内部的实质是————在一块Vector上面（图中的map size涵盖的部分）放着一个个指向容量大小的不同buffer（缓冲区或者节点）上，这些buffer的size会定义好，这里出现了三个Iterator，实际上作为一个容器，这里的deque会提供两个iterator，分别是start和finish（也就是.begin()和.end()传回的两个迭代器），其中的四个组成部分中：first和last分别固定指向当前buffer的开头和结尾，而cur则指向当前的元素，并随指针移动而变化，这个node比较特殊，它作为一个跨级标志，指向的是整个map上的某个小区块，也就是说，如果指针移动超出当前的buffer大小，node会指向前一个或者后一个小区块。它也是实现“分段连续”特性的主要原因。

下面是G2.9版本的deque源码，简单去看，里面包含四个数据，两个迭代器，占据442（一个迭代器有4个指针）一个T**（map_pointer是一个指向指针的指针，因为本来小区块上的元素就是一个个指针）占据4个字节，还有一个无符号整型map_size占据4个字节，综上，一个deque基础要占40字节。

关于buffer设定这方面：通过两个？：语句来确定buffer_size，意思是说如果一个元素的大小超过了512，那么一个buffer就只放一个单位，小于就传回512/size（单个元素的大小）

deque里面有一个成员函数是insert()，他的两个参数分别是要放的位置（迭代器）和要放的元素引用，
其内部的设计遵循一个原则，就是“就近安插”，也就是会判断这个元素的位置是靠前面一点还是靠后面多一点（第二张图片后面的代码）

综合前述，这里讲一下deque是怎么实现“连续”空间假象的：

“连续”空间的实现依靠iterator来操作，例如下图中的front()、back()函数使用start和finish来取到首和末尾元素，这里的back()需要finish前移一位是因为finish迭代器指向的是deque末端的再往后一位。这里的size()和empty()使用的是内部的运算符重载实现的减和等于操作。

如下面这张图所示，这里的减号运算符重载，目的是计算两个迭代器之间（原来是计算元素距离，实际上也是调用迭代器去计算）有多少个小单位，这样就分成了两块：一块是这两个元素所在的那个buffer上的位置的和，另一块是两个元素之间隔了多少个buffer*buffersize的元素，具体实现就是下面这种用迭代器的.node去做相减，当然这里减一是像去数N棵树之间有N-1个空是一样的道理。

这里的加加/减减重载运算可谓经典操作(前面的List成员函数有同样操作)，后加加/减减重载调用前加加/减减重载，
至于前加加/减减的内容，是去做了一个对比，就是把当前元素迭代器位置（cur）和尾端/首段位置进行对比，去选择跳与不跳（setnode()与否），减减与加加不同之处就是先去做了比对（防止cur一开始就位于first位置）。这里有一些值得讨论的地方。_当然set_node也有值得一看的东西在里面。

再到下面就是+=和+的重载函数，这里的 +=重载先对是否同一buffer进行判定，如果不是就进行位移处理，这里的offset > 0 ? :条件判定是为了在-=情况下依旧可以调用（这一部分在下下张图中显示出来）。

最后是G4.9版本的deque特性，和前面一些容器一致，复杂化表面数据，有一点与旧版G2.9不同的是，这个版本的deque不再提供buffersize接口，只能使用默认的设置方式（前面讲的512字节设计）。

还有一点有趣的是，当deque因为内存（buffer）不足进行拓展的时候，迁移拷贝数据时候会拷贝到新拓展内存的中间位置，目的是为了更好地实现push_front()和push_back()，

Stack和queue

stack和queue完全是基于deque实现的容器，他的本质是封锁掉deque容器的部分功能来实现其自己的特性（先进后出或者先进先出），下面的源码证明了这一点

当然，这里参数列表里的Squence默认是deque，但是也可以使用List实现，本质上讲是因为list里面也封装了他们可以用的成员函数，这也是其他容器不能用来作为两者的实现基础的原因。