快速实现std::vector的pop_front方法的方法

Question

我正在使用一些类和多个实用方法，它们使用 std::vector。现在我需要在这些类中的一个上每帧使用 pop_front - push_back 方法（但它们都是链接的，共同工作，所以我不能只更改一个）。大多数操作都是迭代所有元素和 push_back 操作，因此我应该做的最好的工作是：fork 这些类和实用程序的存储库，将所有内容模板化，并使用 deque 或 list。但这意味着要重写大量代码并进行大量测试，这将使我错过截止日期。因此，我需要建议如何对静态大小的向量编写有效的 pop_front（大小不会更改）。我在这里找到了一种方法：

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?
}

另一个想法应该是：

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());
}

这两个解决方案中哪个更快？还有其他的解决方案吗？

- nkint

---

“大小不会改变”是什么意思？执行pop_front操作后，向量的大小是否与之前相同？如果是这样，最后一个元素应该是垃圾吗？ - Vaughn Cato

向量的大小相同，因为在弹出一个元素后我立即进行了推入操作。每个帧中，我都在同一个方法中进行了一次弹出和一次推入操作，因此在该方法之前和之后，向量的大小是相同的。 - nkint

在担心速度之前，要担心“正确性”。就算你的速度再快，如果你得到的结果是完全错误的，那么速度也毫无意义。据我所知，你提供的两个候选方案都是错误的。第一个应该被命名为 pop_back_and_overwrite_front_with_penultimate，第二个应该被命名为 invoke_undefined_behavior_and_pop_back。（在向 vec1.begin() 写入内容时行为是未定义的，因为 vec1 是空的；你需要写成 vec1.resize(vec.size() - 1) 而不是 vec1.clear()）。当我处理向量操作时，有时我会画个图，也许这对你有帮助。 - Rob Kennedy

听说过std::deque吗？它和std::vector一样好用，但可以使用pop_front()函数。 - Sebastian Mach

@SebastianMach 我也在寻找同样的东西。与std::vector不同，std::deque不是连续的内存。 - JustWe

Answer 1

我期望：

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

这可能是最有效的方法，但是它不能保持向量中元素的顺序。

如果您需要保持vec中剩余元素的顺序，可以这样做：

template<typename T>
void pop_front(std::vector<T>& vec)
{
    assert(!vec.empty());
    vec.erase(vec.begin());
}

这将以vec中元素数量的线性时间运行，但在不改变数据结构的情况下，这是你能做到的最好的。

这两个函数都不会保持vector的大小恒定，因为pop_front操作根据定义将从容器中删除一个元素。

- Mankarse

---

我认为假定顺序必须被保留，因为std::vector::pop_back会保留顺序。 - HelloGoodbye

在这之后加入vec.push_back(new_value)和vec.shrink_to_fit()不是更好吗？ - Jorrit Smit

Answer 2

因为pop_front()只删除第一个元素，所以直接实现如下:

template <typename V>
void pop_front(V & v)
{
    assert(!v.empty());
    v.erase(v.begin());
}

现在不用担心速度问题。如果你想回头优化代码，请申请专门的项目时间。

- Kerrek SB

---

抱歉，我不理解你的代码，它不应该只保留第一个元素吗？我想要删除的只是第一个元素，难道不应该是：v.erase(v.begin(), v.begin()+1);？ - nkint

Answer 3

我也有一种方法...不过不是很好...

这看起来像是@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

}

- CppPythonDude

---

还能更无效吗？ - Kennet Celeste

Answer 4

如果你只是想要删除第一个元素，那么在函数中使用以下代码：

if (my_vector.size()){ //check if there any elements in the vector array
    my_vector.erase(my_vector.begin()); //erase the firs element
}

如果您想模拟整个向量数组的弹出操作（即从开始到结束弹出每个元素），我建议使用以下方法：

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

- 0xPwn