qsort и bsearch массив указателей

Мне нужно отсортировать массив указателей на структуру. На самом деле мне нужно выполнить поиск среди адресов, чтобы увидеть, присутствует ли данный указатель на структуру в массиве. К сожалению, внутри этих структур у меня нет ничего "сопоставимого", поэтому я хочу отсортировать их только по адресу. Мой код такой:

item* arr[SIZE];
//something is inserted
qsort(arr, SIZE, sizeof(item*), (void*)compare_funct); 
//CUT
bsearch(curr, arr, SIZE, sizeof(item*), (void*)compare_funct);

Я попытался создать функцию compare_funct, просто указывая на int и возвращая их разницу, но, похоже, это не сработало. В частности, когда я выполняю bsearch, даже если я знаю, что элемент содержится внутри массива, я всегда получаю NULL в качестве возвращаемого значения.


c libc qsort bsearch
person Raffo    schedule 29.05.2011    source источник

Ответы (2)


arrow_upward
5
arrow_downward 

int cmp_items(void const *p, void const *q)
{
    item const *a = *(item const **)p, *b = *(item const **)q;
    return b - a;
}

(Пожалуйста, не преобразовывайте compare_funct в void*. Это ничего не делает, кроме как отключение проверки типов вызывает неопределенное поведение.)

EDIT: как указывает @R.., приведенное выше поведение демонстрирует неопределенное поведение, если только a и b не указывают на общий массив. Для полной переносимости (но за счет непосредственной понятности) вы должны использовать

int compare_pointers(void const *p, void const *q)
{
    return memcmp(p, q, sizeof(item *));
}
person Fred Foo    schedule 29.05.2011
comment
Это даже хуже, чем просто отключить проверку типов: это поведение undefined. Нельзя безопасно привести указатель на функцию к указателю на данные и наоборот. Представьте себе, что происходит на машине с гарвардской архитектурой (отдельные шины для данных и программы) или на старом компиляторе DOS с компактной (32-битные данные, 16-битный указатель на функцию) или средней моделью памяти (16-битные данные и 32-битный указатель на функцию). - person Patrick Schlüter; 29.05.2011
comment
Пока мы на этом, b-a также является неопределенным поведением, если только b и a не указывают на общий массив. Переносимая версия - memcmp(&a, &b, sizeof a); - сравнение представлений указателей побайтно, а не попытка их различия. - person R.. GitHub STOP HELPING ICE; 29.05.2011
comment
А можно упростить до memcmp(p, q, sizeof(item *)); - person R.. GitHub STOP HELPING ICE; 29.05.2011

arrow_upward
0
arrow_downward

Посмотрите здесь.

Этот описывает это довольно хорошо, думайте об этом как об указателях на структуру, а не указатели на char.

По сути, идея состоит в том, чтобы передать struct**, приведенную к (void*), затем вы возвращаете ее в разыменование struct**, чтобы получить struct*, а затем просто выполняете сравнение.

Получить правильное приведение с помощью qsort может быть сложно.

person Eduard Thamm    schedule 29.05.2011