### std::map linear and random access

Posted:

**Fri Oct 21, 2005 11:28 pm**Two short questions:

I assume random access of a STL map has a complexity of O(log n).

What I don't know however, is the time complexity of increasing a map iterator with one. I assume it's constant but you never know.

More preciesly: If we disregard overhead etc, how much slower is iterating through a std::map compared to a std::list or std::vector?

Thanks.

Edit: Forward iterators guarantees to run in O(1).

I assume random access of a STL map has a complexity of O(log n).

What I don't know however, is the time complexity of increasing a map iterator with one. I assume it's constant but you never know.

More preciesly: If we disregard overhead etc, how much slower is iterating through a std::map compared to a std::list or std::vector?

Thanks.

Edit: Forward iterators guarantees to run in O(1).