排序谓词的链接（例如 std::sort）

Question

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

然而，有时（我已经多次遇到过这个问题），您希望能够链接“原始”比较。

一个简单的例子是，如果您要对表示联系人数据的对象集合进行排序。 有时你会想要排序

last name, first name, area code

. Other times

first name, last name

- yet other times

age, first name, area code

... etc

现在，您当然可以为每种情况编写一个附加的函数对象，但这违反了 DRY 原则 - 特别是如果每​​个比较都不那么简单的话。

看起来你应该能够编写比较函数的层次结构 - 低级别的函数执行单一的、原始的比较（例如名字<名字），然后较高级别的函数连续调用较低级别的函数（可能是链接）使用 && 来利用短路评估）来生成复合函数。

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

总而言之，这些都不是无法克服的问题。 这似乎比应有的更难——并且肯定需要一个辅助库的实现。

因此，有谁知道任何现有的库（特别是如果它是 std 或 boost 库）可以在这里提供帮助 - 或者对此事有任何其他想法吗？

[更新]

正如一些评论中提到的 - 我已经编写了自己的类实现来管理这个问题。 它相当小，并且通常可能存在一些问题。 但在此基础上，对于任何感兴趣的人，该课程在这里：

http://pastebin.com/f52a85e4f

还有一些辅助函数（以避免需要指定模板参数）位于：

http://pastebin.com/fa03d66e

Answer 1

您可以像这样构建一个小型链接系统：

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()));

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

Answer 2

处理此问题的一种传统方法是分多次排序并使用稳定排序。 请注意，std::sort 通常不稳定。 但是，有 std::stable_sort。

也就是说，我会编写一个返回三态（表示小于、等于、大于）的函子的包装器。

Answer 3

你可以试试这个：

用法：

struct Citizen {
    std::wstring iFirstName;
    std::wstring iLastName;
};

ChainComparer<Citizen> cmp;
cmp.Chain<std::less>( boost::bind( &Citizen::iLastName, _1 ) );
cmp.Chain<std::less>( boost::bind( &Citizen::iFirstName, _1 ) );

std::vector<Citizen> vec;
std::sort( vec.begin(), vec.end(), cmp );

实现：

template <typename T>
class ChainComparer {
public:

    typedef boost::function<bool(const T&, const T&)> TComparator;
    typedef TComparator EqualComparator;
    typedef TComparator CustomComparator;

    template <template <typename> class TComparer, typename TValueGetter>
    void Chain( const TValueGetter& getter ) {

        iComparers.push_back( std::make_pair( 
            boost::bind( getter, _1 ) == boost::bind( getter, _2 ), 
            boost::bind( TComparer<TValueGetter::result_type>(), boost::bind( getter, _1 ), boost::bind( getter, _2 ) ) 
        ) );
    }

    bool operator()( const T& lhs, const T& rhs ) {
        BOOST_FOREACH( const auto& comparer, iComparers ) {
            if( !comparer.first( lhs, rhs ) ) {
                return comparer.second( lhs, rhs );
            }
        }

        return false;
    }

private:
    std::vector<std::pair<EqualComparator, CustomComparator>> iComparers;
};

Answer 4

std::sort 不能保证稳定，因为稳定排序通常比不稳定排序慢...所以多次使用稳定排序看起来会导致性能问题...

是的sort 要求谓词确实很遗憾：
除了创建一个接受三态函数向量的函子之外，我没有其他方法......

Answer 5

链接解决方案很冗长。 您还可以将 boost::bind 与 std::logic_and 结合使用来构建排序谓词。 有关详细信息，请参阅链接的文章： boost 绑定库如何改进您的 C++ 程序

Answer 6

C++ 11 中的可变参数模板提供了更短的选项：

    #include <iostream>
    using namespace std;

    struct vec { int x,y,z; };

    struct CmpX {
      bool operator() (const vec& lhs, const vec& rhs) const 
      { return lhs.x < rhs.x; }
    };

    struct CmpY {
      bool operator() (const vec& lhs, const vec& rhs) const 
      { return lhs.y < rhs.y; }
    };

    struct CmpZ {
      bool operator() (const vec& lhs, const vec& rhs) const 
      { return lhs.z < rhs.z; }
    };

    template <typename T>
    bool chained(const T &, const T &) {
      return false;
    }

    template <typename CMP, typename T, typename ...P>
    bool chained(const T &t1, const T &t2, const CMP &c, P...p) {
      if (c(t1,t2)) { return true;          }
      if (c(t2,t1)) { return false;         }
      else          { return chained(t1, t2, p...); }
    }

    int main(int argc, char **argv) {
      vec x = { 1,2,3 }, y = { 2,2,3 }, z = { 1,3,3 };
      cout << chained(x,x,CmpX(),CmpY(),CmpZ()) << endl;
      return 0;
    }