Сортировка по ленивому выражению / проекции лямбды

Question

У меня есть массив элементов некоторого типа T.Для некоторой сложной функции я бы хотел отсортировать массив по значению этой функции.Эффективно.

Когда я провел некоторое исследование о том, как это сделать, я быстро обнаружил, что range::v3::sort из библиотеки range-v3 можно использовать с помощью проекций ,В этом контексте значение T может быть спроецировано на новое значение, которое будет использоваться компаратором.Проблема в том, что это делается лениво.

Рассмотрим следующий пример:

#include <range/v3/algorithm/sort.hpp>
#include <vector>
#include <iostream>

int main() {
    int invocations=0;
    std::vector<int> data{1,5,2,7,6,3,4,8,9,0};
    auto f = [&](int val){
        ++invocations;
        return val%2 ? val+100 : val;
    };
    ranges::v3::sort(data, std::less<int>{}, f);
    for (int v : data) {
        std::cout << v << ' ';
    }
    std::cout << "Invocations " << invocations << std::endl;
}

Здесь T и f сохраняются простыми для краткости.Это дает мне вывод:

0 2 4 6 8 1 3 5 7 9 Invocations 60

Но представьте, что f - это некоторая сложная функция, которую я не хочу выполнять повторно, каждый раз, когда она используется в компараторе (в противном случае я мог бы просто написатьПользовательский компаратор и регулярное использование std::sort).Я ожидаю, что f будет вызываться ровно один раз для каждого из значений.Однако после сортировки массива результаты f могут быть отброшены.

Кроме того, реальные значения самих T относительно сложны.Я могу быстро поменять два элемента, но мне не следует копировать их в новый временный контейнер (например, std::vector<std::pair<T,int>>) для сортировки.

Есть ли какой-то краткий подход к этому, кроме ручной сортировки входного массива

Answer 1

Следуя предложению Фила М и частичному решению Макса Лангофа (спасибо!), Я разработал следующую, относительно общую реализацию функции сортировки с не ленивой проекцией.Он использует связанную функцию перестановки на месте.

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

template <typename T, typename Comp, typename Proj>
void sort_proj(std::vector<T>& v, Comp cmp, Proj f) {
    using FRet = std::invoke_result_t<Proj, T>;
    using Tmp = std::pair<size_t, FRet>;

    //create temporary values of f
    std::vector<Tmp> fval;
    fval.reserve(v.size());
    for (size_t i=0; i<v.size(); ++i)
        fval.emplace_back(i, f(v[i]));

    //sort it
    std::sort(fval.begin(), fval.end(), [&cmp](const Tmp& a, const Tmp& b) { return cmp(a.second, b.second); });

    //apply the permutation
    //based on https://stackoverflow.com/a/17074810/635654
    std::vector<bool> done(v.size());
    for (std::size_t i = 0; i < v.size(); ++i) {
        if (done[i])
            continue;
        done[i] = true;
        std::size_t prev_j = i;
        std::size_t j = fval[i].first;
        while (i != j) {
            std::swap(v[prev_j], v[j]);
            done[j] = true;
            prev_j = j;
            j = fval[j].first;
        }
    }
}

int main() {
    int invocations=0;
    std::vector<int> data{1,5,2,7,6,3,4,8,9,0};
    auto f = [&](int val){
        ++invocations;
        return val%2 ? val+100 : val;
    };
    sort_proj(data, std::less<int>{}, f);
    for (int v : data) {
        std::cout << v << ' ';
    }
    std::cout << "Invocations " << invocations << std::endl;
}

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

Answer 2

Вы можете сохранить оценку и использовать ее в качестве проекции (на самом деле я не проецирую, поскольку порядок кортежа в порядке, а исходные данные также сопоставимы):

std::vector<int> data{1,5,2,7,6,3,4,8,9,0};
auto values = data | ranges::view::transform(f) | ranges::to_vector;
// to_vector needed to do evaluation **now**.
ranges::v3::sort(ranges::view::zip(values, data)); // Values first to avoid real projection
                                                   // else use projection on `get<I>`.

Демо

Answer 3

Вам, очевидно, нужно хранить вызовы функций.Если вы не хотите делать это на карте (так что вы можете индексировать по значению данных), но в векторе (намного меньше накладных расходов, чем на карте), то вы не можете сортировать исходный массив напрямую (потому что у вас нет ссылки).от каждого значения данных до его значения функции нужен индекс).Итак, вместо этого мы сортируем индексы в массив данных:

int invocations=0;
std::vector<int> data{1,5,2,7,6,3,4,8,9,0};
auto f = [&](int val){
    ++invocations;
    return val%2 ? val+100 : val;
};

std::vector<int> fValues(data.size());
std::vector<int> indices(data.size());

std::transform(data.begin(), data.end(), fValues.begin(), f);

std::iota(indices.begin(), indices.end(), 0);
std::sort(indices.begin(), indices.end(), [&](auto i, auto j) {
    return fValues[i] < fValues[j];
});

for (int sortedIndex : indices) {
    std::cout << data[sortedIndex] << ' ';
}
std::cout << "Invocations " << invocations << std::endl;

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

Демо