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

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

您可以存储评估，并将其用作投影(我实际上不投影，因为元组的顺序很好，原始数据也具有可比性):

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