如何实现非连续容器(例如std :: deque)的随机访问迭代器？

Question

我理解随机访问迭代器如何对连续容器起作用std::vector:迭代器只是维护一个指向当前元素的指针,并且任何加法/减法都应用于指针.

但是,我对于如何为非连续容器实现类似的功能感到困惑.我对如何std::deque:iterator工作的第一个猜测是,它维护了一个指向它包含的连续内存组的表的指针,但我不确定.

典型的标准库如何实现这一点？

Answer 1

你能满足的了requirememtsstd::deque具有std::vector<std::unique_ptr<std::array<T,N>>>大致。加上低/高水位标记，告诉您第一个/最后一个元素在哪里。（对于定义的 N 可能随 变化的实现T，并且std::arrays 实际上是正确对齐的未初始化内存块而不是std::arrays，但您明白了）。

使用通常的指数增长，但在正面和背面。

查找根本就(index+first)/N和%N找块和子元素。

这比std::vector查找更昂贵，但是是 O(1)。