这个C qsort函数调用中的参数是什么？

Question

qsort(bt->rw[t], bt->num[t], 
      sizeof(TRELLIS_ATOM *), 
      (int (*)(const void *,const void *))compare_wid);

bt->rw[t]是一个指向struct指针的指针,bt->[num]是一个int,我不明白第四个参数是什么,除了compare_wid是在某处定义的函数,如下所示:

static int compare_wid( TRELLIS_ATOM* a, TRELLIS_ATOM* b )
{
   ...
   return x;
}

Answer 1

我将稍微了解一下该行的含义,但在我这样做之前,让我们先了解为什么qsort()需要它所需类型的最终参数的一些基础知识. qsort()是一个可以对任何类型的数据进行排序的函数.

你提供:

• 一个基指针,指向一个连续数据块的开头,
• 块中的元素数量,
• 一个数据成员的大小,和
• 一个比较两个数据值的函数.

由于排序算法通常不依赖于被排序的数据的类型,因此qsort()可以在不知道它正在排序的数据类型的情况下编写.但是为了能够做到这一点,qsort()需要void *参数,这意味着C中的"通用指针".

假设您有一组未排序的int值:

#define N 1024
int data[N] = { 10, 2, 3, -1, ... } /* 1024 values */

然后,你可以通过调用对它们进行排序qsort():

qsort(data, N, sizeof data[0], compare_int);

data是int *传递给的类型qsort(),第一个参数qsort()是类型void *.由于任何对象指针都可以void *在C中转换,这是可以的.接下来的两个论点也没问题.最后一个参数compare_int应该是一个带有两个const void *参数并返回一个的函数int.该函数将被调用通过qsort()与双指针从&data[0]到&data[N-1],因为它需要多次.

声明一个f()"接受两个const void *参数并返回int" 的函数:

int f(const void *, const void *);

如果想要声明我们可以设置的函数指针f,则指针声明为:

int (*pf)(const void *, const void *);
pf = f;

括号是必需的,因为否则pf将是返回的函数int *.现在,pf是一个返回函数的指针int.

回到我们的int排序算法,从上面我们可以定义compare_int()为:

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

在写作时compare_int(),我们知道传递的指针是int *伪装成的void *,所以我们将它们转换回来int *,这没关系,然后我们比较这些数字.

现在,我们将注意力转向相关代码:

static int compare_wid( TRELLIS_ATOM* a, TRELLIS_ATOM* b )

表示这compare_wid是一个带两个TRELLIS_ATOM *参数的函数,并返回一个int.正如我们刚才看到的那样,最后一个参数qsort()应该是一个类型为的函数:

int (*)(const void *, const void *)

即,一个函数采用两个const void *参数并返回int.由于类型不匹配,程序员compare_wid()转换为所需的类型qsort().

但是,这有问题.类型的功能:

int (*)(TRELLIS_ATOM *, TRELLIS_ATOM *)

不等同于类型的函数:

int (*)(const void *, const void *)

所以如果演员阵容能够奏效则无法保证.声明compare_wid()为:更容易,更正确,更标准:

static int compare_wid(const void *a, const void *b);

并且compare_wid()应该看起来像:

static int compare_wid(const void *a, const void *b)
{
    const TRELLIS_ATOM *the_a = a;
    const TRELLIS_ATOM *the_b = b;
    ...
    /* Now do what you have to do to compare the_a and the_b */
    return x;
}

如果你这样做,你将不需要在通话中使用演员表qsort(),你的程序不仅更容易阅读,而且更正.

如果你不能改变compare_wid(),那么写另一个功能:

static int compare_stub(const void *a, const void *b)
{
    return compare_wid(a, b);
}

并呼吁qsort()有compare_stub()(无投)代替compare_wid().

编辑:根据许多错误的答案,这是一个测试程序:

$ cat qs.c
#include <stdio.h>
#include <stdlib.h>

struct one_int {
    int num;
};

#ifdef WRONG
static int compare(const struct one_int *a, const struct one_int *b)
{
#else
static int compare(const void *a_, const void *b_)
{
    const struct one_int *a = a_;
    const struct one_int *b = b_;
#endif
    if (a->num > b->num) return 1;
    else if (a->num < b->num) return -1;
    else return 0;
}

int main(void)
{
    struct one_int data[] = {
        { 42 },
        { 1 },
        { 100 }
    };
    size_t n = sizeof data / sizeof data[0];

    qsort(data, n, sizeof data[0], compare);
    return 0;
}

使用compare()定义为两个const struct one_int *值进行编译:

$ gcc -DWRONG -ansi -pedantic -W -Wall qs.c
qs.c: In function `main':
qs.c:32: warning: passing argument 4 of `qsort' from incompatible pointer type

使用正确的定义进行编译:

$ gcc -ansi -pedantic -W -Wall qs.c
$

编辑2:compare_wid对于最终参数使用as-it-is 的合法性似乎存在一些混淆qsort().在comp.lang.c常见问题,问题13.9有一个很好的解释(重点煤矿):

要理解为什么qsort比较函数中的好奇指针转换是必要的(以及为什么在调用时函数指针qsort的强制转换无法帮助),考虑如何qsort工作是有用的.qsort对所排序的数据的类型或表示一无所知:它只是在一小块内存中乱窜.(所有它知道的块是它们的大小,你在qsort第三个参数中指定.)要确定两个块是否需要交换,请qsort调用比较函数.(要交换它们,它使用相当于memcpy.)

由于qsort使用未知类型的内存块以通用方式进行处理,因此它使用通用指针(void *)来引用它们.当qsort调用比较函数时,它将作为参数传递给要比较的块的两个通用指针.由于它传递通用指针,因此比较函数必须接受通用指针,并在操作它们之前将指针转换回适当的类型(即在执行比较之前).甲void指针不在相同类型的结构的指针,以及在一些机器上它可能具有不同的大小或表示(这就是为什么所需要的正确性这些管型).

如常见问题解答中所述,也可以看到这一点.

Answer 2

(int (*)(const void *,const void *))表示"将后面的内容视为指向函数的指针,该函数接受两个类型的参数const void*并返回int".compare_wid确实是一种可以这种方式对待的功能.

qsort 将调用此函数以在排序时执行项目之间的比较:如果返回的整数为零,则假定项目相等,否则使用整数的符号对它们进行排序.