deque是一种分段连续的容器，特点是双向开口，可以认为它是一段连续的内存空间，不仅可以向前方增加内存空间，也可以向后方增加内存空间。
在实际内存中实现双向扩充是比较复杂的事情，那么deque中是如何实现的呢？deque通过一个控制器来串联一系列的缓冲器（buffer），从而达到逻辑上的连续效果。deque是通过一个vector在维护自身的控制器，在控制器中存储的是指向buffer的指针，因此我们需要用一个指向指针的指针来指向这个vector的地址。
deque能在逻辑上实现内存连续，最关键的是iterator在起作用。迭代器运行到边界的时候，都需要检测是否到边界，然后通过回到控制buffer的那个vector来管理边界的buffer了。在iterator中，cur、first、last和node分别指向了用户使用时的当前的数据，first指向了buffer的第一块空间，last指向了buffer之后那个不在buffer中的空间，而node指向了控制buffer的指针序列中的实际位置
deuqe的插入问题：
元素插入的时候因为是按顺序排列，如果插入元素不在两头在中间，会改变其他元素的位置，如果插入点距离前段比较近，那么移动前段比较合适，效率较高；
如果插入点距离后端比较近，那么将插入点之后的元素向后移动比较快。
容器queue是以deque为底层结构实现的
容器stack也是以deque为底层结构实现的，需要注意的是queue和stack都不允许遍历，也不提供iterator
Red-Black tree（红黑树）是平衡二元搜寻树（balanced Binary search tree）中常被使用的一种。
平衡二院搜寻树的特征：排列规律，有利于search和insert，并保持适度平衡，无任何节点过深。
网友评论