向量中擦除<n複雜度的元素

Question

我需要擦除排序向量中的元素，同時抑制等於或大於n的複雜度。我知道vector . erase方法會消除它，但它的複雜性是n。我可以用最後一個元素重寫那個結構元素，然後使用回彈刪除最後一個應該是常量的方法，但問題是它不會保持排序，所以我不得不重新排序。它甚至有可能解決這個問題並保持低於n的複雜度？

Answer 1

既然你需要它排序，std::vector（據我所知）沒有解決方案。但是，std::vector似乎並不適合您的情況。 std::list是你的一個選擇（可能會更好）。

從該參考文獻：http://www.cplusplus.com/reference/list/list/erase/

複雜

線性在擦除元素的數量（破壞）。

這意味着它將調用析構函數N次，其中N是要刪除的項目數。所以，它是刪除項目的數量（不是std::list項目數量）線性關係

Answer 2

如果您必須保持您的數據結構排序，並能夠從中間擦除元素（s）具有高性能，更好地用另一個容器替換vector（例如set，multiset）？