qsort()与std::sort，比较函数的哲学差异

Question

我在想为什么在qsort() { C版本 }和 std::sort() 中指定比较函数的方法完全不同。 qsort需要以下形式的比较函数：我不知道它为什么需要三种返回值-1、0、+1。

int comp(int *x, int *y){   
   return *x - *y; 
}

std::sort()的比较函数看起来更加一致，因为它是根据遵循不变式的函数编写的。即如果x小于y，则函数返回true，x相对于y处于正确的位置。

bool comp(int x, int y){   
       return x < y; 
}

为什么在返回布尔值（或只有0、1两个值的整数）时，我们需要使用三个值-1、0、+1，而不是更简单和清晰的方式？

- David

---

如果你在使用C++进行编程，那么请使用std::sort；如果你在使用C进行编程，则请使用qsort。此外，有些C++容器不能使用qsort进行排序，因此你别无选择。 - Some programmer dude

我的问题更关注于qsort()排序函数中比较函数的原理。为什么我们需要返回-1、0、+1这三个值，而返回 bool（或只有0和1两个值的 int）会更简单和清晰。请翻译此内容。 - David

@David 因为这样你就可以在一次调用 comp 后区分 x > y vs x == y vs x < y（在第一种情况下）。 - Drew McGowen

@Drew McGowen，快速排序不是稳定排序。你不需要区分所有三种情况 x > y vs x == y vs x < y。因此，x > y 和 x <= y 应该足够了。 - David

顺便提一下，*x - *y 是错误的，例如如果 *x == INT_MAX 且 *y == INT_MIN。 - Cubbi

Answer 1

其他人指出了两种比较方式的等效性，以下是为什么采用这两种方法的原因。

在C语言中，比较需要一个函数指针。这意味着您始终会得到函数调用和指针间接的开销。当qsort在1970年代设计时，它运行在一台PDP-11计算机上，必须减少开销，所以比较函数（如strcmp）需要在单个函数调用中进行三向比较。（请注意，qsort通常是不稳定的排序，因此相等情况可能看起来无用，但可以通过适当的指针比较使其稳定。）

在C ++中，比较可以在模板实例化时进行内联，因此大部分开销消失了（甚至不需要函数调用），可以使用更简单的约定。这也意味着std::sort默认可以使用operator<重载工作。

- Fred Foo

Answer 2

我曾经也思考过同样的问题，并且提出了一个基于strcmp和std::string::compare的理论。也就是说，做比较可能需要相对较长的时间。为了确定一个对象A是否小于、等于或大于另一个对象B，可以使用如下代码：

if (A < B) {
    //do stuff where A is less
} else if (B < A) {
    //do stuff where A is greater
} else {
    //do stuff where A is equal
}

通常需要迭代A和B两次，一次为"A<B"，一次为"B<A"。如果同时检查三种可能性，则只需迭代字符串一次。因此使用了“-1、0、1”约定。

然而，C++似乎已经放弃了这个约定。我听到的一个论点是，由于计算机的变化，由于执行三方比较的代码复杂性，进行一次三方比较会更慢，更容易出错，并且大多数情况下我们并不关心相等的情况。事实上，所有标准排序算法都是按照这种方式设计的，尽管个别实现可能会做一些更有趣的事情。

if (A < B) {
    //do stuff where A is less
} else {
    //do stuff where A is greater or equal
}

根据MSVC在这个测试中的时间记录，string::operator<比strcmp快近一倍，调用string::operator<两次仅比调用一次稍慢。(我猜测是因为缓存和更简单的代码？) GCC的结果也类似。

- Mooing Duck

---

测试在GCC下失败，因为G++不会调用strcmp 200000次，它只是在一个循环后计算结果。如果loop_counter%1000==0 && time(NULL) == 42，可以添加循环内容以修改一个字符串来杀死可怜的优化器... :) - NoSenseEtAl

@NoSenseEtAl 或者使用 volatile。 - Jim Balter

@JimBalter 我认为那会在每个周期中都有影响，我的方法只是做了模运算和比较......除了每1000次迭代之外......但说实话我不知道 volatile 究竟如何破坏优化。 - NoSenseEtAl

@NoSenseEtAl 整个重点在于每个周期都要“受到打击”——调用strcmp。如果strcmp的参数之一是易失性的，那么可以保证。 - Jim Balter

我是说hit正在从内存中重新加载而不是保留在寄存器中...因为它是易失性的，但像我说的那样，我可能是错的。 :) - NoSenseEtAl

@JimBalter：感谢您的“volatile”提示，这使得程序正常运行。 - Mooing Duck

Answer 3

有一个有趣的讨论关于这个问题： https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/bgGrHG_Y_Pw

- Vic99999

Answer 4

如果对于任意的x和y，要么x < y，要么x == y，要么x > y成立，则给出比较函数的两种方式是等价的。可以按照以下方式用<定义==和>运算符：

- x == y等价于!(x < y) && !(y < x) - x > y等价于y < x

正如您可能意识到的那样，通常更高效（也更简单）地使用“三路比较”操作来实现<、<=、==、>=和>，然后像上面所示的那样用<实现==。我认为这应该是C（以及许多其他语言）选择三路比较函数的原因，尽管快速排序可能不会利用这些额外的信息。

C++具有运算符重载功能，但没有三路比较运算符（C也是如此），因此从三路比较转移到“小于”运算符（尽管存在上述潜在缺点）允许利用运算符重载。

- user2545918

---

请注意，!(x < y) && !(y < x)并不总是等同于x == y，尽管对于所有常见情况都是如此。这完全取决于您如何定义 < 和 == 运算符。 - Mark Ransom

@MarkRansom 在 C 中它们是等价的。当然，在 C++ 中可以使它们不一致，但这是如此糟糕的设计，以至于不值得一提。 - Jim Balter

你说得对，cmp 更有效率，特别是对于 std::map/std::set 这样的东西，因为它们会多次应用 std::less/operator<，而只需一次调用 cmp 就足够了。 - Maxim Egorushkin

Answer 5

qsort比较函数的模型是基于strcmp和memcmp的，它们返回<0、0或>0，这比仅返回<或>=指示符更具信息性……需要进行两次这样的调用才能确定两个元素是否相等。这里不适用“不变量”的概念：显然，a [i]<a [i + 1]的不变量不适用于原始数组……实际上，对于最终数组，它也不适用，因为a [i] == a [i + 1]是可能的。术语“一致”也不适用……结果必须对两种类型的比较函数都一致且必须如此。“更干净”的问题在于观察者，而使用“简单得多”则言过其实。

- Jim Balter

---

我认为qsort()没有以任何形式使用三向比较。这里只需要两向比较就足够了。 - David

@David 是的，这已经足够了...但这与你的问题无关，你问的是为什么qsort使用三路比较，我已经回答了...它是模仿strcmp而来；你知道最初的qsort是在40多年前编写的吗？如果你想要一个只接受less_than函数的qsort版本，你可以自己编写一个。 - Jim Balter