为什么在向量前面没有推送/弹出? [英] Why no push/pop in front of vector?

问题描述

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

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

但是我认为并非总是如此.考虑到如果我们使用圆形数组实现< vector> ，则可以从矢量的前部和尾部实现 O(1)推送/弹出，而不会失去功能 O(1)随机访问.因此，就我个人而言，我不能想到任何原因，而不仅仅是为实现< vector> 的 push_front / pop_front 的一小笔开销.有什么想法吗?

解决方案

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

您完全正确， push_front 无法快速运行，因为除了可能的重新分配外，所有项目都需要一个位置复制.这为您提供了n个对象的O(n ² )摊销性能，这不是库设计师想要鼓励的.

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

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

另一个可能被违反的保证是:

当 v 是 vector< T> 时， T 是除 bool 和 n 介于零和向量大小之间的数字，& v [n] ==& v [0] + n 身份必须为真.

这不能用圆形数组实现.

In C++, STL, we have template class <vector>. We know that it supports O(1) random access, and tail modification. My question is why we don't define push_front, or pop_front in <vector>?

One explanation is that if we want to push/pop element in the front of a vector, we must shift each element in the array by one step and that would cost O(n).

But I think that is not always the case. Considering that if we implement <vector> with circular array, we can achieve O(1) push/pop from both front and tail of the vector, without losing the ability of O(1) random access. So personally I can not think of any reason rather than just a minor overhead not to implement push_front/pop_front for <vector>. Any thoughts?

解决方案

One explanation is that if we want to push/pop element in the front of a vector, we must shift each element in the array by one step and that would cost O(n)

You are absolutely right, push_front has no way to run quickly, because, in addition to a possible reallocation, all items need to be copied by one position. This gives you an amortized performance of O(n²) for n objects, which is not something that library designers wanted to encourage.

Considering that if we implement <vector> with circular array

Implementing vector with circular array makes it a lot harder to implement several important guarantees that must be true for a vector. For example, vector must guarantee that if iterator a points to an element with a lower index than iterator b, then a < b. When vector is linear, the comparison boils down to comparing addresses of elements to which iterators a and b are pointing. With a circular array implementation one would need to take the address of the vector origin into consideration, which can now be in the middle of the allocated block of memory.

Another guaranteed that would be violated is this:

When v is a vector<T>, T is any type other than bool, and n a number between zero and vector's size, &v[n] == &v[0] + n identity must be true.

This cannot be implemented with a circular array.

这篇关于为什么在向量前面没有推送/弹出?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！