Russian Qt Forum

Задача простая и довольно типичная:
 - имеется последовательность элементов (может быть контейнер, пара итераторов, ...)
 - есть нетривиальный алгоритм для оценки элементов, результат представляется в виде значения типа double,
 - нужно найти элемент (его индекс/итератор) с максимальным значением оценки.

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

Как можно эту простую задачу решить через алгоритмы в stl/boost чтобы не писать каждый раз вручную цикл наподобие такого:
?

Алгоритм std::max_element не подходит сразу, т.к. требует предикат для сравнения и будет несколько раз вызывать функцию оценки для одного и того же элемента.

Попробовал также boost::range, там есть boost::adaptors::transformed, но в него не получается передавать lambda, которая захватывает контекст. Оборачивать такую lambda в std::function - опять же потеря производительности, насколько я понимаю.

Так чем можно заменить простой цикл с поиском лучшего элемента?

> Алгоритм std::max_element не подходит сразу, т.к. требует предикат для сравнения и будет несколько раз вызывать функцию оценки для одного и того же элемента.

Что тебе мешает закешировать в предикате?

Что именно закешировать? Одно значение только? Все равно придется сравнивать с двумя аргументами предиката, это лишняя работа.

Меня бы устроил вариант через boost::range типа такого:
Простая и понятная запись, но оно не работает с lambda.

наверно имелось ввиду закэшировать в мапе QHash<Point, double> произведенные расчеты, тогда для того же Point расчет уже выполнен

Да тут, наверное, проще свой qmax_element написать:

C++ (Qt)
template <class It,  class UnaryFunction>
It qmax_element(It first, It last, UnaryFunction f)
{
    auto max = f(*first);
    It it = first++;
 
    for (; first != last; ++first)
    {
        auto val = f(*first);
        if (val > max)
        {
            max = val;
            it = first;
        }
    }
    return it;
}
 

А в чём там выйгрышь? Он ведь тоже использует std::max_element в конечном счёте..
https://www.boost.org/doc/libs/1_56_0/boost/range/algorithm/max_element.hpp (https://www.boost.org/doc/libs/1_56_0/boost/range/algorithm/max_element.hpp)

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

Да, boost::range не подходит в таком случае.

Не, в принципе, решается через тот же std::max_element, но это на любителя:

C++ (Qt)
    std::vector<int> v = {21, 3434222, 3, -10, -4, 101, 5};
 
    auto max = cost(v[0]);
 
    auto it = std::max_element(v.begin(), v.end(), [&max](int, int x)->bool
    {
        auto val = cost(x);
        bool res = val > max;
        if (res)
            max = val;
 
        return res;
    });
 

Я этому давно не удивляюсь. Простецкий for часто оказывается лучшим решением. Хороших, полезных вещей в std::algorithm мало, основная масса так - написать вумную соплю чтобы было на 1-2 строки меньше.

С лямбдой работает Range-v3 (https://ericniebler.github.io/range-v3/):

C++ (Qt)
    auto points_costs = ranges::view::transform(points, cost);
    auto index        = ranges::distance(points_costs.begin(),
                                         ranges::max_element(points_costs));

Но во время работы ranges::max_element могут повторно вычисляться cost (для текущей максимальной точки).


Задача может не такая уж и простая. Стандартные алгоритмы не знают, что можно кэшировать, а что нужно вычислять каждый раз. Может в cost рандом какой присутствует, или зависимость от времени. Алгоритму нужно об этом как-то сообщать. И в этом случае действительно проще свой алгоритм написать.