WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::unordered_map — Hash-Map mit eindeutigen Schlüsseln

std::unordered_map speichert Schlüssel-Wert-Paare ohne garantierte Reihenfolge. Erfahre, wie du suchst, ohne einzufügen, worin sich operator[] und at unterscheiden und wie die Verwaltung der Buckets die Gültigkeit von Iteratoren beeinflusst.

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

Syntax

#include <unordered_map>
std::unordered_map<Key, T> map;

std::unordered_map<Key, T> aus <unordered_map> speichert für jeden äquivalenten Schlüssel höchstens einen Wert. Die Iterationsreihenfolge ist nicht festgelegt. Suchen und Einfügen kosten durchschnittlich O(1), im ungünstigsten Fall O(n). Äquivalente Schlüssel müssen denselben Hashwert haben; gleiche Hashwerte bedeuten jedoch nicht, dass die Schlüssel äquivalent sind.

find(key) fügt nichts ein: Es gibt einen Iterator oder end() zurück, den Iterator hinter dem letzten Element, der nicht dereferenziert werden darf. operator[] gibt eine Referenz auf den Wert zurück und fügt einen fehlenden Schlüssel ein; beim Standard-Allocator wird der neue Wert wertinitialisiert, für int also auf 0. at(key) fügt nichts ein und löst bei einem fehlenden Schlüssel std::out_of_range aus. emplace(...) gibt ein Paar aus Iterator und Einfügekennzeichen zurück; ein Duplikat überschreibt den Wert nicht.

size() gibt die Elementanzahl an, bucket_count() die Anzahl der Buckets und load_factor() die durchschnittliche Anzahl von Elementen pro Bucket. max_load_factor() liest den Auslastungsgrenzwert; max_load_factor(z) verlangt ein positives z. Lege den Grenzwert vor reserve(n) fest. Die Funktion plant Platz für insgesamt n Elemente ein, nicht für n zusätzliche. Sie entspricht rehash(ceil(n / max_load_factor())). rehash(n) stellt mindestens n Buckets und genügend Buckets für die vorhandenen Elemente und den Grenzwert sicher; die genaue Anzahl hängt von der Implementierung ab.

Rehashing macht Iteratoren ungültig, nicht aber Zeiger oder Referenzen auf Elemente. Auch Einfügen über operator[] kann Rehashing auslösen. clear() entfernt alle Elemente, setzt size() auf 0 und macht Verweise auf entfernte Elemente ungültig; es garantiert nicht, dass der gesamte Speicher des Containers freigegeben wird.

Geltungsbereich dieses Eintrags: C++23. Ein Compiler-Flag im Repository bestätigt nicht die Produktionslaufzeitumgebung. Der Quelltext ist ein sich weiterentwickelnder Arbeitsentwurf und kein eingefrorener C++23-Text; dieser Eintrag stützt sich nicht auf die dort gezeigten neueren Erweiterungen.

In diesem Eintrag behandelte Referenzbezeichner: std::unordered_map::find, std::unordered_map::end, std::unordered_map::clear, std::unordered_map::operator[], std::unordered_map::max_load_factor, std::unordered_map::reserve, std::unordered_map::rehash, std::unordered_map::size, std::unordered_map::load_factor, std::unordered_map::bucket_count, std::unordered_map::at, std::unordered_map::emplace.

Beispiele

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    counts.max_load_factor(0.75f);
    counts.reserve(8);

    counts.emplace("apple", 2);
    ++counts["apple"];
    ++counts["pear"];
    const bool inserted = counts.emplace("apple", 99).second;

    if (auto it = counts.find("apple"); it != counts.end()) {
        std::cout << "apple=" << it->second << '\n';
    }
    std::cout << std::boolalpha << "duplicate inserted=" << inserted << '\n';
    std::cout << "pear=" << counts.at("pear") << '\n';
    std::cout << "size=" << counts.size() << '\n';

    counts.rehash(32);
    std::cout << "buckets>=32=" << (counts.bucket_count() >= 32) << '\n';
    std::cout << "load within limit="
              << (counts.load_factor() <= counts.max_load_factor()) << '\n';

    counts.clear();
    std::cout << "size after clear=" << counts.size() << '\n';
}

Ergebnis

apple=3
duplicate inserted=false
pear=1
size=2
buckets>=32=true
load within limit=true
size after clear=0

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