使用迭代器循环 STL 映射与向量之间的性能差异是什么？我想使用 map 键进行插入、删除和一些访问，但我还需要定期访问map 中的每个元素。
Billy B
问问题
23724 次
6 回答
25
使用 map 和 vector，遍历整个集合是 O(N)。但是（如列表与向量）向量连续存储元素，因此访问下一个元素要便宜得多，因为它将最佳地使用缓存，而地图不会。
但是由于您需要基于键进行查找，因此没有其他选择。您可以使用按第一个元素排序的对向量，但如果集合需要是可变的，这将非常慢。只需使用地图。
于 2009-04-08T15:30:00.487 回答
11
遍历地图的每个元素需要 O(n) 时间。维基百科
于 2009-04-08T15:28:09.007 回答
5
这个链接有一个很好的关于所有 STL 容器上的各种操作的性能表。
一般来说，如果您需要根据键进行大量插入、删除或搜索，那么映射是可行的方法。
如果您只需要设置一次容器，然后像数组一样访问它，那么请使用向量。
编辑：STL 容器操作的性能表：
于 2009-04-08T15:32:02.650 回答
5
遍历映射可能是线性的，但实际上，从 C++ 中的实现来看，它的效率并不高。所以我的建议是使用一个向量并使用另一个地图在线性时间内定位向量中的项目。
于 2015-06-25T19:09:43.197 回答
3
如果您需要通过钥匙快速访问，请使用地图。否则一直使用向量，除非探查器会发现一些性能问题。
于 2009-04-08T15:27:58.213 回答
2
浏览树并不昂贵（像遵循链表一样的大模式），您不会从缓存中受益于向量，但通常这是您在迭代时所做的事情，而不是迭代本身。
你能告诉我们更多关于当你遍历整个地图时你期望做的事情吗？
于 2009-04-08T15:29:19.770 回答