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

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

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

推荐阅读：
Ordered Three 2TB WD HDD to prolong the life expectancy of HPZ80　 HPZ800 Server Does Not Support Hard Drives Larger Than 2TB　 Fresno Blogger Changing The Vegan Blogging Scene　 Russian ‘Pokemon Go’ Blogger Goes On Trial　 Starting a Blog? 5 Topics People Care About in 2017　 6 Strategies To Grow Your Facebook Page　 5 Sure Shot Content Marketing Trends to Follow　 7 Ways for Your Underdog Blog to Beat the Competition　 Darkstore Aims to be Less Invasive Alternative to Tech Giants ac　 5 Free Blogging Apps You Need On Your IPhone Right Now　
评论列表
添加评论