Introduction aux conteneurs associatifs map

Le conteneur std::map est une structure de données associative qui stocke des éléments formés par la combinaison d'une clé (key) et d'une valeur mappée (mapped value). Les clés sont uniques et servent à identifier et trier les données. En interne, std::map est généralement implémenté sous forme d'un arbre binaire de recherche équilibré (souvent un arbre rouge-noir), garantissant une complexité logarithmique $O(\log N)$ pour les opérations d'insertion, de suppression et de recherche.

template < class Key, 
           class T, 
           class Compare = less<Key>, 
           class Alloc = allocator<pair<const Key,T> > 
         > class map;

La structure de stockage : std::pair

Chaque nœud de l'arbre stocke un objet de type std::pair<const Key, T>. La clé est constante car sa modification directe corromprait l'ordre de l'arbre de recherche.

// Structure simplifiée d'un pair
template <class T1, class T2>
struct MyPair {
    T1 first;
    T2 second;

    MyPair(const T1& a, const T2& b) : first(a), second(b) {}
};

// Utilisation de la fonction utilitaire make_pair
auto p = std::make_pair("ID_01", 100);

Manipulation et Itération

Le parcours d'une map s'effectue via des itérateurs bidirectionnels. Le parcours "in-order" (infixe) de l'arbre permet d'obtenir les éléments triés selon leurs clés.

#include <iostream>
#include <map>
#include <string>

void exemple_parcours() {
    std::map<std::string, int> inventaire = {{"Pomme", 5}, {"Banane", 2}, {"Orange", 8}};

    // Utilisation de l'itérateur classique
    for (auto it = inventaire.begin(); it != inventaire.end(); ++it) {
        std::cout << it->first << " : " << it->second << std::endl;
    }

    // Syntaxe C++17 (Structured Bindings)
    for (const auto& [produit, quantite] : inventaire) {
        std::cout << produit << " -> " << quantite << std::endl;
    }
}

Fonctionnement avancé de l'opérateur []

L'opérateur de crochet operator[] est unique : il permet à la fois l'insertion, la recherche et la modification. S'il ne trouve pas la clé, il insère automatiquement un nouvel élément avec une valeur par défaut. Pour une recherche pure sans modification collatérale, il est préférable d'utiliser find() ou at().

void test_crochets() {
    std::map<int, std::string> base_donnees;

    // 1. Insertion via []
    base_donnees[10] = "Utilisateur A";

    // 2. Modification
    base_donnees[10] = "Utilisateur A Modifié";

    // 3. Attention : l'accès à une clé inexistante crée l'entrée
    std::cout << "Valeur pour 99 : " << base_donnees[99] << std::endl; // Crée une chaîne vide
}

Comparaison : map vs multimap

La principale différence réside dans la gestion des doublons. std::multimap autorise pluiseurs entrées avec la même clé.

• Recherche : find() renvoie le premier élément correspondant trouvé.
• Opérateur [] : Non disponible dans multimap car une clé peut pointer vers plusieurs valeurs.
• Plages : On utilise souvent equal_range() pour récupérer tous les éléments liés à une clé spécifique.

Cas pratique 1 : Clonage d'une liste chaînée avec pointeurs aléatoires

L'utilisation d'une map permet de créer une correspondance entre les anciens nœuds et les nouveaux nœuds pour reconstruire les liens complexes.

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;

    std::map<Node*, Node*> correspondance;
    Node* actuel = head;

    // Première passe : créer les nouveaux nœuds
    while (actuel) {
        correspondance[actuel] = new Node(actuel->val);
        actuel = actuel->next;
    }

    // Deuxième passe : lier les pointeurs next et random
    actuel = head;
    while (actuel) {
        correspondance[actuel]->next = correspondance[actuel->next];
        correspondance[actuel]->random = correspondance[actuel->random];
        actuel = actuel->next;
    }

    return correspondance[head];
}

Cas pratique 2 : Top K des mots les plus fréquents

Ce problème nécessite de compter les occurrences puis de trier les résultats selon deux critères : la fréquence (décroissante) et l'ordre alphabétique (croissant) en cas d'égalité.

#include <vector>
#include <algorithm>
#include <queue>

struct ComparateurFrequence {
    bool operator()(const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) const {
        if (a.second != b.second) {
            return a.second > b.second; // Fréquence plus élevée en priorité
        }
        return a.first < b.first; // Ordre lexicographique si égalité
    }
};

std::vector<std::string> topKFrequent(std::vector<std::string>& words, int k) {
    std::map<std::string, int> compteurs;
    for (const auto& w : words) {
        compteurs[w]++;
    }

    std::vector<std::pair<std::string, int>> trie(compteurs.begin(), compteurs.end());
    
    // Utilisation de stable_sort pour préserver l'ordre alphabétique de la map
    std::stable_sort(trie.begin(), trie.end(), [](const auto& a, const auto& b) {
        return a.second > b.second;
    });

    std::vector<std::string> resultats;
    for (int i = 0; i < k; ++i) {
        resultats.push_back(trie[i].first);
    }
    return resultats;
}

Gestion des bornes : lower_bound et upper_bound

Ces fonctoins permettent de rechercher des plages de clés de manière efficace :

• lower_bound(k) : retourne un itérateur vers le premier élément $\ge k$.
• upper_bound(k) : retourne un itérateur vers le premier élément $> k$.

Cela est particulièrement utile pour extraire des sous-ensembles de données dans un intervalle spécifique sans parcourir tout le conteneur.