deque

<aside> 💡

deque中元素是分段连续的

</aside>

deque中控器

• map：一个指向指针的指针，中控器使用map管理所有buffer
• BufSiz：旧版本允许用户指定buffer大小，新版本固定为512字节

deque iterator

deque的迭代器结构

• node：指向当前buffer在中控器中的位置
• first、last：指向当前buffer的前后边界，在一个buffer中移动时这两个值是不变的。如果迭代器超出边界则需要跳转到其他buffer
• cur：指向迭代器指向元素在当前buffer中的位置

Traits

• iterator_category为随机访问器

deque<T>::insert()

• 调用insert()时，迭代器会判断插入点离deque头部与尾部的距离，选择一个离得近的进行移动
  • 如：若插入点离头部近，则插入点前的元素向头部位置进行移动

deque如何模拟连续空间

• 重载operator-，用于计算两个迭代器之间的距离