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, whilestd::prev(c.end())does.
Advancing in any direction is linear in the number of advances (in your case that's one, so we can call it constant-time), but you don't need to do it. Just use rbegin() which is an iterator to the last element.
std::prev is not equivalent to --std::map.end() though, the latter of which is not guaranteed to do anything useful at all. See the std::prev docs.
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?
All of std::map.end, std::prev(a_std_map_iterator) and std::map::iterator::operator* are constant operations. Therefore that expression is constant as a whole.
Note that the complexity of std::prev is guaranteed to be at most linear in terms of the second argument n, which is defaulted to 1. When n is constant, std::prev as a whole is constant.
