排序谓词的链接(例如，对于 std::sort)

Chaining of ordering predicates (e.g. for std::sort)(排序谓词的链接(例如，对于 std::sort))

问题描述

您可以将函数指针、函数对象(或 boost lambda)传递给 std::sort 以定义要排序的容器元素的严格弱排序.

You can pass a function pointer, function object (or boost lambda) to std::sort to define a strict weak ordering of the elements of the container you want sorted.

但是，有时(我已经多次提到这一点)，您希望能够链接原始"比较.

However, sometimes (enough that I've hit this several times), you want to be able to chain "primitive" comparisons.

一个简单的例子是，如果您对代表联系人数据的对象集合进行排序.有时您会希望按

A trivial example would be if you were sorting a collection of objects that represent contact data. Sometimes you will want to sort by

last name, first name, area code

进行排序.其他时候

first name, last name

- 还有其他时候

age, first name, area code

...等

现在，您当然可以为每种情况编写一个额外的函数对象，但这违反了 DRY 原则——尤其是在每次比较不那么琐碎的情况下.

Now, you can certainly write an additional function object for each case, but that violates the DRY principle - especially if each comparison is less trivial.

似乎您应该能够编写比较函数的层次结构 - 低级别的比较函数执行单一的、原始的比较(例如名字 < 名字)，然后较高级别的函数会连续调用较低级别的函数(可能与 && 链接以利用短路评估)来生成复合函数.

It seems like you should be able to write a hierarchy of comparison functions - the low level ones do the single, primitive, comparisons (e.g. first name < first name), then higher level ones call the lower level ones in succession (probably chaining with && to make use of short circuit evaluation) to generate the composite functions.

这种方法的问题在于 std::sort 采用二元谓词 - 谓词只能返回一个布尔值.因此，如果您正在编写它们，则无法判断false"是否表示相等或大于.您可以让较低级别的谓词返回一个具有三种状态的 int - 但是您必须将它们包装在较高级别的谓词中，然后才能单独与 std::sort 一起使用.

The trouble with this approach is that std::sort takes a binary predicate - the predicate can only return a bool. So if you're composing them you can't tell if a "false" indicates equality or greater than. You can make your lower level predicates return an int, with three states - but then you would have to wrap those in higher level predicates before they could be used with std::sort on their own.

总而言之，这些都不是无法克服的问题.这似乎比它应该做的更难 - 而且肯定会邀请帮助库实现.

In all, these are not insurmountable problems. It just seems harder than it should be - and certainly invites a helper library implementation.

因此，是否有人知道任何可以在这里提供帮助的预先存在的库(尤其是 std 或 boost 库) - 对此事有任何其他想法吗?

Therefore, does anyone know of any pre-existing library (esp. if it's a std or boost library) that can help here - of have any other thoughts on the matter?

[更新]

正如一些评论中提到的 - 我已经开始编写自己的类实现来管理它.它相当小，一般来说可能有一些问题.但在此基础上，任何有兴趣的人都可以在这里上课:

As mentioned in some of the comments - I've gone ahead and written my own implementation of a class to manage this. It's fairly minimal, and probably has some issues with it in general. but on that basis, for anyone interested, the class is here:

http://pastebin.com/f52a85e4f

还有一些辅助函数(避免需要指定模板参数)在这里:

And some helper functions (to avoid the need to specify template args) is here:

http://pastebin.com/fa03d66e

推荐答案

你可以像这样构建一个小链系统:

You could build a little chaining system like so:

struct Type {
  string first, last;
  int age;
};

struct CmpFirst {
  bool operator () (const Type& lhs, const Type& rhs) { return lhs.first < rhs.first; }
};

struct CmpLast {
  bool operator () (const Type& lhs, const Type& rhs) { return lhs.last < rhs.last; }
};

struct CmpAge {
  bool operator () (const Type& lhs, const Type& rhs) { return lhs.age < rhs.age; }
};

template <typename First, typename Second>
struct Chain {
  Chain(const First& f_, const Second& s_): f(f_), s(s_) {}

  bool operator () (const Type& lhs, const Type& rhs) {
    if(f(lhs, rhs))
      return true;
    if(f(rhs, lhs))
      return false;

    return s(lhs, rhs);
  }

  template <typename Next>
  Chain <Chain, Next> chain(const Next& next) const {
     return Chain <Chain, Next> (*this, next);
  }

  First f;
  Second s;
};

struct False { bool operator() (const Type& lhs, const Type& rhs) { return false; } };

template <typename Op>
Chain <False, Op> make_chain(const Op& op) { return Chain <False, Op> (False(), op); }

然后使用它:

vector <Type> v;  // fill this baby up

sort(v.begin(), v.end(), make_chain(CmpLast()).chain(CmpFirst()).chain(CmpAge()));

最后一行有点冗长，但我认为它的意图很清楚.

The last line is a little verbose, but I think it's clear what's intended.

这篇关于排序谓词的链接(例如，对于 std::sort)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！