CKTIS / C
Zpětná volání v C: komparátor pro `qsort`
Předejte komparátor jako typovaný ukazatel na funkci, porovnávejte celý rozsah `int` bez přetečení a zachovejte vstupní pořadí záznamů se stejným klíčem.
Verze: ISO C23; implementation support may vary
Syntaxe
#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);Zpětné volání (callback) je funkce, kterou předáte jinému kódu, aby ji mohl zavolat. qsort z <stdlib.h> řadí zapisovatelné pole přímo na místě a nevrací hodnotu. Přijímá počáteční adresu, počet prvků, velikost jednoho prvku v bajtech a ukazatel na funkci typu int (*)(const void *, const void *). Předejte compare_items, ne compare_items(...): název funkce se zde převede na ukazatel, zatímco druhý výraz funkci volá. Nepřetypovávejte nekompatibilní ukazatel na funkci jen proto, aby odpovídal požadovanému typu. Volání přes nekompatibilní typ ukazatele má nedefinované chování.
Argumenty const void * ukazují na porovnávané prvky. Před čtením položek struktury je přiřaďte do ukazatelů na skutečný typ prvku s kvalifikátorem const. Komparátor nesmí měnit pole ani rozhodovat podle aktuálních pozic prvků: knihovna je může mezi voláními přesouvat. Definujte konzistentní uspořádání: vracejte zápornou hodnotu, nulu nebo kladnou hodnotu podle toho, zda je první prvek menší, rovnocenný nebo větší než druhý. Rozhoduje pouze znaménko.
INT_MIN a INT_MAX z <limits.h> jsou meze typu int. Nevracejte a->key - b->key: například INT_MAX - INT_MIN nelze vyjádřit typem int a přetečení celého čísla se znaménkem má nedefinované chování. Použijte relační porovnání. V zápisu -1 unární minus mění znaménko 1; změna znaménka samotného INT_MIN má v C23 rovněž nedefinované chování.
Stabilní řazení zachovává vstupní pořadí prvků, které se při porovnání jeví jako rovnocenné. qsort to nezaručuje. Při shodě klíčů použijte uloženou původní pozici nebo zvolte stabilní řazení, pokud má komparátor tyto prvky nadále považovat za rovnocenné.
V poli s koncovou značkou označuje NULL konec ukazatelů na tokeny; nejde o znak \0. Koncovou značku nezapočítávejte mezi řazené prvky. Při hledání nejdříve ověřte mez pole a zajistěte, aby čítač typu int nepřekročil INT_MAX ani při zvýšení. Výsledek hledání -1 znamená „nenalezeno“, nikoli záporný výsledek porovnání.
Příklady
#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;
}
Výsledek
low first second high missing index: -1
`first` a `second` mají stejný klíč. Jejich pořadí určuje `original`, nikoli stabilita `qsort`. Hledání se zastaví na `NULL` a vrátí `-1`.
Související lekce
- C · Lekce 88 · Pokročilá · Verze: 3
- C · Lekce 90 · Pokročilá · Verze: 3