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

Question

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

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

它是C标准库中的排序函数.我无法弄清楚第三个论点的含义.我已经读过它被称为二元谓词.这意味着什么？我如何制作自己的谓词？

Answer 1

第三个参数称为谓词.您可以将谓词视为一个函数,它接受许多参数并返回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<int>意思呢？

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

所以,如果greater<T>是a struct,它怎么也可以是谓词？我们不是说谓词是函数吗？

好吧,它greater<T>是一个函数,它是可调用的:它定义了运算符bool operator()(const T& x, const T& y) const;,这使得写法合法:

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

struct可调用的类类型(或s,在C++中几乎相同)的对象称为函数对象或仿函数.

Answer 2

有一个类模板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