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

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

September 6, 2020 No Comments c / c++

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

GD Star Rating
loading...
726 words
Last Post: Using the External Fan to Cool the Hot AMD Radeon HD 6700 Graphic Card
Next Post: Algorithm to Replace All ?'s to Avoid Consecutive Repeating Characters

The Permanent URL is: How Does C++ STL min_element, max_element, minmax_element work for Duplicate Items?

Related posts:

  1. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  2. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  3. Another Batch Utility: Reverse the Given Text If you have something that are not so important but prefer not so easy to...
  4. Microbit Programming: Introduction to AI – Letting Computer Play the Game Last week, we present a apple-catching game in Microbit: Microbit Programming: How to Make a...
  5. Efficient Algorithms to Compute The kth Factor of a Natural Number N Given two positive integers n and k. A factor of an integer n is defined...
  6. Interview Coding Exercise – Nested String (Python) Nested String A string S consisting of N characters is considered to be properly nested...
  7. Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree Given a binary tree root and an integer target, delete all the leaf nodes with...
  8. Teaching Kids Programming – Algorithms to Find the Cycle of a Linked List Teaching Kids Programming: Videos on Data Structures and Algorithms Given a Linked List, find out...

Leave a Reply