如何在删除元素时防止std :: unordered_map重新哈希化？

Question

我有一个 std::unordered_map，我将通过迭代从中删除元素。

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

在我完成删除所有需要删除的元素之前，我希望防止地图执行任何昂贵的操作。我拥有一个有效的关注点吗？我是否误解了内部存储的工作方式？

- vmrob

Answer 1

在erase期间，不允许对无序容器进行重新哈希操作：

[unord.req]/p14:

erase成员函数只能使迭代器和指向已经被删除的元素的引用失效，并保留未删除元素的相对顺序。

[unord.req]/p9:

重新哈希会使迭代器失效、改变元素之间的顺序等……

您的代码没有问题。

- Howard Hinnant

---

我知道我们是在4年后看这个问题，但我很高兴看到这个答案进入了讨论。再次查看文档，很明显最坏情况的复杂度不是来自于可能的重新散列，而是来自于哈希冲突。我认为这是官方正确的答案。 - vmrob

因此表格只能增长。 - Volodymyr Boiko

无序容器中的桶数量在 erase 操作下永远不会缩小。在 rehash 操作下，桶的数量可以缩小，并且所有实现都会这样做。 - Howard Hinnant

Answer 2

据我所知，std::unordered_map在erase(itr)时允许重新散列：

C++11表103--无序关联容器要求 a.erase(q) 删除由q指向的元素。返回值是在删除之前紧接着q的迭代器。

平均情况下为O(1)，最坏情况下为O(a.size()) 因此，您确实有一个有效的问题需要解决。针对这个问题，我可以建议几种方法：

1. 确保它是一个实际的问题而不是假想的问题。对应用程序进行分析，查看C++库的源代码等。
2. 如果这是一个实际的问题，请考虑使用不同的容器或不同的算法。
3. 考虑通过与每个元素相关联的布尔标志来标记要删除的元素，并定期清除已删除的元素，从而分摊成本。
4. 考虑尝试负载因子，正如@amit在评论中建议的那样。即使容器仍然允许花费O(a.size())的时间来删除元素，不同的负载因子可能会影响您的应用程序的实际性能。

- NPE

---

虽然信息丰富且相关，但它并没有回答这个问题：“如何在删除元素时防止std::unordered_map重新散列？” - amit

@amit：如果你仔细揣摩，其实是可以（确切的答案是你不能 :)）。 - NPE

@amit：最坏情况被规定为O(a.size())。它不基于任何其他因素，包括负载因子。 - NPE

@NPE: 最坏情况基于非常糟糕的哈希值，而不是重新哈希。所有unordered_*操作都有可能出现在容器中的所有对象具有相同哈希值的情况下。我几乎可以确定，.erase当前被禁止重新哈希。 - rici

这个答案是不正确的。我已经添加了一个正确的答案。 - Howard Hinnant

Answer 3

我不确定它是否有效，文档中没有确认 - 但如果unordered_map根据经典哈希表数据结构进行重新散列，您可以将 max_load_factor设置为非常高的值，并在完成后将其重置回正常值（这将触发重新散列）（或者根据您可以预测要删除多少元素来预测值）。

从经典哈希表的角度来看，由于在减小表格时重新散列发生在大小低于1 / max_load_factor时，因此应该起作用。

（不确定在C ++中是否是这种情况，但我认为值得尝试，因为它非常容易实现）。

- amit