STL地图的表现？(stl map performance?)

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

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

附加信息：我总是将一个元素之前检查。如果密钥存在，我要报告问题。不是一个点后，我将使用大量的地图为查找并不会增加任何更多的元素。

Answer 1:

首先，你需要了解什么是地图是什么，你正在做的业务代表。一个std::map是一个平衡二叉树，查找需要O( log N )操作，其中的每一个是关键的比较加上一些额外的，你可以在大多数情况下（指针管理）忽略。插入采取大致相同的时间来定位插入的新节点，实际插入的树和重新平衡点，再加上分配。复杂性又是O( log N )虽然隐藏常数较高。

当试图确定一个密钥是否在地图中插入之前，你所负担的查询的成本，如果没有成功，相同的成本来定位插入点。您可以通过避免使用额外成本std::map::insert返回一对与一个迭代器和一个布尔告诉你插入是否实际发生或元素已经在那里了。

除此之外，你需要了解它是多么昂贵，比较你的钥匙，它掉出来什么的问题显示（ MyStruct可容纳只是一个int或它们的万），这是你需要考虑的东西。

最后，它可能是一个案件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缓存]通常被忽视，隐藏在大O符号不变，但对大集合，可能有重大的影响。

Answer 5:

您正在使用的地图的方式，你一的基础上做的查找MyStruct实例，并根据您的具体实现，需要的比较可能会或可能不会是昂贵的。

Answer 6:

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

如果你理解这个问题还不够，你必须详细说明如何执行你的将是优越的。

是map正确的结构？如果是这样，那么你的标准库的实现将可能是质量好（最优化的）。

可以MyStruct相比，能够简化？

问题出在哪里 - 调整？抬头？

你有没有最小化拷贝并分配你的结构成本？

Answer 7:

正如评论指出，如果没有适当的代码，几乎没有通用的答案给你。但是，如果MyStruct真的是巨大的堆栈复制可能是昂贵的。或许是有意义的存储指向MyStruct和实现自己的比较机制：

template <typename T> struct deref_cmp {
  bool operator()(std::shared_ptr<T> lhs, std::shared_ptr<T> rhs) const {
    return *lhs < *rhs;
  }
};

std::map<std::shared_ptr<MyStruct>, I*, deref_cmp<MyStruct>> mymap;

然而，这是你必须的配置文件。它可能会加快速度。

你会看起来像这样的元素

template <typename T> struct NullDeleter {
  void operator()(T const*) const {}
};
// needle being a MyStruct
mymap.find(std::shared_ptr<MyStruct>(&needle,NullDeleter()));

不用说，还有更多潜在的优化。

文章来源: stl map performance?