CKTIS / C++
std::unordered_multimap — mehrere Werte für einen Schlüssel
std::unordered_multimap speichert Schlüssel-Wert-Paare und erlaubt mehrere Einträge mit gleichwertigen Schlüsseln. Die Suche basiert auf Hashing, die Schlüssel werden jedoch nicht sortiert. Mit equal_range lassen sich alle passenden Einträge abrufen.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <unordered_map>
std::unordered_multimap<Key, T> entries;std::unordered_multimap<Key, T> aus <unordered_map> speichert mehrere Werte, die gleichwertigen Schlüsseln zugeordnet sind. Anders als std::unordered_map erlaubt der Container wiederholte Schlüssel und sogar identische Paare. Sein Elementtyp ist std::pair<const Key, T>: Über einen Iterator lässt sich der zugeordnete Wert ändern, nicht aber der Schlüssel.
emplace fügt einen Eintrag hinzu, find sucht ein passendes Element, und equal_range(key) gibt den Bereich [first, last) mit allen Treffern zurück. erase(key) entfernt alle Treffer und gibt ihre Anzahl zurück; erase(it) entfernt nur das angegebene Element. operator[] und at gibt es nicht.
Die Iterationsreihenfolge ist nicht festgelegt, gleichwertige Schlüssel bilden jedoch benachbarte Gruppen. find hat durchschnittlich die Komplexität O(1), im ungünstigsten Fall O(n). Das Auslesen von k Treffern erfordert zusätzlich O(k). Gleichwertige Schlüssel müssen denselben Hashwert haben. Ein Rehash macht Iteratoren ungültig, nicht aber Zeiger oder Referenzen auf Elemente.
Das Beispiel sammelt die Ergebnisse für "Ada" und sortiert eine Kopie, damit die Ausgabe nicht von der Iterationsreihenfolge abhängt. Dieser Eintrag bezieht sich auf C++23; der angegebene Standardentwurf ist ein fortlaufend gepflegtes Dokument und keine eingefrorene C++23-Spezifikation. Das Compiler-Flag im Repository bestätigt keine Unterstützung in der Produktionslaufzeitumgebung.
Beispiele
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
int main() {
std::unordered_multimap<std::string, int> scores;
scores.emplace("Ada", 20);
scores.emplace("Ben", 15);
scores.emplace("Ada", 10);
const auto [first, last] = scores.equal_range("Ada");
std::vector<int> values;
for (auto it = first; it != last; ++it) {
values.push_back(it->second);
}
std::sort(values.begin(), values.end());
std::cout << "Ada:";
for (int value : values) {
std::cout << ' ' << value;
}
std::cout << '\n';
std::cout << "removed: " << scores.erase("Ada") << '\n';
std::cout << "remaining: " << scores.size() << '\n';
}
Ergebnis
Ada: 10 20 removed: 2 remaining: 1
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.