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).
std::map.end() is constant time. But to get the largest key, I must get the previous value of this iterator, i.e.
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.
std::map::rbegin() instead, which:
Returns a reverse iterator pointing to the last element in the container (i.e., its reverse beginning).
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.
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