在纯 C 中，我们可以使用指向 char 的指针而不是指向 void 的指针来实现泛型函数吗？

Question

在纯 C 中，指向 void 的指针可用作泛型函数的参数，例如泛型快速排序或泛型交换等，如下所示：

Implementation of generic quicksort, etc.

但是，如 link 处的通用分区函数示例所示：

size_t generic_partition(void *v, size_t nelems, size_t size, compare_function comp)
{
    // for brevity we'll be using the right-most 'element' for the 
    //  location of the pivot storage. a better choice would use
    //  a median-of-three or median-of-five for pivot selection,
    //  then swap it to that location before the partitioning loop.
    
    void *ploc = (unsigned char*)v + (nelems-1) * size;
    size_t pvt = 0;

    for (size_t i=0; i<nelems; ++i)
    {
        if (comp((unsigned char*)v + (i*size), ploc) < 0)
            generic_swap((unsigned char*)v + (pvt++*size), (unsigned char*)v + (i*size), size);
    }

    generic_swap((unsigned char*)v + (pvt*size), ploc, size);

    return pvt;
}

循环内的指针运算和类型转换可能会很繁重。原因似乎是我们必须经常在void*和char*之间进行转换，因为char*支持指针运算，而void*不支持（因为元素大小未知）。

那么为什么我们不使用 char* 而不是 void* 来实现泛型函数的泛型参数呢？它似乎具有 void* 的优点（通用性，因为不是每种类型都占用一个字节的某个整数倍吗？）以及支持指针运算的额外优点。

仅使用指向 char 的指针，而不使用指向 void 的指针，上述代码中的循环是否需要更少的加法、乘法和类型转换？如果是这样，那岂不是更有效率？

也许我遗漏了一些与“comp”等函数有关的东西，它会自动将传递给它们的参数转换为预期的类型？

也许我一般都忽略了这一点。

编辑（包含 generic_swap 的代码）：

void generic_swap(void *a, void *b, size_t size)
{
    if (a == b)
        return;

    unsigned char *p1 = a, *p2 = b;
    while (size-- > 0)
    {
        unsigned char c = *p1;
        *p1++ = *p2;
        *p2++ = c;
    }
}

编辑 - 这就是我所说的避免乘法（对于它的价值）。我把它写成对 dbush 的好答案的修改：

size_t generic_partition(void *v, size_t nelems, size_t size, compare_function comp)
{
    // for brevity we'll be using the right-most 'element' for the 
    //  location of the pivot storage. a better choice would use
    //  a median-of-three or median-of-five for pivot selection,
    //  then swap it to that location before the partitioning loop.
    
    unsigned char *pboundary = v;
    unsigned char *ploc = pboundary + (nelems-1) * size;
    size_t pvt = 0;

    unsigned char *pcurrent = pboundary + size;

    while (pcurrent < ploc)
    {
        if (comp(pcurrent, ploc) < 0)
        {
            generic_swap(pboundary, pcurrent, size);
            pboundary = pboundary + size;
            pvt++;
        }
        pcurrent = pcurrent + size;
    }

    generic_swap(pboundary, ploc, size);

    return pvt;
}

编辑：还有更多说明。算术：

如果while条件中的比较pcurrent < ploc没有定义，也许可以用pcurrent != ploc代替。

另外，我知道有些边缘情况可能会失败，例如，如果数组只有一个元素，但我假设我会在现实生活中小心那些，这里我的问题更多是关于 void *、char* 和指针运算。

编辑：（第四个！）我很乐意将“while”循环恢复为原来的“for”循环，代价是 return 中的一个额外变量（迭代器）以避免在通过 < 或比较指针时可能出现的棘手行为通过 !=.

编辑：（第五个）等等，等一下——有什么地方不对劲！我刚刚回到 Kernighan 和 Ritchie 的书“C 编程语言”，在那里我发现了这个通用分区代码的（变体）包含在快速排序的通用实现中（这是我实际上正在尝试的）实行）。令我惊讶的是，虽然它似乎是完全通用的，但它似乎不使用 指针算法，不使用 转换为字符或无符号字符！我是不是遗漏了什么，或者我咨询过的许多课程和网站的作者是否把事情复杂化了？这是 Kernighan 和 Ritchie 书中的代码：

void qsort(void *v[], int left, int right, int (*comp)(void *, void *))
{
    int i, last;
    void swap(void *v[], int, int);

    if (left >= right)
        return;
    swap(v, left, (left + right)/2);
    last = left;
    for (i = left + 1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1, comp);
    qsort(v, last+1, right, comp);
}

EDIT（第六个！！！）我很抱歉，我显然比我意识到的还要菜鸟：我的消息来源可靠地告诉我，这个 Kernighan-Ritchie“通用”快速排序总是在 指针数组 上运行，并且因此，通用性必须得到程序员的帮助，确保将一个指针数组提供给他们试图排序的实际数组。我可以看到我发布的第一个代码，将其强制转换为 char* 等，以不同的方式实现了通用性。

Answer 1

与 void * 之间的转换可以在没有转换的情况下发生，并且保证适用于任何对象类型。

您实际上可以通过将 void * 参数分配给 unsigned char * 一次，然后在函数的其余部分中使用它来消除转换：

size_t generic_partition(void *v, size_t nelems, size_t size, compare_function comp)
{
    // for brevity we'll be using the right-most 'element' for the 
    //  location of the pivot storage. a better choice would use
    //  a median-of-three or median-of-five for pivot selection,
    //  then swap it to that location before the partitioning loop.
    
    unsigned char *pstart = v;
    unsigned char *ploc = pstart + (nelems-1) * size;
    size_t pvt = 0;

    for (size_t i=0; i<nelems; ++i)
    {
        if (comp(pstart  + (i*size), ploc) < 0)
            generic_swap(pstart + (pvt++*size), pstart + (i*size), size);
    }

    generic_swap(pstart + (pvt*size), ploc, size);

    return pvt;
}

注意构造指针时还是要乘以元素大小

在纯 C 中，我们可以使用指向 char 的指针而不是指向 void 的指针来实现泛型函数吗？

In plain C, could we implement generic functions using pointers to char instead of pointers to void?

c

generics

pointers

void-pointers

char-pointer