迭代器访问性能为STL映射与矢量？ [英] Iterator access performance for STL map vs. vector?

问题描述

使用迭代器循环通过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.

推荐答案

对于map和vector，遍历整个集合都是O（N）。然而（像列表vs矢量）矢量连续地存储元素，所以访问下一个元素要便宜得多，因为它将最佳地使用缓存，而映射将不会。

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.

这篇关于迭代器访问性能为STL映射与矢量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！