How to find max element of a vector with user defined predicate

Question

I need to find the maximum element of a vector. I want to use max_element from the STL library.

The code I have tried is:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class A
{
public:
    A(int _size, long _len) : size(_size), len(_len){}

    int size;
    long len;
};

bool CompareMaxA(const A& _a, const A& _b)
{
    return _a.len > _b.len;
}

int main() {

    vector<A> vec;
    A a1(3, 10);
    A a2(5, 30);
    vec.push_back(a1);
    vec.push_back(a2);

    auto it = max_element(vec.begin(), vec.end(), CompareMaxA);

    cout << "max = " << it->len;

    return 0;
}

I get max = 10, instead of max = 30. Why?

Answer 1

This comparison

bool CompareMaxA(const A& _a, const A& _b)
{
    return _a.len > _b.len;
}

returns true if the first argument is greater than the second argument.

The standard algorithm std::max_element uses the following condition

comp( max_value, current_value )

and if the return value is true then current_value becomes max_value.

Your comparison function never returns true because 10 is always less than 30.

It will return true if some current_element will be less then the first element that initially is considered as a current maximum.

So your function searches the minimum element in the vector.

To find the maximum element you have to invert the condition.

bool CompareMaxA(const A& _a, const A& _b)
{
    return _a.len < _b.len;
}

that corresponds to the standard function object std::less.

Consider the following demonstration program

#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>

/*
//How the algorithm can look

template <class ForwardIterator, class Compare>
ForwardIterator max_element( ForwardIterator first, ForwardIterator last, Compare comp )
{
    auto max_element = first;

    if ( first != last )
    {
        while ( ++first != last )
        {
            if ( comp( *max_element, *first ) ) max_element = first;
        }
    }

    return max_element;
}
*/

int main( void )
{
    int a[] = { 1, 2, 3, 4, 5 };

    auto it = max_element( std::begin( a ), std::end( a ), std::less<>() );

    std::cout << *it << '\n';

    // this corresponds to your comparison function
    it = max_element( std::begin( a ), std::end( a ), std::greater<>() );

    std::cout << *it << '\n';
}

Its output is

5
1

That is using the algorithm std::max_element with the a compare function similar to the standard function object std::less gives the maximum value.

Using the algorithm std::max_element with the a compare function similar to the standard function object std::greater gives the minimum value.

And vice versa

Using the algorithm std::min_element with the a compare function similar to the standard function object std::less gives the minimum value.

And using the algorithm std::min_element with the a compare function similar to the standard function object std::greater gives the maximum value.

Answer 2

Your comparison function does the wrong thing. It returns true whenever _a.len is greater than _b.len, but std::max_element requires a custom comparison function that returns true in exactly the opposite scenarios. From cppreference on std::max_element:

Parameters

[...]

comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than the second.

You can fix it by

bool lessThanByLen(const A& _a, const A& _b)
{
    return _a.len < _b.len;
}

auto it = max_element(vec.begin(), vec.end(), lessThanByLen);

Custom comparators used by/passed to the standard library for order relations always seek for a less-than relation. In this case, the algorithm name (max_element) indicates that a maximum shall be found.

Note that as @JeJo pointed out in the comments, you can also consider passing a lambda:

auto it = max_element(vec.begin(), vec.end(),
    [](const A& lhs, const A& rhs) { return lhs.len < rhs.len; });

Answer 3

In STL, predicates are expected to check the less relationship (i.e., if LHS is less than RHS). If your custom predicate implements the greater operator, the result will be opposite (ex. max->min).

The solution is to replace the > in CompareMaxA with <.