使用unordered_map时的内存分配

Question

如果一个std::unordered_map<int,...>保持大致相同的大小，但不断添加和删除项目，它会不断分配和释放内存或缓存并重新使用内存（即像池或向量）？假设库的现代标准MS实现。

Answer 1

该标准对这些方面没有具体说明，因此它们都是实现定义的。最值得注意的是，像您描述的缓存行为通常通过使用自定义分配器（例如，对于memory pool allocator）来实现，因此通常应该从容器实现中分离出来。

的the standard, ~p874约无序容器中的相关位：

一个无序关联容器的元件被组织成 桶。具有相同散列码的密钥出现在同一个存储桶中。 桶的数量自动增加，因为元素被添加到一个无序的关联容器中，因此每个桶的平均数量为 元素被保持在界限以下。

和插入：

插入件和布设成员不应影响 迭代器的有效性，如果（N + N）< = Z * B，其中N是在 元件的数量容器之前的插入操作中，n是元素 插入的数目，B是容器的桶数，和z是容器的 最大负载因子

你可以在行之间读取，并假设由于迭代器有效性不受影响，可能不会发生内存分配。尽管这不是保证的（例如，如果存储区数据结构是链接列表，您可以附加到它而不会使迭代器失效）。该标准似乎没有指定当元素被移除时应该发生什么，但是因为它不能使上面的约束无效，所以我没有看到释放内存的理由。

找出您的具体实现的最简单方法是阅读代码的源代码或配置文件。 或者，您可以尝试通过使用rehash和resize方法并调整地图的load_factor来控制此行为（如果确实需要）。