为什么 C++11/Boost `unordered_map` 在擦除时不重新散列？

我想知道为什么 C++11 和 Boost 的 hashmap 在通过迭代擦除元素时不会调整大小。即使这在技术上不是内存泄漏，我认为这可能是应用程序中的一个严重问题（这对我来说是一个隐藏的问题，很难追踪它），并且它实际上可能会影响许多应用程序。这是容器的“设计缺陷”吗？

我对它进行了基准测试，似乎影响了多个编译器版本（包括 VS、Clang、GCC）

重现该问题的代码是：

std::unordered_map<T1,T2> m;

for (int i = 0; i < 5000000; i++)
        m.insert(std::make_pair(i, new data_type));


for (map_type::iterator it = m.begin(); it != m.end();) {
        delete it->second;
        it = m.erase(it);
}   

我创建了一个独立测试 https://github.com/Darelbi/PublicProfileTests/blob/master/BoostMemoryUsage/UnorderedMap.cpp使用自定义分配器来跟踪内存使用情况的文件。

据我了解，其背后的原因是允许通过迭代擦除元素并保留有效的迭代器以不擦除元素。这似乎有点奇怪，因为插入元素可能会导致重新哈希，从而使迭代器无效。

但你可以直接破坏地图..

这就是我解决这个问题的方法（我将地图包装在智能指针内，当它为空时，我只需重新创建一个新的空地图，结果比重新散列更快，不知道为什么。）。

一般来说，任何使用的应用程序unordered_map因为缓存元素的容器可能会遇到这个问题（您可能想从缓存中删除元素，但通常没有人执行“缓存重置”）

据我所知，这种行为并不是要求不使迭代器无效的结果（std::unordered_map::rehash也不会使它们无效）而不是复杂性要求的结果std::unordered_map::erase，平均需要恒定时间。

我不能告诉你，为什么这样指定，但我可以告诉你，为什么这是正确的默认行为for me:

1. 在许多应用程序中，我的哈希表的内容实际上是 无论如何，初始化后不变 - 所以这里我不在乎。
2. 如果不是这种情况，至少元素的平均数量 或多或少保持相同（在一个数量级内）。 所以即使在某个时间点删除了很多对象，new 元素可能很快就会添加。在这种情况下，它 不会真正减少内存占用和开销 重新散列两次（一次在删除后，一次在添加新元素后）通常会超过我通过更紧凑的表可能获得的任何性能改进。
3. 如果您无法控制启发式（就像通过修改插入元素时可以的那样），则擦除大量元素（例如通过过滤器函数）将因中间重新哈希而严重减慢max_load_factor).
   因此，最后，即使在重新散列实际上有益的情况下，我通常也可以做出更好的决定，即何时进行（例如通过重新散列或复制和交换）而不是通用启发式std::unordere_map could.

再说一次，这些观点对于我的典型用例来说是正确的，我并不声称它们对于其他人的软件来说普遍正确，或者它们是规范背后的动机unordered_map

有趣的是，VS2015和libstc++似乎实现rehash(0)不同*：

• libstdc++ 实际上会收缩（重新分配）存储表的内存
• VS2015 将减小表大小（也称为存储桶编号），但不会重新分配表。因此，即使在重新散列空哈希图之后，表的剩余内存也不会被返回。

显然，最小化内存占用的唯一可移植方法是复制和交换。

关于文档，我同意这可能应该在某处明确提及，但另一方面它是例如与文档一致std::vector::erase()。另外，我也不是 100% 确定，是否真的不可能编写一个至少有时在擦除时重新哈希而不违反要求的实现。

*）我从结果中推断出这一点bucket_count and getAllocatedBytes()来自您的分配器，而不是实际查看源代码。