stl地图表现？

Question

我在用map<MyStruct, I*> map1;.显然,我总应用时间的9%用于那里.特别是我的一个主要职能的一行.地图不是很大(<1k几乎总是,<20是常见的).

是否有我可能想要使用的替代实现？我想我不应该写自己的,但如果我认为这是一个好主意我可以.

附加信息:我总是在添加元素之前检查.如果存在密钥,我需要报告问题.在一点之后,我将大量使用地图进行查找,并且不会再添加任何元素.

Answer 1

首先,您需要了解地图是什么以及您正在执行的操作代表什么.A std::map是一个平衡的二叉树,查找将进行O( log N )操作,每个操作都是键的比较加上一些额外的,你可以在大多数情况下忽略它们(指针管理).插入大致需要大致相同的时间来定位插入点,加上新节点的分配,实际插入树和重新平衡.O( log N )虽然隐藏的常数更高,但复杂性仍然存在.

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

除此之外,您需要了解比较密钥的成本是多少,这与问题显示的内容(MyStruct可能只包含其中的一个int或几千个)有关,这是您需要考虑的事项.

最后,情况可能是a map不是满足您需求的最有效的数据结构,并且您可能想要考虑使用std::unordered_map具有预期的恒定时间插入的(散列表)(如果散列函数不可怕)或者小数据集甚至是一个简单的有序数组(或std::vector),你可以使用二进制搜索来定位元素(这将减少分配的数量,代价是更昂贵的插入,但如果保持的类型足够小,它可能是值得)

与性能一样,测量然后尝试了解花费的时间.另请注意,在特定功能或数据结构中花费的时间的10%可能很多或几乎没有,具体取决于您的应用程序.例如,如果您的应用程序只是在数据集中执行查找和插入,并且只占CPU的10%,那么您可以在其他任何地方进行优化!

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使用散列键而不是树来查找元素.这个答案给出了一些提示时喜欢unordered_map过map.

Answer 4

这可能是一个长期的尝试，但对于小型集合，有时最关键的因素是缓存性能。

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

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