Question

我使用map<MyStruct, I*> map1;。显然我的总应用程序时间的 9 ％花在那里。特别是在我的一个主要功能的一行。地图不是很大（＆ lt;1k 几乎总是，＆ lt;20 是常见的）。

我想我不应该写我自己的，但我可以，如果我认为这是一个好主意。

附加信息：我总是在添加元素之前检查。如果一个键存在，我需要报告一个问题。比点后，我将大量使用 map 进行查找，并且不会添加任何更多的元素。

57

10

7

5

Answer 1

首先，您需要了解映射是什么以及您正在做的操作代表什么。std::map是一个平衡的二叉树，查找将需要O( log N )操作，每个操作都是键的比较以及在大多数情况下可以忽略的一些额外操作（指针管理）。插入花费大致相同的时间来定位插入点，再加上新节点的分配，实际插入到树中的复杂性更高。

当您尝试在插入之前确定一个键是否在映射中时，您将产生查找的成本，如果它不成功，则查找插入点的成本相同。您可以通过使用std::map::insert来避免额外的成本，它返回一个带有迭代器和 bool 的对，告诉您插入是否实际发生或元素是否已经存在。

除此之外，您还需要了解比较密钥的成本有多高，这与问题所显示的不同（MyStruct只能容纳一个int或一千个），这是您需要考虑的。

最后，可能是map不是满足您需求的最有效的数据结构的情况，您可能需要考虑使用std::unordered_map（哈希表）具有预期的常量时间插入（如果哈希函数不是可怕的）或对于小数据集，即使是简单的有序数组（或std::vector），您可以使用二进制搜索来定位它的数量更多

与往常一样，对性能进行测量，然后尝试了解所花费的时间。还要注意，在特定功能或数据结构上花费的时间的 10 ％可能很多，或者几乎没有，这取决于您的应用程序是什么。例如，如果您的应用程序只是在数据集中执行查找和插入，而这只需要 10 ％的 CPU，那么您在其他地方都有很多需要优化的地方！

Answer 2

可能会更快，只是做一个insert，并检查pair.second是false如果键已经存在：

像这样

if ( myMap.insert( make_pair( MyStruct, I* ) ).second == false)
{
  // report error
}
else
  // inserted new value

...而不是每次都执行find调用。

Answer 3

而不是map，你可以尝试unordered_map使用哈希键，而不是树，找到元素。This answer给出了一些提示何时更喜欢unordered_map而不是map。

Answer 4

这可能是一个很长的镜头，但对于小集合，有时最关键的因素是cache性能。

由于std::map实现了一个红黑树，这是 [AFAIK] 不是很高效的缓存-也许将地图实现为std::vector<pair<MyStruct,I*>>将是一个好主意，并使用二进制搜索 [而不是地图查找]，至少它应该是有效的，一旦你开始只查找 [停止插入元素]，因为std::vector比更适合缓存。

这个因素 [cpu-cache] 通常被忽略并隐藏为大 O 符号中的常量，但对于大型集合，它可能会产生重大影响。