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

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

4 голосов
/ 02 апреля 2010

У меня есть массив указателей на объекты 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;
}

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

Ответы [ 2 ]

10 голосов
/ 02 апреля 2010

Проблема в два раза:

  • первый аргумент 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 в исходном коде не требуется.

1 голос
/ 02 апреля 2010

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

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);

    ...
}
...