C++ STL .. 自定义比较器如何工作？

Question

我不明白自定义比较器在 C++ 中是如何工作的..幕后到底发生了什么？

假设我们的比较器 comp(x,y) 有两个参数 x 和 y 我们将此比较器函数用于让我们说 vector<int> v (size) 之类的向量 std::sort() 或 priority_queue。在运行时间传递给 comp() 的数组元素是按什么顺序...是不是像-->

comp(v[0],v[1]) 
comp(v[1],v[2])

任何一种自定义比较的规则是什么？我听说过弱排序的概念，谁能解释清楚一点？

Answer 1

来自here：

comp

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.

The function shall not modify any of its arguments.

This can either be a function pointer or a function object.

换句话说，如果 x 应该放在结果向量中的 y 之前，comp(x,y) 应该 return 为真。

编辑： 我想我误读了你的问题。矢量元素传递给比较器的顺序取决于所使用的算法，即 implementation-dependent 因为标准没有指定确切的算法。我相信 quicksort 是它的常用算法。

Answer 2

无法保证比较函数如何使用，但除了user9549915的回答中指出的其他属性外，还必须满足strict weak ordering

定义严格弱排序的函数类似于通常的小于 (<) 运算符：

对于所有x，x < x都是假的。
对于所有x和y，如果x < y为真，y < x为假。
对于所有x、y和z，如果x < y和y < z都为真，则x < z必须为真.

为了阅读方便，我用 x < y 代替 comp(x, y)。

Answer 3

保存可用于对矩阵进行排序的标准C库qsort()。顾名思义，该函数使用 QuickSort 算法对指定数组进行排序。下面是qsort()

的例子

void qsort (void * base, size_t num, size_t size, int (* 比较器) (const void *, const void *)); qsort()的要点是比较函数比较。比较函数有两个参数，并包含一个逻辑来确定其在已排序输出中的相对顺序。这个想法是为了提供灵活性，以便 qsort() 可以用于任何类型（包括 user-defined 类型）并且可以用于获得任何所需的顺序（增加或减少或其他任何）。比较函数以两个索引为大小（都绑定const星座*），确定元素顺序为return（常量和倍数）

内部比较(const void * p1, const void * p2); 值return 含义 <0 p1 引用的项目在 p2 引用的元素之前 0 p1中引用的元素等于p2中引用的元素

0 The item referenced by p1 moves after the item referenced by p2

C++ STL .. 自定义比较器如何工作？

C++ STL .. how does custom comparator work?

c++

stl

comparator