std::sort 通过一元映射

Question

C++ 标准库提供了将比较器传递给 std::sort 的功能。但是，在我的代码中有很多情况，我想通过函数 f 对 T 对象列表进行排序。像这样的比较器将是一个有效的选择：

bool compare(const T& a, const T& b) {
  return f(a) < f(b);
}

虽然这不是最优的。 f 的计算速度很慢，但是 return 每次调用相同的 T 对象时都会得到相同的值。所以我宁愿做的是为范围内的每个对象计算一次 f，然后使用这些结果对它们进行排序。

我的目标是编写这个函数（我没能做到）：

template <typename IterT, typename Transformation>
void sort(IterT left, IterT right, Transformation f) { /* ? */ }

这样在这个调用之后，f(*iter) <= f(*std::next(iter)) 对于序列 left 到 right 中的所有 iter。

此外，函数应满足以下要求：

不分配类型为 T 的任何其他对象。
多次 std::distance(left, right) 准确计算 f。
保持 O(n log n) 的整体复杂度。
应根据std::sort实施。当然，我可以通过实现自己的合并排序来解决这个问题，但这是我想避免的事情。

（首选C++11；C++14也可以）

Answer 1

如果你想坚持 std::sort，只需编写一个比较器，为 T.

的每个实例缓存你的函数值

示例：

struct Foo {
    int value;
};

// Replace with your CPU time intensive f() function
int evaluate(const Foo& foo) {
    std::cout << "Evaluating complex function on an instance of Foo..." << std::endl;
    return foo.value;
}

bool compare(const Foo& left, const Foo& right) {
    static std::unordered_map<Foo, int> cache;
    auto leftIt = cache.find(left);
    auto rightIt = cache.find(right);
    if (leftIt == cache.end())
        leftIt = cache.emplace(left, evaluate(left)).first;
    if (rightIt == cache.end())
        rightIt = cache.emplace(right, evaluate(right)).first;
    return (*leftIt).second < (*rightIt).second;
}

您可以在此处找到完整示例：https://gist.github.com/PandarinDev/ee75b095c4cc256a88496f1985bf57ba

这样 evaluate(const Foo&);（f(T) 在你的情况下）只会运行 N 次，其中 N = the number of unique instances of Foo.

编辑： 如下评论所述，如果将 T 个实例复制到地图中对您来说是个问题，您可以使用唯一标识符 -例如对象的地址 - 作为键而不是对象本身。

Answer 2

所以你想要的是我的 C++14 库中 Schwartzian transform. I don't have a simple solution in a few lines of code, but I did implement a Schwartzian transform utility 的 C++ 实现。不幸的是，它依赖于 std::sort 不处理的代理迭代器（至少在 Ranges TS 之前），但您可以使用库中的任何其他排序器。以下是您如何编写问题中提到的 sort 函数：

#include <cpp-sort/adapters/schwartz_adapter.h>
#include <cpp-sort/sorters/default_sorter.h>

template <typename IterT, typename Transformation>
void sort(IterT left, IterT right, Transformation f)
{
    using sorter = cppsort::schwartz_adapter<cppsort::default_sorter>;
    sorter{}(left, right, f);
}

当以这种方式调用时，排序器将跨越 [left, right) 并创建 std::distance(left, right) 对，将迭代器 it 关联到 f(*it)。然后它将使用传递的排序器（上面示例中的default_sorter，它是在引擎盖下使用的pattern-defeating quicksort at the time of writing) to sort the collection of pairs. Proxy iterators，以便在交换对时交换原始集合的元素。

我不会说这很简单，但它应该可以解决您的问题。如果你不想依赖外部库，你仍然可以从 the soure code 中获取灵感。它是在一个宽松的许可下，所以如果你需要使用它的元素，你几乎可以用它做任何你想做的事情。

总之，看起来基本满足你的要求了：

它不会分配 T 的额外实例（除非 f return 是 T 的新实例，因为它存储 return 的值f).
它在实际排序之前 f 恰好应用 std::distance(left, right)。
如果与 O(n log n) 排序器一起使用，它会保持 O(n log n) 的整体复杂度。
最新的项目符号是唯一不满意的项目符号：它不使用 std::sort 因为 std::sort 目前还不够智能，但它可以使用等效算法而无需您自己写。

std::sort 通过一元映射

std::sort by unary mapping

c++

sorting

std

c++11