qsort для массива указателей на объекты Objective-C

Question

У меня есть массив указателей на объекты Objective-C.С этими объектами связан ключ сортировки.Я пытаюсь использовать qsort для сортировки массива указателей на эти объекты.Однако при первом вызове моего компаратора первый аргумент указывает на первый элемент моего массива, а второй аргумент указывает на мусор, что дает мне EXC_BAD_ACCESS, когда я пытаюсь получить доступ к его ключу сортировки.

Вот мой код (перефразированный):

- (void)foo:(int)numThingies {
    Thingie **array;
    array = malloc(sizeof(deck[0])*numThingies);

    for(int i = 0; i < numThingies; i++) {
        array[i] = [[Thingie alloc] initWithSortKey:(float)random()/RAND_MAX];
    }

    qsort(array[0], numThingies, sizeof(array[0]), thingieCmp);
}

int thingieCmp(const void *a, const void *b) {
    const Thingie *ia = (const Thingie *)a;
    const Thingie *ib = (const Thingie *)b;

    if (ia.sortKey > ib.sortKey) return 1; //ib point to garbage, so ib.sortKey produces the EXC_BAD_ACCESS
    else return -1;
}

Есть идеи, почему это происходит?

Answer 1

Проблема двоякая:

• первый аргумент qsort должен быть указателем на начало массива

• аргументы, передаваемые в вашу функцию сортировки, на самом деле являются указателями на указатели ваших данных.

Рассмотрим этот рабочий код:

int thingieCmp(const void *a, const void *b) {
    NSObject *aO = *(NSObject **)a;
    NSObject *bO = *(NSObject **)b;

    if (aO.hash > bO.hash) return 1; 
    else return -1;
}


int main (int argc, const char * argv[]) {
    NSObject **array;
    array = malloc(sizeof(NSObject*)*20);

    for(int i = 0; i < 20; i++) {
        array[i] = [NSObject new];
    }

    qsort(array, 20, sizeof(NSObject*), thingieCmp);

    return 0;
}

Обратите внимание, что функция сравнения разрешает указатели данных по NSObject *aO = *(NSObject **)a и qsort функция принимает array как прямой аргумент.

Однако все это вызывает вопрос о Зачем беспокоиться?

NSArray очень хорошо хранит массивы объектов и довольно удобно сортируется.Производительность в общем случае отличная.Если анализ производительности показывает, что это не так, вы можете относительно легко это оптимизировать.

Заметьте также, что я последовательно использовал sizeof() -- один и тот же тип в обоих местах.Так же const в исходном коде нет необходимости.

Answer 2

Я думаю, одна ошибка лежит прямо в строке

qsort(array[0], numThingies, sizeof(array[0]), thingieCmp);

Пытаться

qsort(&array[0], numThingies, sizeof(array[0]), thingieCmp);

или даже

qsort(array, numThingies, sizeof(array[0]), thingieCmp);

вместо.Компилятор здесь не будет жаловаться, т.к. qsort должен занять void* и ты передашь это Thingy* который по закону может быть приведен к void* без предупреждения, но ты очень хочешь qsort для работы со всем массивом, имеющим тип Thingy**.

Другое дело:компаратор будет вызываться с указателями на слоты массива в качестве аргументов, так что на самом деле вы получите Thingy**:

int 
thingieCmp(void* a, void* b) 
{
    Thingie *ia = *((Thingie**)a);
    Thingie *ib = *((Thingie**)b);

    ...
}