CODEWITHSUNDEEP
c++algorithmstdmap
user3882729
user3882729

Reputation: 1534

Finding minimum value in std::map

For a non-selfbalancing binary search tree, finding the minimum in the worst case can take O(N) and average case O(log(N)) to traverse to the corresponding leaf node.

Per CPPreference, the time complexity of the function std::map::begin() is constant. Therefore extending this a little further, de-referencing std::map::begin() which yields the lowest key by default also takes constant time. Can someone explain why this might be the case?

Upvotes: 0

Views: 370

Answers (1)

cdhowie
cdhowie

Reputation: 169028

The map object could simply maintain an internal pointer to the minimum element; if the tree is mutated in a way that changes which node is the minimum, the pointer to this element could be adjusted at that time. Returning an iterator from the pointer is therefore a constant-time operation since no tree traversal is necessary.

Note that std::map is self-balancing.

Upvotes: 4

Related Questions