C ++: выбрать argmax по вектору классов по произвольному выражению

Question

У меня проблемы с описанием моей проблемы, поэтому я приведу пример:

У меня есть описание класса, в котором есть пара переменных, например:

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

Теперь я поддерживаю vector<A>, который содержит многие из этих классов. То, что мне нужно сделать очень часто, - это найти объект внутри этого вектора, который удовлетворяет тому, что один из его параметров является максимальным по отношению к другим. т.е. код выглядит примерно так:

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.

Есть ли какой-нибудь хороший способ избежать этого безумия в C ++? Какой самый лучший способ справиться с этим?

Спасибо!

Answer 1

Я знаю, что этот поток старый, но я считаю весьма полезным реализовать мощную функцию argmax в C ++.

Однако, насколько я вижу, все приведенные выше примеры основаны на std ::max_element, который выполняет сравнение между элементами (используя функтор или вызывая оператор <).это может быть медленным, если расчет для каждого элемента стоит дорого.Он хорошо работает для сортировки чисел и обработки простых классов, но что, если функтор намного сложнее?Может быть, вычисление эвристического значения шахматной позиции или чего-то еще, что генерирует огромное дерево и т. Д. </p>

Реальный argmax, как упоминалось в начале потока, вычислит только один аргумент arg, а затем сохранит его для сравнения сдругие.

РЕДАКТИРОВАТЬ: Хорошо, я был раздражен и имел слишком много свободного времени, поэтому я создал одну версию

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

Версия без C ++ 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

Answer 2

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 представляет собой итератор до максимального значения.Вы можете разыменовать его, чтобы получить элемент max, или вы можете использовать std::distance(v.begin(), i), чтобы найти соответствующий индекс (сначала включите <iterator>).

См. http://codepad.org/XQTx0vql для полного кода.

Answer 3

Всегда ли выражение линейно? Вы можете передать массив из четырех коэффициентов. Если вам нужно поддерживать произвольные выражения, вам понадобится функтор, но если это просто аффинная комбинация из четырех полей, тогда вам не понадобится вся эта сложность.

Answer 4

Вы можете использовать алгоритм std::max_element STL, каждый раз предоставляя пользовательский предикат сравнения.

С C ++ 0x вы даже можете использовать лямбда-функцию для максимальной краткости:

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

Answer 5

Вот для чего созданы функторы и 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));

Answer 6

Вы можете использовать алгоритм 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));

Answer 7

Пример использования max_element / min_element с пользовательским функтором

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