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

Question

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

现在我需要在其中一个类上使用pop_front - push_back方法的每一帧(但它们都是链接的,并且一起工作所以我不能只更改一个).

大多数操作都是遍历所有元素和push_back操作,因此我应该做的最好的工作是:分叉这些类和实用程序的存储库,模板化所有内容并使用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());
}

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

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

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