WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::map — eine geordnete Map mit eindeutigen Schlüsseln

std::map speichert Schlüssel-Wert-Paare in der Reihenfolge des Vergleichers und enthält höchstens ein Element je äquivalentem Schlüssel. Lerne nicht verändernde Suchvorgänge, Einfügen, Löschen und den Transfer von Knoten kennen – und warum operator[] keine Anwesenheitsprüfung ist.

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

Syntax

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

std::map<Key, T, Compare> aus <map> speichert Elemente vom Typ std::pair<const Key, T> in der Reihenfolge des Vergleichers; standardmäßig wird std::less<Key> verwendet. Compare muss eine strikte schwache Ordnung definieren. Schlüssel sind äquivalent, wenn !comp(a, b) && !comp(b, a), nicht unbedingt wenn a == b. Die Map erlaubt nur einen solchen Schlüssel; über einen Iterator lässt sich der Wert, nicht aber der Schlüssel ändern.

Um die Überladung von std::map::insert für ein einzelnes Element auszuwählen, konstruiere explizit ein Element vom Typ value_type der Map: m.insert(value_type{key, value}). Diese Überladung liefert ein Iterator-bool-Paar: Ist bereits ein äquivalenter Schlüssel vorhanden, ist der bool-Wert false, und der gespeicherte Wert wird nicht überschrieben. Sind sowohl key als auch value implizit in value_type konvertierbar, kann m.insert({key, value}) stattdessen die Überladung für std::initializer_list<value_type> auswählen. Diese gibt void zurück und versucht, zwei Elemente einzufügen. Im Beispiel mit std::map<int, int> wählt der Aufruf mit geschweiften Klammern die Überladung für ein einzelnes Element aus. std::map::find liefert einen Iterator oder std::map::end; end() zeigt hinter das letzte Element und darf nicht dereferenziert werden. std::map::contains liefert bool, std::map::count dagegen 0 oder 1. std::map::equal_range liefert einen halboffenen Bereich [first, last) mit null oder einem Element. Diese Suchvorgänge fügen nichts ein und benötigen O(log n).

std::map::operator[] liefert eine Referenz auf den Wert; fehlt der Schlüssel, wird ein neues Element mit diesem Schlüssel eingefügt. Mit dem Standard-Allokator wird der zugehörige Wert wertinitialisiert (bei int beispielsweise mit 0); dafür muss T standardkonstruierbar sein. Ein benutzerdefinierter Allokator kann beeinflussen, wie das Element konstruiert wird. Verwende [] nicht nur zur Anwesenheitsprüfung. std::map::erase(key) liefert die Zahl der gelöschten Elemente; erase(it) liefert den nächsten Iterator und erfordert einen dereferenzierbaren Iterator. std::map::size liefert die Elementzahl in O(1). Normales Einfügen und Löschen nach Schlüssel benötigen O(log n), Löschen per Iterator amortisiert O(1). Einfügen invalidiert keine Iteratoren oder Referenzen; Löschen nur solche auf gelöschte Elemente.

std::map::extract löst einen Knoten, ohne dessen Element zu kopieren oder zu verschieben; bei fehlendem Schlüssel entsteht ein leerer Handle. Prüfe empty() vor key(); der abgetrennte Schlüssel kann vor dem Wiedereinfügen geändert werden. std::map::merge überträgt typkompatible Knoten ohne Kopieren oder Verschieben der Elemente; kollidierende Schlüssel bleiben in der Quelle. Für den Knotentransfer müssen die Allokatoren gleich sein. Das Beispiel verwendet in C++23 verfügbare Operationen; das verlinkte Dokument ist ein fortlaufend entwickelter Entwurf, nicht die endgültige C++23-Norm. Das Compiler-Flag des Repositorys bestätigt nicht die Produktionsumgebung.

Beispiele

#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';
    }
}

Ergebnis

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

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen