我了解随机访问迭代器如何为类似std::vector的容器工作：迭代器仅维护指向当前元素的指针，并且任何加法/减法都会应用于该指针。
但是，我对于如何为非连续容器实现类似功能感到困惑。我对std::deque:iterator工作方式的第一个猜测是，它维护着一个指向它所包含的连续内存组的某些表的指针，但是我不确定。
典型的标准库将如何实现呢？
你能满足的了requirememtsstd::deque具有std::vector<std::unique_ptr<std::array<T,N>>>大致。加上低/高水位标记，告诉您第一个/最后一个元素在哪里。（对于定义为N的实现，它可能随而变化T，并且std::arrays实际上是正确对齐的未初始化内存的块，而不是std::arrays，但是您可以理解）。
使用通常的指数增长，但同时在正面和背面。
查找只是简单地进行操作(index+first)/N并%N找到block和sub元素。
这比std::vector查找要贵，但是是O（1）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句