我需要擦除排序向量中的元素,同時抑制等於或大於n的複雜度。我知道vector . erase
方法會消除它,但它的複雜性是n。我可以用最後一個元素重寫那個結構元素,然後使用回彈刪除最後一個應該是常量的方法,但問題是它不會保持排序,所以我不得不重新排序。它甚至有可能解決這個問題並保持低於n的複雜度?向量中擦除<n複雜度的元素
3
A
回答
3
既然你需要它排序,std::vector
(據我所知)沒有解決方案。但是,std::vector
似乎並不適合您的情況。 std::list
是你的一個選擇(可能會更好)。
從該參考文獻:http://www.cplusplus.com/reference/list/list/erase/
複雜
線性在擦除元素的數量(破壞)。
這意味着它將調用析構函數N次,其中N是要刪除的項目數。所以,它是刪除項目的數量(不是std::list
項目數量)線性關係
+1
感謝您的回答。 – kvway
3
如果您必須保持您的數據結構排序,並能夠從中間擦除元素(s)具有高性能,更好地用另一個容器替換vector(例如set,multiset)?
+0
使用set/multiset的@kvway可能是您需要的,因爲使用列表您可以訪問一個元素的O(n)成本。 – ead
相關問題
- 1. 結構向量的擦除元素
- 2. 向量的餘弦相似度,與<爲O(n^2)複雜
- 3. 函數中的向量中的擦除元素
- 4. 擦除程序中的矢量元素
- 5. 擦除元素
- 6. 是否vector ::擦除向量中的重新排序元素?
- 7. 使用算法擦除向量中的特定元素
- 8. 如何內雙擦除向量元素的循環
- 9. 如何擦除C++映射中的最後n個元素?
- 10. K-個元素N * N和向量
- 11. C++ std ::向量擦除元素0拋出異常
- 12. 2^n複雜度算法
- 13. vector :: erase不會擦除所需的元素,而是會擦除矢量中的最後一個元素
- 14. 增加比較向量元素的運行時複雜度的效率?
- 15. C++向量擦除檢查
- 16. 如何用`std :: set`中的反向迭代器擦除元素?
- 17. 八度複雜元素操作
- 18. 移除向量元素使用向量中的條件<bool>
- 19. C++在for_each期間從擦除元素中刪除元素
- 20. 通過判斷該向量的元素來擦除2d向量C++的一個向量
- 21. unordered_set <int> :: iterator it + n的時間複雜度是多少?
- 22. 查找向量中的重複元素
- 23. Matlab:向量中重複的元素塊
- 24. 從對象的矢量按值擦除矢量元素
- 25. 如何擦除物體矢量中的元素?
- 26. 如何從向量中刪除元素<char>?
- 27. matlab:如何將複雜的雙元素向量轉換爲24位向量(每個元素)?
- 28. 遞歸重複向量元素N次每個
- 29. STD向量的擦除和的push_back
- 30. C++矢量元素擦除與新矢量創建
不能做。或者a。)使用另一個數據結構b。)批量移除元素(參見擦除 - 刪除習慣用法)c。)將元素標記爲未使用 – milleniumbug
將元素標記爲未使用對我來說不是正確的選項,它會吃掉大量內存。 – kvway
在嘗試進行任何更改之前,請確保您**測量性能**。在現代硬件上,它往往需要令人驚訝的大的N來使向量的性能超過其他容器類型。 –