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

Question

我正在使用一些类和几个使用std :: vector的实用方法。

现在我需要在其中一个类上使用pop_front - push_back方法的每一帧（但它们都是链接的，并且一起工作所以我不能只改变一个）。

大多数操作都是遍历所有元素和push_back操作，因此我应该做的最好的工作是：分叉这些类和实用程序的存储库，模板化所有内容并使用deque或list。

但这意味着大量的代码重写和大量的测试会让我错过截止日期。

所以我需要建议将高效的pop_front写入静态大小的向量（大小不会改变）。

我找到了here的方式：

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

这两种解决方案的速度有多快？还有其他方法吗？

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操作将根据定义从容器中删除元素。

Answer 2

由于pop_front()只删除了第一个元素，因此直接实现如下：

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

现在不要担心速度。如果您想返回并优化代码，请询问专用项目时间。

Answer 3

你也可以像阵列那样具有快速恒定时间访问操作的IgushArray（https://github.com/igushev/IgushArray），但插入/擦除操作只需要O（N ^ 1/2）时间。因此，在您的情况下，插入到开头将非常有效。注意，结构对reserve（）非常敏感。

template <class T>
void pop_front(IgushArray<T>& v)
{
  if (!v.empty())
    v.erase(v.begin());
}

在您编写的第一个选项中，您违反了元素的顺序。这是一个问题吗？

如果是这样，请使用我写的变体。

如果没有，元素的顺序根本不重要，可能最好使用std :: set或std :: multiset。

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
}

如果你想模仿整个矢量数组的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