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

C++ STL sort() function, binary predicate

提问by Vis Viva

I have a piece of code that confuses me:

我有一段代码让我感到困惑：

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

it is a sort function in the C standard library. I am having trouble figuring out the meaning of the third argument. I have read that it is called a binary predicate. What does that mean and how can I make my own such predicate?

它是 C 标准库中的一个排序函数。我无法弄清楚第三个参数的含义。我读过它被称为二元谓词。这是什么意思，我怎样才能做出自己的这样的谓词？

回答by Jon

The third argument is called a predicate. You can think of a predicate as a function that takes a number of arguments and returns trueor false.

第三个参数称为谓词。您可以将谓词视为接受多个参数并返回trueor的函数false。

So for example, here is a predicate that tells you whether an integer is odd:

例如，这里有一个判断一个整数是否为奇数的谓词：

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

The function above takes one argument, so you could call it a unarypredicate. If it took two arguments instead, you would call it a binarypredicate. Here is a binary predicate that tells you if its first argument is greater than the second:

上面的函数接受一个参数，因此您可以将其称为一元谓词。如果取而代之的是两个参数，则将其称为二元谓词。这是一个二元谓词，它告诉你它的第一个参数是否大于第二个：

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

Predicates are commonly used by very general-use functions to allow the caller of the function to specify how the function should behave by writing their own code (when used in this manner, a predicate is a specialized form of callback). For example, consider the sortfunction when it has to sort a list of integers. What if we wanted it to sort all odd numbers before all even ones? We don't want to be forced to write a new sort function each time that we want to change the sort order, because the mechanics (the algorithm) of the sort is clearly not related to the specifics (in what order we want it to sort).

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

So let's give sorta predicate of our own to make it sort in reverse:

因此，让我们给出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;
}

Now this would sort in reverse order:

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

sort(data, data+count, isLarger);

The way this works is that sortinternally compares pairs of integers to decide which one should go before the other. For such a pair xand y, it does this by calling isLarger(x, y).

其工作方式是在sort内部比较整数对以决定哪个应该在另一个之前。对于这样的一对xand y，它通过调用isLarger(x, y).

So at this point you know what a predicate is, where you might use it, and how to create your own. But what does greater<int>mean?

因此，此时您知道谓词是什么，可以在哪里使用它，以及如何创建自己的谓词。但是是什么greater<int>意思呢？

greater<T>is a binary predicate that tells if its first argument is greater than the second. It is also a templated struct, which means it has many different forms based on the type of its arguments. This type needs to be specified, so greater<int>is the template specializationfor type int(read more on C++ templates if you feel the need).

greater<T>是一个二元谓词，表明它的第一个参数是否大于第二个参数。它也是一个模板化的struct，这意味着它根据其参数的类型有许多不同的形式。这种类型的需要指定，所以greater<int>是模板特供型int（阅读更多关于C ++模板，如果你觉得有必要）。

So if greater<T>is a struct, how can it also be a predicate? Didn't we say that predicates are functions?

那么如果greater<T>是 a struct，它怎么可能也是一个谓词呢？我们不是说谓词是函数吗？

Well, greater<T>is a function in the sense that it is callable: it defines the operator bool operator()(const T& x, const T& y) const;, which makes writing this legal:

嗯，greater<T>是一个函数，它是可调用的：它定义了 operator bool operator()(const T& x, const T& y) const;，这使得编写这个合法：

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

Objects of class type (or structs, which is pretty much the same in C++) which are callable are called function objectsor functors.

struct可调用的类类型（或s，在 C++ 中几乎相同）的对象称为函数对象或函子。

回答by Nawaz

There is a class template called greaterwhich needs a type argument. So you provide intas one. It became greater<int>and you create an instance of this class and pass it to the function as third argument.

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

Such an object is called function object or simply functorin C++, as the class overloads ()operator. It's a callable entity. Its like this:

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

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;
   }
};

If you create an instance of greater<int>and, say, the object is g, then you can write g(100,200)which evaluates to a boolean value, as the expression g(100,200)calls operator(), passing 100as first argument and 200as second argument, and operator()compares them and return either trueor false.

如果您创建greater<int>and的实例，例如，对象 is g，那么您可以编写g(100,200)which 评估为布尔值，作为表达式g(100,200)调用operator()，100作为第一个参数和200第二个参数传递，并operator()比较它们并返回trueor false。

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

Output:

输出：

0
1

Online demo : http://ideone.com/1HKfC

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

回答by Matteo Italia

A binary predicate is any function/object that receives two objects (hence binary) and returns a bool(hence predicate); the idea is that it evaluates if the two objects satisfy some particular condition - in the example, if one is greater than the other.

二元谓词是接收两个对象（因此是二元对象）并返回一个bool（因此是谓词）的任何函数/对象；这个想法是它评估两个对象是否满足某些特定条件 - 在示例中，如果一个大于另一个。

You can create a predicate either by just defining a function with the correct signature

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

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

and passing the name of the function as the argument (this will result in passing a function pointer), or creating a function object (a functor), i.e. an object which overloads the function call operator and thus can be used as a function; the std::greater<T>type is a template functor, and in your snippet a temporary object of type std::greater<int>is created and passed to the std::sortalgorithm.

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

Functors have several advantages over functions, especially when they have to be passed as arguments, have a look herefor more information about this.

与函数相比，函子有几个优点，特别是当它们必须作为参数传递时，请查看此处以获取有关此的更多信息。

回答by Ed Heal

See compin http://www.cplusplus.com/reference/algorithm/sort/

见comp在http://www.cplusplus.com/reference/algorithm/sort/

It is the function that does the comparison.

它是进行比较的函数。