C++ STL sort() 函数，二元谓词

Question

C++ STL sort() 函数，二元谓词

13

我有一段令我困惑的代码:

   sort(data, data+count, greater<int>() );

这是C标准库中的一个排序函数，我不明白第三个参数的含义。我看到它被称为二元谓词(binary predicate)。这是什么意思？我该如何编写自己的谓词函数呢？

- Anon

4个回答

7

有一个叫做greater的类模板，需要一个类型参数。所以你提供了一个int。它变成了greater<int>，然后你创建了这个类的一个实例，并将其作为第三个参数传递给函数。

在C++中，这样的对象被称为函数对象或简称functor，因为该类重载了()运算符。它是一个可调用的实体。就像这样：

template<typename T>
struct greater
{
   bool operator()(const T &a, const T &b)
   {
      //compare a and b and return either true or false.
      return a > b;
   }
};

如果创建一个greater<int>的实例，例如对象是g，那么可以编写g(100,200)，它将计算出一个布尔值。因为表达式g(100,200)调用了operator()，并传递100作为第一个参数和200作为第二个参数，operator()比较它们并返回true或false之一。

       std::cout << g(100,200) << std::endl;
       std::cout << g(200,100) << std::endl;

输出：

0
1

在线演示： http://ideone.com/1HKfC

- Nawaz

3

一个二元谓词是指任何接收两个对象（因此称为“二元”）并返回一个布尔值的函数/对象（因此称为predicate）；其思想是评估这两个对象是否满足某个特定条件-例如，在本例中，一个对象是否大于另一个对象。

您可以通过定义具有正确签名的函数来创建谓词。

bool IsIntGreater(int First, int Second)
{
    return First>Second;
}

通过传递函数名作为参数（这将导致传递一个函数指针），或者创建一个函数对象（一个“函数对象”），即重载函数调用运算符的对象，因此可以用作函数；std::greater<T> 类型是一个模板函数对象，在您的片段中创建了一个临时对象 std::greater<int> 并传递给 std::sort 算法。

与函数相比，函数对象具有几个优点，特别是当它们必须作为参数传递时，请参阅这里以获取更多信息。

- Matteo Italia

1

在http://www.cplusplus.com/reference/algorithm/sort/中查看comp

它是执行比较的函数。

- Ed Heal

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

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

- Jon · Accepted Answer

第三个参数被称为谓词。你可以将谓词看作是一个函数，它接受若干个参数并返回true或false。

例如，下面是一个判断整数是否为奇数的谓词：

bool isOdd(int n) {
    return n & 1;
}

以上函数接受一个参数，因此可以称其为一元谓词。如果它接受两个参数，你会称其为二元谓词。下面是一个二元谓词，用于判断其第一个参数是否大于第二个参数：

bool isFirstGreater(int x, int y) {
    return x > y;
}

谓词通常由非常通用的函数使用，以允许函数的调用者通过编写自己的代码来指定函数应该如何行事（在这种情况下，谓词是回调函数的一种专门形式）。例如，考虑当sort函数需要对整数列表进行排序时。如果我们希望将所有奇数排在偶数之前进行排序怎么办？我们不想被迫每次都编写新的排序函数以更改排序顺序，因为排序的机制（算法）显然与具体要求（我们希望它按什么顺序排序）无关。

所以让我们为sort添加自己的谓词，使其可以反向排序：

// As per the documentation of sort, this needs to return true
// if x "goes before" y. So it ends up sorting in reverse.
bool isLarger(int x, int y) {
    return x > y;
}

现在这将按相反的顺序排序：

sort(data, data+count, isLarger);

这是如何工作的：sort内部比较整数对以确定哪个应该排在前面。对于这样一对x和y，它通过调用isLarger(x, y)来实现。

所以现在你知道了谓词是什么，何时使用它以及如何创建自己的谓词。但是greater是什么意思呢？ greater是一个二元谓词，告诉我们第一个参数是否大于第二个参数。它也是一个模板结构体，这意味着它有许多不同的形式，基于其参数的类型而变化。需要指定此类型，因此greater是类型int的模板特化（如果您需要，可以阅读更多关于C ++模板的内容）。

既然greater是一个结构体，那它怎么能成为谓词呢？难道我们不是说过谓词是函数吗？

好吧，从某种意义上说，greater是一个函数，因为它是可调用的：它定义了运算符bool operator()(const T& x, const T& y) const;，这使得编写这个合法：

std::greater<int> predicate;
bool isGreater = predicate(1, 2); // isGreater == false

可调用的类类型对象（或者在 C++ 中几乎等同的 struct）被称为函数对象或functor。