c++ - std::sort by unary 映射

Question

C++ 标准库提供了将比较器传递给 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 transform 的 C++ 实现.我没有几行代码的简单解决方案，但我确实实现了 Schwartzian transform utility在我的 C++14 库中。不幸的是，它依赖于代理迭代器，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)对集合进行排序。 Proxy iterators在引擎盖下使用，以便在交换对时交换原始集合的元素。

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

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

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