我正在使用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)增长.