qsortfunction比较困惑我
我看到很多人在qsort比较器函数中使用减法。 我认为这是错误的，因为在处理这些数字时： int nums[]={-2147483648,1,2,3}; INT_MIN = -2147483648; int nums[]={-2147483648,1,2,3}; INT_MIN = -2147483648;
int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); }
我写了这个函数来测试：
#include #include 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 return 0; }
我无法弄清楚为什么许多书籍和网站以如此误导的方式写作。 如果您有任何不同的观点，请告诉我。
我认为这是错误的
是的，一个简单的减法可能导致int溢出，这是未定义的行为 ，应该避免。
return *(int*)a - *(int*)b; // Potential undefined behavior.
常见的习惯用法是减去两个整数比较。 各种编译器都认识到这一点并创建了高效良好的代码。 保持const也是很好的forms。
const int *ca = a; const int *cb = b; return (*ca > *cb) - (*ca < *cb);
为什么许多书籍和网站都以这种误导性的方式写作。
return *a - *b; 在概念上很容易消化 - 即使它提供了极端值的错误答案 - 通常学习者的代码省略边缘条件来理解 - “知道”价值永远不会很大 。
或者考虑比较long doubles与NaN的复杂性。
你的理解绝对正确。 这个常用的习惯用法不能用于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; }
请注意，现代编译器将使用或不使用这些局部变量生成相同的代码：始终更喜欢更易读的forms。
虽然有点难以理解，但通常使用具有相同精确结果的更紧凑的解决方案：
int compare(const void *a, const void *b) { const int *aa = a; const int *bb = b; return (*aa > *bb) - (*aa < *bb); }
请注意，此方法适用于所有数字类型，但对于NaN浮点值将返回0 。
至于你的评论： 我无法弄清楚为什么许多书籍和网站以如此误导的方式写作 ：
-
许多书籍和网站都存在错误，大多数程序也是如此。 如果对程序进行明智的测试，许多编程错误会在它们到达生产之前被捕获并被压扁。 书中的代码片段没有经过测试，虽然它们从未达到过生产 ，但它们所包含的错误确实通过学习伪造方法和习语的毫无戒心的读者进行了病毒传播。 非常糟糕和持久的副作用。
-
感谢你抓住这个！ 你在程序员中有一种罕见的技能：你是一个好读者。 编写代码的程序员远远多于能够正确读取代码并看到错误的程序员。 通过阅读其他人的代码，堆栈溢出或开源项目来实现此技能......并报告错误。
-
减法方法是常用的，我已经在很多像你这样的地方看到它，它确实适用于大多数价值对。 这个bug可能会被忽视。 类似的问题在zlib中潜伏了几十年：
int m = (a + b) / 2;导致a和b大int值的命运整数溢出。 -
作者可能看到它使用并认为减法很酷而且很快，值得在印刷中显示。
-
但请注意，对于小于
int类型，错误的函数可以正常工作：signed或unsignedchar和short，如果这些类型确实小于目标平台上的int，而C Standard并不强制要求。 -
事实上，类似的代码可以在Brian Cnighan和Dennis Ritchie 的C编程语言中找到，它是着名的K＆R C圣经的发明者。 他们在第5章的
strcmp()的简单实现中使用了这种方法。本书中的代码已经过时，一直追溯到七十年代末期。 虽然它具有实现定义的行为，但它不会在除了臭名昭着的DeathStation-9000之外的任何最稀有的架构中调用未定义的行为，但它不应该用于比较int值。
你是对的， *(int*)a - *(int*)b存在整数溢出的风险，应该避免作为比较两个int值的方法。
它可能是受控情况下的有效代码，其中人们知道这些值使得减法不会溢出。 但总的来说，应该避免。
这么多书错的原因很可能是万恶之源：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找到无效字符（例如，非常可能的语言环境问题与. , ），此代码将崩溃和刻录的事实，他们实际上设法教导编写这样的比较函数的正确方法。 由于此函数使用浮点数，因此实际上没有其他方法可以编写它。
现在有人可能想要提出这个版本的int版本。 如果他们基于strcmp实现而不是浮点实现来做，他们就会遇到错误。
总的来说，仅仅通过翻阅这本曾经规范的书中的几页，我们已经发现了大约3-4个依赖于未定义行为的案例和1个依赖于实现定义行为的案例。 因此，难怪从本书中学习C的人是否编写了充满未定义行为的代码。
首先，在比较期间，整数当然是正确的，可能会给您带来严重的问题。
另一方面，进行单次减法比通过if / then / else更便宜，并且比较在快速排序中执行O（n ^ 2）次，所以如果这种性能至关重要且我们可以逃脱有了它我们可能想要使用差异。
只要所有值都在小于2 ^ 31的某个范围内，它就能正常工作，因为它们的差异必须更小。 因此，如果生成要排序的列表的任何内容将保持在十亿到十亿之间的值，那么您可以使用减法。
请注意，在排序之前检查值是否在此范围内是O（n）操作。
另一方面，如果溢出可能发生，你可能想要使用你在问题中写的代码
请注意，您看到的大量内容并未明确考虑溢出; 只是可能在更明显是“算术”背景的东西中更可取。