std ::按一元映射排序

Question

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

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

这不是最佳选择.f评估速度很慢,但每次使用同一个T对象的调用都会返回相同的值.所以我宁愿做的是f为范围内的每个对象计算一次,然后使用这些结果对它们进行排序.

我的目标是编写这个函数(我无法做到):

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

这样,这个电话之后,f(*iter) <= f(*std::next(iter))所有iter序列中left来right.

此外,该功能应满足这些要求:

• 不分配任何其他类型的对象T.
• 评估f正是std::distance(left, right)很多次.
• 保持O(n log n)的整体复杂性.
• 应该用std :: sort来实现.当然,我可以通过实现自己的合并排序来解决这个问题,但这是我想避免的.

(C++ 11是首选; C++ 14也可以)

Answer 1

因此，您需要的是Schwartzian 变换的 C++ 实现。我没有几行代码的简单解决方案，但我确实在我的 C++14 库中实现了Schwartzian 变换实用程序。不幸的是，它依赖于代理迭代器，而代理迭代器不被处理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在上面的示例中，在撰写本文时这是一种破坏模式的快速排序）对对的集合进行排序。代理迭代器在底层使用，以便每当交换对时原始集合的元素都会交换。

我不会说这很简单，但它应该可以解决您的问题。如果您不想依赖外部库，您仍然可以从源代码中获取灵感。它具有宽松的许可证，因此如果您需要使用其中的元素，您几乎可以用它做任何您想做的事情。

不管怎样，看起来它基本上满足了你的要求：

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