Architecture des conteneurs associatifs

Contrairement aux structures séquentielles (std::vector, std::list) qui préservent l'ordre d'insertion linéaire, les conteneurs associatifs organisent les données via des associations clé, valeur. Cette disposition optimise drastiquement les phases de recherche et de tri en s'appuyant sur des structures arborescentes auto-équilibrées, typiquement des arbres rouge-noir, garantissant des performances en O(log n).

Le conteneur std::set

Ce composant gère une collection d'entités uniques et triées. L'interface expose uniquement des valeurs, mais l'implémentation interne les encapsule dans des paires (valeur, valeur) pour harmoniser le comportement avec les autres conteneurs associatifs.

• Tri automatique : Les éléments sont classés selon un comparateur (par défaut std::less).
• Immutabilité : Les itérateurs retournent des références constantes. Modifier un élément sur place briserait la propriété de l'arbre ; il faut supprimer puis réinsérer.
• Unicité : Les doublons sont automatiquement filtrés lors de l'insertion.

Exemples d'intégration

#include <iostream>
#include <set>
#include <functional>
#include <iterator>

void demonstrerSet() {
    // Initialisation depuis une plage
    int valeursBrutes[] = {45, 12, 12, 8, 89, 45};
    std::set<int> stockage(std::begin(valeursBrutes), std::end(valeursBrutes));
    // Résultat interne : {8, 12, 45, 89}

    // Parcours décroissant via itérateur inverse
    for (auto iter = stockage.rbegin(); iter != stockage.rend(); ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << "\n";

    // Analyse du résultat d'insertion
    auto verdictAjout = stockage.insert(20);
    if (verdictAjout.second) {
        std::cout << "Insertion réussie. Valeur : " << *verdictAjout.first << "\n";
    } else {
        std::cout << "Rejet : clé déjà présente.\n";
    }

    // Recherche et suppression
    stockage.erase(45);
    auto pointeur = stockage.find(8);
    std::cout << (pointeur != stockage.end() ? "Trouvé" : "Absence") << "\n";
    std::cout << "Occurrences de 89 : " << stockage.count(89) << "\n";
}

Le conteneur std::map

Le map dissocie explicitement l'identifiant (key) des données métier (mapped_type). Les clés restent uniques et ordonnées, permetant un accès direct. Chaque nœud interne correspond à un std::pair<const Key, T>.

• Opérateur [] : Si la clé est absente, l'opérateur construit l'entrée avec un objet par défaut et retourne une référence modifiable. Si la clé existe, il retourne une référence sur la valeur associée.
• Méthode at() : Comportement similaire à [], mais lève std::out_of_range au lieu d'insérer une nouvelle paire.

Manipulation avancée

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

template <typename C, typename D>
void imprimerRegistre(const std::map<C, D>& annuaire) {
    for (auto cur = annuaire.cbegin(); cur != annuaire.cend(); ++cur) {
        std::cout << "[" << cur->first << "] => " << cur->second << "\n";
    }
}

void utiliserMap() {
    std::map<int, std::string> catalogue;
    catalogue.emplace(101, "Capteur A");
    catalogue.emplace(205, "Relais B");

    // Lecture/Écriture via []
    catalogue[205] = "Relais B-Mise à jour";
    catalogue[999]; // Crée une entrée "999" avec chaîne vide

    try {
        std::cout << "Donnée 101 : " << catalogue.at(101) << "\n";
        catalogue.at(888); // Exception immédiate
    } catch (const std::out_of_range& err) {
        std::cerr << "Clé invalide : " << err.what() << "\n";
    }

    // Suppression ciblée
    catalogue.erase(999);
    
    // Vérification d'existence
    if (catalogue.find(205) != catalogue.end()) {
        std::cout << "Clé 205 présente dans le registre.\n";
    }
}

Gestion des multiplicités : std::multiset et std::multimap

Ces variantes assouplissent la contrainte d'unicité. Les arbres sous-jacents acceptent plusieurs nœuds partageant la même clé. L'ordre relatif des éléments équivalents n'est pas garanti par le standard.

Attension : std::multimap refuse l'opérateur [] car la notion de "retourner la valeur de la clé" devient ambiguë lorsque plusieurs associations coexistent. Il est nécessaire d'utiliser equal_range(), count() ou les itérateurs directs pour parcourir les groupes.

Scénarios de données répétitives

#include <set>
#include <map>
#include <iostream>
#include <vector>

void traiterMultiConteneurs() {
    // Collecte sans dédoublonnage
    std::vector<int> relevés = {10, 15, 10, 20, 10, 15};
    std::multiset<int> historique(relevés.begin(), relevés.end());
    
    std::cout << "Fréquence brute : ";
    for (const auto& v : historique) std::cout << v << " ";
    std::cout << "\n";

    // Associations multiples par identifiant
    std::multimap<int, int> connexions;
    connexions.insert({1, 100});
    connexions.insert({1, 200});
    connexions.insert({1, 150});
    connexions.insert({2, 300});

    // Extraction d'un groupe spécifique
    auto intervalle = connexions.equal_range(1);
    std::cout << "Sous-ensemble pour clé 1 : ";
    for (auto ptr = intervalle.first; ptr != intervalle.second; ++ptr) {
        std::cout << ptr->second << " ";
    }
    std::cout << "\n";
}