为什么vector没有push/pop在前面？

Question

在C++的STL中，我们有一个模板类 <vector>。我们知道它支持O(1) 的随机访问和尾部修改。我的问题是为什么我们不在<vector>中定义push_front或pop_front？

一个解释是，如果我们想要在vector的前面推入/弹出元素，则必须将数组中的每个元素向前移动一步，这将花费O(n)的时间。

但是我认为这并非总是如此。考虑到如果我们使用循环数组来实现<vector>，我们可以从向量的前面和尾部同时实现O(1)的推入/弹出，而不会失去O(1)随机访问的能力。因此，我个人无法想到任何原因，除了轻微的开销外，不实现<vector>的push_front/pop_front。您有什么想法？

- Taylor Huang

---

它被设计成现在这样的。就是这样了，没什么好说的。 - Ed Heal

处理循环缓冲所需的计算开销不值得思考吗？这不仅仅是关于O()，还涉及实际的现实性能。 - Sami Kuhmonen

由于标准设置的限制，我们无法将std::vector定义为循环的。 - Tommy Andersen

让容器易于被误用是毫无意义的。如果你真的非常需要，可以自己动手制作。这并不难。 - xaxxon

Answer 1

我们已经在STL中有了像你所描述的东西。它被命名为deque。

正如你所写，实际上确实存在一些开销。因此，如果你需要这个功能并且不介意开销，请使用deque。如果你不需要它，你不想要这个开销，那么最好有一些避免这个开销的东西，它被命名为vector。

另外，vector保证存储在连续存储位置中的所有元素，因此可以应用指针算法。而对于循环缓冲区，情况并非如此。

- koalo

---

哦，我想deque确实是我在寻找的东西。 我曾经认为deque不支持O（1）随机访问，我想我错了。 :) - Taylor Huang

好的谢谢。 我认为这很有帮助，但是@dasblinklight指出了我的许多缺点，所以我想我会选择他的作为被接受的答案，但您的回答也很有帮助。 :) - Taylor Huang

Answer 2

一个解释是，如果我们想要在向量的前面推/弹出元素，则必须将数组中的每个元素移动一步，这将花费O(n)。

您说得对，push_front没有快速运行的方法，因为除了可能会重新分配外，所有项都需要向前复制一个位置。这给您提供了O(n^2)的摊销性能，其中n个对象，这不是库设计人员想要鼓励的东西。

考虑到如果我们用环形数组实现 使用循环数组实现向量使得实现必须满足向量必须成立的几个重要保证更加困难。例如，向量必须保证，如果迭代器" a "指向比迭代器" b "具有较低的索引的元素，则a < b.当向量是线性的时，比较归结为比较迭代器"a"和"b"所指向的元素的地址。使用循环数组实现时，需要考虑向量起点的地址，它现在可以位于分配的内存块的中间。

另一个将被违反的保证是：

当v是vector、T是除bool之外的任何类型，n是介于零和向量大小之间的数字时，&v [n] == &v [0] + n身份必须为真。

这不能用循环数组实现。

- Sergey Kalinichenko

---

我认为比较迭代器实际上可以很容易地实现。例如，我们可以取特定指针到开始指针之间的距离的余数，然后进行比较。这样做会在实现中引起问题吗？ - Taylor Huang

@TaylorHuang 这当然可以实现，但它会使向量远离成为良好的数组替代品。按设计，向量提供极低的开销；循环数组在性能方面接近，但仍不是免费的。对于库设计者来说，添加元素到前面的灵活性并不能证明做出任何性能牺牲是值得的。 - Sergey Kalinichenko

哦，好的，而且这也违反了一些协议，我想我当时没有想得很清楚。 - Taylor Huang

Answer 3

实际上，这是一个可行的要求。据我所知，标准中没有规定向量不能在元素之前拥有缓冲区（v.prefix_capacity()），就像之后一样（v.capacity() - v.size()）。这可以保证 v.push_front() 和 v.push_back() 的运行时间相同，同时对于那些不使用它的人来说没有任何成本。此外，这可以保证 O(1) v.pop_front()，尽管会使迭代器无效。想写一个提案吗？

与此同时，您可以创建一个基于向量的模板（devector？），其中：

- 有一个初始化为0的字段pre_capacity_和获取器pre_capacity() - 实现pre_reserve(size_t i)，其中包括以下两个调用:

reserve(capacity() - pre_capacity_ + i) pre_capacity_ += i - 实现operator[](size_t i)，并委托给v[i + pre_capacity()] - 实现at(size_t i)，并委托给v.at(i + pre_capacity()) - 实现begin()，并委托给v.begin() + pre_capacity() - 将所有其他方法委托给向量

或者您可以跟踪您从前面推送/弹出的元素数量 :).

- lorro

---

我认为这样的通用容器会很有帮助，比如'deque'，不是吗？ :) 但是对于这样的协议呢： ''' 当v是vector<T>，T是除bool以外的任何类型，n是0到vector大小之间的数字时，&v[n] == &v[0] + n标识必须成立。 ''' 在元素之前加入缓冲区，如何满足这样的保证？ - Taylor Huang

我正在开发一种名为devector的数据结构。不过实现还没有完成（我真应该有一天把它完成）。 - orlp

@TaylorHuang：请注意，push_front() 会使迭代器失效。因此，在不重新分配内存的情况下进行 push_front() 操作时，&v[0] 可能会减少。可以这样想：重新分配内存是在当前缓冲区之前 sizeof(T) 字节处完成的。 - lorro

@lorro 好的，我明白了。但是这样会有问题吗？我的意思是，如果没有重新分配内存，迭代器是否必须始终指向同一个索引是受标准管控的呢？迭代器保持在相同地址似乎也是有道理的。 顺便问一下，你所谓的“devector”和“deque”有什么区别？它们似乎是一样的。 - Taylor Huang

@TaylorHuang：deque 不需要连续地分配成员。一个流行的 deque 实现是数组向量，除了最后一个数组外，所有数组都有相同数量的元素。vector 很好，因为它是连续的；实际上，v.data() 或 &v[0] 是一个可变长度数组。我们想要保持这个属性；它只需要一个 size_t 每个 vector。 - lorro

Answer 4

实现de-vector有两个挑战：

• 保持O(1)的随机访问（不像：deque）。
• O(1)的推送操作，可以在前面或后面完成（这是deque的好处）。

通过以下方式都能实现：

• 实现一个继承自std::vector的devector类。因此，我们可以使用std::vector API，并且只需要重写需要重写的方法。
• 继承的向量（基类）将用于常规push_back插入。
• devector类还将具有一个私有的std::vector成员变量，让我们称之为front_insertions。
• 向devector中的任何push_front操作，都将执行对front_insertions（私有成员向量）的push_back操作。
• devector的大小将是两者大小之和：继承的向量和front_insertions的大小。
• 对索引i的元素进行随机访问，将按以下方式实现： 如果front_insertions为空，则直接重复使用继承的随机访问方法。 如果i < front_insertions.size()，则访问front_insertions[front_insertions.size() - 1 - i]。否则，我们访问继承向量的[i-front_insertions.size()]。
• 显然，还可以覆盖一些其他的std::vector 方法，如emplace_back、emplace_front、at等等。 我专注于保留O(1)的随机访问和同时推送到两侧的功能。

- Ori