qsort:将比较函数本身或比较函数体内的参数强制转换?

36

使用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);

我倾向于使用前者,主要是出于审美原因。是否有任何技术上的理由更喜欢其中一种?

3个回答

41

你应该避免后一种情况,因为它是无效的。

要使两个函数类型兼容,返回类型必须兼容,并且相应的参数类型也必须兼容。由于 const void * 不兼容于 const double *,因此这两个函数类型不兼容。通过不兼容的指针类型调用函数会导致未定义行为

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

这意味着将 const double * 传递给函数的方式可能与将 const void * 传递给函数的方式不同。因此,通过将类型为 int (*)(const double*, const double*) 的函数调用视为类型为 int (*)(const void*, const void*) 的函数调用,参数可能会以错误的方式传递。

x64和ARM系统通常会对所有指针类型使用相同的表示方式,尽管您也许可以使用前者的方式,但仍然不能保证其有效性。现代编译器通常假定未定义行为不会发生,并基于此事实执行优化。

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


7
@jjg:代码出现的次数并不意味着它符合任何标准或规范。 - Eric Postpischil
11
这是一个非常好的问题和优秀的答案。值得深入理解,因为虽然比较器方法起初看起来很合理,但是如果你考虑编译器将要生成的代码(或者已经生成的代码)在qsort中调用比较器函数,你会发现它调用了一个具有两个void *指针的函数,所以这就是您的比较器函数必须是的内容。(如果所有数据指针类型都是“相同的”--当然,在当今流行的机器上它们都是相同的--错误的代码将会工作,但它仍然是错误的。) - Steve Summit
7
我认为不是这样,因为将指针转换为void *不在默认参数提升之列。这就是为什么传递给printf的指向符合%p格式说明符的指针必须明确转换为void *的原因。 - dbush
4
尽管我从未使用过这种方法,但我认为在基于字的机器上(如PR1ME),它可能会失败,因为该机器有16位字指针,但(相当于)18位的“char”和“void”指针。[C FAQ list](http://c-faq.com/null/machexamp.html)中有一些相关信息。 - Steve Summit
2
@NateEldredge 如果在早期的Cray上比较char字符,肯定会失败,因为Cray指针寻址64位字,并包含额外的内部字段来处理将char数据打包到一个字中的情况。 - alephzero
显示剩余4条评论

12
作为补充,还有另一种调用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指针可以转换为任何不完整或对象类型的指针......并再次转换回去。


2
注意:这种技术的编程术语是“thunk”,意思是一个中间函数,它进行一些微调,使不兼容的源和目标可以结合在一起。 - M.M
1
@M.M 我认为这应该被称为“包装器”,而不是thunk。Thunk是使用函数或闭包来“暂停”表达式的评估,像数据一样传递代码以在急切语言中添加惰性的技术,在严格的函数式语言中是一种常见的技术。Thunk通常不带参数,并返回指定类型的值。 - Mario Carneiro

8
除了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);
    }
}

3
我喜欢这个处理NAN UV的double比较方式 - 就像这个好答案一样。首先把那些 NANs 搞定。 - chux - Reinstate Monica
2
这与问题所问的内容无关,应该作为评论或单独提出一个问题。 - pipe
@管道: 这个答案对于与问题相关的思考真的是很有启发性。虽然 OP 没有发布他的比较函数的代码,但是普通读者应该学会如何正确编写这些比较函数,超越了原型问题。 - chqrlie
3
可能更多的是评论,但a) 由于长度和包含代码,它不适合作为评论,b) 它非常明显地为本帖的读者提供了价值,因此有助于建立已接受答案的基础。我认为没有理由将其删除为“不是答案”。如果在审查答案时需要慎重考虑,那么这肯定是一个这样的案例;删除它会对未来的读者造成不利影响。 - Jeremy Caney
@MSalters:也许吧。虽然我已经标记或审核了超过7500个答案,但我只遇到了两三个“评论性答案”,它们添加了足够的价值,以至于我不感到舒服投票删除。绝大多数都非常明显。 - Jeremy Caney
显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接