如何在删除元素时防止对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; 
    } 
}

我想阻止地图进行任何昂贵的操作，直到我做删除所有我需要删除的元素。我有一个有效的关注吗？我误解了内部存储的工作原理吗？

答

无序容器从一个erase期间重散列禁止的。REQ]/P14：

的erase成员应到失效只迭代器和引用被擦除的元件，并且保持未擦除的元件的相对顺序。

[unord.req]/P9：

换汤不换药无效迭代器，改变要素之间的排序，并...

你的代码是罚款的。

我知道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())时间擦除元素，但不同的加载因素可能会影响应用程序的实际性能。

尽管内容丰富且相关 - 它并没有回答这个问题：'如何防止在移除元素时重新调整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：

如何在删除元素时防止对std :: unordered_map进行重新散列？

相关推荐