Geek asks and answers

C ++: select argmax over wrt class vector arbitrary expression

I have problems describing my problem, so I will give an example:

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

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

Now I support vector<A>, which contains many of these classes. What I need to do very often is to find an object inside this vector that satisfies the fact that one of its parameters is maximum wrt to the other. The code looks something like this:

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];

a, b, 0.8*a + 0.2*b, a*VAR + b, VAR - , .. , max. , , res.

++? ?

!

+2
7
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); }

<functional>. , <algorithm>

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


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


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


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;
};


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

a a b. , mem_ptr . std::max_element . , , std::distance(v.begin(), i) ( <iterator>).

. http://codepad.org/XQTx0vql.

+1

, , argmax ++.

, , std:: max_element, ( , <). , . , , ? , - , ..

argmax, , , .

EDIT: , , < ++ 11 ++ 11 r-, ++ 11:

#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;
}

++ 11 , :

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;
}

, , , unary_function

+2

std::max_element .

, -.

, . "-", :

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);
}

:

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

, STL :

// 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));
+1

std::max_element STL, .

With C ++ 0x, you can even use a lambda function for this for maximum brevity:

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);
});
+1
source

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

+1
source

Example using max_element / min_element with a 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;
}
0
source

More articles:


All Articles