qsort函数的比较让我困惑

Question

qsort函数的比较让我困惑

8

我看到很多人在qsort比较函数中使用减法。我认为这是错误的，因为当处理这些数字时：int nums[]={-2147483648,1,2,3}; INT_MIN = -2147483648;

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

我写了这个函数来进行测试：

#include <stdio.h>
#include <limits.h>

int compare (const void * a, const void * b)
{
    return ( *(int*)a - *(int*)b );
}

int main(void)
{
    int a = 1;
    int b = INT_MIN;
    printf("%d %d\n", a,b);
    printf("%d\n",compare((void *)&a,(void *)&b));
    return 0;
}

输出结果为：

1 -2147483648
-2147483647

但是a > b，因此输出应为正数。我看过很多书籍都是这样写的，但我认为这是错误的；在处理int类型时应该这样写：

int compare (const void * a, const void * b)
{
    if(*(int *)a < *(int *)b)
        return -1;
    else if(*(int *)a > *(int *)b)
        return 1;
    else 
        return 0;
}

我就是想不通为什么很多书籍和网站都用这种具有误导性的方式写作。如果您有不同的看法，请告诉我。

- 52coder

qsort() 与什么有关？信号整数溢出是未定义行为，你期望什么？还有一个 INT_MAX 和 1 + INT_MIN 溢出。 - Stargateur

我想知道我是否错了，我认为仅使用“-”进行比较是错误的，你认为应该是1 + INT_MAX溢出吗？ - 52coder

基本数学，1 - (-INT_MIN) == 1 + INT_MIN - Stargateur

你是正确的，使用减法进行比较是错误的，因为会产生溢出问题，可以将其转换为更大的类型（long），或者使用标准的if/else语句。 - Iłya Bursov

@52coder 你好，这段代码需要更多的上下文信息才能进行翻译。请提供更多的细节和背景信息。谢谢！ - Stargateur

显示剩余4条评论

5个回答

3

您的理解是完全正确的。这个常见的习语不能用于 int 值。

您提出的解决方案是正确的，尽管使用本地变量避免过多强制转换会更易读：

int compare(const void *a, const void *b) {
    const int *aa = a;
    const int *bb = b;
    if (*aa < *bb)
        return -1;
    else if (*aa > *bb)
        return 1;
    else 
        return 0;
}

请注意，现代编译器将生成相同的代码，无论是否使用这些局部变量：始终优先选择更易读的形式。

一种更紧凑的解决方案具有完全相同的结果，尽管有点难以理解。

int compare(const void *a, const void *b) {
    const int *aa = a;
    const int *bb = b;
    return (*aa > *bb) - (*aa < *bb);
}

请注意，这种方法适用于所有数字类型，但对于NaN浮点值将返回0。

至于您的评论：“我只是无法理解为什么许多书籍和网站以如此误导的方式编写”：

许多书籍和网站都存在错误，大多数程序也是如此。如果程序经过明智的测试，在它们到达生产环境之前就会捕获并解决许多编程错误。书中的代码片段没有经过测试，虽然它们永远不会到达生产环境，但它们包含的错误会通过毫无戒心的读者以虚假的方法和习语的形式传播。一个非常糟糕且持久的副作用。
感谢您发现了这个问题！在程序员中，您拥有一项罕见的技能：您是一位优秀的读者。写代码的程序员比正确阅读代码和发现错误的程序员要多得多。通过阅读其他人的代码，例如在stackoverflow或开源项目中，来磨练这项技能...并报告错误。
减法方法是常用的，我像你一样在很多地方看到过它，并且对大多数值对都有效。这个bug可能会被忽略数百年。类似的问题在zlib中潜伏了几十年：int m = (a + b) / 2; 对于大的int值的a和b会导致致命的整数溢出。
作者可能看到它被使用并认为减法是酷且快速的，值得在印刷品中展示。
请注意，对于小于int的类型，错误的函数确实可以正确工作：signed或unsigned char和short，如果这些类型在目标平台上确实比int小，C标准没有规定。
事实上，在Brian Kernighan和Dennis Ritchie的《The C Programming Language》中，也可以找到类似的代码，这是由其发明者编写的著名的K&R C圣经。他们在第5章中使用这种方法来实现strcmp()的简单实现。该书中的代码已经过时，可以追溯到70年代末。尽管它具有实现定义的行为，但除了最罕见的架构之外，它不会引起未定义的行为，其中包括臭名昭著的DeathStation-9000，但不应用于比较int值。

- chqrlie

1

很多书出现错误的原因可能是万恶之源：K&R书。在第5.5章中，他们试图教授如何实现strcmp函数。

int strcmp(char *s, char *t)
{
  int i;
  for (i = 0; s[i] == t[i]; i++)
    if (s[i] == '\0')
      return 0;
  return s[i] - t[i];
}

这段代码存在问题，因为char的符号是实现定义的。忽略这一点，并且忽略了他们没有像标准C版本中那样使用const正确性，除此之外，该代码基本可以工作，部分原因是它依赖于隐式类型提升为int（这很丑陋），部分原因是它假设7位ASCII，最坏情况下0 - 127不会下溢。

在书的第5.11节中，他们试图教授如何使用qsort：

qsort((void**) lineptr, 0, nlines-1,
  (int (*)(void*,void*))(numeric ? numcmp : strcmp));

忽略代码调用未定义行为的事实，因为strcmp不兼容函数指针int (*)(void*, void*)，他们教授使用上述来自strcmp的方法。但是，看着他们的numcmp函数，它长这样：

/* numcmp: compare s1 and s2 numerically */
int numcmp(char *s1, char *s2)
{
  double v1, v2;
  v1 = atof(s1);
  v2 = atof(s2);
  if (v1 < v2)
    return -1;
  else if (v1 > v2)
    return 1;
  else
    return 0;
}

忽略掉这段代码如果atof发现无效字符就会崩溃（例如很可能的区域设置问题，.和,的区别），他们实际上教了正确编写此类比较函数的方法。由于该函数使用浮点数，因此没有其他编写方式。

现在有人可能想出一个基于strcmp而不是浮点数实现的int版本，但他们会遇到错误。

总的来说，仅仅翻阅一本曾经的经典书籍中的几页，我们已经发现了3-4个依赖未定义行为和1个依赖实现定义行为的情况。因此，如果从这本书中学习C语言的人编写充满未定义行为的代码，那也就不足为奇了。

- Lundin

请注意，此 strcmp() 实现不会出现未定义行为（除非 sizeof(int) == 1 并且 char 是有符号的，这是一种病态和罕见的情况）。如果 char 默认为无符号，则它是正确的，如果 char 默认为有符号，则可以通过将最后一个语句更改为 return (unsigned char)s[i] - (unsigned char)t[i]; 来修复它。 - chqrlie

@chqrlie 实际上，整数提升使得返回语句的类型为 int，无论其类型如何。所以这不是未定义行为，只是糟糕的编写代码，依赖于隐式提升。 - Lundin

是的，返回类型没问题。即使有(unsigned char)强制转换，每个值也会被提升为int，差异将被计算为int并作为此类返回。这些强制转换是为了符合C标准中指定的使用基于它们的unsigned char值比较字符的strcmp实现所必需的。 - chqrlie

@chqrlie 标准在哪里说strcmp函数中的字符是基于无符号字符值进行比较的？而且强制转换并不能实现这一点，因为它会导致整数提升为（有符号）int类型。 - Lundin

7.24.4 比较函数比较函数 memcmp、strcmp 和 strncmp 返回的非零值的符号由被比较对象中第一对不同字符（均解释为 unsigned char）的差异决定。此外，强制转换正好做到了所需的效果。char 值被转换为 unsigned char，然后提升为 int。 - chqrlie

@chqrlie 好的，我不知道有这个限制。那么，K＆R版本确实不符合标准。你引用的标准文本可能与K＆R一样有责任，但当然标准最初可能是从K＆R得到的想法。 - Lundin

1

你是正确的，*(int*)a - *(int*)b存在整数溢出的风险，因此应该避免使用这种方法来比较两个int值。

在已知减法不会导致溢出的受控情况下，它可能是有效的代码。但一般情况下，应该避免使用它。

- Eric Postpischil

0

首先，在比较过程中，整数可能会给您带来严重的问题，这当然是正确的。

另一方面，进行单个减法比经过if/then/else更便宜，并且在快速排序中执行比较O(n^2)次，因此如果这种排序对性能至关重要，并且我们可以使用差异，那么我们可能需要使用差异。

只要所有值都在小于2^31的某个大小范围内，它就可以正常工作，因为它们的差异必须更小。因此，如果生成要排序的列表的任何内容将保留在十亿和负十亿之间的值，则可以使用减法。

请注意，在排序之前检查这些值是否在这样的范围内是一个O(n)操作。

另一方面，如果存在溢出的可能性，则应使用类似于您在问题中编写的代码

请注意，很多您看到的东西并没有明确考虑溢出；只是可能在更明显的“算术”上下文中更加预期。

- Daniel McLaury

O(n^2) 是最坏情况且很少见的。平均情况是 O(n log n)。 - Eric Postpischil

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chux - Reinstate Monica · Accepted Answer

我认为这是错误的

是的，简单的减法可能会导致 int 溢出，这是一种未定义的行为，应该避免。

return *(int*)a - *(int*)b;  // Potential undefined behavior.

一种常见的习惯用法是减去两个整数比较。各种编译器都能识别这种用法并创建高效、良好行为的代码。保留const性质也是一个好的做法。

const int *ca = a;
const int *cb = b;
return (*ca > *cb) - (*ca < *cb);

为什么很多书籍和网站都以这样误导性的方式编写。

return *a - *b; 在概念上很容易理解——即使在极端值下提供错误答案——通常学习者的代码会省略边缘条件以便传达思想——“知道”值永远不会很大。

或者考虑比较 long doubles 关于 NaN 的复杂性。