Difference between revisions of "cpp/algorithm/minmax element"

Revision as of 11:13, 31 January 2019

Finds the smallest and greatest element in the range [first, last).

Parameters

Return value

a pair consisting of an iterator to the smallest element as the first element and an iterator to the greatest element as the second. Returns std::make_pair(first, first) if the range is empty. If several elements are equivalent to the smallest element, the iterator to the first such element is returned. If several elements are equivalent to the largest element, the iterator to the last such element is returned.

Complexity

At most max(floor((3/2)*(N−1)), 0) applications of the predicate, where N = std::distance(first, last).

Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Notes

This algorithm is different from std::make_pair(std::min_element(), std::max_element()), not only in efficiency, but also in that this algorithm finds the last biggest element while std::max_element finds the first biggest element.

Possible implementation

template<class ForwardIt>
std::pair<ForwardIt, ForwardIt> 
    minmax_element(ForwardIt first, ForwardIt last)
{
    return std::minmax_element(first, last, std::less<>());
}

template <class ForwardIt, class Compare>
std::pair<ForwardIt, ForwardIt> minmax_element(ForwardIt it, ForwardIt last,
                                               Compare comp) {
	const auto it_comp = [&comp](const auto& lhs, const auto& rhs) {
		return comp(*lhs, *rhs);
	};
 
	auto min = it;
	auto max = it;
 
	if (it == last or ++it == last) {
		return {min, max};
	}
 
	if (it_comp(it, min)) {
		min = it++;
	} else {
		max = it++;
	}
 
	// Note that `it` is increased TWICE per iteration of the loop
	// as there are three invocations of the predicate per iteration
	// this means that there are about 3/2 invocations per element:
	while (it != last) {
		const auto i0 = it++; // first advancement
		if (it == last) {
			if (it_comp(i0, min)) {
				min = i0;
			} else {
				max = std::max(i0, max, it_comp);
			}
			break;
		}
		const auto i1 = it++; // second advancement
		const auto [min_it, max_it] = std::minmax(i0, i1, it_comp);
		min = std::min(min, min_it, it_comp);
		max = std::max(max_it, max, it_comp);
	}
	return {min, max};
}
}

Example

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    const auto v = { 3, 9, 1, 4, 2, 5, 9 };
    const auto [min, max] = std::minmax_element(begin(v), end(v));
 
    std::cout << "min = " << *min << ", max = " << *max << '\n';
}

min = 1, max = 9

See also