通过存储指向引用值的指针和指向该值所在的连续内存块的双指针，可以实现deque迭代器。双指针指向指向deque管理的块的连续指针数组。
我了解随机访问迭代器是如何为std::vector这样的连续容器工作的：迭代器只需维护一个指向当前元素的指针，任何加法/减法都会应用于该指针。
然而，我对如何为非连续容器实现类似的功能感到困惑。我对std::deque:iterator如何工作的第一个猜测是，它维护了一个指向它所包含的连续内存组的某个表的指针，但我不确定。
一个典型的标准库将如何实现这一点？
您可以用std::vector<std::unique_ptr<std::array<T,N>>>大致满足std::deque的要求。加上一个告诉你第一个/最后一个元素在哪里的低/高水位标记。（对于一个实现定义的N，它可能随T而变化，而std::array实际上是正确对齐的未初始化内存块，而不是std::array，但你已经明白了）。
使用通常的指数增长，但前后都要使用。
查找只是执行(index+first)/N和%N来查找块和子元素。
这比std::vector查找更昂贵，但它是O（1）。
class deque_iterator
{
T* value;
T** block;
…
}
因为value和block都指向连续内存，所以可以实现诸如在恒定时间内查找迭代器之间的距离之类的操作（示例改编自libc++）。
difference_type operator-(deque_iterator const& x, deque_iterator const& y)
{
return (x.block - y.block) * block_size
+ (x.value - *x.block)
- (y.value - *y.block);
}
注意，虽然value不会被诸如push_front和push_back之类的操作无效，但block可能是，这就是为什么deque_iterator会被这样的操作无效的原因。