Why no push/pop in front of vector?

Question

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?

Answer 1

We already have something as you describe in the STL. It is named deque.

As you wrote there IS actually some overhead. So if you need this functionality and you have no problem with the overhead, use deque. If you do not require it, you do not want the overhead, so it is better to have something that avoids this overhead, named vector.

And as an addition: vector guarantees that all its elements are stored in contiguous storage locations, so you can apply pointer arithmetic. This is not the case for a circular buffer.

Answer 2

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.