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.

Solution 1

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.

Solution 2

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

Solution 3

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.

EDIT: Performance table of STL container operations:

Solution 4

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 .

Solution 5

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.

View more solutions