26

我正在使用std::unordered_mapfrom 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) 次增长。

4

5 回答 5

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

ifpow(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, 且 thatload_factor()保持小于或等于max_load_factor()

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

a.reserve(n): 同a.rehash(ceil(n / a.max_load_factor()))

于 2011-05-05T23:56:25.167 回答
4

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

于 2011-05-05T23:49:25.240 回答
3

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

于 2011-05-05T23:38:40.663 回答
1

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

所以做你的示例代码所说的最简单的方法是:

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

这将更有效率,因为未定义在构造时将保留多少桶,否则,它可能必须在您之后调用 Reserve 时分配然后解除分配。

于 2016-10-07T18:21:10.543 回答
-2

我认为只有当您事先知道映射值将占用多少内存时,rehashreserve才能起作用。如果映射的值很复杂或大小动态变化(例如向量),您将需要自己的实现。例如,如果您的内存大小允许,您可以保留可能碰巧存在的最大容器。

于 2016-01-14T21:12:24.137 回答