將矢量元素移動到矢量的後面

有沒有比擦除元素並將其重新添加到背面更好的方法（更快或更少的代碼符號）？將矢量元素移動到矢量的後面

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現在好了，你有什麼想法。只要相對順序不變，就可以旋轉。我只是簡單回答了「將一個元素移到後面」的問題 –

將矢量元素移動到矢量的後面

回答

相關問題