23

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

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

我想阻止地图执行任何昂贵的操作，直到我完成删除所有需要删除的元素。我有正当的担忧吗？我是否误解了内部存储的工作原理？

4

3 回答 3

11

在 期间禁止无序容器重新散列erase：

[unord.req]/p14：

成员应仅使迭代器和对已擦除元素的erase引用无效，并保留未擦除元素的相对顺序。

[unord.req]/p9：

重新散列使迭代器无效，更改元素之间的顺序，并且...

你的代码是好的。

于 2016-11-30T16:03:59.120 回答
3

据我所知，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())时间来擦除元素，不同的负载因子可能会对应用程序的实际性能产生影响。
于 2012-12-05T19:24:22.867 回答
2

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

就经典哈希表而言，它应该可以工作，因为减小表时的 rehash 发生在大小较低时1/max_load_factor。

（不确定在 C++ 中是否如此，但我认为值得一试，因为它真的很容易实现）。

于 2012-12-05T19:35:46.943 回答