What is the time complexity of getting the max key of a std::map in C++?

  • A+
Category:Languages

I'm trying to find the largest value in a std::map, which would be the last node in the tree (since std::map keys are sorted).

Cppref says std::map.end() is constant time. But to get the largest key, I must get the previous value of this iterator, i.e. *std::prev(std::map.end()).

What's the time complexity of that operation?

I understand that this should equivalent to --std::map.end(), but I don't know the cost of that operation either.

 


Use an std::map::rbegin() instead, which:

Returns a reverse iterator pointing to the last element in the container (i.e., its reverse beginning).

and:

Complexity

Constant.

where the last word should sound like music in your ears.


std::prev(std::map.end()) is constant in complexity.


Moreover, your understanding about the equivalency is wrong.

From std::prev notes:

Although the expression --c.end() often compiles, it is not guaranteed to do so: c.end() is an rvalue expression, and there is no iterator requirement that specifies that decrement of an rvalue is guaranteed to work. In particular, when iterators are implemented as pointers, --c.end() does not compile, while std::prev(c.end()) does.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: