c++ - 在 C++ std::unordered_map 中预分配桶

Question

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

我想做的是打电话:

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

其中 x 是已知的。

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

其他一些限制:

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

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

Answer 1

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

if 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() 和 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()))。