为什么矢量前没有推/弹？

Question

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

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

但我认为并非总是如此.考虑到如果我们<vector>用循环数组实现,我们可以O(1)从向量的前端和尾端实现推/弹,而不会失去O(1)随机访问的能力.所以我个人认为没有任何理由,而不仅仅是一个不实施push_front/ pop_frontfor 的小额开销<vector>.有什么想法吗？

Answer 1

我们已经在STL中描述了一些内容.它被命名deque.

正如你所写,实际上有一些开销.因此,如果您需要此功能并且开销没有问题,请使用deque.如果你不需要它,你不需要开销,所以最好有一些避免这种开销的命名vector.

并且作为补充:vector保证其所有元素都存储在连续的存储位置,因此您可以应用指针算法.循环缓冲区不是这种情况.

Answer 2

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

你是绝对正确的,push_front无法快速运行,因为除了可能的重新分配之外,所有项目都需要被一个位置复制.这为n个对象提供了O(n ²)的摊销性能,这不是图书馆设计者想要鼓励的.

考虑到如果我们<vector>用圆形数组实现

使用圆形数组实现向量使得实现几个对于向量必须为true的重要保证变得更加困难.例如,vector必须保证如果迭代器a指向索引低于迭代器的元素b,那么a < b.当vector是线性的时,比较归结为比较迭代器a和b指向的元素的地址.使用循环数组实现时,需要考虑向量原点的地址,现在它可以位于已分配的内存块的中间.

另一个保证会被违反的是:

如果v是a vector<T>,T是除了之外的任何类型bool,以及n介于0和向量大小之间的数字,则&v[n] == &v[0] + n标识必须为true.

这不能用圆形数组实现.

Answer 3

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

同时，您可以devector根据向量创建一个模板（？），其中：

• 有一个pre_capacity_初始化为 0 的字段和一个 getterpre_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()
• 将所有其余方法委托给vector

或者您可以只跟踪已推入/从前面弹出的元素数量:)。