How Does C++ STL min_element, max_element, minmax_element work for Duplicate Items?

justyy (81)in #wherein • 4 years ago

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 &lt; *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 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!