c++ - 如何根据某个值的某个转换值对范围进行排序？

令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和func的返回值包装在结构中并对其进行排序。这在计算上是最佳的，但它也可以在排序之前对初始数组进行一个完整复制，然后对它进行另一个完整复制以将值放回arr

创建第二个数组并对数组进行并行排序。据我所知，还没有惯用的方式对两个数组进行排序。可以通过编写自定义迭代器和交换函数来完成。这已经足够好了，但是它还需要比理想代码还要多的样板代码。

理想的解决方案是基于STL并尽可能减少样板代码，但欢迎所有贡献。

最佳答案

第一个非通用解决方案

您需要的是一种功能结果的记忆。如果您的函数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>{};

关于c++ - 如何根据某个值的某个转换值对范围进行排序？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55668347/