STL映射与向量的迭代器访问性能？

Question

使用迭代器循环STL映射与向量之间的性能差异是什么？我想使用map键进行插入,删除和一些访问,但我还需要定期访问map中的每个元素.

Answer 1

使用map和vector,遍历整个集合的是O(N).然而(像列表与矢量一样)矢量连续存储元素,因此访问下一个元素要便宜得多,因为它将最佳地使用缓存,而地图则不会.

但由于您需要基于密钥进行查找,因此没有其他选择.你可以使用在第一个元素上排序的对向量,但如果集合需要是可变的,那么这将是非常慢的.只需使用地图.

Answer 2

迭代地图的每个元素需要O(n)时间.维基百科

Answer 3

此链接有一个很好的性能表,可用于所有STL容器上的各种操作.

一般来说,如果您需要根据密钥进行大量插入,删除或搜索,那么地图就是您的选择.

如果您只需要设置一次容器然后像数组一样访问它,那么使用向量.

编辑:STL容器操作的性能表:

Answer 4

遍历映射可能是线性的，但实际上，从 C++ 中的实现来看，效率并不高。所以我的建议是使用一个向量并使用另一个地图在线性时间内定位向量中的项目。