C++: select argmax over vector of classes w.r.t. arbitrary expression

Question

I have trouble describing my problem so I'll give an example:

I have a class description that has a couple of variables in it, for example:

class A{
  float a, b, c, d;
}

Now, I maintain a vector<A> that contains many of these classes. What I need to do very very often is to find the object inside this vector that satisfies that one of it's parameters is maximal w.r.t to the others. i.e code looks something like:

int maxi=-1;
float maxa=-1000;
for(int i=0;i<vec.size();i++){
  res= vec[i].a;
  if(res > maxa) {
    maxa= res;
    maxi=i;
  }
}
return vec[maxi];

However, sometimes I need to find class with maximal a, sometimes with maximal b, sometimes the class with maximal 0.8*a + 0.2*b, sometimes I want a maximal a*VAR + b, where VAR is some variable that is assigned in front, etc. In other words, I need to evaluate an expression for every class, and take the max. I find myself copy-pasting this everywhere, and only changing the single line that defines res.

Is there some nice way to avoid this insanity in C++? What's the neatest way to handle this?

Thank you!

The name of the vector makes no difference at all. That you're even concerned about it suggests that you need to read about formal and actual parameters in [a good C++ book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Ben Voigt, Feb 23 '11 at 02:37
Thanks for judging me so quickly. I only included that because I didn't want someone to come up with some preprocessor hacks. — karpathy, Feb 23 '11 at 06:09
I removed that paragraph because it seems noone came up with those kinds of ideas anyway. — karpathy, Feb 23 '11 at 06:12

score 2 · Answer 1 · edited Nov 01 '12 at 13:37

I know this thread is old, but i find it quite useful to implement a powerful argmax function in C++.

However, as far as i can see, all the given examples above rely on std::max_element, which does comparison between the elements (either using a functor or by calling the operator<). this can be slow, if the calculation for each element is expensive. It works well for sorting numbers and handling simple classes, but what if the functor is much more complex? Maybe calculating a heuristic value of a chess position or something else that generate a huge tree etc.

A real argmax, as the thread starter mentioned, would only calculate its arg once, then save it to be compared with the others.

EDIT: Ok i got annoyed and had too much free time, so i created one < C++11 and one C++11 version with r-value references, first the C++11 version:

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

template<typename IteratorT, typename HeuristicFunctorT>
IteratorT argmax(IteratorT && it, const IteratorT & end, const HeuristicFunctorT & functor) {
    IteratorT best(it++);
    typename HeuristicFunctorT::result_type best_value(functor(*best));

    for(; it != end; ++it) {
        typename HeuristicFunctorT::result_type value(functor(*it));

        if (value > best_value) {
            best_value = value;
            best = it;
        }
    }

    return best;
}

template<typename IteratorT, typename HeuristicFunctorT>
inline IteratorT argmax(const IteratorT & begin, const IteratorT & end, const HeuristicFunctorT & functor) {
    return argmax(IteratorT(begin), end, functor);
}

class IntPairFunctor : public std::unary_function< std::pair<int, int>, int > {
public:
    int operator() (const std::pair<int, int> & v) const {
        return v.first + v.second;
    }
};

std::pair<int, int> rand_pair() {
    return std::make_pair(rand(), rand());
}

int main(int argc, const char **argv) {
    srand(time(NULL));

    std::vector< std::pair<int, int> > ints;

    std::generate_n(std::back_insert_iterator< std::vector< std::pair<int, int> > >(ints), 1000, rand_pair);

    std::vector< std::pair<int, int> >::iterator m (argmax(ints.begin(), ints.end(), IntPairFunctor()));

    std::cout << std::endl << "argmax: " << *m << std::endl;
}

The non C++11 version is much simpler, only the template:

template<typename IteratorT, typename HeuristicFunctorT>
IteratorT argmax(IteratorT it, const IteratorT & end, const HeuristicFunctorT & functor) {
IteratorT best(it++);
typename HeuristicFunctorT::result_type best_value(functor(*best));

for(; it != end; ++it) {
    typename HeuristicFunctorT::result_type value(functor(*it));

    if (value > best_value) {
        best_value = value;
        best = it;
    }
}

return best;
}

Note that neither version requires any template arguments, the only requirement is that the heuristic implements the unary_function class

James McNellis · Answer 2 · 2011-02-22T23:30:58.090

You can use the std::max_element algorithm with a custom comparator.

It's easy to write the comparator if your compiler supports lambda expressions.

If it doesn't, you can write a custom comparator functor. For the simple case of just comparing a single member, you can write a generic "member comparator" function object, which would look something like this:

template <typename MemberPointer>
struct member_comparator
{
    MemberPointer p_;

    member_comparator(MemberPointer p) : p_(p) { }

    template <typename T>
    bool operator()(const T& lhs, const T& rhs) const
    {
        return lhs.*p_ < rhs.*p_;
    }
};

template <typename MemberPointer>
member_comparator<MemberPointer> make_member_comparator(MemberPointer p)
{
    return member_comparator<MemberPointer>(p);
}

used as:

// returns an iterator to the element that has the maximum 'd' member:
std::max_element(v.begin(), v.end(), make_member_comparator(&A::d));

this works for one field, does it generalize to linear combinations of fields, however? I can't see how — karpathy, Feb 23 '11 at 05:56

score 1 · Answer 3 · answered Feb 22 '11 at 23:25

This is what functors and STL are made for:

// A class whose objects perform custom comparisons
class my_comparator
{
public:
    explicit my_comparator(float c1, float c2) : c1(c1), c2(c2) {}
    // std::max_element calls this on pairs of elements
    bool operator() (const A &x, const A &y) const
    {
        return (x.a*c1 + x.b*c2) < (y.a*c1 + y.b*c2);
    }
private:
    const float c1, c2;
};


// Returns the "max" element in vec
*std::max_element(vec.begin(), vec.end(), my_comparator(0.8,0.2));

Matteo Italia · Answer 4 · 2011-02-22T23:32:41.187

1

You could use the std::max_element STL algorithm providing a custom comparison predicate each time.

With C++0x you can even use a lambda function for it for maximum conciseness:

auto maxElement=*std::max_element(vector.begin(), vector.end(), [](const A& Left, const A& Right) {
    return (0.8*Left.a + 0.2*Left.b)<(0.8*Right.a + 0.2*Right.b);
});

edited Feb 22 '11 at 23:32

answered Feb 22 '11 at 23:27

Matteo Italia

123,740
17
206
299

score 1 · Answer 5 · answered Feb 22 '11 at 23:30

Is the expression always linear? You could pass in an array of four coefficients. If you need to support arbitrary expressions, you'll need a functor, but if it's just an affine combination of the four fields then there's no need for all that complexity.

Alexandre C. · Accepted Answer · 2011-02-23T23:18:09.173

template <typename F>
struct CompareBy
{
    bool operator()(const typename F::argument_type& x,
                    const typename F::argument_type& y)
    { return f(x) < f(y); }

    CompareBy(const F& f) : f(f) {}

 private:
    F f;
};


template <typename T, typename U>
struct Member : std::unary_function<U, T>
{
    Member(T U::*ptr) : ptr(ptr) {}
    const T& operator()(const U& x) { return x.*ptr; }

private:
    T U::*ptr;
};

template <typename F>
CompareBy<F> by(const F& f) { return CompareBy<F>(f); }

template <typename T, typename U>
Member<T, U> mem_ptr(T U::*ptr) { return Member<T, U>(ptr); }

You need to include <functional> for this to work. Now use, from header <algorithm>

std::max_element(v.begin(), v.end(), by(mem_ptr(&A::a)));

or

double combination(A x) { return 0.2 * x.a + 0.8 * x.b; }

and

std::max_element(v.begin(), v.end(), by(std::fun_ptr(combination)));

or even

struct combination : std::unary_function<A, double>
{
    combination(double x, double y) : x(x), y(y) {}
    double operator()(const A& u) { return x * u.a + y * u.b; }

private:
    double x, y;
};

with

std::max_element(v.begin(), v.end(), by(combination(0.2, 0.8)));

to compare by a member or by linear combinations of a and b members. I split the comparer in two because the mem_ptr thing is damn useful and worth being reused. The return value of std::max_element is an iterator to the maximum value. You can dereference it to get the max element, or you can use std::distance(v.begin(), i) to find the corresponding index (include <iterator> first).

See http://codepad.org/XQTx0vql for the complete code.

Hmmm, your first block of code does not compile. "Syntax error: missing ';' before identifier 'by'". There are many more, but this is how it starts... — karpathy, Feb 23 '11 at 05:49
@karpathy: it works fine. Did you include the correct headers ? Here is a sample version which shows you how to use: http://codepad.org/UwLw66ek — Alexandre C., Feb 23 '11 at 08:45
@karpathy: my bad, I did not specify them. I update my post for if someone comes across the same problem as yours. — Alexandre C., Feb 23 '11 at 23:14

score 0 · Answer 7 · answered Feb 22 '11 at 23:30

Sample of using max_element/min_element with custom functor

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

using namespace std;

struct A{
  float a, b, c, d;
};


struct CompareA {
  bool operator()(A const & Left, A const & Right) const {
    return Left.a < Right.a;
  }
};


int main() {
  vector<A> vec;
  vec.resize(3);
  vec[0].a = 1;
  vec[1].a = 2;
  vec[2].a = 1.5;

  vector<A>::iterator it = std::max_element(vec.begin(), vec.end(), CompareA());
  cout << "Largest A: " << it->a << endl;
  it = std::min_element(vec.begin(), vec.end(), CompareA());
  cout << "Smallest A: " << it->a << endl;
}

C++: select argmax over vector of classes w.r.t. arbitrary expression

7 Answers7

Linked