Sort by non-lazy lambda expression / projection

Question

I have an array of element of some type T. For some complex function I would like to sort the array by the value of that function. Efficiently.

When I did some research on how to do such a thing, I quickly found that range::v3::sort, from the range-v3 library, could be used with the help of projections. In that context, the value T can be projected onto a new value to be used by a comparator. The problem is, that it is done lazily.

Consider the following example:

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

Here T and f are kept simple for the sake of brevity. This gives me the output:

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

But envision that f is some complex function that I do not want to be executed repeatedly, each time it is used in the comparator (otherwise I could just write a custom comparator and use regular std::sort). I would expect f to be called exactly once for each of the values. However, once the array is sorted, the results of f can be discarded.

Also, the real values of T themselves are relatively complex. I can quickly swap two elements around, but I shouldn't copy them into a new, temporary container (e.g. std::vector<std::pair<T,int>>) for sorting.

Is there some brief approach to that, besides manually sorting my input array?

Answer 1

You might store evaluation, and use it as projection (I don't project actually as order of tuple is fine, and original data is also comparable):

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>`.

Demo

Answer 2

You evidently need to store the function invocations. If you don't want to do this in a map (so you can index by the data value) but in a vector (much less overhead than a map) then you can't sort the original array directly (because you have no link from each data value to its function value, you need the index). So, we sort indices into the data array instead:

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;

You'd still have to apply the permutation to get the exact same effect as sorting directly with comparing f values, but maybe that's unnecessary for you.

Demo

Answer 3

Following the suggestion of Phil M and partial solution of Max Langhof (thank you!) I devised the following, relatively general implementation of sort function with non-lazy projection. It uses the linked in-place permutation function.

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

I was hoping that there is some library or very short application of existing tools to avoid reinventing the wheel.