按一元映射进行std::sort排序

Question

按一元映射进行std::sort排序

7

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

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) { /* ? */ }

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

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

- 不会分配任何额外的T类型对象。 - 精确评估f std :: distance（left，right）次。 - 保持O(n log n)的总体复杂度。 - 应基于std :: sort实现。当然，我可以通过实现自己的合并排序来解决这个问题，但是我想避免这样做。

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

- Andreas T

1

为什么不将f(a)的结果存储在对象a中，并且只有当对象状态改变时才计算它呢？ - Richard Critten

1

f(*iter) 只依赖于 *iter 还是同时依赖于 iter？ - Kerrek SB

2

你可以为所有的 a 创建一个值范围 f(a)，同时也创建一个索引范围，然后根据预先计算好的 f 值对这些索引进行排序。这样你就得到了将原始范围按照排序顺序排列的排列方式，所以你只需要应用该排列方式即可。 - Kerrek SB

@RichardCritten 这可能是一种可能性，但非常丑陋。f与类没有直接关系，只在某些用例中相关；因此我会在类中有一些成员，在许多代码片段中从未使用。除此之外，每次更改对象时，我都必须手动调用类似于“updateF”的东西。 - Andreas T

@AlanStokes：不一定。记忆化的 f 也有优点；它简化了逻辑并且可能在更广泛的范围内被重复使用。这取决于 T 对于记忆化是否合适。 - Kerrek SB

显示剩余4条评论

2个回答

0

如果您想坚持使用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 = Foo 的唯一实例的数量。 编辑： 如下面评论中所提到的，如果将T实例复制到映射中是问题，请使用唯一标识符（例如对象的地址）作为键，而不是对象本身。

- Krisztián Szabó

1

这会导致序列中的每个对象都被复制，我理解错了吗？ - Andreas T

@AndreasT - 如果问题是在cache映射中复制Foo对象，您可以使用一个指向Foo键的cache映射：static std::unordered_map<Foo*, int> cache;；搜索变为auto leftIt = cache.find(&left); auto rightIt = cache.find(&right);；插入cache.emplace(&left, evaluate(left)).first;和cache.emplace(&right, evaluate(right)).first;。 - max66

是的，它将把 T 对象复制到映射中（如果尚未存在）。如果您不想将对象复制到映射中，只需使用每个实例的唯一标识符作为键即可。 - Krisztián Szabó

2

缓存指针是行不通的，因为排序算法会移动对象，从而改变它们的指针。 - Raymond Chen

1

@RaymondChen：你最近在博客上不是已经讲过这个了吗？哦，对了，系列文章从这里开始：https://blogs.msdn.microsoft.com/oldnewthing/20170102-00/?p=95095 - Adrian McCarthy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Morwenn · Accepted Answer

你需要的是一个C++实现Schwartzian变换。我没有几行代码的简单解决方案，但我在我的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今天还不够聪明，但是它可以使用等效算法，而无需编写自己的算法。