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

Question

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.

Answer 1

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.