如何将比较器 a-la std::less 传递给 C 风格的 Qsort？

Question

所以，我有一个任务要编写一个程序来测试不同排序算法的速度，其中一个很好旧 qsort。我需要向它传递一个比较器，但不是它期望的那个，而是一些布尔值 a-la std::less，我知道要使用它以便 qsort 接受它，我需要实际传递它 less(b, a) - less(a,b) --- 这样，它的范围为 [-1; 1] 并生成我需要的内容。

问题是：我不知道该怎么做！我尝试使用 lambda --- 并且（因为我需要捕获比较器而 qsort 无法处理）它失败了。我试图创建另一个函数，将我的比较器转换为 qsort's:

int make_comparator(const void* a, const void* b) {
    return (int)comp(*(int*)b, *(int*)a) - (int)comp(*(int*)a, *(int*)b);
}

但我不知道如何实际将 comp 传递给它（因为我不能只写 qsort(..., make_comparator(comp, a, b))，可以吗？）。我尝试使用模板来传递 comp，但不知道如何。

所以我已经为此苦苦挣扎了将近一个小时，但离解决方案还差得很远。正确的做法是什么？

Answer 1

您不能通过 qsort 将 cmp 传递给 make_comparator。最好的选择是将函数指针设置为正确的函数。

bool (*comp)(int a, int b) = nullptr;

int make_comparator(const void* a, const void* b) {
    return (int)comp(*(int*)b, *(int*)a) - (int)comp(*(int*)a, *(int*)b);
}

然后将 comp 设置为有效的函数指针

comp = <some function pointer>;

在调用 qsort.

之前

qsort(ptr, count, size, make_comparator);

如果您选择采用这种方法，请确保在 make_comparator 中添加检查，以防止在未设置为有效函数时调用 cmp。

int make_comparator(const void* a, const void* b) {
    if ( comp == nullptr )
    {
       // Deal with error
    }
    return (int)comp(*(int*)b, *(int*)a) - (int)comp(*(int*)a, *(int*)b);
}

Answer 2

你可以尝试这样的事情。 qsort_friendly_comparator 只是作为比较器对象的包装器。唯一的缺点是您必须手动指定比较器类型及其参数类型。

#include <functional>
#include <cstdlib>
#include <cstdio>

// Assumes Comparator take two arguments of the same type and returns a bool.
// Have to manually specify the ArgType because it is tricky to deduce without
// excessive template magic.
template <typename Comparator, typename ArgType>
int qsort_friendly_comparator(const void *first, const void *second)
{
  Comparator comp;

  return (int)comp(*(ArgType*)second, *(ArgType*)first) -
         (int)comp(*(ArgType*)first,  *(ArgType*)second);
}

int main() {
  int data[] = {2, 1, 3, 0}; 

  qsort(data,
        /*num_elem=*/4,
        /*size_of_elem=*/sizeof(int),
        &qsort_friendly_comparator<std::less<int>, int>);

  for (int i = 0; i < 4; i++) {
    printf("%d ", data[i]);
  }
  printf("\n");
}

如何将比较器 a-la std::less 传递给 C 风格的 Qsort？

How to pass a comparator a-la std::less to C-style Qsort?

c++

lambda

compare

qsort