c++ - 带圆形数组的向量实现

Question

我很困惑。我正在阅读有关使用数组实现向量的内容。当我们使用简单的动态数组实现时，一切都很好。

有人提到，您可以通过以循环方式使用数组来实现向量，这将使元素的添加和删除（第一个和最后一个）在恒定时间内运行。这不是链表应该做的吗？

我想知道它是如何工作的，但我真的找不到实现或正确的解释。欢迎任何关于什么是一般想法以及如何实施它的信息。

编辑：我的猜测是新数据应该写在“最旧的”数据上，并且数组具有固定大小，并且您必须有一个变量来存储最后使用的位置。

Answer 1

由于 C++03vector保证连续存储，也就是说对于 each 0 <= n < vec.size()：

&vec[n] == &vec[0] + n

这意味着您不能使用循环缓冲区来实现vector. 在您从缓冲区的末尾“环绕”到开头时，您违反了此限制。

如果您认为它operator[]可以返回一些满足此要求的重载代理operator&- 不，它不能，它需要 return T&。

除了这个要求之外，我认为标准中没有任何内容可以防止vector使用循环缓冲区实现。在缓冲区已满的情况下，您vector实际上会做同样的事情——重新分配到更大的缓冲区。行为上的唯一区别是在开始时擦除或插入时会发生什么。使用循环缓冲区，假设有足够的空间，所有其他元素将保持静止，而通常它们都会移动。但是标准并没有明确要求它们移动，并且由于在开始插入或擦除时迭代器和对所有元素的引用都无效，因此程序不能合法地依赖它们以任何特定方式移动。

确实std::list可以在恒定时间内在开始和结束处插入和删除。所以可以std::deque。

Answer 2

你在谈论循环缓冲区

不幸的是，您无法使用它来实现向量，因为您将无法在中间插入或从中间删除等。