The C++ STL min_element, max_element and minmax_element (C++ 11) are useful functions from header algorithms to get the min, max, and min-and-max iterator from a given range of iterators. These functions take first parameter the begin iterator of a range (vector, list or array), and second parameter the end iterator. Optionally, you can use customize comparator as the third parameter.
C++ min_element
For example, one possible of min_element implementation with first version is:
template<class It>
It min_element(It first, It last) {
if (first == last) {
return last;
}
auto smallest = first;
++first;
for (; first != last; ++first) {
if (*first < *smallest) {
smallest = first;
}
}
return smallest;
}
Example usage is:
vector<int> data = {1, 3, 2, 5, 4};
auto it = min_element(begin(data), end(data));
// it is now equal to begin(data)
// where *it is 1 and *it-begin(data) is 0 ie. the index
The second version of min_element takes a third parameter which provides a custom comparator:
template<class It, class Compare>
It min_element(It first, It last, Compare comp) {
if (first == last) {
return last;
}
auto smallest = first;
++first;
for (; first != last; ++first) {
if (comp(*first, *smallest)) {
smallest = first;
}
}
return smallest;
}
Both implementation have O(N) time and O(1) space complexity.
C++ max_element
Similarly, the C++ max_element returns the iterator of the maximum element.
template<class It>
It max_element(It first, It last) {
if (first == last) {
return last;
}
auto largest = first;
++first;
for (; first != last; ++first) {
if (*largest < *first) {
largest = first;
}
}
return largest;
}
And it also supports an optional third parameter as the custom comparator:
template<class It, class Compare>
It max_element(Itfirst, It last, Compare comp) {
if (first == last) {
return last;
}
auto largest = first;
++first;
for (; first != last; ++first) {
if (comp(*largest, *first)) {
largest = first;
}
}
return largest;
}
Example usage similar to above:
vector<int> data = {1, 3, 2, 5, 4};
auto it = max_element(begin(data), end(data));
// it is now equal to begin(data)+3
// where *it is 5 and *it-begin(data) is 3, ie. the index.
C++ 11 minmax_element
Sometimes, we want to know the min and max - and instead of doing two passes, we can use the C++ STL minmax_element to return both at one go:
template<class It> std::pair<It, It> minmax_element(It first, It last) {
using value_type = typename std::iterator_traits<It>::value_type;
return std::minmax_element(first, last, std::less<value_type>());
}
template<class It, class Compare> std::pair<It, It> minmax_element(It first, It last, Compare comp) {
auto min = first, max = first;
if (first == last || ++first == last) {
return {min, max};
}
if (comp(*first, *min)) {
min = first;
} else {
max = first;
}
while (++first != last) {
auto i = first;
if (++first == last) {
if (comp(*i, *min)) min = i;
else if (!(comp(*i, *max))) max = i;
break;
} else if (comp(*first, *i)) {
if (comp(*first, *min)) min = first;
if (!(comp(*i, *max))) max = i;
} else {
if (comp(*i, *min)) min = i;
if (!(comp(*first, *max))) max = first;
}
}
return {min, max};
}
Example usage in C++:
const auto v = { 3, 9, 1, 4, 2, 5, 9 };
const auto [minValue, maxValue] = std::minmax_element(begin(v), end(v));
// minValue is 1
// maxValue is 9
Duplicate Min/Max Items using std::min_element, max_element and minmax_element
By default, if there are duplicate min, max elements in the array, these functions will return the first item (iterator) unless you provide the custom comparator.
const auto v = { 3, 9, 1, 4, 2, 5, 9 };
auto it = max_element(begin(v), end(v));
// it will be the first 9
--EOF (The Ultimate Computing & Technology Blog) --
Reposted to Algorithms, Blockchain and Cloud
Follow me for topics of Algorithms, Blockchain and Cloud.
I am @justyy - a Steem Witness
https://steemyy.com
Steem/Blurt On!~
Every little helps! I hope this helps!
If you like my work, please consider voting for me or Buy Me a Coffee, thanks!
https://steemit.com/~witnesses type in justyy and click VOTE
Alternatively, you could proxy to me if you are too lazy to vote!
Also: you can vote me at the tool I made: https://steemyy.com/witness-voting/?witness=justyy