C++ stl映射性能？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10165708/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
stl map performance?
提问by David Rodríguez - dribeas
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).
我正在使用map<MyStruct, I*> map1;. 显然，我的应用程序总时间的 9% 都花在了那里。特别是在我的主要职能之一的一行上。地图不是很大（几乎总是<1k，<20 很常见）。
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.
附加信息：我总是在添加元素之前进行检查。如果存在密钥，我需要报告问题。在一点之后，我将大量使用 map 进行查找，并且不会添加更多元素。
回答by David Rodríguez - dribeas
First you need to understand what a map is and what the operations that you are doing represent. A std::mapis 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.
首先，您需要了解什么是地图以及您正在执行的操作代表什么。Astd::map是平衡二叉树，查找将进行O( log N )操作，每个操作都是键的比较加上一些在大多数情况下可以忽略的额外内容（指针管理）。插入需要大致相同的时间来定位插入点，加上新节点的分配、实际插入树和重新平衡。O( log N )尽管隐藏常数更高，但复杂性再次提高。
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::insertthat return a pair with an iterator and a bool telling you whether the insertion actually happened or the element was already there.
当您尝试在插入之前确定某个键是否在映射中时，您将承担查找成本，如果不成功，则定位插入点的成本相同。您可以通过使用std::map::insert带有迭代器和布尔值的返回对来避免额外的成本，告诉您插入是实际发生还是元素已经存在。
Beyond that, you need to understand how costly it is to compare your keys, which falls out of what the question shows (MyStructcould hold just one intor a thousand of them), which is something you need to take into account.
除此之外，您需要了解比较您的密钥的成本，这超出了问题所显示的内容（MyStruct可能只包含一个int或一千个），这是您需要考虑的事情。
Finally, it might be the case that a mapis 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)
最后，可能 amap不是满足您需求的最有效数据结构，您可能需要考虑使用std::unordered_map具有预期恒定时间插入的（哈希表）（如果哈希函数不可怕）或用于小数据集甚至是一个简单有序的数组（或std::vector），您可以在其上使用二分搜索来定位元素（这将减少分配的数量，代价是插入更昂贵，但如果持有的类型足够小，它可能是值得）
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!
与性能一样，衡量并尝试了解时间都花在了什么地方。另请注意，花在特定函数或数据结构上的 10% 的时间可能很多或几乎没有，这取决于您的应用程序是什么。例如，如果您的应用程序只是在数据集中执行查找和插入操作，而这仅占用 10% 的 CPU，那么您还有很多地方需要优化！
回答by EdChum
Probably it will be quicker to just do an insertand check if the pair.secondis falseif key already exists:
可能只是执行insert并检查pair.secondis falseif 键是否已经存在会更快：
like this
像这样
if ( myMap.insert( make_pair( MyStruct, I* ) ).second == false)
{
// report error
}
else
// inserted new value
... rather than doing a findcall every time.
...而不是find每次都打电话。
回答by Christian Ammer
Instead of mapyou could try unordered_mapwhich uses hash keys, instead of a tree, to find elements. This answergives some hints when to prefer unordered_mapover map.
而不是map您可以尝试unordered_map使用散列键而不是树来查找元素。这个答案给出了一些提示时喜欢unordered_map过map。
回答by amit
It might be a long shot, but for small collections, sometimes the most critical factor is the cacheperformance.
这可能是一个长期的尝试，但对于小型集合，有时最关键的因素是缓存性能。
Since std::mapimplements a Red-Black Tree, which is [AFAIK] not very cache-efficient - maybe implementing the map as a std::vector<pair<MyStruct,I*>>would be a good idea, and use binary search there [instead of map look-ups], at the very least it should be efficient once you start only looking up [stop inserting elements], since the std::vectoris more likely to fit in cache than the map.
由于std::map实现了红黑树，这 [AFAIK] 缓存效率不是很高 - 也许将地图实现为std::vector<pair<MyStruct,I*>>一个好主意，并在那里使用二分搜索 [而不是地图查找]，至少它一旦你开始只有仰视[停止插入元素]，因为要有效率std::vector更容易适应高速缓存比map。
This factor [cpu-cache] is usually neglected and hidden as constant in the big O notation, but for large collections it might have major effect.
这个因素 [cpu-cache] 通常在大 O 符号中被忽略并隐藏为常量，但对于大型集合，它可能会产生重大影响。
回答by Johann Gerell
The way you are using the map, you're doing lookups on the basis of a MyStructinstance and depending on your particular implementation, the required comparison may or may not be costly.
您使用地图的方式是基于MyStruct实例进行查找，并且根据您的特定实现，所需的比较可能会或可能不会很昂贵。
回答by justin
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.
是否有我可能想要使用的替代实现？我想我不应该自己写，但如果我认为这是个好主意，我可以。
If you understand the problem well enough, you should detail how your implementation will be superior.
如果您对问题理解得足够好，您应该详细说明您的实施将如何更好。
Is mapthe proper structure? If so, then your standard library's implementation will likely be of good quality (well optimized).
map结构是否合理？如果是这样，那么您的标准库的实现可能具有良好的质量（优化良好）。
Can MyStructcomparison be simplified?
可以MyStruct相比，能够简化？
Where is the problem -- resizing? lookup?
问题出在哪里——调整大小？抬头？
Have you minimized copy and assign costs for your structures?
您是否已将结构的复制和分配成本降至最低？
回答by bitmask
As stated in the comments, without proper code, there is little universal answers to give you. However, if MyStructis really huge the stack copying may be costly. Perhaps it makes sense to store pointers to MyStructand implement your own compare mechanism:
正如评论中所述，如果没有正确的代码，几乎没有通用的答案可以给你。但是，如果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;
However, this is something you will have to profile. It mightspeed things up.
但是，这是您必须配置的内容。它可能会加快速度。
You would look up an element like this
你会查找这样的元素
template <typename T> struct NullDeleter {
void operator()(T const*) const {}
};
// needle being a MyStruct
mymap.find(std::shared_ptr<MyStruct>(&needle,NullDeleter()));
Needless to say, there is more potential to optimise.
不用说，还有更多的优化潜力。
