Indexation des données : id → objet, tag → liste

1. Index des données

Imaginez que vous stockez des tâches dans std::vector<Task> et qu'à chaque fois qu'il faut trouver une tâche par id, vous parcourez honnêtement tout le vecteur avec une boucle. Ça fonctionne… tant que le nombre de tâches et de requêtes reste faible. Un index est une structure de données qui accélère une requête typique : « trouve-moi l'objet par clé ». En développement réel, ce sont les index qui rendent les applications rapides, mais ils apportent aussi un nouveau souci : il faut les maintenir cohérents.

Prenons une analogie simple et concrète. Une bibliothèque a des livres sur des étagères (ce sont les « objets réels »), et elle a aussi un catalogue par auteur et un catalogue par titre (ce sont des « index »). Si le bibliothécaire ajoute un livre sur l'étagère mais oublie de l'enregistrer dans le catalogue, le lecteur pensera que le livre n'existe pas. À l'inverse, si l'entrée existe dans le catalogue mais pas sur l'étagère, le lecteur cherchera un « fantôme ». Voilà à quoi ressemble la désynchronisation des index.

Mini-modèle de données : Task et « source unique de vérité »

Pour être concrets, définissons un petit modèle de données. Supposons que nous avons une mini-application TaskBook : nous stockons des tâches, chacune ayant un id numérique, un title textuel et un ensemble de tags (par exemple, "cpp", "study", "home"). Pas d'architecture compliquée : pas de classes magiques, seulement struct et des conteneurs STL, comme nous savons le faire.

Il est important de se mettre d'accord dès le départ sur un principe : la source unique de vérité. Cela signifie que l'objet réel Task est stocké en un seul endroit, et que l'index ne contient que des références (par exemple, des id). Ainsi, lorsque la tâche change, on ne synchronise pas « deux copies de l'objet », on met seulement à jour les index qui y réfèrent.

Commençons par le modèle :

#include <string>
#include <vector>

struct Task {
    int id{};
    std::string title;
    std::vector<std::string> tags;
};

Ici tags est un vector, car c'est pratique pour l'affichage et l'itération. L'unicité des tags sera assurée séparément (plus loin), pour éviter d'avoir "cpp", "cpp", "cpp" — oui, ça arrive, surtout si l'utilisateur saisit les tags manuellement.

2. Index : primaire et secondaire

Index primaire id → Task : accès rapide à l'objet

L'index primaire est l'endroit où résident les objets « réels ». La solution la plus simple : std::unordered_map<int, Task> tasksById; Ainsi, par id on obtient la tâche rapidement sans recherche linéaire. On ne discute pas les complexités idéales ni le fonctionnement interne de la table de hachage ; l'important est que l'opération passe de « parcourir tout » à « trouver par clé ».

Définissons des alias de types (le code est plus lisible ainsi) :

#include <unordered_map>

using TaskId = int;
using TaskById = std::unordered_map<TaskId, Task>;

Voici le pattern de lecture de base : find → vérifier → utiliser. Notez : c'est une lecture sans effets de bord (on ne crée rien accidentellement).

#include <iostream>
#include <unordered_map>

int main() {
    TaskById tasks;
    tasks.emplace(1, Task{1, "Learn C++", {"cpp", "study"}});

    if (auto it = tasks.find(1); it != tasks.end()) {
        std::cout << it->second.title << '\n'; // Learn C++
    }
}

Petite remarque pratique : si vous voulez lire, utilisez find/contains. Utilisez operator[] lorsque vous voulez explicitement « créer ou mettre à jour ».

Index secondaire tag → liste de id : recherche rapide par catégorie

Maintenant ajoutons le second type de requêtes : « montre toutes les tâches avec le tag cpp ». Si nous n'avons que tasksById, il faudra parcourir toutes les tâches et vérifier si le tag est présent dans Task::tags. C'est encore un parcours linéaire et ce sera lent sur de grands ensembles.

Nous introduisons donc un index secondaire : tag → liste de id. Pourquoi pas tag → liste de Task ? Parce que nous avons convenu d'une source unique de vérité : le Task vit dans tasksById, et l'index ne conserve que des références à lui via les id.

Le choix du conteneur pour la « liste d'id » dépend des exigences. Pour l'exemple pédagogique, std::unordered_set<int> est pratique : il supprime automatiquement les doublons et la vérification de présence d'un id est rapide. Si l'ordre ou les doublons étaient importants, on pourrait utiliser std::vector<int>, mais il faudrait gérer les doublons manuellement. Pour commencer, choisissons l'option « robuste ».

#include <string>
#include <unordered_map>
#include <unordered_set>

using Tag = std::string;
using IdSet = std::unordered_set<TaskId>;
using TagIndex = std::unordered_map<Tag, IdSet>;

Les structures de données de notre application deviennent donc (conceptuellement) :

flowchart LR
    subgraph Primary["Index primaire (source de vérité)"]
        A["tasksById: id → Task"]
    end

    subgraph Secondary["Index secondaire (références)"]
        B["tagToIds: tag → {id, id, id}"]
    end

    B -->|"id"| A

Il est utile de garder en tête : dans l'index secondaire nous ne stockons pas la tâche, nous stockons un « pointeur » vers elle via le id. C'est comme une « fiche de catalogue », pas le livre.

4. Opérations sans désynchronisation

Quand on ajoute un second index, toute opération « créer un objet » devient « créer l'objet + mettre à jour les index ». C'est là que commencent les erreurs typiques : l'étudiant ajoute la tâche dans tasksById mais oublie d'ajouter son id dans tagToIds, puis s'étonne que la recherche par tag « ne trouve rien ».

Pour éviter ces erreurs disséminées dans le code, nous appliquons une règle simple : toutes les modifications passent par une seule fonction. Appelons-la AddTask(...). Oui, ça paraît ennuyeux. Mais le code ennuyeux fonctionne, le code « fun » amuse surtout le compilateur.

D'abord, préparons une petite fonction qui supprime les doublons de tags. Nous utiliserons un unordered_set « temporaire », puis nous reviendrons à un vector. Le code est court, mais le principe est important : les tags à l'intérieur de Task seront propres.

#include <string>
#include <unordered_set>
#include <vector>

std::vector<std::string> MakeUniqueTags(const std::vector<std::string>& tags) {
    std::unordered_set<std::string> uniq(tags.begin(), tags.end());
    return std::vector<std::string>(uniq.begin(), uniq.end());
}

Ajout cohérent : mettre à jour les deux index

Remarquez : on tente d'abord d'insérer dans tasksById. Si l'id est déjà pris, on sort sans rien changer. Si l'insertion réussit, on met à jour tagToIds. Ici operator[] est utilisé volontairement : si le tag n'existe pas encore, on veut créer un ensemble vide pour lui.

#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>

bool AddTask(TaskById& tasksById, TagIndex& tagToIds, Task task) {
    task.tags = MakeUniqueTags(task.tags);

    auto [it, inserted] = tasksById.emplace(task.id, task);
    if (!inserted) return false;

    for (const std::string& tag : it->second.tags) {
        tagToIds[tag].insert(it->first);
    }
    return true;
}

Effet pratique : le code appelant n'a pas à se souvenir des « deux index ». Il appelle simplement AddTask, et la fonction fait tout le travail ennuyeux. C'est un petit pas vers une bonne architecture, sans grands discours.

Suppression cohérente : éviter les « fantômes »

La suppression est encore plus dangereuse que l'ajout. L'erreur classique : on supprime la tâche de tasksById mais on oublie d'enlever son id de tagToIds. Ensuite, une recherche par tag retourne un id qui n'existe plus dans l'index primaire. C'est le « fantôme » : l'index dit que la tâche existe, la réalité dit non.

La suppression doit se faire en deux étapes : enlever d'abord les références dans les index secondaires, puis supprimer l'objet lui-même. L'ordre est important : d'abord nettoyer les catalogues, ensuite retirer le livre de l'étagère. Là encore, on encapsule cela dans une seule fonction pour éviter la duplication logique.

#include <string>
#include <unordered_map>
#include <unordered_set>

bool RemoveTask(TaskById& tasksById, TagIndex& tagToIds, TaskId id) {
    auto it = tasksById.find(id);
    if (it == tasksById.end()) return false;

    for (const std::string& tag : it->second.tags) {
        if (auto jt = tagToIds.find(tag); jt != tagToIds.end()) {
            jt->second.erase(id);
            if (jt->second.empty()) tagToIds.erase(jt);
        }
    }
    tasksById.erase(it);
    return true;
}

Petite esthétique : si après la suppression l'ensemble pour un tag devient vide, on efface aussi la clé du tag dans l'index. Ce n'est pas obligatoire, mais ça garde la structure propre : pas de « tags sans tâches ».

Modification des données : comment changer les tags et le titre en sécurité

Les modifications sont la zone où les index aiment particulièrement se désynchroniser. Le titre (title) peut être modifié sans problème : il ne participe pas à notre index (pour l'instant). Les tags, par contre, sont le cœur de l'index secondaire. Si vous changez Task::tags sans mettre à jour tagToIds, l'index secondaire devient immédiatement incorrect.

Le modèle correct pour mettre à jour les tags est le suivant : enlever l'id des tags anciens, ajouter l'id aux nouveaux tags, puis écrire les nouveaux tags dans le Task. C'est essentiellement un « déménagement » d'un ensemble à un autre. Là encore, on crée une fonction dédiée pour éviter d'éparpiller cette logique dans l'application.

#include <string>
#include <vector>

bool UpdateTaskTags(TaskById& tasksById, TagIndex& tagToIds,
                    TaskId id, std::vector<std::string> newTags) {
    auto it = tasksById.find(id);
    if (it == tasksById.end()) return false;

    for (const std::string& tag : it->second.tags) {
        if (auto jt = tagToIds.find(tag); jt != tagToIds.end()) {
            jt->second.erase(id);
            if (jt->second.empty()) tagToIds.erase(jt);
        }
    }

    newTags = MakeUniqueTags(newTags);
    it->second.tags = newTags;

    for (const std::string& tag : it->second.tags) {
        tagToIds[tag].insert(id);
    }
    return true;
}

Si vous pensez maintenant : « Wow, tout ce code juste pour des tags… », c'est normal. Les index apportent la vitesse, mais demandent un « coût » en mises à jour soignées. Dans les grands systèmes ce coût est géré par l'architecture et la discipline, ici par des fonctions soignées.

5. Requêtes et validation

Les index existent pour les requêtes, pas pour la beauté. Faisons donc deux petites fonctions d'affichage : l'une affiche une tâche par id, l'autre affiche toutes les tâches pour un tag. Pas de rendu fancy : l'objectif est d'illustrer l'usage des index.

Requêtes : « afficher par id » et « afficher par tag »

Afficher une tâche :

#include <iostream>

void PrintTask(const Task& t) {
    std::cout << "#" << t.id << " " << t.title << " [";
    for (std::size_t i = 0; i < t.tags.size(); ++i) {
        std::cout << t.tags[i] << (i + 1 == t.tags.size() ? "" : ", ");
    }
    std::cout << "]\n";
}

La requête « afficher par id » est simplement un find dans l'index primaire :

#include <iostream>

void PrintById(const TaskById& tasksById, TaskId id) {
    if (auto it = tasksById.find(id); it != tasksById.end()) {
        PrintTask(it->second);
    } else {
        std::cout << "no such task\n"; // no such task
    }
}

La requête « afficher par tag » utilise l'index secondaire. Remarquez : l'index secondaire nous donne un ensemble d'id, puis pour chaque id nous interrogeons tasksById pour obtenir l'objet. C'est la mise en œuvre de la source unique de vérité.

#include <iostream>
#include <string>

void PrintByTag(const TaskById& tasksById, const TagIndex& tagToIds,
                const std::string& tag) {
    auto it = tagToIds.find(tag);
    if (it == tagToIds.end()) {
        std::cout << "no such tag\n"; // no such tag
        return;
    }

    for (TaskId id : it->second) {
        if (auto jt = tasksById.find(id); jt != tasksById.end()) {
            PrintTask(jt->second);
        }
    }
}

Notez cette paranoïa utile : même si l'index devrait être cohérent, nous vérifions quand même tasksById.find(id). Dans un monde parfait la vérification n'est pas nécessaire, mais en code pédagogique elle aide à survivre à une désynchronisation et à détecter le problème plutôt qu'à s'effondrer de façon incompréhensible.

Vérification de cohérence : invariants et validation simple

Quand on a plusieurs index, il est utile de formuler des règles « en fer » qui doivent toujours être vraies. En programmation ces règles s'appellent souvent des invariants. Sans maths formelles, en langage courant :

Si dans tagToIds["cpp"] figure 42, alors dans tasksById il doit exister une tâche avec l'id 42. Et inversement : si la tâche 42 contient le tag "cpp", alors tagToIds["cpp"] doit contenir 42.

Dans les projets pédagogiques, une simple fonction de validation qu'on peut appeler après une série d'opérations aide beaucoup. Oui, c'est un parcours supplémentaire des données, mais c'est comme une lampe torche : elle n'accélère pas la marche, mais empêche d'heurter un poteau.

Faisons une vérification simple « de secondaire vers primaire » (en pratique cela détecte la plupart des erreurs) :

#include <iostream>
#include <string>

bool ValidateTagIndex(const TaskById& tasksById, const TagIndex& tagToIds) {
    for (const auto& [tag, ids] : tagToIds) {
        for (TaskId id : ids) {
            if (!tasksById.contains(id)) {
                std::cout << "Broken index: tag '" << tag
                          << "' refers to missing id=" << id << '\n';
                return false;
            }
        }
    }
    return true;
}

Si on veut, on peut ajouter la vérification inverse (de primaire vers secondaire), mais même une seule vérification discipline déjà : on commence à considérer les index comme quelque chose à maintenir activement, pas comme une « optimisation magique ».

6. Erreurs typiques avec plusieurs index

Ici, la plupart des erreurs sont architecturales plutôt que syntaxiques : le code compile, parfois il fonctionne, mais les données finissent par devenir un mystère. Il est donc utile d'identifier les erreurs par leurs symptômes et habitudes, pas seulement par les messages du compilateur.

Erreur n°1 : deux sources de vérité (duplication des objets dans les index).
On a souvent envie de faire tag → vector<Task> « pour faciliter l'affichage ». Les premiers instants c'est pratique. Puis vous modifiez le title dans tasksById, oubliez la copie ailleurs — et vous vous retrouvez avec deux réalités divergentes. Il est beaucoup plus sûr de stocker l'objet en un seul point et de garder seulement les id dans les index.

Erreur n°2 : mettre à jour un index et oublier l'autre.
Classique : on ajoute la tâche dans tasksById mais on n'ajoute pas son id dans tagToIds; ou on supprime de tasksById sans nettoyer tagToIds. Symptômes : « trouvé par id mais pas par tag » ou « le tag renvoie un id sans tâche ». La solution : discipline et fonctions centralisées comme AddTask/RemoveTask/UpdateTaskTags.

Erreur n°3 : lire via operator[] et créer accidentellement des entrées vides.
Par exemple, accéder à tagToIds[tag] en lecture créera un nouveau tag avec un ensemble vide, et vous vous demanderez d'où viennent ces tags vides. En lecture, préférez find/contains. Réservez operator[] aux cas où la création à l'absence est souhaitée (comme dans AddTask).

Erreur n°4 : ne pas nettoyer les clés « vides » dans l'index secondaire.
Si après avoir retiré l'id l'ensemble devient vide et que vous laissez la clé, la logique ne casse pas forcément, mais la structure se « salit »: des tags sans tâches apparaissent. C'est gênant si les tags sont affichés à l'utilisateur. Supprimer les clés vides rend le comportement plus propre et prévisible.

Erreur n°5 : des doublons dans les tags à l'intérieur de Task, et l'index se comporte « bizarrement ».
Si une tâche a les tags {"cpp", "cpp"}, vous faites du travail en trop lors de la mise à jour des index, et l'affichage montre des doublons, ce qui crée de la confusion. Normaliser les tags (au moins supprimer les doublons) est une petite opération qui améliore fortement la qualité des données et réduit les bugs « magiques ».