How Does C++ STL min_element, max_element, minmax_element work f

  • 时间：2020-10-09 18:35:39
  • 分类：网络文摘
  • 阅读：119 次

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;
}
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:

1
2
3
4

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
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
}
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
}
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
}
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:

1
2
3
4

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.
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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};
}
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++:

1
2
3
4

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

1
2
3

const auto v = { 3, 9, 1, 4, 2, 5, 9 };
auto it = max_element(begin(v), end(v));
// it will be the first 9
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) —

推荐阅读：
关于平方数　 翻茶杯问题　 百人报数问题　 归纳法之公鸡的智慧　 不可缺少的反证法　 1985是两个平方数的差吗　 111……111是平方数吗　 为什么1+1＝10　 共和国的脊梁　 遇见你就是幸福　
评论列表
添加评论