解释标准库排序函数C++的比较谓词的工作原理?

Question

在阅读了堆栈溢出的一些答案后，我仍然无法理解比较函数何时必须返回 false，何时返回 true。在这个答案中写道，它对小于运算符进行了建模，但我现在仍然认为，如果比较函数是这样的：

bool compare(const myClass& object1, const myClass& object2)
{
if(object1.property < object2.property)
return true;
else
return false;
}

将按升序对myclass对象的向量进行排序。我说的对吗?...我想我仍然很困惑。

Answer 1

如有疑问，请阅读参考资料。

补偿 -

比较函数对象(即满足 Compare 要求的对象(，如果第一个参数小于(即在第二个参数之前排序(，则返回 true。

比较函数的签名应等效于以下内容：

bool cmp(const Type1 &a, const Type2 &b);

签名不需要有 const &，但函数对象不得修改传递给它的对象。 类型类型1 和类型2 必须使得 RandomIt 类型的对象可以取消引用，然后隐式转换为这两个对象。

Answer 2

虽然参考标准很好，但理解它有时可能非常困难......

用更简单的话来说，尝试：

如果要对元素进行排序，则需要某种顺序关系来定义两个元素中的哪一个应该先出现("是较小的一个"(。某些数据类型带有自然顺序，例如整数，例如：-12 <-10 - 0 - 10 <12。std::sort(不带比较参数(使用此自然顺序对元素进行升序排序。

第三个参数使您可以明确地告诉std::sort如何定义此顺序，想象一下以下内容：

std::vector v({12, 7, 10});
std::sort(v.begin(), v.end(), [](int x, int y){return x > y;});

看起来不自然，不是吗？std::sort将比较解释为"更少"，但我们实现了"更大"！通过这样做，较大的值(被认为是"较小的"(在较小的值(被认为是"更大的"(之前排序，因此我们实现了降序排序......

因此，传递给std::sort的比较参数用于以不同于自然顺序的方式进行排序，或者为不存在此类顺序的数据类型显式定义顺序。

旁注：顺序关系不一定是总顺序;但是，等效元素可以按任意顺序排序(不过，您可以使用std::stable_sort来代替，至少在排序之前保留它们的相对顺序(：

int a[12, 7, 10, 7];
std::vector<int*> v({&a[0], &a[1], &a[2], &a[3]});
std::sort(v.begin(), v.end(), [](int* x, int* y) { return *x < *y; });
// v[2] == &a[2]
// v[3] == &a[1]
// BUT:
// v[0] == &a[1] && v[1] == &a[3] || v[0] == &a[3] && v[1] == &a[1]