CKTIS / C
Функции за обратно извикване в C: компаратор за `qsort`
Подайте компаратор чрез указател към функция с подходящ тип, сравнявайте целия диапазон на `int` без препълване и запазете реда на записите с еднакви ключове.
Версия: ISO C23; implementation support may vary
Синтаксис
#include <stdlib.h>
typedef int (*compare_fn)(const void *, const void *);
int compare_items(const void *left, const void *right);
/* For a writable array named items, inside a function: */
compare_fn callback = compare_items;
qsort(items, sizeof items / sizeof items[0], sizeof items[0], callback);Функция за обратно извикване (callback) е функция, която подавате на друг код, за да я извика той. qsort от <stdlib.h> сортира изменяем масив на място и не връща стойност. Приема начален адрес, брой елементи, размер на един елемент в байтове и указател към функция от тип int (*)(const void *, const void *). Подайте compare_items, а не compare_items(...): името на функцията тук се преобразува в указател, докато вторият израз я извиква. Не преобразувайте принудително несъвместим указател към функция; извикването през несъвместим тип указател има неопределено поведение.
Аргументите const void * сочат към сравняваните елементи. Преди да прочетете полетата, ги присвоете на указатели към действителния тип на елементите с квалификатор const. Не променяйте масива в компаратора и не определяйте резултата според текущите позиции: библиотеката може да мести елементите между извикванията. Определете последователна наредба: върнете отрицателна стойност, нула или положителна стойност, ако първият елемент е съответно по-малък, равностоен или по-голям от втория. Има значение само знакът.
INT_MIN и INT_MAX от <limits.h> са границите на int. Не връщайте a->key - b->key: например INT_MAX - INT_MIN не може да се представи като int, а препълването на цяло число със знак има неопределено поведение. Използвайте оператори за сравнение. В -1 унарният минус обръща знака на 1; обръщането на знака на самото INT_MIN също има неопределено поведение в C23.
Стабилното сортиране запазва входния ред на елементите, които при сравнение са равностойни. qsort не гарантира това. При равни ключове използвайте запазената първоначална позиция като втори критерий или изберете стабилно сортиране, ако компараторът трябва да продължи да приема тези елементи за равностойни.
В масив с краен маркер NULL отбелязва края на указателите към токени и не е символът \0. Не включвайте маркера в броя на елементите за сортиране. При търсене проверявайте границата на масива преди четене и не допускайте брояч от тип int да надхвърля INT_MAX, включително при увеличаване. Резултатът -1 от търсенето означава „не е намерено“, а не отрицателен резултат от сравнение.
Примери
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct item {
int key;
int original;
const char *token;
};
typedef int (*compare_fn)(const void *, const void *);
static int compare_items(const void *left, const void *right)
{
const struct item *a = left;
const struct item *b = right;
if (a->key < b->key) return -1;
if (a->key > b->key) return 1;
return (a->original > b->original) - (a->original < b->original);
}
static int find_token(const struct item *items, int capacity, const char *token)
{
for (int i = 0; i < capacity && items[i].token != NULL; ++i) {
if (strcmp(items[i].token, token) == 0) return i;
}
return -1;
}
int main(void)
{
struct item items[] = {
{INT_MAX, 0, "high"},
{0, 1, "first"},
{INT_MIN, 2, "low"},
{0, 3, "second"},
{0, 0, NULL}
};
enum { CAPACITY = sizeof items / sizeof items[0] };
compare_fn callback = compare_items;
qsort(items, CAPACITY - 1, sizeof items[0], callback);
for (int i = 0; i < CAPACITY - 1; ++i) {
puts(items[i].token);
}
printf("missing index: %d\n", find_token(items, CAPACITY, "missing"));
return 0;
}
Резултат
low first second high missing index: -1
`first` и `second` имат еднакъв ключ. Редът им се определя от `original`, а не от стабилността на `qsort`. Търсенето спира при `NULL` и връща `-1`.
Свързани уроци
- C · Урок 88 · Напреднало · Версия: 3
- C · Урок 90 · Напреднало · Версия: 3