将矢量元素移动到矢量的后面

有没有比擦除元素并将其重新添加到背面更好的方法（更快或更少的代码符号）？将矢量元素移动到矢量的后面

template <typename T> 
void moveItemToBack(std::vector<T>& v, size_t itemIndex) 
{ 
    T tmp(v[itemIndex]); 
    v.erase(v.begin() + itemIndex); 
    v.push_back(tmp); 
}

来源

2014-05-21 Violet Giraffe

不是真的......向量不是一种非常有效的方法来存储需要从开始删除的东西。看看'std :: queue'或'std :: dequeue' – IdeaHat

@MadScienceDreams：std :: dequeue在这里没有更好的，我需要随机访问。 –

然后，要使用的有效结构是制作自己的环形缓冲区。 – IdeaHat

您可以使用标准库中的std::rotate执行此操作。由于这不会更改矢量大小，所以它也不会触发重新分配。你的函数看起来是这样的：

template <typename T> 
void moveItemToBack(std::vector<T>& v, size_t itemIndex) 
{ 
    auto it = v.begin() + itemIndex; 
    std::rotate(it, it + 1, v.end()); 
}

来源

2014-05-21 17:47:01 Blastfurnace

这就是斯捷潘诺夫（设计STL）的建议：http://www.stepanovpapers.com/notes.pdf，pg。 154. –

只需注意：如果我正确读取这个，这具有O（n）的复杂性。下面的std :: swap解决方案的复杂度为O（1）。 – imallett

@imallett你是对的。这个答案不会保留被移动项目以外的元素的顺序，而另一个答案则不会。如上所述，这个问题并不清楚这是否是一项要求。保持秩序是更昂贵的。 – Blastfurnace

您可以避免额外的变量。

v.push_back(v[itemIndex]); 
v.erase(v.begin() + itemIndex);

如果从矢量的中点频繁删除和可以重写你的代码，因此它不需要随机访问，您可以通过使用链表（std::list），而不是提高效率。

来源

2014-05-21 16:59:00 Brian

啊，当然，整洁！谢谢。顺便说一句，在这里使用'emplace_back'而不是'push_back'有什么好处吗？ –

@VioletGiraffe，如果'T'很小，'emplace_back'不可能比'push_back'快。如果'T'很大，我其实不确定。 – Brian

@Brian emplace_back实际上调用了类的构造函数，这会减少到使用此调用的复制构造函数...所以在这种情况下，我认为这对两者都不重要。你可以使用'v.push_back（std :: move（v [itemIndex））'来触发在C++ 11中使用移动构造函数。 – IdeaHat

可能最快的方式，将与最后一个元素

template <typename T> 
void moveItemToBack(std::vector<T>& v, size_t itemIndex) 
{ 
    std::swap(v[itemIndex], v.back()); // or swap with *(v.end()-1) 
}

一个操作来交换吧！ Ofcourse std::swap必须使用T

来源

2014-05-21 19:12:55

这是一个明显的解决方案，但它改变了项目的顺序，而不仅仅是将项目移动到最后。 –

@VioletGiraffe虽然旋转不？ –

@VioletGiraffe现在好了，你有什么想法。只要相对顺序不变，就可以旋转。我只是简单回答了“将一个元素移到后面”的问题 –

将矢量元素移动到矢量的后面

回答

相关问题