deque
deque 有个以 vector 组成的控制中心 map ,意味这它会自动扩充,每个 vector 元素指向一个 buffer缓冲区,这个控制中心有 start 和 finish iterator分别有 node 指向第一个 buffer 和 最后一个,每个 buffer 也有 iterator ,里面有4个元素:cur、first、last、node分别指向该 buffer 的当前指向元素、buffer 空间第一和最后元素和在控制中心的位置
map 的类型是 T**,指针指针,因为还有指向 vector 元素嘛
那 buffer 里可以放多少个元素呢?可以指定,但是没有指定的情况下,如果元素大小大于 512 字节,那就放 1 个,小于的话放 512/该元素大小 个
deque iterator
首先它的 iterator_category 是 random_access_iterator_tag 虽然事实上它不少连续的但是声称它是连续的
deque::insert()
先判断是不是头或尾,那就可以直接 push front 或 back,都不是就看看插入位置离哪边近,推动较少元素的那边再插入
如何模拟连续空间
靠重载,像数组一样的 +、-、[ ]、+=、-= 等都要进行重载,比如 - ,那要知道两个元素之间的距离,就要知道其中所处之间有几个 buffer 再加上其在 buffer 上所处的位置关系,要知道有几个 buffer 用 node 相减 - 1,就可以