Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C

Fonctions de rappel en C : comparateur pour `qsort`

Passez un comparateur par un pointeur de fonction typé, comparez les valeurs `int` sans débordement et préservez l’ordre d’entrée des enregistrements de même clé.

Version : 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);

Une fonction de rappel (callback) est une fonction passée à un autre code pour que celui-ci l’appelle. qsort, déclaré dans <stdlib.h>, trie sur place un tableau modifiable et ne renvoie aucune valeur. Il reçoit l’adresse de début, le nombre d’éléments, la taille d’un élément en octets et un pointeur de fonction de type int (*)(const void *, const void *). Passez compare_items, pas compare_items(...) : le nom de la fonction est ici converti en pointeur, tandis que la seconde expression appelle la fonction. Ne forcez pas la conversion d’un pointeur de fonction incompatible : un appel via un type de pointeur incompatible a un comportement indéfini.

Les arguments const void * pointent vers les éléments à comparer. Avant de lire leurs champs, affectez-les à des pointeurs vers le type réel des éléments, qualifié par const. Ne modifiez pas le tableau dans le comparateur et ne vous fondez pas sur les positions actuelles : la bibliothèque peut déplacer les éléments entre deux appels. Définissez un ordre cohérent : renvoyez une valeur négative, nulle ou positive si le premier élément est respectivement inférieur, équivalent ou supérieur au second. Seul le signe compte.

INT_MIN et INT_MAX, définis dans <limits.h>, sont les bornes de int. Ne renvoyez pas a->key - b->key : par exemple, INT_MAX - INT_MIN n’est pas représentable par un int, et un débordement d’entier signé a un comportement indéfini. Utilisez plutôt des comparaisons relationnelles. Dans -1, le moins unaire inverse le signe de 1 ; l’appliquer à INT_MIN a aussi un comportement indéfini en C23.

Un tri stable préserve l’ordre d’entrée des éléments jugés équivalents. qsort ne le garantit pas. Départagez les clés égales à l’aide de la position d’origine enregistrée, ou utilisez un tri stable si le comparateur doit continuer à considérer ces éléments comme équivalents.

Dans un tableau terminé par une sentinelle, NULL marque la fin des pointeurs vers les jetons ; ce n’est pas le caractère \0. Excluez la sentinelle du nombre d’éléments à trier. À la recherche, vérifiez la borne du tableau avant toute lecture et veillez à ce qu’un compteur int ne dépasse jamais INT_MAX, même lors de son incrémentation. Le résultat de recherche -1 signifie « introuvable » et non « comparaison négative ».

Exemples

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

Résultat

low
first
second
high
missing index: -1

`first` et `second` ont la même clé. Leur ordre est déterminé par `original`, et non par la stabilité de `qsort`. La recherche s’arrête à `NULL` et renvoie `-1`.

Leçons associées

  • C · Leçon 88 · Avancé · Version : 3
  • C · Leçon 90 · Avancé · Version : 3

Sources