按非惰性 lambda 表达式/投影排序

Question

我有一个某种类型的元素数组 T。对于一些复杂的函数我想按该函数的值对数组进行排序。高效。

当我研究如何做这样的事情时，我很快发现可以在 projections[= 的帮助下使用 range-v3 库中的 range::v3::sort 39=]。在这种情况下，值 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

您显然需要存储函数调用。如果您不想在地图中执行此操作（因此您可以按数据值进行索引）但在向量中（比地图开销少得多）那么您不能直接对原始数组进行排序（因为您没有 link从每个数据值到它的函数值，需要索引）。因此，我们改为将索引排序到数据数组中：

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 值直接排序完全相同的效果，但也许这对您来说没有必要。

Demo

Answer 2

根据 Phil M 的建议和 Max Langhof 的部分解决方案（谢谢！），我设计了以下具有非惰性投影的排序函数的相对通用的实现。它使用链接就地置换函数。

#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 
    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 3

你可以存储评估，并将其用作投影（我实际上不投影，因为元组的顺序很好，原始数据也可以比较）：

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

按非惰性 lambda 表达式/投影排序

Sort by non-lazy lambda expression / projection

c++

sorting

c++11

range-v3