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

Question

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

我对其进行了基准测试，似乎影响了几个编译器版本（包括 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..

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

一般来说，任何使用 unordered_map 作为缓存元素容器的应用程序都可能遇到这个问题（您可能想从缓存中删除元素，但通常没有人这样做 "cache reset"）

Answer 1

据我所知，这种行为与其说是要求不使迭代器无效（std::unordered_map::rehash 也不会使它们无效）的结果，不如说是 [= 的复杂性要求的结果11=]，这应该平均花费常数时间。

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

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

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

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

libstc++ 实际上会缩小（重新分配）存储 table 的内存
VS2015 将减小 table 大小（a.k.a。存储桶编号）但不会重新分配 table。因此，即使在重新散列空散列映射后，table 的剩余内存也不会返回。

显然，table 减少内存占用的唯一方法是复制和交换。

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

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

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

Why does C++11/Boost `unordered_map` not rehash when erasing?

c++

boost

unordered-map

c++11