How smart is std::max_element()?

user_1387866 0
Viewed 217

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?

stl algorithm c++
1 Answers

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.
user_9924900
Related