C Orienté Objet | 3 - clavier ouvert

🟨2026.04.13
C Orienté Objet | 3

Avec une Person et une PersonsTable, nous avons les prémisses d’un programme “orienté objet”. Peut-on aller un peu plus loin? Pour ça, je pense qu’il est temps de penser à une petite application qui nous permettra de tester les limites de ce qu’on peut faire sans devoir se casser déraisonnablement la tête.

Idée: un annuaire

J’imagine un menu:

=== Choose option ===

[1] Add new contact
[2] Remove contact
[3] List all contacts
[4] List all groups
[5] List contacts in group
[0] Quit

On doit pouvoir lister, ajouter et supprimer des “contacts” pour des personnes, qui auraient un nom, un prénom, un email et un numéro de téléphone, et qu’on peut rassembler en groupes qui, eux-même, ont un nom unique. La combinaison nom-prénom-email-numéro de téléphone doit, elle aussi, être unique. Un contact peut être dans plusieurs groupes, ou dans aucun.

On devrait donc avoir une structure de type:

AddressBook
    - Groups
    - Contacts

Group
    - Contacts

Contact
    - firstName
    - lastName
    - email
    - phoneNumber
    - Groups

J’ai mis beaucoup de critères d’unicité dans cette description, ce qui signifie qu’on aurait bien besoin d’une notion d’ensemble. Ca tombe bien, je viens de voir les ensemble dans le cours de structures de données que je donne. Voyons-voir: est-ce qu’on peut se créer une “classe ensemble” générique, à partir de laquelle on va pouvoir faire des ensembles de groupes et des ensembles de contacts ?

Aucune idée, mais ça se tente. Essayons déjà de faire un ensemble d’une chose: des objets bidons.

Ensemble d’objets

Je définis, juste pour avoir quelque chose à mettre, un Object contenant une valeur sous forme d’int:

// set.h
typedef struct Object Object;

// set.c
struct Object {
    int value;
};

Et, puisqu’on est avec des objets, on a besoin de ses méthodes:

// set.c
Object* Object_make(int value){ 
    Object* o = malloc(sizeof(Object));
    o->value = value;
    return o;
}
void Object_destroy(Object* o){ free(o); }

Jusque là, rien de bien intéressant. Pour gérer des ensembles, je vais essayer d’implémenter une “table de hachage”. Pour chaque objet, on doit pouvoir calculer un “hash code”, et avoir une notion d’égalité:

int Object_hash(Object* o){ return o->value; }
int Object_equals(Object* o, Object* other){ return o->value == other->value; }

C’est ce qui va permettre d’avoir un accès aux objets en O(1) (si tout va bien) dans l’ensemble. Celui-ci devra avoir l’interface suivante:

// set.h
typedef struct SetObject SetObject;

SetObject* SetObject_make();
void SetObject_destroy(SetObject* s);
bool SetObject_add(SetObject* s, Object* p);
bool SetObject_remove(SetObject* s, Object* p);
bool SetObject_contains(SetObject* s, Object* p);
int SetObject_size(SetObject* s);

On retrouve tout ce qu’on avait dans les tables avant, mais maintenant on va l’implémenter avec une table de hachage et on va garantir l’unicité.

L’idée avec la table de hachage est qu’on garde un tableau dans lequel on met des listes chaînées contenant les éléments de l’ensemble. Soit un objet ayant le hash code N, si le tableau a une taille T, on ajoutera l’élément dans la liste liée située en table[N%T]. Imaginons 5 éléments avec les hash code 1, 3, 6, 4, 7 dans une table de taille 6. On aura:

table[0] -> [6]
table[1] -> [1] -> [7]
table[2] -> []
table[3] -> [3]
table[4] -> [4]
table[5] -> []

Pour faire une liste chaînée, on doit introduire une notion de “noeud”, qui contiennent un élément ainsi qu’un pointeur vers l’élément suivant. En complétant l’exemple précédent, on a:

table[0] -> N[6, [/]]
table[1] -> N[1, [-> N[7, [/]]]]
table[2] -> [/]
table[3] -> N[3, [/]]
table[4] -> N[4, [/]]
table[5] -> [/]

Ou [/] représente un pointeur NULL.

En C, on aura donc des noeuds:

typedef struct NodeObject NodeObject;
struct NodeObject {
    Object* obj;
    NodeObject* next;
};

Et une liste chaînée:

typedef struct {
    NodeObject* first;
    int size;
} LinkedListObject;

Qui nous amène à notre ensemble:

struct SetObject {
    LinkedListObject** table;
    int capacity;
    int size;
};

SetObject aura donc une liste de pointeurs vers des LinkedListObject, qui eux-même contiennent un pointeur vers leur premier NodeObject, qui contient un pointeur vers le suivant, etc.

Comment créer notre Set? On doit allouer de la mémoire pour le SetObject, fixer sa capacité initiale, allouer de la place pour les pointeurs vers des LinkedListObject et, pour chacun de ces LinkedListObject, on doit allouer de l’espace en mémoire et initialiser la taille à 0 et le pointeur de tête à NULL.

LinkedListObject* LinkedListObject_make(){
    LinkedListObject* ll = malloc(sizeof(LinkedListObject));
    ll->size = 0;
    ll->first = NULL;
    return ll;
}

SetObject* SetObject_make() {
    SetObject* set = malloc(sizeof(SetObject));
    set->capacity = 16;
    set->size = 0;
    set->table = malloc(sizeof(LinkedListObject*)*set->capacity);
    for (int i=0; i < set->capacity; i++){
        set->table[i] = LinkedListObject_make();
    }

    return set;
}

Il faut aussi prévoir de pouvoir créer des noeuds:

NodeObject* NodeObject_make(Object* o, NodeObject* next){
    NodeObject* node = malloc(sizeof(NodeObject));
    node->obj = o;
    node->next = next;
    return node;
}

Lorsqu’on détruit un SetObject, il faudra détruire les LinkedListObject, qui elles-même devront détruire les NodeObject.

void NodeObject_destroy(NodeObject* node){
    if (node->next != NULL)
        NodeObject_destroy(node->next);
    free(node);
}

void LinkedListObject_destroy(LinkedListObject* ll){
    if (ll->size > 0)
        NodeObject_destroy(ll->first);
    free(ll);
}

void SetObject_destroy(SetObject* set){
    for (int i=0; i < set->capacity; i++)
        LinkedListObject_destroy(set->table[i]);
    free(set);
}

Pour rajouter un objet, il faut:

Calculer son hash code
En déduire la position dans la table
Vérifier si la liste liée contient déjà l’élément
Sinon: le rajouter

On renvoie un booléen à la fin pour savoir si on a pu ajouter l’élément ou non.

bool LinkedListObject_add(LinkedListObject* ll, Object* o){
    if (ll->size == 0){
        // Empty list -> add to the front
        ll->first = NodeObject_make(o, NULL);
        ll->size++;
        return true;
    } else {
        // Go through the list. If we haven't found it at the end, 
        // we can connect it to the last non-null element we found.
        NodeObject* node = ll->first;
        NodeObject* prev = NULL;
        while (node != NULL){
            if (Object_equals(node->obj, o))
                return false;
            prev = node;
            node = node->next;
        }
        // if we're here, we are at the end of the list and we 
        // haven't found the object, so we can add it.
        prev->next = NodeObject_make(o, NULL);
        ll->size++;
        return true;
    }
}

bool SetObject_add(SetObject* set, Object* o){
    int h = Object_hash(o) % set->capacity;
    if (LinkedListObject_add(set->table[h], o)){
        set->size++;
        return true;
    }
    return false;
}

Le retrait se fait de manière très semblable. S’il n’y a rien, on n’a rien à retirer. Sinon, on cherche l’objet. Pour le retirer, on connecte le noeud précédent l’objet au noeud suivant l’objet. On peut aussi retirer le NodeObject de la mémoire. On n’appelle pas NodeObject_destroy car celui-ci est prévu pour aussi aller détruire tout ce qui suit de manière récursive, ce qu’on ne veut pas voir ici comme comportement. Si on n’a pas trouvé l’objet à la fin, c’est qu’on ne peut pas le retirer.

bool LinkedListObject_remove(LinkedListObject* ll, Object* o){
    if (ll->size == 0){
        return false;
    } else {
        NodeObject* node = ll->first;
        NodeObject* prev = NULL;
        while (node != NULL){
            if (Object_equals(node->obj, o)){
                if (prev == NULL)
                    ll->first = node->next;
                else
                    prev->next = node->next;
                free(node);
                ll->size--;
                return true;
            }
            prev = node;
            node = node->next;
        }
        return false;
    }
}

bool SetObject_remove(SetObject* set, Object* o){
    int h = Object_hash(o) % set->capacity;
    if (LinkedListObject_remove(set->table[h], o)){
        set->size--;
        return true;
    }
    return false;
}

Pour savoir si l’ensemble contient un objet, on reste dans la même logique:

bool LinkedListObject_contains(LinkedListObject* ll, Object* o){
    if (ll->size == 0){
        return false;
    } else {
        NodeObject* node = ll->first;
        while (node != NULL){
            if (Object_equals(node->obj, o)){
                return true;
            }
            node = node->next;
        }
        return false;
    }
}

bool SetObject_contains(SetObject* set, Object* o){
    int h = Object_hash(o) % set->capacity;
    return LinkedListObject_contains(set->table[h], o);
}

Et renvoyer la taille ne pose pas trop de difficultés:

int SetObject_size(SetObject* set){
    return set->size;
}

Conclusion

Nous avons maintenant une notion d’un “ensemble” pour un objet “bidon”, Object. A priori, adapter cet ensemble à n’importe lequel de nos objets (comme Person, ou le futur Group) devrait être raisonnablement simple. Il faut:

Modifier toutes les références à Object.
S’assurer que l’on dispose de méthodes _hash et _equals pour l’objet que l’on désire mettre dans un ensemble.

Et si on veut éviter les copier-coller foireux… on va devoir s’intéresser aux macros. Je n’en ai jamais fait: il va me falloir un peu de lecture d’abord.

[lien permanent]

Commentaires, remarques, erreurs qu'il faut absolument me faire remarquer? Contactez-moi sur Mastodon ou par mail (adrien@adfoucart.be)

🟨2026.04.13C Orienté Objet | 3

Idée: un annuaire

Ensemble d’objets

Conclusion

🟨2026.04.13
C Orienté Objet | 3