C++ std::deque 实现:为什么不使用循环缓冲区？

Question

我对双端队列的实现进行了一些搜索。根据this post ，双端队列使用 vector 的 vector 。我知道开始和结束时的推送都应该是恒定的时间，并且还需要随机访问。我认为循环缓冲区满足所有这些要求，而且简单得多。那么为什么不使用循环缓冲区呢？

我还找到了boost circular buffer 。它与双端队列相比如何？

<小时/>

编辑: 好的，所以它与 Iterator Invalidation Rules 有关。 .它指出:

all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected)

我的理解是重载像iter++这样的运算符，迭代器必须拥有一个指向节点映射的指针和一个指向 block 的指针，所以如果节点映射被重新分配，迭代器就会失效。但由于数据永远不会移动，因此引用仍然有效。

Answer 1

循环缓冲区不能无限扩展。最终，您需要分配一个新的项目并将所有项目复制过来。

Deque 可以简单地在之前的 vector 前面分配一个新 vector ，并在其中添加一个“中间”元素。我认为它是 vector 的“智能列表”(即快速push_front()，但可能更快一点随机访问)。