我想知道为什么C++11和Boost的哈希表在迭代删除元素时不会进行调整大小。即使这不是技术上的内存泄漏,我认为它可能是应用程序中的严重问题(对我来说是一个隐藏的问题,很难追踪回去),并且实际上可能影响许多应用程序。这是容器的“设计缺陷”吗?
我进行了基准测试,似乎影响了几个编译器版本(包括VS、Clang、GCC)。
复现此问题的代码如下:
我创建了一个自包含测试文件,使用自定义分配器来跟踪内存使用情况。
据我所知,这样做的原因是允许在迭代过程中擦除元素并保持有效的迭代器以不被擦除的元素。这似乎是一个有点奇怪的要求,因为插入元素可能会导致重新哈希,从而使迭代器无效。
一般来说,任何使用
我进行了基准测试,似乎影响了几个编译器版本(包括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);
}
我创建了一个自包含测试文件,使用自定义分配器来跟踪内存使用情况。
据我所知,这样做的原因是允许在迭代过程中擦除元素并保持有效的迭代器以不被擦除的元素。这似乎是一个有点奇怪的要求,因为插入元素可能会导致重新哈希,从而使迭代器无效。
这就是我解决这个问题的方式(我将映射表包装在智能指针中,当它为空时,我只需重新创建一个新的空映射表,结果比重新哈希更快,不知道为什么)。但是你可以直接销毁映射表。
一般来说,任何使用
unordered_map
作为缓存元素容器的应用程序都可能遇到这个问题(您可能想从缓存中删除元素,但通常没有人执行“缓存重置”)。
erase
作为实际上的clear
(希望获得shrink_to_size
的效果),那么就要明确地编写代码。即使在这种情况下保持相同的大小也有价值,如果哈希表反复使用并且最终的人口密度具有相同类型的桶负载,则重用比重新开始增长更有效。 - sehevector
在擦除时不重新分配的原因相同。 - sbabbistd::unordered_map
规范过于详细,这意味着std
实现者无法很大程度上改变其工作方式。据我所知,编写了一个示例实现,然后根据其操作行为制定了抽象需求...... - Yakk - Adam Nevraumont