c - qsort のような C 関数は、さまざまなデータ型でどのように機能しますか?

Question

ではstdlib.h、プロトタイプを使用した関数 qsort() の宣言があります。

void qsort( void *ptr, size_t count, size_t size,
        int (*comp)(const void *, const void *) );

明らかにそれはジェネリックプログラミングです。どのように実装するのだろうか、void * 型から要素を取得する方法は?

Answer 1

void *size_t sizeポインターは( の 3 番目の引数qsort)に従ってキャストされます。

最初に to を型キャストvoid*しchar*、次に に従ってポインター演算を行いますsize(char は1バイトを取るため、サイズを追加すると正しいポインター演算が得られます)。

EDIT : (組み込みデータ型の場合)

char *ptr = (char*)vp; //here vp is void *p

*(ptr + (n-1)*size); //will give you nth element 

例えば

size =1 and want 3rd element it means it will give you 3rd char
size =4 and want 3rd element it means it will give you 3rd int or float
size =2 and want 3rd element it means it will give you 3rd short int
size =8 and want 3rd element it means it will give you 3rd double

注：サイズは実装定義であるため、コンパイラによって異なる場合があります

Answer 2

#include <stdio.h>

void compare_first_to_rest(void *ptr, size_t nelem, 
   size_t size, int (*cmp)(const void*, const void*)) {
    unsigned i;
    for(i = 1; i < nelem; ++i)
        {
        int res = cmp(ptr, (char*)ptr + i * size);
        if(res < 0)
            printf("First element is less than element at %u\n", i);
        else if(res > 0)
            printf("First element is greater than element at %u\n", i);
        else
            printf("First element is equal to element at %u\n", i);
        }
}

int icmp(const void *x, const void *y) {
   return *(int*)x - *(int*)y;
}

int main()
{
   int x[] = { 5, 3, 6, 2, 4, 8, -1, 10 };
   compare_first_to_rest(x, 8, sizeof(int), icmp);
}

ご覧のとおり、「compare_first_to_rest」は、最初の引数で受け取る要素の型を認識していません。しかし、それぞれのサイズがわかれば、それらすべてへのポインターを取得して、関数ポインターに仕事を任せることができます。

Answer 3

最後のパラメータは関数ポインタです。あなたが暗黙のうちに述べたように、この機能をどこかに実装しているに違いありません。しかし、それを実装すると、実際に void* 要素であるポインタの王様がわかります。

comp 関数では、次のように、2 つのパラメーターを使用するポインター型にキャストする必要があります。

int myCompFn(const void * e1, const void * e2)
{
    MyType *elem1=(MyType*)e1;
    MyType *elem2=(MyType*)e2;
    ... /* then compare elem1 and elem2 regarding to there definition */
}