5

我想知道为什么有两种完全不同的方法来指定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; 
}

为什么我们需要三个值 -1,0,+1 当返回一个 bool （或具有两个值 0 、 1 的 int ）更简单和干净？

4

5 回答 5

6

其他人指出了两种比较方式的等价性；这就是为什么要遵循这两种方法的原因。

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

在 C++ 中，可以在模板实例化时内联比较，从而消除了很多开销（甚至不需要函数调用）并且可以使用更简单的约定。这也意味着默认情况下std::sort可以使用operator<重载。

于 2013-08-01T20:43:32.497 回答
2

对此有一个有趣的讨论： https ://groups.google.com/forum/#!topic/comp.lang.c++.moderated/bgGrHG_Y_Pw

于 2014-06-10T10:24:48.177 回答
2

qsort 比较函数是在 strcmp 和 memcmp 之后建模的，它们返回 < 0、0 或 > 0 ...这比仅返回 < 或 >= 指示符提供更多信息 ...它需要两次这样的调用来确定两个元素是否是平等的。“不变量”的概念在这里并不适用：显然 a[i] < a[i+1] 的不变量不适用于原始数组......实际上它不适用于最终数组，因为 a [i] == a[i+1] 是可能的。术语“一致”也不适用......对于两种类型的比较函数，结果是并且必须是一致的。“更干净”在旁观者眼中，“更简单”是夸大其词。

于 2013-08-01T19:57:04.253 回答
2

如果对于任意两个 x 和 y，x < y 或 x == y 或 x > y 成立，那么给出比较函数的两种方式是等价的。可以根据 < 定义 == 和 > 运算符，如下所示：

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

正如您可能意识到的那样，在三路比较操作方面实现 <、<=、==、>= 和 > 通常更有效（并且更简单），然后在 < 方面实现 ==，如上所示。我认为这应该是 C（实际上还有许多其他语言）选择三向比较函数的原因，即使快速排序可能不会利用这些额外信息。

C++ 有运算符重载，但没有三向比较运算符（C 也没有），因此从三向比较转向“less”运算符（尽管存在上述潜在缺点）允许利用运算符重载。

于 2013-08-01T19:19:13.643 回答
2

我想知道同样的事情，并提出了一个基于strcmpand的理论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 的迭代进行两次，一次 forA<B和一次 for 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 的结果是相似的。

于 2013-08-01T19:11:54.363 回答