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

Question

我对deque的实现进行了一些搜索.根据这篇文章,deque使用向量的向量.我知道在开始和结束时推送应该是恒定的时间,并且还需要随机访问.我认为循环缓冲区满足所有这些要求,并且更加简单.那么为什么不使用循环缓冲区？

我还发现了增强循环缓冲区.它与deque相比如何？

---

编辑:好的,所以它与迭代器失效规则有关.它指出:

所有迭代器和引用都是无效的,除非插入的成员位于双端队列的末尾(前面或后面)(在这种情况下,所有迭代器都无效,但对元素的引用不受影响)

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

Answer 1

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

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