C中的qsort与非全局查找表比较

Question

我正在尝试重构一个当前是独立的C程序的实用工具，以便我可以制作可重用的库。它包括对数组进行排序的步骤，根据全局数组中相应的值。

// Global lookup table
double *rating;

// Comparator using lookup
int comp_by_rating(const void *a, const void *b) {
  int * x = (int *) a;
  int * y = (int *) b;
  if (rating[*x] > rating[*y])
    return 1;
  else if (rating[*x] < rating[*y])
    return -1;
  else
    return 0;
}

int main() {
  int* myarray;
  // ...
  // initialize values of local myarray and global rating
  // ...

  qsort(myarray, length_myarray, sizeof(int), comp_by_rating);
  // ...
  return 0;
}

有没有办法避免使用全局的rating查找表？我通常使用C++，所以我的第一个想法是使用函数对象，但我必须保持在C中，所以我猜我没有函数对象可用。我也不能用一个包含每个项目评分的结构体数组替换int *myarray，因为其他代码需要当前形式的数组。我还有其他选择吗？

- beldaz

---

总之，不行。这是C语言的脑残方式。说真的，添加一个接受额外void *user_data参数并将其传递给比较函数的qsort变体有多难？ - n. m.

@n.m. 谢谢，我想知道我漏掉的两行代码是干什么用的。现在已经放回去了。 - beldaz

使用qsort_r进行编程。 - BLUEPIXY

@BLUEPIXY https://dev59.com/t2855IYBdhLWcg3wg0nC - n. m.

@BLUEPIXY 很遗憾，那是不可移植的。 - fuz

Answer 1

我无法用包含每个项目评分的结构体数组替换 int *myarray，因为其他代码需要以其当前形式使用该数组。

您可以暂时替换排序，调用 qsort，并将结果收集回原始数组：

struct rated_int {
    int n;
    double r;
};

struct rated_int *tmp = malloc(length_myarray * sizeof(struct rated_int));
for (int i = 0 ; i != length_myarray ; i++) {
    tmp[i].n = myarray[i];
    tmp[i].r = ratings[myarray[i]];
}
qsort(tmp, length_myarray, sizeof(struct rated_int), comp_struct);
for (int i = 0 ; i != length_myarray ; i++) {
    myarray[i] = tmp[i].n;
}
free(tmp);

这样，代码中的其他部分就会把myarray视为整数数组。

- Sergey Kalinichenko

---

没错。这就是你在 C 中的操作方式，顺便说一下，“只需将性能关键部分重写为 C”这个论点在实践中并不总是奏效的原因之一... - user268396

@FUZxxl，虽然不是完全一样，但制作副本、对副本进行排序，然后使用for循环迭代副本并将结果插入到相应位置的一般思路仍然适用。 - user268396

这对我来说是最好的选择，谢谢。 - beldaz

@FUZxxl：不，如果你需要摆脱像这样被自己困住的局面，那么复制就是在C中解决问题的方法...做“聪明”的事情通常会导致更糟糕的灾难。 - user268396

@user268396 看起来你不够有创意，找不到一个高效的解决方案。 - fuz

Answer 2

这就是在C语言中的操作方法。如果你担心线程安全问题，可以考虑将变量设为线程本地变量，这样多个线程就会有不同的副本：

static _Thread_local double *rating;

这在旧编译器中不受支持，因此您需要某种可移植性巧妙解决方法。如果您也不喜欢这个方法，那么您实际上无法避免编写自己的排序程序以允许额外的参数。

gcc提供嵌套函数作为扩展来解决这个问题，但它们有其他问题，即它们需要一个可执行堆栈，这会降低您的程序对错误的弹性。

- fuz

---

@beldaz 我不知道任何现成的，我为这个问题编写了自己的排序算法。排序并不是最难实现的算法。 - fuz

@beldaz FreeBSD有一个BSD许可的qsort_r函数。你可以在源代码树中找到入口点（https://github.com/freebsd/freebsd/blob/master/lib/libc/stdlib/qsort_r.c）。不过代码有点复杂。 - fuz

@FUZxxl glibc 也有 qsort_r 函数可以实现相同的功能。它具有不同的接口。这个区别可能在编译时被检测到，也可能不会。但如果你意外地使用了错误的函数，在运行时会出错。这就是 C 语言的风格。 - n. m.

@n.m. 我指的是 qsort_r 作为一种排序例程，可以满足 OP 的需求并且可以自由复制。我并不是告诉他依赖于 qsort_r 可用，而是告诉他将代码复制到自己的项目中。也许我应该表述得更清楚些。 - fuz

@n.m. 是的。我的第一个建议是编写自己的排序程序，这样你就能理解它存在的错误。 - fuz

Answer 3

不，数组评分不必是全局的：您可以在此处使用static：

int comp_by_rating(const void *a, const void *b) {
    static double *rating = { .. init here .. };

如果成员变量是非常量，可以使用另一种初始化方式：

int comp_by_rating(const void *a, const void *b) {
    static double *rating = NULL;
    if (!rating) {
        // Initialize rating here
    }
}

- Ctx

---

@user268396 什么？请问，你不会认真地声称rating是一个全局变量吧。 - Ctx

@user268396 不，这不是全局变量。在这个语义中，函数comp_by_rating是全局的，而评分是它的本地变量。你实际上想要表达的是任何不在堆栈上的变量都是全局的。但事实并非如此。另请参阅：https://en.wikipedia.org/wiki/Static_variable（示例）。 - Ctx

文件静态变量比函数静态变量更加灵活，而且没有任何显著的缺点。 - n. m.

@user268396 在语言结构方面，全局和局部是变量作用域的术语，你使用这些术语是完全错误的。 - Ctx

@user268396 全局变量的定义是指可以在整个项目中访问的变量（大惊小怪）。也就是说，它可以在项目的任何地方被访问。因此，按照定义，static变量永远不可能是全局变量，最多只能具有文件作用域。文件作用域并非全局作用域。总的来说，您混淆了“作用域”和“存储期限”，它们是完全不同的概念。单例模式与作用域关系不大，但与存储期限有很大关系。 - Lundin