qsort с указателем на указатель на пустоту

Здесь работает qsort, но если каждый член массива v занимает sizeof(void *), почему qsort ожидает sizeof(int)?

#include <stdio.h>
#include <stdlib.h>

int comp(const void *pa, const void *pb)
{
    int a = *(int *)pa;
    int b = *(int *)pb;

    if (a > b)
        return +1;
    else
    if (b > a)
        return -1;
    else
        return 0;
}

int main(void)
{
    int i, a[] = {3, 1, 2, 0, 4};
    void **v;

    v = malloc(sizeof(void *) * 5);
    for (i = 0; i < 5; i++) {
        v[i] = &a[i];
    }
    for (i = 0; i < 5; i++) {
        printf("%d\n", *(int *)v[i]);
    }
    qsort(v[0], 5, sizeof(int), comp); // why sizeof(int) if v is void **
    printf("Sorted:\n");
    for (i = 0; i < 5; i++) {
        printf("%d\n", *(int *)v[i]);
    }
    free(v);
    return 0;
}

c qsort
person David Ranieri    schedule 10.07.2013    source источник
comment
Дэвид: ты понимаешь v[i] = &a[i]; выражение в своем коде, зачем это нужно и почему v здесь правильно void* ??   -  person Grijesh Chauhan    schedule 10.07.2013
comment
@GrjeshChauhan, мне приходится использовать void ** (как абстракцию для универсального контейнера) для сортировки разных типов   -  person David Ranieri    schedule 10.07.2013
comment
Правильно!, и v[i] = &a[i] необходим, потому что вы хотите отсортировать массив a[], но в вызове qsort() вы передаете v, который не содержит информацию о типе вашего массива a[], поэтому вы явно передаете информацию о содержимом, что a[i] элементы являются int.   -  person Grijesh Chauhan    schedule 10.07.2013

Ответы (1)


arrow_upward
6
arrow_downward 

qsort(v[0], 5, sizeof(int), comp); // why sizeof(int) if v is void **

Адрес начала сортируемого блока памяти, который вы передаете qsort, равен

v[0] = &a[0]

адрес начального элемента a, поэтому массив, который вы сортируете, это a, а не блок, на который указывает начальный элемент v. Элементы a равны ints, поэтому sizeof(int) — правильный размер.

Если вы хотите отсортировать массив указателей, вам нужно передать адрес первого элемента в этом массиве, &v[0], или просто v в qsort. Тогда, конечно, аргумент размера должен быть sizeof (void*):

qsort(v, 5, sizeof(void*), cmp);

но для этого вы не можете использовать функцию сравнения, которая у вас есть, вам нужно

int cmp(const void *pa, const void *pb) {
    int a = *(int*)(*(void**)pa);
    int b = *(int*)(*(void**)pb);

    if (a > b)
        return +1;
    else
    if (b > a)
        return -1;
    else
        return 0;
}

или что-то подобное. Поскольку то, что передается в функцию сравнения из qsort, является адресом сравниваемых вещей, нам нужна одна косвенность, чтобы получить указатели для сравнения, и поскольку здесь мы хотим сравнить указатели по тому, на какие int значения они указывают, нам нужна вторая косвенность, чтобы получить указанный ints.

person Daniel Fischer    schedule 10.07.2013
comment
Нет, qsort передает &a[i] и &a[j] (вычисленные через параметр size) в comp, так что это правильно. Возможно, это не то, что было задумано — если целью была сортировка массива указателей — но, как оказалось, код правильный. Возможно случайно. - person Daniel Fischer; 10.07.2013
comment
Да, я знаю, что &a[i] и &a[j] передаются в компаратор, и это именно меня смущает... Я не понимаю, как это правильно, я пропускаю уровень косвенности... может быть, я нужно вздремнуть, а не торчать на SO :) - person ; 10.07.2013
comment
понял Даниэль, спасибо, и да, целью было отсортировать массив указателей, как передать void ** в qsort, чтобы отсортировать v (не a)? - person David Ranieri; 10.07.2013
comment
@ H2CO3 На самом деле вызов qsort(a, 5, sizeof(int), comp); (ну, &a[0], если кто-то хочет сделать преобразование явным). Вы понимаете, почему это работает? v - это просто ерунда, которая никак не влияет на сортировку. - person Daniel Fischer; 10.07.2013
comment
@DanielFischer Да, правильно, это то, чего мне не хватало. Я такой глупый. Ааааааааааааааааааааааааааааааа :/ - person ; 10.07.2013
comment
@DavidRF Чтобы отсортировать массив указателей, вам нужно изменить функцию сравнения (и вызов). Дайте мне несколько минут, чтобы напечатать это. - person Daniel Fischer; 10.07.2013