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

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

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) —

推荐阅读：
5 Tips for Staying Safe Online　 10 Signs Your Blog is Working　 The Key to Risk-Free Cloud-Based IT Equipment Shipping　 Bring Your Multi-Site Development Work To The Next Level With A 　 
How to Create Killer SEO Content on a Budget　 Learn to Achieve Your Goals with 5 Secrets of Great Bloggers　 What is Cornerstone Content And Why It’s Important　 How to Attract Female Readership For Your Blog　 Double your traffic with White Hat SEO techniques　 Blogging As Therapy: True Life Stories Of Victims And How They C　
评论列表
添加评论