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

Question

我想知道为什么 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);
}   

我创建了一个 self-contained test使用自定义分配器跟踪内存使用情况的文件。

据我所知，其背后的原因是允许通过迭代删除元素并将有效的迭代器保留为未删除的元素。这似乎有点奇怪的要求，因为插入元素可能会导致重新散列，无论如何都会使迭代器无效。

But you could destroy the map directly..

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

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

Answer 1

据我所知，这种行为与其说是要求不使迭代器无效(std::unordered_map::rehash 也不使它们无效)的结果，不如说是std::unordered_map::erase 的复杂性要求的结果。 ，这平均需要常数时间。

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

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

同样，这些观点适用于我的典型用例，我并不声称它们对其他人的软件普遍适用，或者它们是 unordered_map 规范背后的动机。

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

• libstc++ 实际上会缩小(重新分配)存储表的内存
• VS2015 将减小表大小(也称为桶数)但不会重新分配表。因此，即使在重新散列空散列映射之后，表的剩余内存也不会返回。

显然，最小化内存占用的唯一可移植方法是 copy-and-swap 。

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

---

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