Как отсортировать диапазон на основе значения некоторого преобразования его значений?

Question

Позвольте arr быть массивом некоторого типа T и func(const &T) некоторой вычислительно дорогой функцией. Чтобы отсортировать arr по значению func(T), мы могли бы наивно написать.

std::sort(arr.begin(), arr.end(), [](const T& a, const T&b) {
    return func(a) < func(b);
}

Однако это вызовет в среднем func O (nlogn) раз. Очевидно, нам нужно не более чем ровно n вызовов. Есть ли какой-то идиоматичный и лаконичный способ сделать это?

Мне известны следующие два решения, но я бы хотел найти более подходящее.

• Упаковка T s и возвращаемого значения func в структуру и сортировка. Это оптимально в вычислительном отношении, но также делает одну полную копию исходного массива перед сортировкой и еще одну полную копию для последующего возврата значений в arr

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

Идеальным решением было бы использование STL с как можно меньшим количеством стандартного кода, но все материалы приветствуются.

Answer 1

Первое неуниверсальное решение

То, что вам нужно, это своего рода запоминание результата функции.Если ваша функция fun не имеет побочных эффектов и при использовании ее в std::sort я предполагаю, что нет, я бы подумала что-то вроде этого:

#include <unordered_map>

template<class T, class U>
class caller{
public:
    const U &call(const T& t) const{
        auto found = memoized.find(t);
        if (found != memoized.end())
            return found->second;

        return memoized.insert(std::make_pair(t, fun(t))).first->second;
    }
private:
    mutable std::unordered_map<T, U> memoized;
};

Ее использование будет выглядеть следующим образом:

caller<T, decltype(func(std::declval<T>()))> c;
std::sort(arr.begin(), arr.end(), [](const T& a, const T&b) {
    return c.call(a) < c.call(b);
}

Более общее решение

После принятия первого решения я немного поиграл и сделал немного более универсальным, совместимым с C ++ 17.Он должен работать с каждой функцией, принимающей один аргумент, который может быть преобразован и хэшируем.Взгляните:

#include <unordered_map>

int fii(int){
    return 0;
}

template<class T, auto fun>
class memoizer{
public:
    const auto &call(const T& t) const{
        auto found = memoized.find(t);
        if (found != memoized.end())
            return found->second;

        return memoized.insert(std::make_pair(t,  fun(t)))
            .first->second;
    }
private:
    mutable std::unordered_map<T, decltype(fun(T()))> memoized;
};

auto memoized_fii = memoizer<int, fii>{};