• Advertisement
Sign in to follow this  

std::map::find() speed

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
find() will operate in O(logN) while iterating through it could be O(N). I would use the find function.

Share this post


Link to post
Share on other sites
If you already have an iterator you can access the element through that iterator in constant time (O(1)).

Share this post


Link to post
Share on other sites
map::find() is O(logn)
find() in <algorithm> is always O(n)
binary_search() in <algorithm> is O(logn), but only with random-access iterators, which map doesn't provide.

Each of these methods will give you an iterator which gives O(1) access to the corresponding element.

Note that I'm assuming you're looking for a key in your map. If you're looking for a value you're stuck with the O(n) find_if() in <algorithm> with a custom predicate -- nothing else will work.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement