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

Question

我了解随机访问迭代器如何为 std::vector 这样的连续容器工作:迭代器只是维护一个指向当前元素的指针，任何加法/减法都应用于该指针。

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

典型的标准库将如何实现它？

Answer 1

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

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

查找只是做 (index+first)/N和 %N找到 block 和子元素。

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