Qsort使用的比较函数 - 比较（char **）

Question

这里是比较函数：

int compare(const void *a, const void *b) {
    char* *s = (char* *) a;
    char* *t = (char* *) b;
    return sort_order * strcmp(*s, *t); // sort_order is -1 or 1
}

现在我的问题是，将特定类型的转换为double指针背后的推理是什么？或者说，为什么需要双指针强制转换以及它在内部如何使用？

其他使用的变量： char **wordlist; int nbr_words;（数组元素为）char *word; 示例 qsort 调用：qsort(wordlist, nbr_words, sizeof(char *), compare);

- Chris Cirefice

---

不是答案，但是如果 sort_order == -1 并且 strcmp 返回 INT_MIN，则您的代码存在整数溢出可能性。 - zch

我不知道这是否有问题，因为它是可行的。我只想知道将指针转换为双指针的原因是什么 :) - Chris Cirefice

@ChrisCirefice，当s1比s2“小”时，它可以返回任何值<0。 INT_MIN是最小可能的int。在常见的架构（2补码）中，INT_MIN == -INT_MAX - 1。 - zch

@self 这也在 Paul Griffiths 的回答中得到了展示和解释 :) - Chris Cirefice

@self：我在我的答案底部添加了一个编辑，以解释正在发生的事情。 - Crowman

Answer 1

如果您显示wordlist的定义会很有帮助，但最有可能它被定义为char **。 compare()函数接收您列表中每个元素的指针。如果您列表中的每个元素都是char *类型，则compare()将接收两个指向char *或两个char **的指针。

转换为char **(请注意，在这种特殊情况下，实际上进行转换是多余的，如果您不是从const void指针转换为非const char **)本身是必要的，因为qsort()必须处理任何类型的参数在传递之前都会转换为void *。您无法对void *进行解引用，因此您必须在执行任何操作之前将它们转换回其原始类型。

例如：

#include <stdio.h>

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

int compare_double(void * a, void * b) {
    double * pa = a;
    double * pb = b;
    if ( *pa < *pb ) {
        return -1;
    } else if ( *pa > *pb ) {
        return 1;
    } else {
        return 0;
    }
}

int compare_any(void * a, void * b, int (*cfunc)(void *, void *)) {
    return cfunc(a, b);
}

int main(void) {
    int a = 1, b = 2;
    if ( compare_any(&a, &b, compare_int) ) {
        puts("a and b are not equal");
    } else {
        puts("a and b are equal");
    }

    double c = 3.0, d = 3.0;
    if ( compare_any(&c, &d, compare_double) ) {
        puts("c and d are not equal");
    } else {
        puts("c and d are equal");
    }

    return 0;
}

输出：

paul@local:~/src/c/scratch$ ./comp
a and b are not equal
c and d are equal
paul@local:~/src/c/scratch$

“compare_any（）”函数将比较任何受支持的类型，例如“int”和“double”，因为我们可以向其传递函数指针。然而，所传递函数的签名必须相同，因此我们不能声明“compare_int（）”需要两个“int *”参数，“compare_double（）”需要两个“double *”参数。我们必须将它们都声明为需要两个“void *”参数，并且在这样做时，我们必须在这些函数内部将这些“void *”参数转换为有用的内容，然后才能使用它们。

在您的情况下，发生的情况完全相同，但是数据本身是指针，因此我们正在传递指向指针的指针，因此我们需要将“void *”转换为“char **”。

编辑：为了解释原始问题评论中的一些混淆，这是“qsort（）”的签名：

void qsort(void *base, size_t nmemb, size_t size,
           int(*compar)(const void*, const void*))

“base”是一个指向数组第一个元素的指针，“nmemb”是该数组成员的数量，“size”是每个元素的大小。

当“qsort()”在您的数组的第一个和第二个元素上调用“compar”时，它将发送第一个元素的地址（即“base”本身）和元素的地址（即“base + size”）。

如果最初声明“base”为“int”数组，则比较函数必须将其接收到的那些指针解释为指向“int”的指针，即“int *”。如果最初将“base”声明为字符串数组，则比较函数必须将这些指针解释为指向“char *”的指针，即“char **”。

在所有情况下，比较函数都会得到元素的指针。如果您有一个“int”数组，则必须在比较函数中将这些指针解释为“int *”。如果您有一个“char *”数组，则必须将它们解释为“char **”，依此类推。

在这种情况下，如果您只是向比较函数传递普通的“char *”参数，显然您可以调用“strcmp()”。但是，由于“qsort()”是通用的，它只能传递指向比较函数的指针，而不能实际传递您的元素值 - 使用“void *”使其通用成为可能，因为任何类型的对象指针都可以转换为“void *”，但是没有等效的数据类型可以将任何非指针值转换为。因此，即使元素本身也是指针时，“qsort()”必须以相同的方式处理常规类型（如“int”和“double”），指针和结构体，使其能够正确处理所有可能的类型的唯一方法是让它处理指向元素的指针，而不是元素本身，即使这些元素本身也是指针。因此，在这里，它似乎会获得不必要的间接级别，但实际上为了使“qsort()”能够以其通用方式工作，这是必需的。

如果我修改上面的代码，使“compare_any()”更类似于“qsort()”，并且不是两个指针，而是一个指向各种类型的两个元素数组的单个指针（稍微牵强的例子，但我们保持简单），您可以更清楚地看到这一点。

#include <stdio.h>
#include <string.h>

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

int compare_double(void * a, void * b) {
    double * pa = a;
    double * pb = b;
    if ( *pa < *pb ) {
        return -1;
    } else if ( *pa > *pb ) {
        return 1;
    } else {
        return 0;
    }
}

int compare_string(void * a, void * b) {
    char ** pa = a;
    char ** pb = b;
    return strcmp(*pa, *pb);
}

int compare_any(void * arr, size_t size, int (*cfunc)(void *, void *)) {
    char * first = arr;
    char * second = first + size;
    return cfunc(first, second);
}

int main(void) {
    int n[2] = {1, 2};
    if ( compare_any(n, sizeof(*n), compare_int) ) {
        puts("a and b are not equal");
    } else {
        puts("a and b are equal");
    }

    double d[2] = {3.0, 3.0};
    if ( compare_any(d, sizeof(*d), compare_double) ) {
        puts("c and d are not equal");
    } else {
        puts("c and d are equal");
    }

    char * s[] = {"abcd", "bcde"};
    if ( compare_any(s, sizeof(*s), compare_string) ) {
        puts("'abcd' and 'bcde' are not equal");
    } else {
        puts("'abcd' and 'bcde' are equal");
    }

    return 0;
}

输出：

paul@local:~/src/c/scratch$ ./comp
a and b are not equal
c and d are equal
'abcd' and 'bcde' are not equal
paul@local:~/src/c/scratch$

正如你所看到的，如果没有compare_string()函数得到它需要处理为char **的指针，compare_any()不可能同时接受int数组和char *数组，因为它对数组元素进行了指针运算。如果没有这个额外的间接层，compare_int()和compare_double()都无法正常工作。

- Crowman

---

在我看来，传递的值似乎是数组的元素（当然）。这些作为指针传递到比较函数中。由于 qsort 接受 任何 类型，正如你所说，它们是空指针。因此，您必须将它们转换回其原始类型，这是有道理的。我想我只是困惑为什么它们不直接转换回 char *X 和 char *Y，然后作为 strcmp(X, Y) 传递给 strcmp。 - Chris Cirefice

看了你的编辑，现在我明白了！我对指针还很新，所以这个*转换看起来像是多余的，但考虑到它不仅仅是一个数据而且数据本身就是一个指针，所以这一步是必要的。感谢你的解释 :) - Chris Cirefice

@PaulGriffiths 我必须说我感到非常惊喜；我错了，不知怎么把指针和数组搞混了。 - this

请注意，在您的问题中，实际的转换是不必要的 - 因为我们正在处理void *，所以这个：char* *s = (char* *) a;可以（并且在我看来应该）写成char ** s = a;。在转换到或从void *时，实际的转换是不必要的，它会隐式转换。如果您尝试直接对其进行解引用（即在未将其先存储在char ** s中的情况下），则需要进行转换，例如strcmp(*((char **) a), *((char **) b));。 - Crowman

qsort函数的最后一个参数是一个带有const参数的函数指针。 - this