I'm using some classes and several utility methods that use std::vector.
Now I need to use each frame a pop_front - push_back method on one of those classes (but they are all linked, and work together so I can't change only one).
Most of the operations are iterate over all element and push_back operations, so what I should do for the best work is: fork the repository of those classes and utilities, template everything and use deque or list.
But this means a lot of code rewriting and a lot of testing that will make me miss the deadline.
So I need advice to write an efficient pop_front to a static-size vector (the size will not change).
I've found here a way:
template<typename T>
void pop_front(std::vector<T>& vec)
{
vec.front() = vec.back();
vec.pop_back();
vec.front() = vec.back(); // but should this work?
}
And another idea should be:
template<typename T>
void pop_front(std::vector<T>& vec, already_allocated_vector vec1)
{
vec1.clear();
copy(vec.begin(), vec.end()-1, vec1.begin());
copy(vec1.begin(), vec1.end(), vec.begin());
}
What is the faster of these two solutions? Any other solutions?
Since
pop_front()
only erases the first element, the direct implementation is this:Don't worry about speed for now. If you want to go back and optimize code, ask for dedicated project time.
if you just try to erase the first element then in the function use:
if you want to emulate pop front for the entire vector array ( you want to keep pop out every element from start to end) , i suggest on:
You can also IgushArray ( https://github.com/igushev/IgushArray ) which like an array has fast constant-time access operation, but insert/erase operation takes only O (N^1/2) time. So, in your case inserting to the beginning would be very effective here. Be careful, the structure is very sensitive for reserve().
In first option you wrote you violate the order of elements. Is it an issue?
If so, use the variant I wrote.
If not and order of elements doesn't matter at all, may be it's better to use std::set or std::multiset.
I would expect:
to be the most efficient way of doing this, but it does not maintain the order of the elements in the vector.
If you need to maintain the order of the remaining elements in
vec
, you can do:This will have linear time in the number of elements in
vec
, but it is the best you can do without changing your data structure.Neither of these functions will maintain the
vector
at a constant size, because apop_front
operation will by definition remove an element from a container.