STL的地图表现？ [英] stl map performance?

问题描述

我使用地图＆LT; MYSTRUCT，I *＆GT; MAP1; 。显然，我的总的应用程序时间9％花费在那里。特别是在一行中的我的主要功能之一。该地图是不是很大（小于1K几乎总是小于20是常见的）。

I am using map<MyStruct, I*> map1;. Apparently 9% of my total app time is spent in there. Specifically on one line of one of my major functions. The map isn't very big (<1k almost always, <20 is common).

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

Is there an alternative implementation i may want to use? I think i shouldn't write my own but i could if i thought it was a good idea.

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

Additional info: I always check before adding an element. If a key exist I need to report a problem. Than after a point i will be using map heavily for lookups and will not add any more elements.

推荐答案

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

First you need to understand what a map is and what the operations that you are doing represent. A std::map is a balanced binary tree, lookup will take O( log N ) operations, each of which is a comparison of the keys plus some extra that you can ignore in most cases (pointer management). Insertion takes roughly the same time to locate the point of insertion, plus allocation of the new node, the actual insertion into the tree and rebalancing. The complexity is again O( log N ) although the hidden constants are higher.

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

When you try to determine whether an key is in the map prior to insertion you are incurring the cost of the lookup and if it does not succeed, the same cost to locate the point of insertion. You can avoid the extra cost by using std::map::insert that return a pair with an iterator and a bool telling you whether the insertion actually happened or the element was already there.

除此之外，你需要明白它是多么昂贵，比较你的钥匙，它掉出来什么的问题显示（ MYSTRUCT 可容纳只是一个 INT 或三千人），这是你需要考虑的东西。

Beyond that, you need to understand how costly it is to compare your keys, which falls out of what the question shows (MyStruct could hold just one int or a thousand of them), which is something you need to take into account.

最后，它可能是一个地图是不是最有效的数据结构，为您的需求的情况下，你可能要考虑使用任何的性病:: unordered_map （哈希表）已预期恒定时间插入（如果散列函数是不可怕的）或小的数据集，即使一个普通的有序阵列（或的std ::矢量）上，您可以使用二进制搜索找到的元素（这将减少分配的数量，以更昂贵的插入成本，但如果手持类型是足够小，它可能是值得的）

Finally, it might be the case that a map is not the most efficient data structure for your needs, and you might want to consider using either an std::unordered_map (hash table) that has expected constant time insertions (if the hash function is not horrible) or for small data sets even a plain ordered array (or std::vector) on which you can use binary search to locate the elements (this will reduce the number of allocations, at the cost of more expensive insertions, but if the held types are small enough it might be worth it)

与往常一样，性能，测量，然后试着去了解那里的时间被消耗。还要注意的是在一个特定的功能或数据结构所用时间的10％，可能是一个地段或几乎什么都没有，这取决于您的应用程序。例如，如果你的应用程序仅仅是执行查找和插入到一组数据，而这需要你有很多优化其他地方的CPU只有10％！

As always with performance, measure and then try to understand where the time is being spent. Also note that a 10% of the time spent in a particular function or data structure might be a lot or almost nothing at all, depending on what your application is. For example, if your application is just performing lookups and insertions into a data set, and that takes only a 10% of the CPU you have a lot to optimize everywhere else!

这篇关于STL的地图表现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！