在 C++ std::unordered_map 中预分配存储桶

Question

我正在使用 std::unordered_map 来自 gnu++0x 来存储大量数据。我想为大量元素预先分配空间，因为我可以限制所使用的总空间。

我想做的是打电话：

std::unordered_map m;
m.resize(pow(2,x));

其中 x 已知。

std::unordered_map 不支持这个。我宁愿使用 std::unordered_map 如果可能的话，因为它最终将成为标准的一部分。

其他一些限制：

需要可靠的 O(1) 访问和变异地图。所需的散列和比较函数已经是非标准的并且有些昂贵。O(log n) 突变（如 std::map）太贵了。

-> 昂贵的哈希和比较也使得基于摊销的增长方式过于昂贵。每个额外的插入都需要这些函数进行 O(n) 次操作，这会导致算法运行时间中出现额外的二次项，因为指数存储需求需要 O(n) 增长。

Answer 1

m.rehash(pow(2,x));

如果 pow(2, x) 是您想要预分配的存储桶数量。你也可以：

m.reserve(pow(2,x));

但现在 pow(2, x) 是您计划插入的元素数量。这两个函数除了预分配存储桶之外什么都不做。他们不插入任何元素。它们都旨在完全适合您的用例。

笔记：不保证你能准确地得到 pow(2, x) 桶。某些实现仅使用 2 的幂数的桶。其他实现将仅使用质数个桶。还有一些人将仅使用素数的子集来表示桶的数量。但无论如何，实施应该接受你的 暗示 您想要的存储桶数量，然后在内部舍入到下一个可接受的存储桶数量。

这是最新的（N4660）用来指定参数的精确措辞 rehash:

a.rehash(n) : 后置条件： a.bucket_count() >= a.size() / a.max_load_factor() and a.bucket_count() >= n.

这个后置条件确保 bucket()_count() >= n, ， 然后 load_factor() 仍然小于或等于 max_load_factor().

随后 reserve(n) 定义为 rehash(n):

a.reserve(n) :与...一样 a.rehash(ceil(n / a.max_load_factor())).

Answer 2

我认为无序映射具有预先分配的内存并不重要。STL 的摊销插入时间预计为 O(n)。在我看来，在您知道这是代码的瓶颈之前，您可以省去编写自己的分配器的麻烦。

Answer 3

我建议您编写自己的分配器 std::unordered_map 完全按照您想要的方式分配内存。

Answer 4

构造函数根据参数“size_typebucket_count” http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map

所以按照示例代码所说的最简单的方法是：

std::unordered_map m{ pow(2,x) };

这会更有效，因为未定义在构造时将保留多少个存储桶，否则，当您之后调用保留时，它可能必须分配然后取消分配。

Answer 5

我认为 重新散列 和 预订 仅当您事先知道映射值将占用多少内存时，两者才起作用。如果映射的值很复杂或者大小动态变化（例如向量），您将需要自己的实现。例如，如果您的内存大小允许，您可以保留可能存在的最大容器。