Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

std::map — une map ordonnée à clés uniques

std::map stocke des paires clé-valeur selon l’ordre du comparateur, avec au plus un élément par clé équivalente. Découvrez la recherche sans modification, l’insertion, la suppression et le transfert de nœuds, ainsi que la raison pour laquelle operator[] ne vérifie pas la présence d’une clé.

Version : C++23; repository compiler flag, production runtime not attested

Syntaxe

#include <map>
std::map<Key, T> m;
std::map<Key, T, Compare> ordered;

std::map<Key, T, Compare> de <map> stocke des éléments std::pair<const Key, T> dans l’ordre du comparateur ; par défaut, elle utilise std::less<Key>. Compare doit définir un ordre strict faible. Des clés sont équivalentes si !comp(a, b) && !comp(b, a), pas nécessairement si a == b. La map n’autorise qu’une seule clé de ce type ; un itérateur permet de modifier la valeur, mais pas la clé.

Pour sélectionner la surcharge de std::map::insert qui insère un seul élément, construisez explicitement un élément du type value_type de la map : m.insert(value_type{key, value}). Cette surcharge renvoie une paire itérateur-bool : si une clé équivalente existe déjà, le bool vaut false et la valeur stockée n’est pas remplacée. Si key et value sont tous deux implicitement convertibles en value_type, m.insert({key, value}) peut sélectionner à la place la surcharge qui prend un std::initializer_list<value_type>, renvoie void et tente d’insérer deux éléments. Dans l’exemple avec std::map<int, int>, l’appel avec des accolades sélectionne la surcharge qui insère un seul élément. std::map::find renvoie un itérateur ou std::map::end ; end() désigne la position après le dernier élément et ne doit pas être déréférencé. std::map::contains renvoie bool, tandis que std::map::count renvoie 0 ou 1. std::map::equal_range renvoie une plage semi-ouverte [first, last) contenant zéro ou un élément. Ces recherches n’insèrent aucun élément et coûtent O(log n).

std::map::operator[] renvoie une référence à la valeur ; si la clé est absente, il insère un nouvel élément avec cette clé. Avec l’allocateur par défaut, la valeur associée est initialisée par valeur (à 0 pour int, par exemple), ce qui exige que T soit constructible par défaut. Un allocateur personnalisé peut modifier la façon dont l’élément est construit. N’utilisez pas [] uniquement pour vérifier la présence. std::map::erase(key) renvoie le nombre d’éléments supprimés ; erase(it) renvoie l’itérateur suivant et exige un itérateur déréférençable. std::map::size renvoie le nombre d’éléments en O(1). L’insertion ordinaire et la suppression par clé coûtent O(log n) ; la suppression par itérateur est en O(1) amorti. L’insertion n’invalide aucun itérateur ni référence ; la suppression invalide uniquement ceux des éléments supprimés.

std::map::extract détache un nœud sans copier ni déplacer son élément ; une clé absente produit un handle vide. Vérifiez empty() avant key() ; la clé détachée peut être modifiée avant de réinsérer le nœud. std::map::merge transfère les nœuds de types compatibles sans copier ni déplacer les éléments ; les clés en conflit restent dans la source. Le transfert de nœuds exige des allocateurs égaux. L’exemple utilise des opérations disponibles en C++23 ; le document lié est un projet évolutif, pas la norme C++23 définitive. Le drapeau du compilateur du dépôt ne certifie pas l’environnement de production.

Exemples

#include <iostream>
#include <map>
#include <utility>

int main() {
    std::map<int, int> m{{2, 20}};
    auto result = m.insert({2, 99});
    std::cout << std::boolalpha << "inserted=" << result.second << '\n';
    m[1] += 10;
    if (auto it = m.find(2); it != m.end()) {
        std::cout << "found=" << it->second << '\n';
    }
    auto [first, last] = m.equal_range(2);
    std::cout << "contains=" << m.contains(2)
              << " count=" << m.count(2)
              << " range=" << (first != last) << '\n';

    auto node = m.extract(1);
    if (!node.empty()) {
        node.key() = 3;
        m.insert(std::move(node));
    }
    std::map<int, int> source{{2, 200}, {4, 40}};
    m.merge(source);
    std::cout << "erased=" << m.erase(2)
              << " size=" << m.size()
              << " source=" << source.size() << '\n';
    for (const auto& [key, value] : m) {
        std::cout << key << ':' << value << '\n';
    }
}

Résultat

inserted=false
found=20
contains=true count=1 range=true
erased=1 size=2 source=1
3:10
4:40

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources