C++ STL 映射与向量的迭代器访问性能？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/730498/
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
Iterator access performance for STL map vs. vector?
提问by Greg Rogers
What is the performance difference between using an iterator to loop through an STL map, versus a vector? I'd like to use the map key for insertion, deletion, and some accesses, but I also need to do regular accesses to everyelement in the map.
使用迭代器循环遍历 STL 映射与使用向量之间的性能差异是什么？我想使用映射键进行插入、删除和某些访问，但我还需要对映射中的每个元素进行定期访问。
回答by Greg Rogers
With both map and vector, iterating through the entire collection is O(N). however (like list vs vector) vector stores elements contiguously, so accessing the next element is much cheaper because it will use cache optimally, whereas the map won't.
使用 map 和 vector，遍历整个集合是 O(N)。但是（如列表与向量）向量连续存储元素，因此访问下一个元素要便宜得多，因为它将以最佳方式使用缓存，而地图则不会。
But since you needto have lookup based on keys, there isn't really an alternative. You could use a vector of pairs sorted on the first element, but if the collection needs to be mutable this is going to be very slow. Just use a map.
但是由于您需要基于键进行查找，因此实际上没有其他选择。您可以使用按第一个元素排序的对向量，但如果集合需要可变，这将非常慢。只需使用地图。
回答by Sanjaya R
回答by 17 of 26
This linkhas a nice table of performance for various operations on all of the STL containers.
这个链接有一个很好的关于所有 STL 容器上的各种操作的性能表。
Generally speaking, if you need to do a lot of inserting, removing or searching based on a key then the map is the way to go.
一般来说，如果你需要根据一个键进行大量的插入、删除或搜索，那么地图就是要走的路。
If you only need to set up the container once and then access it like an array then use a vector.
如果您只需要设置容器一次，然后像数组一样访问它，则使用向量。
EDIT: Performance table of STL container operations:
编辑：STL 容器操作的性能表：
回答by Pinkoo
Iterating through a map may be linear but practically , it is not so efficient from the implementations in C++ . So my advice is to use a vector and use another map to locate the items in the vector in linear time .
遍历映射可能是线性的，但实际上，从 C++ 中的实现来看，效率并不高。所以我的建议是使用一个向量并使用另一个地图在线性时间内定位向量中的项目。
回答by Edouard A.
Browsing the tree is not expensive (grosso modo like following a linked list), you won't benefit from the cache as much with a vector, but generally it's what you do when you iterate that is expensive, not the iteration itself.
浏览树并不昂贵（就像遵循链表一样），使用向量不会从缓存中受益，但通常是迭代时所做的事情是昂贵的，而不是迭代本身。
Could you tell us more about what you expect to do when you iterate through the whole map?
你能告诉我们更多关于当你遍历整个地图时你期望做什么吗？
回答by Mykola Golubyev
Use map if you need fast way of access by the key. Otherwise use vector all the time unless some performance issues will be discovered with profiler.
如果您需要通过钥匙快速访问，请使用地图。否则一直使用 vector 除非使用 Profiler 会发现一些性能问题。
