C++ 将 pop_front 实现到 std::vector 的快速方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9445327/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fast way to implement pop_front to a std::vector
提问by nkint
I'm using some classes and several utility methods that use std:: vector.
我正在使用一些类和几个使用 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).
现在我需要在这些类之一上使用每个帧的 pop_front - push_back 方法（但它们都是链接的，并且一起工作，所以我不能只更改一个）。
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.
大多数操作都是迭代所有元素和 push_back 操作，所以我应该做的最好的工作是：fork 这些类和实用程序的存储库，模板化所有内容，并使用 deque 或 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).
所以我需要建议将一个有效的 pop_front 写入一个静态大小的向量（大小不会改变）。
I've found herea 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?
这两种解决方案中哪个更快？还有其他解决方案吗？
回答by Mankarse
I would expect:
我希望：
template<typename T>
void pop_front(std::vector<T>& vec)
{
assert(!vec.empty());
vec.front() = std::move(vec.back());
vec.pop_back();
}
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:
如果你需要保持 中剩余元素的顺序vec，你可以这样做：
template<typename T>
void pop_front(std::vector<T>& vec)
{
assert(!vec.empty());
vec.erase(vec.begin());
}
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.
这将在 中的元素数量上具有线性时间vec，但这是您可以在不更改数据结构的情况下做的最好的事情。
Neither of these functions will maintain the vectorat a constant size, because a pop_frontoperation will by definitionremove an element from a container.
这些函数都不会将 保持vector在恒定大小，因为根据定义，pop_front操作将从容器中删除元素。
回答by Kerrek SB
Since pop_front()only erases the first element, the direct implementation is this:
由于pop_front()只擦除第一个元素，直接实现是这样的：
template <typename V>
void pop_front(V & v)
{
assert(!v.empty());
v.erase(v.begin());
}
Don't worry about speed for now. If you want to go back and optimize code, ask for dedicated project time.
暂时不要担心速度。如果您想返回并优化代码，请要求专门的项目时间。
回答by 0xPwn
if you just try to erase the first element then in the function use:
如果您只是尝试擦除第一个元素，则在函数中使用：
if (my_vector.size()){ //check if there any elements in the vector array
my_vector.erase(my_vector.begin()); //erase the firs element
}
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:
如果你想模拟整个向量数组的 pop front（你想从头到尾弹出每个元素），我建议：
reverse(my_vector.begin(),my_vector.end()); // reverse the order of the vector array
my_vector.pop_back(); // now just simple pop_back will give you the results
回答by CppPythonDude
I also have a way... Not so good tho..
我也有办法……不太好……
This looks like @0xPwn's solution, but he didn't reverse the vector the second time. You will probably understand this code, so i will not explain it.
这看起来像@0xPwn 的解决方案，但他没有第二次反转向量。你可能会理解这段代码，所以我不会解释它。
#include <algorithm>
#include <vector>
template <typename T>
void pop_front(std::vector<T>& vec){
std::reverse(vec.begin(),vec.end()); // first becomes last, reverses the vector
vec.pop_back(); // pop last
std::reverse(vec.begin(),vec.end()); // reverses it again, so the elements are in the same order as before
}
