如何在刪除元素時防止對std :: unordered_map進行重新散列？

我有一個std :: unordered_map，我將通過迭代去除元素。如何在刪除元素時防止對std :: unordered_map進行重新散列？

auto itr = myMap.begin(); 
while (itr != myMap.end()) { 
    if (/* removal condition */) { 
     itr = myMap.erase(itr); 
    } else { 
     ++itr; 
    } 
}

我想阻止地圖進行任何昂貴的操作，直到我做刪除所有我需要刪除的元素。我有一個有效的關注嗎？我誤解了內部存儲的工作原理嗎？

來源

2012-12-05 vmrob

無序容器從一個erase期間重散列禁止的。REQ]/P14：

的erase成員應到失效只迭代器和引用被擦除的元件，並且保持未擦除的元件的相對順序。

[unord.req]/P9：

換湯不換藥無效迭代器，改變要素之間的排序，並...

你的代碼是罰款的。

來源

2016-11-30 16:03:59

我知道4年後我們看到了這個問題，但我很高興看到這個答案進入混合。再次查看文檔，很明顯，最糟糕的複雜性不是來自潛在的重新哈希，而是來自哈希碰撞。我認爲這是正確的答案。 – vmrob

所以表只能增長。 –

無序容器中的桶數永遠不會在'erase'下縮小。這個數字可以在'rehash'下縮小，所有的實現都會這樣做。 –

據我所知，std::unordered_map被允許重新散列上erase(itr)：

C++ 11表103 - 無序關聯容器要求

a.erase(q)

擦除元件指出到由q。返回值是迭代器緊接在刪除之前的q 之後。

平均情況 O(1)，最壞情況 O(a.size())

這將因此似乎是你有一個有效的關注。至於解決的話，我可以建議幾種途徑：

確保它是一個實際的問題，而不是一個假設。剖析應用程序，查看C++庫的源代碼等。
如果這是實際問題，請考慮使用不同的容器或不同的算法。
考慮通過與每個元素相關的布爾標誌簡單地標記要刪除的元素，並不時清除已刪除的元素，從而攤銷成本。
請考慮使用加載因子進行試驗，如註釋中的@amit所示。儘管容器仍然可以採用O(a.size())時間擦除元素，但不同的加載因素可能會影響應用程序的實際性能。

來源

2012-12-05 19:24:22 NPE

儘管內容豐富且相關 - 它並沒有回答這個問題：'如何防止在移除元素時重新調整std :: unordered_map？' – amit

@amit：如果您在行之間讀取，它會（對此的答案確切的問題是，你不能:)） – NPE

不知道你不能，你可以將max_load_factor設置爲一個虛構的高值，稍後重新設置爲正常大小。我找不到在文檔中證實這一點的任何東西（因此沒有發佈答案） - 但我懷疑它會使您能夠控制rehashes，並且最多隻有2. – amit

我不知道它會工作，我沒有找到文檔中爲它的確認 - 但如果unordered_map根據經典的哈希表的數據結構，你可以set the max_load_factor到一個非常高的老調重彈值，並在完成後將其重置爲正常（這將觸發重新散列）（或者，如果可以預測將刪除多少個元素，則將其重新設置爲預測值）。

在經典哈希表方面，它應該在自減少表發生重新散列時起作用，當尺寸小於1/max_load_factor時。

（不確定它是在C++中的情況，但我認爲它會刺激嘗試，因爲它很容易實現）。

[unord：

來源

2012-12-05 19:35:46 amit

如何在刪除元素時防止對std :: unordered_map進行重新散列？

回答

相關問題