std::map linear and random access

Write here if you have problems with your C++ source code

Moderator: Board moderators

Post Reply
Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden

std::map linear and random access

Post by Bj » 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).

Post Reply

Return to “C++”