qsort函数比较让我困惑

Question

我看到很多人在 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;
}

我只是不明白为什么许多书籍和网站都以这种误导性的方式书写。如果你有什么不同的看法，请告诉我。

Answer 1

你是对的，*(int*)a - *(int*)b 会带来整数溢出的风险，应该避免将其作为比较两个 int 值的方法。

在受控情况下，它可能是有效代码，在这种情况下，人们知道这些值使得减法不会溢出。不过，一般来说，应该避免这种情况。

Answer 2

首先，比较期间的整数会给您带来严重的问题，这当然是正确的。

另一方面，做一次减法比进行一次减法要便宜 if/then/else，并且比较在快速排序中执行 O(n^2) 次，所以如果这种排序是 performance-critical 我们可以摆脱它，我们可能想使用差异。

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

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

另一方面，如果有可能发生溢出，您需要使用类似于您在问题中编写的代码

请注意，您看到的很多内容并未明确考虑溢出；只是在更明显的 "arithmetic" 上下文中，这可能更令人期待。

Answer 3

I think it is wrong

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

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

一个常见的习惯用法是减去两个整数比较。各种编译器认识到这一点并创建高效的行为良好的代码。也是不错的形式。

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

why many books and web sites write in such a misleading way.

return *a - *b; 在概念上很容易理解 - 即使它提供了带有极值的错误答案 - 通常学习者代码会省略边缘条件来理解这个想法 - "knowing" 值将 never be large.

或者考虑的复杂性。

Answer 4

您的理解完全正确。此常见习语不能用于 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);
}

请注意，此方法适用于所有数字类型，但 return 0 适用于 NaN 浮点值。

至于你的评论：我只是不明白为什么很多书和网站都以这种误导的方式写:

许多书籍和网站都包含错误，大多数程序也是如此。如果对程序进行明智的测试，许多编程错误在投入生产之前就被捕获并消除了。书中的代码片段未经测试，虽然它们从未到达 生产环境 ，但它们包含的错误确实会通过毫无戒心的 reader 学习虚假方法和习语的人传播。一个非常糟糕和持久的副作用。
感谢你抓住了这个！你有程序员中难得一见的技能：你是个好人reader。编写代码的程序员远远多于能够正确阅读代码并看到错误的程序员。通过阅读其他人的代码、堆栈溢出或开源项目来磨练这项技能...并报告错误。
减法很常用，我和你一样在很多地方都见过它，它对大多数值对都有效。这个错误可能会被忽视很长时间。一个类似的问题在 zlib 中潜伏了几十年：int m = (a + b) / 2; 导致 a 和 b.
[=64 的大 int 值的致命整数溢出=]
作者可能看到它被使用并认为减法酷并且速度很快，值得在印刷品中展示。
但是请注意，对于小于 int 的类型，错误函数确实可以正常工作：signed 或 unsigned char 和 short，如果这些类型在目标平台上确实小于 int，C 标准不强制要求。
确实可以在The C Programming Language by Brian Kernighan and Dennis Ritchie, the famous K&R C bible by its inventors. They use this approach in a simplistic implementation of strcmp() in chapter 5. The code in the book is dated, going all the way back to the late seventies. Although it has implementation defined behavior, it does not invoke undefined behavior in any but the rarest architectures among which the infamous DeathStation-9000中找到类似的代码，但不应该用来比较int值。

Answer 5

这么多书错的原因可能是万恶之源：K&R 书。在第 5.5 章中，他们尝试教授如何实现 strcmp:

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

此代码有问题，因为 char 具有 implementation-defined 签名。忽略这一点，并忽略它们未能像标准 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 发现无效字符（例如 . 与 , 之间很可能存在的区域设置问题），则忽略此代码将崩溃并烧毁的事实，他们实际上设法教授编写这种比较函数的正确方法。因为这个函数用的是浮点数，实在没办法写了

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

总的来说，仅仅翻开这本曾经的经典书籍的几页，我们已经发现了大约 3-4 个依赖未定义行为的案例和 1 个依赖 implementation-defined 行为的案例。所以难怪从这本书学C的人写出的代码都是未定义行为。

qsort函数比较让我困惑

qsort function compare confused me

c

qsort