STL 映射与向量的迭代器访问性能？
使用迭代器循环 STL 映射与使用向量之间的性能差异是什么？ 我想使用映射键进行插入、删除和某些访问，但我还需要对映射中的每个元素进行常规访问。
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 every element in the map.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
对于映射和向量，迭代整个集合的时间复杂度为 O(N)。 然而（就像列表与向量一样）向量连续存储元素，因此访问下一个元素要便宜得多，因为它将最佳地使用缓存，而映射不会。
但由于您需要基于键进行查找，因此实际上没有其他选择。 您可以使用在第一个元素上排序的成对向量，但如果集合需要可变，这将非常慢。 只需使用地图即可。
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.
But since you need to 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.
迭代映射的每个元素需要 O(n) 时间。 维基百科
Iterating through every element of a map takes O(n) time. wikipedia
迭代映射可能是线性的，但实际上，与 C++ 中的实现相比，它的效率并不高。 所以我的建议是使用一个向量并使用另一个映射在线性时间内定位向量中的项目。
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 .
如果您需要通过钥匙快速访问，请使用地图。 否则，始终使用向量，除非分析器发现一些性能问题。
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.
浏览树并不昂贵（就像遵循链表一样），您不会像使用向量一样从缓存中受益，但通常是您在迭代时所做的事情才是昂贵的，而不是迭代本身。
您能否告诉我们更多有关迭代整个地图时您期望做什么的信息？
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?