C++

Conteneurs associatifs : map, set, unordered_map

Découvrez les conteneurs associatifs ordonnés et non ordonnés — maps, sets et leurs variantes multi- et unordered. Comprenez quand choisir les arbres plutôt que les tables de hachage.

Conteneurs associatifs ordonnés vs non ordonnés

La STL fournit deux familles de conteneurs associatifs :

Ordonnés (implémentés sous forme d'arbres rouge-noir) :
- std::map — paires clé-valeur triées, clés uniques
- std::set — clés uniques triées
- std::multimap — paires clé-valeur triées, clés dupliquées autorisées
- std::multiset — clés triées, doublons autorisés

Non ordonnés (implémentés sous forme de tables de hachage) :
- std::unordered_map — clé-valeur basé sur le hachage, clés uniques
- std::unordered_set — clés uniques basées sur le hachage
- std::unordered_multimap — basé sur le hachage, clés dupliquées
- std::unordered_multiset — basé sur le hachage, doublons

Les conteneurs ordonnés maintiennent les éléments triés et fournissent une recherche, insertion et suppression en O(log n). Les conteneurs non ordonnés utilisent le hachage pour des opérations en O(1) en moyenne mais O(n) dans le pire cas si beaucoup de collisions surviennent.

Utilisation de map et set

std::map stocke des paires clé-valeur triées par clé. std::set stocke des valeurs uniques triées. Les deux sont implémentés sous forme d'arbres rouge-noir auto-équilibrés, garantissant des opérations en O(log n).

map_set.cpp
#include <map>
#include <set>
#include <string>
#include <iostream>

int main() {
    // std::map — sorted key-value pairs
    std::map<std::string, int> ages;
    ages["Alice"] = 30;              // insert or update
    ages["Bob"]   = 25;
    ages.insert({"Charlie", 35});    // insert only if key absent
    ages.emplace("Diana", 28);       // construct in-place

    // Lookup
    if (auto it = ages.find("Bob"); it != ages.end()) {
        std::cout << it->first << " is " << it->second << '\n';
    }

    // C++17 structured bindings — elegant map iteration
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << '\n';
    }
    // Output is sorted by key: Alice, Bob, Charlie, Diana

    // std::set — sorted unique values
    std::set<int> primes = {2, 3, 5, 7, 11, 13};
    primes.insert(5);                // no effect — 5 already present
    primes.insert(17);               // inserted

    if (primes.contains(7)) {        // C++20
        std::cout << "7 is prime\n";
    }

    // count() — returns 0 or 1 for set (useful pre-C++20)
    if (primes.count(4) == 0) {
        std::cout << "4 is not prime\n";
    }

    // lower_bound / upper_bound — range queries
    auto lo = primes.lower_bound(5);
    auto hi = primes.upper_bound(11);
    for (auto it = lo; it != hi; ++it) {
        std::cout << *it << ' ';     // 5 7 11
    }
    std::cout << '\n';
}

Conteneurs non ordonnés et fonctions de hachage personnalisées

Les conteneurs non ordonnés utilisent des tables de hachage pour une recherche en O(1) en moyenne. Pour les types de clés personnalisés, vous devez fournir une fonction de hachage et un opérateur d'égalité.

unordered_custom.cpp
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <iostream>

// Custom type as key
struct Point {
    int x, y;
    bool operator==(const Point&) const = default;  // C++20
};

// Custom hash function
struct PointHash {
    std::size_t operator()(const Point& p) const {
        // Combine hashes — a common pattern
        auto h1 = std::hash<int>{}(p.x);
        auto h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);  // simple combine (consider better hashes in production)
    }
};

int main() {
    // Basic unordered_map — O(1) average lookup
    std::unordered_map<std::string, double> prices;
    prices["apple"]  = 1.50;
    prices["banana"] = 0.75;
    prices["cherry"] = 3.00;

    // try_emplace (C++17) — only constructs value if key is absent
    prices.try_emplace("apple", 9.99);   // no-op, "apple" exists
    prices.try_emplace("date", 4.50);    // inserted

    // extract and insert (C++17 node API)
    auto node = prices.extract("banana");
    if (!node.empty()) {
        node.key() = "plantain";          // rename key without copy
        prices.insert(std::move(node));
    }

    for (const auto& [fruit, price] : prices) {
        std::cout << fruit << ": $" << price << '\n';
    }

    // Custom type as key
    std::unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2});   // duplicate — not inserted
    std::cout << "Unique points: " << points.size() << '\n';  // 2
}

Multimap et Multiset

std::multimap et std::multiset autorisent les clés dupliquées. Utilisez equal_range() pour trouver toutes les entrées avec une clé donnée.

multimap_multiset.cpp
#include <map>
#include <set>
#include <iostream>
#include <string>

int main() {
    // multimap — multiple values per key
    std::multimap<std::string, std::string> phone_book;
    phone_book.insert({"Alice", "555-0100"});
    phone_book.insert({"Alice", "555-0101"});  // duplicate key OK
    phone_book.insert({"Bob",   "555-0200"});

    // equal_range returns a pair of iterators [first, last)
    auto [begin, end] = phone_book.equal_range("Alice");
    std::cout << "Alice's numbers:\n";
    for (auto it = begin; it != end; ++it) {
        std::cout << "  " << it->second << '\n';
    }

    // multiset — count duplicates
    std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
    std::cout << "Count of 3: " << ms.count(3) << '\n';  // 3
}

Comparateurs personnalisés pour les conteneurs ordonnés

Les conteneurs ordonnés utilisent par défaut std::less (ordre croissant). Vous pouvez fournir un comparateur personnalisé comme troisième argument template :

std::set<int, std::greater<int>> descending = {1, 5, 3};
// ordre d'itération : 5, 3, 1

Pour les types personnalisés, vous pouvez soit définir operator< dans votre classe, soit passer un foncteur comparateur ou une lambda :

auto cmp = [](const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
};
std::set<Point, decltype(cmp)> point_set(cmp);

En C++20, vous pouvez utiliser l'opérateur spaceship (operator<=>) pour générer automatiquement tous les opérateurs de comparaison.

Piège

Utiliser operator[] sur un std::map ou std::unordered_map insère une valeur construite par défaut si la clé n'existe pas. C'est une source courante de bugs subtils :

std::map<std::string, int> m;
int val = m["missing"];  // insère {"missing", 0} dans la map !

Utilisez find(), count() ou contains() (C++20) pour la recherche sans modification. Utilisez at() si vous voulez une exception en cas de clé manquante.

Bonne pratique

Utilisez unordered_map/unordered_set lorsque vous n'avez besoin que de recherche, insertion et suppression — le O(1) en moyenne bat le O(log n) pour les grandes collections.

Utilisez map/set lorsque vous avez besoin de :
- Un ordre d'itération trié
- Des requêtes par plage (lower_bound, upper_bound, equal_range)
- Un O(log n) garanti dans le pire cas (pas de collisions de hachage pathologiques)

Pour les petites collections (moins d'environ 100 éléments), un std::vector trié avec std::lower_bound peut surpasser les deux grâce à la localité de cache.

Points clés
  • std::map et std::set utilisent des arbres rouge-noir — opérations en O(log n) avec ordre trié
  • std::unordered_map et std::unordered_set utilisent des tables de hachage — O(1) en moyenne mais nécessitent une fonction de hachage
  • Utilisez les structured bindings C++17 (auto& [key, val]) pour une itération propre sur les maps
  • operator[] sur les maps insère silencieusement des valeurs par défaut — utilisez find() ou contains() pour une recherche sûre
  • Les types personnalisés comme clés nécessitent operator< (ordonné) ou une fonction de hachage + operator== (non ordonné)
  • try_emplace (C++17) évite de construire la valeur si la clé existe déjà

Quiz — Testez vos connaissances

(15 XP)

1. Quelle est la complexité temporelle moyenne d'une recherche dans `std::unordered_map` ?

2. Que se passe-t-il lorsque vous utilisez `operator[]` avec une clé qui n'existe pas dans un `std::map` ?

3. Quel conteneur devriez-vous choisir si vous avez besoin d'une itération triée ET de requêtes par plage (lower_bound/upper_bound) ?

Précédent
Conteneurs séquentiels : vector, deque, list, array
Suivant
Adaptateurs de conteneurs et conteneurs spéciaux