向qsort的比较器传递额外参数

Question

我想知道是否有一种方法可以向比较器传递额外的参数，然后在qsort函数中使用?

例如，我有这两个比较器（一个按升序排列，一个按降序排列）

qsort(entries, 3, sizeof(struct entry), compare_desc);

int compare_asc(const void *elem1, const void *elem2)
{
     return strcmp(elem1.name.last, elem2.name.last);
}


int compare_desc(const void *elem1, const void *elem2)
{
     return strcmp(elem2.name.last, elem1.name.last);
}

有没有办法让我像这样做：

int compare(const void *elem1, const void *elem2, const char *order)
{
     if (strcmp(order, "asc") == 0)
         return strcmp(elem1.name.last, elem2.name.last);
     else if (strcmp(order, "desc") == 0)
         return strcmp(elem2.name.last, elem1.name.last);
}

我问的原因是我的排序程序需要使用开关，如果我有两个不同的开关（+a，-a）表示升序和降序，那么我必须编写两个不同的比较函数。如果我添加更多，则会变得更加复杂。有没有一种改进此程序设计的方法？

编辑：不允许全局和外部变量。

- Jugo Monte

---

希望你的代码不是这样的 - 你不能访问 void * 的 .name 成员。 - Chris Lutz

顺便提一下，如果你担心添加更多选项，注意你不一定需要每个函数都有升序和降序版本——你总是可以在排序后反转整个数组。 - Arkku

下面有很好的答案，但关键是qsort()库代码只会向您的比较器传递两个值。您可以控制给qsort()的函数指针，但不能控制回调的执行方式。 - Blastfurnace

我也遇到了这个问题，找到了一个非常简单的解决方案： int foo(int a,int b,int c){ return (a-b)c; } int main(){ int arr[]={3,5,1,7,9}; int extraparam=6,i; for(i=0;i<5;++i){ printf("%d ",arr[i]); } printf("\n"); int cmp(const void a,const void b){ return foo((int)a,(int*)b,extraparam); } qsort(arr,5,sizeof(int),cmp); for(i=0;i<5;++i){ printf("%d ",arr[i]); } printf("\n"); } 输出： 3 5 1 7 9 1 3 5 7 9 效果非常好 - Ariana

你真的不想在快速排序的每个比较中执行strcmp()，甚至是多余的if。你提前知道你想要升序还是降序：提供适当的比较器。 - user207421

Answer 1

虽然这是一个老问题，但如果有人碰巧遇到它......

有一些非标准版本的qsort（）函数可让您向回调函数传递额外的参数。 glib提供了qsort_r（）函数，而VC则提供了qsort_s（）函数。

- cleong

---

请注意，对于qsort_r()和qsort_s()，在不同的平台上有不同的签名（大多数平台只提供其中一个）。您必须知道哪个函数可用，以及它的调用序列和比较器调用序列是什么。请参见我的答案获取详细信息。 - Jonathan Leffler

Answer 2

在您的例子中，最好有两个不同的比较器。如果只有一个，每次比较都不必要地确定排序顺序，你无论如何都不能在排序过程中更改排序方式以获得任何有意义的结果。因此，不要把if (ascending_sort) { } else { }放在比较器内部，而是放在qsort调用处：

qsort(e, n, sizeof(*e), (strcmp(order, "asc") ? compare_desc : compare_asc));

编辑： 如果您添加更多比较器，请注意以下几点：

- 记住，您不需要重新编写每个比较器；如果您正在对多个字段进行排序，可以让它们相互调用（如果需要反转比较结果，可以始终使用-，例如，compare_asc(a, b) 可以返回 -compare_desc(a, b)）。 - 在最后轻松地反转整个数组的顺序，因此您无需将支持反转整个排序顺序的选项的比较器数量翻倍。 - 您可以用下面评论中建议的函数替换我示例中的三元运算符（? :），以返回适当的比较器。

- Arkku

---

实际上，我们可能应该说 int (*sort_type(const char *))(const void *, const void *) { if(!strcmp(rder, "asc") return compare_asc; return compare_desc; } 来简化排序调用为 qsort(e, n, sizeof *e, sort_type("asc")); （这也使添加新的排序类型更容易）。 - Chris Lutz

是的，如果有超过两个选项，那是一个不错的选择。 - Arkku

即使只有两个，这也是一个不错的选择，因为它可以让你添加更多选项或调整选项的读取方式，而无需修改对 qsort 的每个调用。 - Chris Lutz

好的，我基本上是假设只有一个对qsort的调用。 - Arkku

Answer 3

qsort_r()和qsort_s()

一些实现中提供了名为qsort_r()或qsort_s()的函数，它们可以接受传递给比较函数的额外数据指针。

BSD变体实现（包括macOS或Mac OS X）提供了一个版本的qsort_r()，GNU C库也提供了一个版本。不幸的是，这两个变体具有不同的签名。这并不妨碍它们的实用性，但这意味着不能在两个平台上使用相同的源代码，并且需要确保您了解在任何尝试使用它的机器上可用的qsort_r()的哪个变体。

同样地，Microsoft提供了qsort_s()的版本，C11标准定义了qsort_s()的版本（作为附录K中的可选函数，基于TR-24731），但两者的签名再次不同。也许值得庆幸的是，附录K的函数没有被广泛实现。

BSD qsort_r()

void qsort_r(void *base, size_t nel, size_t width, void *thunk,
             int (*compar)(void *, const void *, const void *));

GNU C library qsort_r()

void qsort_r(void *base, size_t nmemb, size_t size,
             int (*compar)(const void *, const void *, void *),
             void *arg);

请注意，在BSD中，“thunk”等同于GNU中的“arg”，但是这些参数在调用qsort_r()函数时出现在不同的位置（在比较器函数指针之前和之后）。此外，请注意，“thunk”作为第1个参数传递给BSD比较器函数，但是“arg”作为第3个参数传递给GNU比较器函数。

记忆qsort_r的助记符：上下文数据与比较器相关，在调用序列中与将上下文传递给比较器与比较的两个值之间的关系相同。指向比较器的指针之前的上下文意味着调用比较器之前的上下文；指向比较器的指针之后的上下文意味着在调用比较器之后的上下文。

附录K qsort_s()

errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
               int (*compar)(const void *x, const void *y, void *context),
               void *context);

附录K中的qsort_s()函数具有返回值的独特特点，而其他变体则没有返回任何值。对于大多数实际目的而言，它与GNU qsort_r()函数相匹配。

微软qsort_s()

void qsort_s(void *base, size_t num, size_t width,
             int (__cdecl *compare )(void *, const void *, const void *),
             void * context);

rsize_t和size_t的区别在比较附录K和Microsoft的qsort_s()时并不是非常重要，但在附录K的qsort_s()中，上下文作为第3个参数传递给比较器，而在Microsoft的qsort_s()中，上下文作为第1个参数传递给比较器。

摘要

调用qsort_r()或qsort_s()函数提供所需功能。 但是，您必须检查平台规范以了解哪个函数存在，并了解排序函数参数和比较器参数的正确呼叫顺序及。名义上，您也应该检查函数的返回类型，但很少有程序考虑检查它，主要是因为大多数qsort()变体没有返回值。

- Jonathan Leffler

Answer 4

您需要做的是交换 qsort 的参数，以便适当地传递函数指针。

根据您的情况，可能是这样的：

// selectively invoke qsort:
if(strcmp(var, "+a")){
    qsort(entries, 3, sizeof(struct entry), compare_asc);
}else{
    qsort(entries, 3, sizeof(struct entry), compare_desc);
}

或者，您可以像这样做：

// declare a function pointer
int (*func)(const void*, const void*);

// sometime later decide which function to assign
// to the function pointer
if(strcmp(var, "+a")){
    func = compare_asc;
}else{
    func = compare_Desc;
}

// sometime later invoke qsort
qsort(entries, 3, sizeof(struct entry), compare_desc);

- Mark Elliot

---

我会将选择排序函数的代码放入一个单独的函数中（称为 sort_type），然后只需调用 qsort(entries, 3, sizeof *entries, sort_type(user_type));。 - Chris Lutz

Answer 5

> 有没有办法改进这个程序的设计？

不要这样做-这并不是设计上的改进，这只是一个实验。

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

int comparefx(const void *a, const void *b) {
    static int extra = 0;
    if (a == NULL) {
        extra = (int)b;
        return 0;
    }
    switch (extra) {
        case 24: puts("24"); return *(const int*)a + *(const int*)b; break;
        case 42: puts("42"); return *(const int*)b - *(const int*)a; break;
        default: puts("--"); return *(const int*)a - *(const int*)b; break;
    }
}

int main(void) {
    int entries[] = {4, 2, 8};

    qsort(entries, 3, sizeof *entries, comparefx);
    printf("%d %d %d\n", entries[0], entries[1], entries[2]);

    comparefx(NULL, (void*)42); /* set 'extra' parameter */
    qsort(entries, 3, sizeof *entries, comparefx);
    printf("%d %d %d\n", entries[0], entries[1], entries[2]);

    return 0;
}

这段代码可以“干净”地编译通过三个编译器

$ gcc -std=c89 -pedantic -Wall 4210689.c
4210689.c：在函数‘comparefx’中：
4210689.c：7：警告：不同大小的指针转换为整数

$ clang -std=c89 -pedantic -Wall 4210689.c
$ tcc -Wall 4210689.c
$ 

并且按预期运行

$ ./a.out
--
--
--
2 4 8
42
42
42
8 4 2

- pmg

---

在初始化时，传递指针作为“b”会更正确。 - SLaks

Answer 6

据我所知，一般情况下，如果不使用全局变量，你无法实现这个功能，你必须为两种排序方法提供两个不同的函数。实际上，这就是为什么在C++中经常使用函数对象（即提供重载函数调用运算符的对象）的原因之一。

- Matteo Italia

Answer 7

在简单的情况下，您可以使用全局变量。

- SLaks

---

抱歉，我忘了提到其中一个要求是不允许使用全局变量。 - Jugo Monte

这是一个更一般问题的简单而可行的解决方案 :) - Yan King Yin

Answer 8

缺乏类和闭包意味着你必须为每种不同类型的比较编写单独的比较器，这让你束手无策。

你可以将数组的每个元素都作为一个结构体，包含value和sort_order字段。所有的sort_order字段都是相同的...但这比只有2个比较器还要糟糕。

可以这样想：你最终会编写所有相同的比较器代码。但是，你不需要使用8个复杂的嵌套if/else语句，而是有8个函数。区别在于多了一些额外的函数声明。

编辑：回复R的评论...这是一个好观点。我之前有过这个想法，但我删掉了它：

你可以创建一个类似于Python的list.sort()函数的框架。基本上：

• 创建一个带有value和sortvalue字段的结构体。
• 将初始值放入value中。
• 编写任何代码来将项目转换为sortvalue字段。
• 使用标准比较器以及qsort。
• 完成后，只需从value字段中取出元素。它们将按sortvalue排序，但值将是正确的。

在Python中，例如，如果您想按元组中的第4个项目进行排序，您不需要编写整个比较器（如lambda v1,v2: v1[3]-v2[3]），而只需使用key函数（lambda k:k[3]）转换输入并使用标准排序方法即可。在“数十亿次排序”的情况下，它将起作用，因为您的代码可以对无论多少个输入执行任何复杂的操作以转换值。

- Claudiu

---

但是如果有数十亿个可能的比较函数依赖于整数或浮点数（例如某种权重或偏移量），怎么办呢？在C语言中，qsort等函数缺乏闭包（或等效功能）是一个主要问题。在我看来，唯一的解决方案（我不认为全局变量是一个解决方案）是编写自己的排序框架，如果需要闭包支持，并祈祷它在所有目标上运行得像系统的qsort一样快或更快。 - R.. GitHub STOP HELPING ICE

Answer 9

只需使用lambda函数进行闭包。 类似于这样的C++代码：

string sortOrder="asc";   
qsort(entries, 3, sizeof(struct entry),    
[=](const void *elem1, const void *elem2) -> int{
        myCompare(elem1,elem2,sortOrde)             

});

- O_Z

---

这个问题被标记为[tag:c]而不是[tag:c++]。你的建议只适用于C++。 - Jonathan Leffler