在预先知道大小时初始化std :: map

Question

我想初始化一个std::map.现在我正在使用,::insert但我觉得我浪费了一些计算时间,因为我已经知道我想要分配的大小.有没有办法分配固定大小的地图,然后填写地图？

Answer 1

不,地图的成员内部存储在树结构中.在知道要存储的键和值之前,无法构建树.

您可以创建一个精确大小的池分配器,这将使单个节点的分配明显更快.然而,为了确保这一点非常有效,您还必须知道节点的数量永远不会改变.如果您知道这一切,那么编写一个可以完成这项工作的自定义分配器并不难. (3认同)
这个答案是错误的 - 如果你有例如。100.000 多个元素，您一开始就知道 - 将所有内容分配到一个连续数组中可以极大地加快处理速度。 (3认同)
@Mankarse:它不会有太大的区别,因为每个节点必须分别分配(和解除分配).从地图内容的先进知识中获得的确很少(除非它完全是constexpr). (2认同)

Answer 2

简短的回答是:是的,这是可能的,但这不是微不足道的.您需要为地图定义自定义分配器.基本思想是你的自定义分配器将为地图留出一块内存.由于映射需要新节点,因此分配器将在预分配块中简单地分配它们.像这样的东西:

std::map<KeyType, ValueType, std::less<KeyType>, MyAllocator> myMap;

myMap.get_allocator().reserve( nodeSize * numberOfNodes );

但是,您需要处理许多问题.

首先,您并不真正了解每个地图节点的大小或地图将执行的分配数量.这些是内部实现细节.您可以尝试找出答案,但您不能假设结果将适用于不同的编译器(甚至是同一编译器的未来版本).因此,您不必担心分配"固定"大小的地图.相反,您的目标应该是减少少量所需的分配数量.

其次,如果你想支持删除,这个策略会变得相当复杂.

第三,不要忘记内存对齐问题.分配器返回的指针必须正确对齐内存将存储的各种类型的对象.

所有这些,在你尝试之前,确保它是必要的.内存分配可能非常昂贵,但您仍然不应该认为这对您的程序来说是一个问题.找出答案.您还应该考虑更自然地允许预分配的替代策略.例如,排序列表或std :: unordered_map.