How smart is std::max_element()?

Question

Suppose I have an std::vector<int>:

std::vector<int> v;
[v is initialized]

and I want to get the maximum element of v. There is an algorithm for doing that:

int max_value = *std::max_element(v.begin(), v.end());

So far, so good.

Now, suppose that v contains 10,000,000 elements, and its 10th element is equal to std::numeric_limits<int>::max(). Is std::max_element() going to (unnecessarily) examine the 9,999,990 last elements of v, or is it going to recognize that there cannot be elements larger than std::numeric_limits<int>::max(), and thus stop after the 10th element?

Answer 1

I can't speak for all implementations, but libc++'s implementation of max_element does not do that.

There's a couple problems with the idea:

• The assumption that there exists a specialization of numeric_limits for the type of the elements of the sequence. (max_element works on anything that can be ordered.) This could be worked around with some template meta-programming.
• There's a version of max_element that takes a comparison predicate, not just operator <. What's the max value in that case?
• This would require that the type in the sequence be "equality-comparable", not just "less than comparable".
• (Probably the most important) This would introduce a test inside the loop that enumerates the elements of the sequence, thereby slowing the algorithm down for everyone else.