qsort：转换比较器函数本身还是比较器函数体中的参数？

html5 • • 问答

有几种明显的使用方法qsort：在比较器中强制转换：

int cmp(const void *v1, const void *v2) 
{
    const double *d1 = v1, *d2 = v2;
    ?
}

qsort(p, n, sizeof(double), cmp);

或投射比较器：

int cmp(const double *d1, const double *d2) 
{
    ?
}

qsort(p, n, sizeof(double), (int (*)(const void *, const void *))cmp);

我倾向于使用前者，更多的是出于审美原因。是否有任何技术上的原因偏爱其中一个？

回答

您应该避免后一种情况，因为它无效。

两个函数类型要兼容，返回类型必须兼容，对应的参数类型必须兼容。Aconst void *与 a 不兼容，const double *因此函数类型不兼容。通过不兼容的指针类型调用函数会导致未定义的行为。

请注意，仅仅因为可以隐式转换两种类型并不意味着它们是兼容的。以const double *and为例const void *，两种类型之间的转换可以在没有强制转换的情况下进行，但是两种类型的表示不必相同。

这意味着 aconst double *传递给函数的方式可能与 a 传递给函数的方式不同 const void *。因此，通过调用类型int (*)(const double*, const double*)为type 的函数，就好像它具有 type 一样int (*)(const void*, const void*)，参数可能会以不正确的方式传递。

虽然 x64 和 ARM 系统通常会为所有指针类型使用相同的表示，但您可能会避免使用前者，但仍然无法保证这一点。现代编译器通常会假设未定义的行为不会发生并基于该事实执行优化。

前一种情况是正确的方法，因为函数的签名与qsort函数期望的兼容。

  • This is an excellent question and an excellent answer. And it's worth understanding well, because although the cast-the-comparator method *looks* reasonable at first, if you think about the code the compiler is going to generate (or *has already* generated) down in `qsort`, to actually call the comparator function, you'll see that it's calling a function with two `void *` pointers, so that's what your comparator function *must* be. (If all data pointer types are "the same" -- as of course they are all on all popular machines these days -- the wrong code will work, but it's still wrong.)
  • @jjg: The number of places code is seen is not an indication of its conformance to any standard or specification.
  • @chux-ReinstateMonica I don't think so, as a conversion to `void *` is not among the default argument promotions. This is why pointers passed to `printf` corresponding to the `%p` format specifier must be explicitly casted to `void *`.
  • @NateEldredge Although I've never used one, I believe it would have failed on word-addressed machines such as the PR1ME, which had 16-bit word pointers but (the equivalent of) 18-bit `char` and `void` pointers. There's some information on this in the [C FAQ list](http://c-faq.com/null/machexamp.html).
  • @NateEldredge It would certainly have failed comparing `char`s on the early Crays, because Cray pointers addressed 64-bit words and contained additional internal fields to handle `char` data packed 8 bytes to a word.

回答

作为附录，还有另一种调用策略qsort：创建一个中间qsort所需的原型函数，该函数调用启用类型的比较函数。

#include <stdlib.h>
#include <stdio.h>

static int double_cmp(const double *d1, const double *d2)
    { return (*d1 > *d2) - (*d2 > *d1); }

static int double_void_cmp(const void *v1, const void *v2)
    { return double_cmp(v1, v2); }

int main(void) {
    double p[] = { 2.18, 6.28, 3.14, 1.20, 2.72, 0.58, 4.67, 0.0, 1, 1.68 };
    const size_t n = sizeof p / sizeof *p;
    size_t i;
    qsort(p, n, sizeof *p, &double_void_cmp);
    for(i = 0; i < n; i++) printf("%s%.2f", i ? ", " : "", p[i]);
    fputs(".n", stdout);
    return EXIT_SUCCESS;
}

虽然这有其自身的问题，但可以double_cmp用作其他非qsort事物的比较器。此外，根据我对ISO 9899 6.3.2.3 的解释，它不需要任何强制转换或显式分配，

指向void的指针可以与指向任何不完整或对象类型的指针相互转换。. . 然后再回来。

  • note: the programming jargon for this technique is *thunk*, meaning an intermediate function that makes some wee adjustments so that incompatible source and destination can come together

回答

除了dbush出色的答案之外，还应该注意的是，具有原型的替代比较函数的情况int cmp(const char *s1, const char *s2)，例如strcmp不像问题中的那样明确。C 标准规定：

6.2.5 类型

[...] 指向的指针void应具有与指向字符类型的指针相同的表示和对齐要求。类似地，指向兼容类型的限定或非限定版本的指针应具有相同的表示和对齐要求。所有指向结构类型的指针都应具有相同的表示和对齐要求。所有指向联合类型的指针都应具有相同的表示和对齐要求。指向其他类型的指针不需要具有相同的表示或对齐要求。

因此，函数指针与原型int cmp(const void *v1, const void *v2)和int cmp(const char *v1, const char *v2)是不兼容的，但调用序列是不太可能是不同的，甚至在那些极为罕见的目标，其中int cmp(const double *v1, const double *v2)将有问题的（早期的Cray系统和缺乏字节寻址的CPU）。

您没有提供比较函数的代码：简单地返回值的差异 ( *d1 - *d2)是一个常见的错误。这不适用于浮点值，也不适用于int值，因为减法可能会溢出。

这是适用于所有数字类型的递增顺序实现：

int cmp(const void *v1, const void *v2) {
    const int *p1 = v1, *p2 = v2;
    return (*p1 > *p2) - (*p1 < *p2);
}

对于浮点类型，可能需要对 NaN 值进行特殊处理：

// sort by increasing values, with NaN after numbers
int cmp(const void *v1, const void *v2) {
    const double *p1 = v1, *p2 = v2;
    if (isnan(*p1)) {
        return isnan(*p2) ? 0 : 1;
    } else
    if (isnan(*p2)) {
        return -1;
    } else {
        return (*p1 > *p2) - (*p1 < *p2);
    }
}

  • I like this `double` compare handling of `NAN` UV - like this [good answer](https://stackoverflow.com/a/48069558/2410359). Get those `NAN`s out of the way first.
  • @pipe: It may well be more of commentary, but a) it wouldn’t work well as a comment due to its length and inclusion of code, and b) it very clearly provides value to readers of this thread, and thus helps build off of the accepted answer. I see no reason to e.g. delete it as _not an answer_. If there is a case for discretion in reviewing answers, surely this is one such case; removing it would do a disservice to future readers.
  • This has nothing to do with the problem asked in the question and should be a comment or a separate question.
以上是qsort：转换比较器函数本身还是比较器函数体中的参数？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>