Iterator access performance for STL map vs. vector?

Question

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.

Answer 1

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.

Answer 2

Iterating through every element of a map takes O(n) time. wikipedia

Answer 3

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?

Answer 4

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.

Answer 5

This link has a nice table of performance for various operations on all of the STL containers.

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.