Why there is no pop_front method in C++ std::vector?

Question

Why there is no pop_front method in C++ std::vector?

Solution 1

Because a std::vector has no particular feature regarding inserting elements at the front, unlike some other containers. The functionality provided by each container makes sense for that container.

You probably should be using a std::deque, which is explicitly good at inserting at the front and back.

Check this diagram out.

Solution 2

Although inefficient on large vectors, the following is equivalent to a pop_front() for a std::vector

vec.erase(vec.begin());

As stated in other answers, std::vector is not designed to remove the first element and will require to move/copy all remaining elements. Depending on the specific use case, it might be convenient to consider other containers.

Solution 3

Because push_back and pop_back are special operations for a vector that require only O(1) computation. Any other push or pop takes O(n).

This is not a "bug" or a "quirk", this is just a property of the vector container. If you need a fast pop_front consider changing to an other container.

Solution 4

However, if you need a pop_front and do NOT care about the index of the elements in the vector, you can do kind of a pop_front with something like

template<typename T>
void pop_front(std::vector<T>& vec)
{
   vec.front() = vec.back();
   vec.pop_back();
}

Dan Higgins talks about this too: https://youtu.be/oBbGC-sUYVA?t=2m52s

Solution 5

Probably because it would be monumentally slow for large vectors.

pop_front() on a vector containing 1000 objects would require 999 operator=() calls.

View more solutions

Comments

[orlp]

Not any slower then erase(v.begin()). It's because vectors have no special properties for pushing in the beginning, opposed to pushing at the end (or popping).

[ildjarn]

Specifically, consider changing to std::deque<> if you need fast pop_front().

[Steve Jessop]

"requires only O(1) computation" - amortized O(1) in the case of push_back, worst case is Theta(n) when it has to reallocate because you haven't reserved the space.

[Roddy]

@nightcracker - True, erase() is equally bad. And I agree that wanting pop_front() on a vector is a good 'smell' that you're using the wrong type of container!

[orlp]

I left out allocation in this example because the user was talking about popping. You are right though.

[deceleratedcaviar]

Naturally it would have to do a re-allocation, but why would that be O(n) in comparison to a re-allocation of 'push_back'

[MSalters]

It would be a weird case where you both did and did not care about the order of elements. Because if you really didn't care, this is even easier: template<typename T> void pop_front(std::vector<T>& v) { v.pop_back(); }

[Lightness Races in Orbit]

@Daniel: Because push_back doesn't always have to re-allocate.

[marchelbling]

Your comment seems wrong to me. By doing template<typename T> void pop_front(std::vector<T>& v) { v.pop_back(); } you would not remove the expected front element. My suggestion is to "swap" front and back elements and remove the last one.

[marchelbling]

Also, using a vector when not deeply caring about elements order may happen if you want to manipulate a continuous buffer of memory. I'm not arguing wether this is a good idea or not but in this very specific (and specified) case, it is a valid way of doing a pop_front in O(1).

[Jonathan.]

Why couldn't pop_front be O(1)? You'd just advance the pointer to the start of the array by one element?

[orlp]

@Jonathan. You can, but not using the same implementation as a regular vector, there is more logic there. See github.com/orlp/devector (implementation is not finished, but the concept is there.)

[Super-intelligent Shade]

pretty clever, but mostly useless :) +1 from me

[Lightness Races in Orbit]

@Jonathan. Something like a deque does that, but the end result is that it has to work a bit differently if you don't want to end up with your whole computer's memory allocated but no longer used... which is why deque exists... which is why deque has pop_front.

[Alexis Wilke]

@marchelbling I think this is an O(2) since you have a copy + an erase. I think it is a clever way of doing it if you use a vector just to hold N items and not to hold N items in a specific order.

[Alexis Wilke]

This works but it's not going to be efficient on large vectors.

[marchelbling]

@AlexisWilke indeed that's 2 O(1) operations which is equivalent to O(1) or said differently no matter the size of the vector, we can perform the pop_front in a constant time.

[quetzalcoatl]

What MSalters referred to is that this code you proposed effectively ensures that any later other front-reading operations will actually read at the tail. Keep using this pop_front, and they keep consuming the vector from behind. Except for the very first element when pop_front was never called yet and the consumers actually got true front. So, if to follow your words and if to really "not care about the order", then why care about popping the first element from front? Just read back() and pop_back() already from the very beginning. en.wikipedia.org/wiki/Principle_of_least_astonishment

[marchelbling]

Thank you for your comment. As emphasized in bold in my original answer, I'm just providing a O(1) deletion of a vector element. As your answer implies, this could actually be for any position in the vector. Again, I'm not saying this is a good idea but I just plain disagree if people assume that a vector order is necessarily important. Cache friendliness may also be important.

[AnotherDeveloper]

Nice diagram there but that's all black hard to comprehend

[Rasmus Dall]

This doesn't really explain why there is no pop_front() method, it only talks about insertion. How does inserting elements relate to popping elements?

[cpchung]

would be nice if there is way to fix the diagram.

[Swastik Singh]

what will be the time complexity of this btw?

[OwnageIsMagic]

@SwastikSingh O(n)

[Alexis Wilke]

The question was not "how do I do that?" but "why is there no such function?" ...

[Alexis Wilke]

Note that you say "inserting", the OP asked about "pop_front()" which, if I'm correct, is deleting/removing (erasing). Not inserting.