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