快速的方式来实现pop_front到std :: vector [英] fast way to implement pop_front to a std::vector

问题描述

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

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

大多数操作都是遍历所有元素和push_back操作，所以我应该做的最好的工作是：fork这些类和实用程序的存储库，模板一切，使用deque或列表。

但这意味着很多代码重写和很多测试，这将使我错过的截止日期。

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

我找到这里的方法：

  template< typename T> 
 void pop_front（std :: vector< T>& vec）
 {
 vec.front（）= vec.back 
 vec.pop_back（）; 
 vec.front（）= vec.back（）; //但是这应该工作吗？ 
} 
  

另一个想法应该是：

  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（））; 
} 
  

这两个解决方案的速度更快？任何其他解决方案？

解决方案

我会期望：

  template< typename T> 
 void pop_front（std :: vector< T>& vec）
 {
 assert（！vec.empty（））; 
 vec.front（）= std :: move（Vec.back（））; 
 vec.pop_back（）; 
} 
  

是最有效的方法，但它不维护

如果您需要维护 vec 中剩余元素的顺序，您可以：

 模板< typename T& 
 void pop_front（std :: vector< T>& vec）
 {
 assert（！vec.empty（））; 
 vec.erase（vec.begin（））; 
} 
  

这将具有 vec ，但它是最好的，你可以做而不改变你的数据结构。

这些函数都不会保持 vector 以常量大小，因为 pop_front 操作将按定义从容器中删除一个元素。 / p>

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?

解决方案

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:

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.

Neither of these functions will maintain the vector at a constant size, because a pop_front operation will by definition remove an element from a container.

这篇关于快速的方式来实现pop_front到std :: vector的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！