10

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

但是，有时（我已经打了好几次了），您希望能够链接“原始”比较。

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

姓氏，名字，区号
. 其他时间
名字，姓氏
- 还有其他时候
年龄、名字、区号
... ETC

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

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

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

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

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

[更新]

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

http://pastebin.com/f52a85e4f

还有一些辅助函数（为了避免需要指定模板参数）在这里：

http://pastebin.com/fa03d66e

4

6 回答 6

8

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

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

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

于 2008-11-08T18:45:16.847 回答
2

处理此问题的一种常规方法是多次排序并使用稳定排序。请注意，这std::sort通常是不稳定的。然而，有std::stable_sort.

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

于 2008-11-08T17:27:00.110 回答
2

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

是的，要求一个谓词真的很可惜：我认为除了创建一个接受三态函数向量的函子之外别无他法......

于 2008-11-08T18:21:49.937 回答
2

你可以试试这个：

用法：

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;
};
于 2012-06-23T06:55:41.727 回答
1

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

于 2008-11-09T17:34:44.743 回答
1

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;
    }
于 2013-02-22T00:09:00.927 回答