Comparatoren verketten

Will man Vergleichsfunktionen verketten, lassen sich grundsätzlich zwei Ansätze unterscheiden.

Der erste Ansatz bündelt sämtliche Ordnungskriterien in einer Vergleichsfunktion. Die Kriterien werden dabei sequenziell ausgewertet: Zuerst erfolgt der Vergleich nach Kriterium A. Nur wenn dort Gleichheit vorliegt, wird Kriterium B herangezogen usw. Ein klassisches Beispiel ist die Sortierung nach Name, und bei gleichem Namen zusätzlich nach Alter. Die Logik ist kompakt, aber wenig modular — bei mehreren Sortierschlüsseln oder wiederverwendbaren Kombinationen wächst der Code schnell an.

int cmp_person(const void *pa, const void *pb) {
    const Person *a = pa;
    const Person *b = pb;

    int r = strcmp(a->name, b->name);
    if (r != 0)
        return r;

    if (a->age < b->age) return -1;
    if (a->age > b->age) return 1;
    return 0;
}

Der zweite Ansatz trennt die Kriterien in eigenständige Vergleichsfunktionen. Für jedes Feld existiert eine spezialisierte Compare-Routine. Diese werden anschließend verkettet. Das erhöht die Wiederverwendbarkeit und hält einzelne Funktionen klein und isoliert testbar.

Zunächst entstehen Feldvergleiche:

#define CMP3(a,b) ((a) < (b) ? -1 : ((a) > (b) ? 1 : 0))

int cmp_name(const void *pa, const void *pb) {
    const Person *a = pa;
    const Person *b = pb;
    return strcmp(a->name, b->name);
}

int cmp_age(const void *pa, const void *pb) {
    const Person *a = pa;
    const Person *b = pb;
    return CMP3(a->age, b->age);
}

Darauf aufbauend erfolgt die Verkettung. Die zweite Funktion wird nur aufgerufen, wenn die erste Gleichheit liefert.

#define DEFINE_CHAINED_CMP(name, first_cmp, second_cmp) \
    static int name(const void *a, const void *b) {     \
        int r = first_cmp(a, b);                        \
        return r != 0 ? r : second_cmp(a, b);           \
    }

DEFINE_CHAINED_CMP(cmp_name_age, cmp_name, cmp_age)

Diese verkettete Funktion kann direkt an qsort() übergeben werden:

• qsort(arr, n, sizeof *arr, cmp_name_age);

Beide Ansätze erfüllen funktional denselben Zweck, unterscheiden sich jedoch in der Strukturierung:

In kleinen, einmaligen Sortierfällen reicht meist der erste Ansatz. Sobald Vergleichskriterien kombiniert oder variiert werden sollen, ist die funktionale Verkettung strukturierter und wartbarer.