47

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

4

5 回答 5

50

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

于 2012-10-24T12:43:45.317 回答
25

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

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

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

但是，您必须处理许多问题。

首先，您并不真正知道每个映射节点的大小或映射将执行多少次分配。这些是内部实现细节。您可以尝试找出答案，但不能假设结果将适用于不同的编译器（甚至是同一编译器的未来版本）。因此，您不必担心分配“固定”大小的地图。相反，您的目标应该是将所需的分配数量减少到少数。

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

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

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

于 2012-10-24T14:13:12.683 回答
3

不确定这是否回答了您的问题，但Boost.Container有一个flat_map您可以在其中保留空间的地方。基本上，您可以将其视为（键，值）对的排序向量。提示：如果您还知道您的输入已排序，则可以使用带有提示的插入来获得最大性能。

于 2016-02-26T09:51:27.453 回答
2

你在谈论block allocators。但实施起来很困难。在考虑这些困难的事情之前先衡量一下。不管怎样， Boost有一些关于实现块分配器的文章。或者使用已经实现的预分配地图Stree

于 2012-10-24T12:44:15.473 回答
2

这个问题已经有几个很好的答案，但他们错过了一些要点。

直接初始化地图

如果直接使用迭代器初始化，则映射预先知道大小：

auto mymap = std::map(it_begin, it_end);

这是回避问题的最佳方法。如果您对实现不了解，则映射可以从迭代器预先知道大小，然后您将问题转移到std::实现来担心。

或者与迭代器一起使用insert，即：

mymap.insert(it_begin, it_end);

请参阅：https ://en.cppreference.com/w/cpp/container/map/insert

提防过早的优化

但我觉得我在浪费一些计算时间。

这听起来很像您过早地进行优化（这意味着您不知道瓶颈在哪里 - 您正在猜测或看到一个不是真正的问题）。相反，首先测量然后进行优化 - 如有必要，重复。

内存分配已经在很大程度上得到优化

为地图滚动你自己的块分配器可能几乎没有结果。在现代系统上（这里我包括操作系统/硬件和C++ 语言级别）内存分配已经针对一般情况进行了很好的优化，如果滚动您自己的块分配器，您可能会看到很少或没有改进。即使您非常小心并将地图放入一个连续的数组中 - 虽然本身是一种改进 - 您仍然可能面临这样的问题，即最终元素可能会随机放置在数组中（例如插入顺序）并且无论如何都要对缓存不那么友好（这在很大程度上取决于您的实际用例 - 我假设一个超大数据集）。

使用其他容器或第三方地图

如果您仍然面临这个问题 - 最好的方法可能是使用另一个容器（例如，排序的std::vector-std::lower_bound用于查找）或使用针对您使用地图的方式优化的第三方地图。一个很好的例子flat_map来自 - 请参阅这个答案。

结论

  1. 让 std::map 担心这个问题。
  2. 当性能是主要问题时：使用最适合您的数据使用方式的数据结构（可能是第 3 方）（随机插入或批量插入/主要是迭代或主要是查找等）。然后，您需要分析和收集性能指标以进行比较。
于 2019-09-23T08:39:31.550 回答