Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C

Funkcja zwrotna w C: komparator dla `qsort`

Przekaż komparator przez typowany wskaźnik na funkcję, porównuj pełny zakres `int` bez przepełnienia i zachowaj kolejność rekordów o równych kluczach.

Wersja: ISO C23; implementation support may vary

Składnia

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

Funkcja zwrotna (callback) to funkcja przekazana innemu kodowi, aby ten ją wywołał. qsort z <stdlib.h> sortuje zapisywalną tablicę w miejscu i nie zwraca wartości. Otrzymuje adres początku tablicy, liczbę elementów, rozmiar jednego elementu w bajtach oraz wskaźnik na funkcję typu int (*)(const void *, const void *). Przekaż compare_items, nie compare_items(...): nazwa funkcji jest tu zamieniana na wskaźnik, a drugie wyrażenie wywołuje funkcję. Nie rzutuj niezgodnej funkcji, aby dopasować jej typ; wywołanie przez niezgodny typ wskaźnika ma niezdefiniowane zachowanie.

Argumenty const void * wskazują porównywane elementy. Przypisz je do wskaźników na właściwy typ elementu z kwalifikatorem const, zanim odczytasz pola. Nie zmieniaj tablicy w komparatorze ani nie uzależniaj wyniku od aktualnej pozycji elementu: biblioteka może go przenieść między wywołaniami. Ustal spójny porządek: zwracaj wartość ujemną, zero lub dodatnią, gdy pierwszy element jest odpowiednio mniejszy, równoważny lub większy. Liczy się znak, nie wartość bezwzględna wyniku.

INT_MIN i INT_MAX z <limits.h> to granice typu int. Nie zwracaj a->key - b->key: na przykład INT_MAX - INT_MIN nie mieści się w int, a przepełnienie ze znakiem ma niezdefiniowane zachowanie. Użyj porównań relacyjnych. W -1 minus jednoargumentowy neguje 1; negowanie samego INT_MIN w C23 również ma niezdefiniowane zachowanie.

Stabilne sortowanie zachowuje kolejność wejściową elementów uznanych za równoważne. qsort tego nie gwarantuje. Rozstrzygaj remisy według zapisanej pierwotnej pozycji albo użyj stabilnego sortowania, jeśli komparator ma nadal uznawać te elementy za równoważne.

W tablicy zakończonej wartownikiem NULL oznacza koniec wskaźników na tokeny, a nie znak \0; nie wliczaj wartownika do elementów przekazywanych do sortowania. Podczas wyszukiwania sprawdzaj granicę tablicy przed odczytem i pilnuj, by licznik typu int nie przekroczył INT_MAX, także przy zwiększaniu. Wynik -1 oznacza tu brak tokenu, a nie ujemny wynik porównania.

Przykłady

#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;
}

Wynik

low
first
second
high
missing index: -1

Rekordy `first` i `second` mają ten sam klucz. Ich kolejność wynika z pola `original`, a nie ze stabilności `qsort`. Wyszukiwanie zatrzymuje się na `NULL` i zwraca `-1`.

Powiązane lekcje

  • C · Lekcja 88 · Zaawansowany · Wersja: 3
  • C · Lekcja 90 · Zaawansowany · Wersja: 3

Źródła