CKTIS / C
Spätné volania v C: komparátor pre `qsort`
Odovzdajte komparátor ako typovaný ukazovateľ na funkciu, porovnávajte celý rozsah `int` bez pretečenia a zachovajte vstupné poradie záznamov s rovnakým kľúčom.
Verzia: ISO C23; implementation support may vary
Syntax
#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);Spätné volanie (callback) je funkcia, ktorú odovzdáte inému kódu, aby ju zavolal. qsort z <stdlib.h> triedi zapisovateľné pole priamo na mieste a nevracia hodnotu. Prijíma počiatočnú adresu, počet prvkov, veľkosť jedného prvku v bajtoch a ukazovateľ na funkciu typu int (*)(const void *, const void *). Odovzdajte compare_items, nie compare_items(...): názov funkcie sa tu konvertuje na ukazovateľ, kým druhý výraz funkciu volá. Neprispôsobujte nekompatibilný ukazovateľ na funkciu pretypovaním; volanie cez nekompatibilný typ ukazovateľa má nedefinované správanie.
Argumenty const void * ukazujú na porovnávané prvky. Pred čítaním členov ich priraďte do ukazovateľov na skutočný typ prvku s kvalifikátorom const. Komparátor nesmie meniť pole ani rozhodovať podľa aktuálnych pozícií: knižnica môže medzi volaniami prvky presúvať. Definujte konzistentné usporiadanie: vráťte zápornú hodnotu, nulu alebo kladnú hodnotu podľa toho, či je prvý prvok menší, rovnocenný alebo väčší než druhý. Rozhoduje iba znamienko.
INT_MIN a INT_MAX z <limits.h> sú hranice typu int. Nevracajte a->key - b->key: napríklad INT_MAX - INT_MIN sa do int nezmestí a pretečenie celého čísla so znamienkom má nedefinované správanie. Použite relačné porovnania. V zápise -1 unárne mínus mení znamienko 1; negácia samotného INT_MIN má v C23 tiež nedefinované správanie.
Stabilné triedenie zachováva vstupné poradie prvkov, ktoré sa pri porovnaní vyhodnotia ako rovnocenné. qsort to nezaručuje. Pri zhode kľúčov použite uloženú pôvodnú pozíciu alebo zvoľte stabilné triedenie, ak má komparátor tieto prvky naďalej považovať za rovnocenné.
V poli s koncovou značkou označuje NULL koniec ukazovateľov na tokeny; nejde o znak \0. Značku nezapočítajte medzi triedené prvky. Pri vyhľadávaní skontrolujte hranicu poľa ešte pred čítaním a zaistite, aby počítadlo typu int neprekročilo INT_MAX ani pri zvýšení. Výsledok vyhľadávania -1 znamená „nenájdené“, nie záporný výsledok porovnania.
Prí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ýsledok
low first second high missing index: -1
`first` a `second` majú rovnaký kľúč. Ich poradie určuje `original`, nie stabilita `qsort`. Vyhľadávanie sa zastaví na `NULL` a vráti `-1`.
Súvisiace lekcie
- C · Lekcia 88 · Pokročilá · Verzia: 3
- C · Lekcia 90 · Pokročilá · Verzia: 3