使用void指针和类型参数对C中的多个类型进行排序

Question

在这个问题中,一个带有void指向数组的指针,元素个数和一个表示元素类型的整数的函数应该对数组进行排序.是否有任何技巧可以避免在以下解决方案中编写相同的代码4次？

//type 1:short, 2:int, 3:float, 4:double
void Sort(void *values, int nValues, int type) {
    int i, j, temp;

    switch(type) {
    case 1: //short
    {
        short *ptr = (short *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
        break;
    }
    case 2: // int
    {
        int *ptr = (int *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
        break;
    }
    case 3: // float
    {
        float *ptr = (float *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
        break;
    }
    case 4: // double
    {
        double *ptr = (double *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
    }
    }
}

Answer 1

是的,还有另一种选择.在C标准库中已经有一个叫做的函数qsort(可能是快速排序的缩写,但它也可以是任何其他的排序算法).要使用该函数,可以将数组,数组中的元素数,每个元素的大小和比较函数传递给它.

您只需要为每种数据类型编写比较函数,如该页面上的示例所示.

如果要将4个比较函数合并到单个函数中,则必须将一些上下文信息传递给比较函数.在这种情况下,你不能再使用qsort,但必须使用qsort_s.然后您的比较功能可能如下所示:

#define compare(a, b) (((a) > (b)) - ((b) > (a)))
#define compare_ptr(type) (compare(*(type *)(p1), *(type *)(p2)))

static int compare_by_type(const void *p1, const void *p2, void *ctx) {
    int type = *(int *) ctx;
    switch (type) {
    case 1: return compare_ptr(short);
    case 2: return compare_ptr(int);
    case 3: return compare_ptr(float);
    case 4: return compare_ptr(double);
    default: return 0;
    }
}

#undef compare
#undef compare_ptr

int main(void) {
    int iarray[] = {1, 6, 4, 9, 55, 999, -33333};
    int sort_type = 1;

    qsort_s(iarray, 7, sizeof(int), compare_by_type, &type);
}

这是一些相当先进的东西:

• 传递函数指针
• 使用指向任意类型的指针做指针
• 使用接受类型名称作为宏参数的宏
• 将布尔算术与整数运算混合

但最终,只要它们支持<运营商,就可以在列表中添加更多类型.

请注意,float和double甚至不属于这一类,因为它们的操作<返回false只要数目之一NaN,这意味着不是一个数字,从表现形式,例如成果0.0 / 0.0.只要在数组中有这样的值,行为就会变得不确定.排序功能甚至可能陷入无限循环.要解决此问题,请更改compare宏的定义:

#define compare(a, b) (((a) > (b)) - !((b) <= (a)))

它现在看起来更复杂,但适用于NaN.例如:

compare(NaN, 5)
= (NaN > 5) - !(5 <= NaN)
= false - !(5 <= NaN)
= false - !(false)
= false - true
= 0 - 1
= -1

这意味着NaN将被排序到数组的前面.

compare(NaN, NaN)
= (NaN > NaN) - !(NaN <= NaN)
= false - true
= -1

该死.比较两个NaN应该得到0,意味着它们是相等的.所以在这种特殊情况下需要进行修正:

#define compare(a, b) (((a) > (b)) - ((b) > (a)) - ((a) != (a) || (b) != (b)))

由于NaN是唯一一个与自身不相等的值,因此这个附加代码不会影响整数运算,并且会被编译器优化掉.