Saurav Sahu Saurav Sahu - 1 month ago 5
C++ Question

Is there any efficiency advantage in using minmax_element over min_element and max_element together?

std::minmax_element
: returns a pair consisting of an iterator to the smallest element as the first element and an iterator to the greatest element as the second.

std::min_element
: returns an iterator to the smallest element in the range [first, last).

std::max_element
: returns an iterator to the largest element in the range [first, last).

What I am most afraid of is : does std::minmax_element uses sorting of complete list to achieve this? Is yes, then I would be least excited in using it.

Is the overhead of processing returned pair from std::minmax_element worthy enough?

Answer

You do not have to worry about std::minmax_element doing any sorting. It leaves the range in the exact way it was traversed. The reason it is more efficient is it can find both the max and min in a single pass where when looking for max and min separately you have to do two full traversals.

std::minmax_element has the complexity of max(floor(3/2(N−1)), 0) where as std::max_element and std::min_element each are max(N-1,0) so it is about 25% less operations using std::minmax_element

There is also a difference where std::minmax_element finds the last largest element while std::max_element finds the first largest.

So if you need to find the min and max of a range then you should use std::minmax_element. If you only need the min or max then you should use the specialized version.