Why there is no pop_front method in C++ std::vector?
C++VectorC++ Problem Overview
Why there is no pop_front
method in C++ std::vector
?
C++ Solutions
Solution 1 - C++
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 - C++
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 - C++
vector
struct
{
T* begin; // points to the first T in the vector
T* end; // points just after the last T in the vector
int capacity; // how many Ts of memory were allocated
};
"begin" serves double-duty as "pointer to the first T in the vector" and "pointer to all the memory we allocated." therefore it's impossible to "pop" elements off the front of the vector by simply incrementing "begin" - do this and you no longer have a pointer to the memory you need to deallocate. that would leak memory. so a "pop_front" would need to copy all the Ts from the back of the vector to the front of the vector, and that is comparatively slow. so they decided to leave it out of the standard.
what you want is something like this:
struct
{
T* allocated; // points to all the memory we allocated
T* begin; // points to the first T in the vector
T* end; // points just after the last T in the vector
int capacity; // how many Ts of memory were allocated
};
with this, you can "pop_front" by moving "begin" forward and backward with no danger of forgetting which memory to deallocate later. why doesn't std::vector
Solution 4 - C++
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 5 - C++
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 6 - C++
Probably because it would be monumentally slow for large vectors.
pop_front()
on a vector containing 1000 objects would require 999 operator=()
calls.
Solution 7 - C++
#define push_front(v,val) v.insert(v.begin(), 1, val);
#define pop_front(v) if(!v.empty())v.erase(v.begin());
You can directly write this and use this
push_front(vec,val);
pop_front(vec);
Solution 8 - C++
Vector seems like a stack container, we have a stack to store data.
So we just pop_back
not to pop_front
.
If you want to pop_front
, std::list
may be a better choice for you. Cause it is a bi-direction like queue structure.