unordered_map ist ein zugehöriger Container, der Elemente speichert, die durch die Kombination eines Schlüsselwerts und eines zugeordneten Werts gebildet werden. Der Schlüsselwert wird zur eindeutigen Identifizierung des Elements verwendet und der zugeordnete Wert ist der mit dem Schlüssel verknüpfte Inhalt. Sowohl Schlüssel als auch Wert können von jedem vordefinierten oder benutzerdefinierten Typ sein. Einfach ausgedrückt, ein unordered_map ist wie eine Datenstruktur vom Typ Wörterbuch, die Elemente in sich selbst speichert. Es enthält aufeinanderfolgende Paare (Schlüssel, Wert), was das schnelle Abrufen eines einzelnen Elements basierend auf seinem eindeutigen Schlüssel ermöglicht.
Versuchen Sie es mit Catch Catch Java
Intern wird unordered_map mit Hash Table implementiert. Der für die Zuordnung bereitgestellte Schlüssel wird in Indizes einer Hash-Tabelle gehasht, weshalb die Leistung der Datenstruktur stark von der Hash-Funktion abhängt, im Durchschnitt jedoch die Kosten dafür Suchen, Einfügen und Löschen aus der Hash-Tabelle ist O(1).
Notiz: Im schlimmsten Fall kann die zeitliche Komplexität von O(1) auf O(n) steigen, insbesondere bei großen Primzahlen. In dieser Situation wird dringend empfohlen, stattdessen eine Karte zu verwenden, um einen TLE-Fehler (Time Limit Exceeded) zu vermeiden.
Syntax:
unordered_map-Syntax
Unten ist das C++-Programm zur Demonstration einer ungeordneten Karte:
C++
// C++ program to demonstrate> // functionality of unordered_map> #include> #include> using> namespace> std;> > // Driver code> int> main()> {> >// Declaring umap to be of> >// type key> >// will be of STRING type> >// and mapped VALUE will> >// be of int type> >unordered_mapint>umap; // Einfügen von Werten mithilfe des []-Operators umap['techcodeview.com'] = 10; umap['Praxis'] = 20; umap['Contribute'] = 30; // Durchlaufen einer ungeordneten Karte für (auto x : umap) cout<< x.first << ' ' << x.second << endl; }> |
>
>Ausgabe
Contribute 30 Practice 20 techcodeview.com 10>
unordered_map-Ausgabe
Erläuterung: Das Spezifische, was diese Ausgabe rechtfertigt, ist, dass der Wert des Ergebnisses von unordered_map auf zufällige Schlüssel-zu-Wert-Weise erzeugt wird, während die Karte Wert und Schlüssel auf geordnete Weise anzeigt.
unordered_map vs unordered_set
| Ungeordnete_Karte | Unordered_set |
|---|---|
| Unordered_map enthält Elemente nur in Form von (Schlüssel-Wert-)Paaren. | Unordered_set enthält nicht unbedingt Elemente in Form von Schlüssel-Wert-Paaren, diese werden hauptsächlich verwendet, um die Anwesenheit/Abwesenheit einer Menge zu erkennen. |
| Operator ' []' um den entsprechenden Wert eines Schlüssels zu extrahieren, der in der Karte vorhanden ist. | Die Suche nach einem Element erfolgt mit a finden ()-Funktion. Es ist also kein Operator[] erforderlich. |
Notiz: Betrachten Sie beispielsweise das Problem, die Häufigkeit einzelner Wörter zu zählen. Wir können unordered_set (oder set) nicht verwenden, da wir keine Zählungen speichern können, während wir unordered_map verwenden können.
unordered_map vs. Karte
| Ungeordnete_Karte | Karte |
|---|---|
| Der unordered_map-Schlüssel kann in beliebiger Reihenfolge gespeichert werden. | Die Karte ist eine geordnete Folge eindeutiger Schlüssel |
| Unordered_Map implementiert eine unausgeglichene Baumstruktur, aufgrund derer es nicht möglich ist, die Reihenfolge zwischen den Elementen aufrechtzuerhalten | Map implementiert eine ausgewogene Baumstruktur, weshalb es möglich ist, die Reihenfolge zwischen den Elementen aufrechtzuerhalten (durch spezifische Baumdurchquerung). |
| Die zeitliche Komplexität von unordered_map-Operationen beträgt im Durchschnitt O(1). | Die zeitliche Komplexität von Kartenoperationen beträgt O(log n) |
Methoden auf unordered_map
Es stehen viele Funktionen zur Verfügung, die auf unordered_map funktionieren. Die nützlichsten davon sind:
- Operator = Operator [] leere Größe für Kapazitätsanfang und -ende für den Iterator. Finden und zählen für die Suche. Zum Ändern einfügen und löschen.
Die folgende Tabelle zeigt die vollständige Liste der Methoden einer unordered_map:
| Methoden/Funktionen | Beschreibung |
|---|---|
| bei() | Diese Funktion in C++ unordered_map gibt den Verweis auf den Wert mit dem Element als Schlüssel k zurück |
| beginnen() | Gibt einen Iterator zurück, der auf das erste Element im Container im unordered_map-Container zeigt |
| Ende() | Gibt einen Iterator zurück, der auf die Position hinter dem letzten Element im Container im unordered_map-Container zeigt |
| Eimer() | Gibt die Bucket-Nummer zurück, in der sich das Element mit dem Schlüssel k in der Karte befindet |
| Bucket_count | Bucket_count wird verwendet, um die Gesamtzahl zu zählen. von Buckets in der unordered_map. Für die Übergabe an diese Funktion ist kein Parameter erforderlich |
| Bucket_size | Gibt die Anzahl der Elemente in jedem Bucket der unordered_map zurück |
| zählen() | Zählen Sie die Anzahl der Elemente, die in einer unordered_map mit einem bestimmten Schlüssel vorhanden sind |
| equal_range | Gibt die Grenzen eines Bereichs zurück, der alle Elemente im Container umfasst, mit einem Schlüssel, der im Vergleich gleich k ist |
| finden() | Gibt den Iterator zum Element zurück |
| leer() | Überprüft, ob der Container im unordered_map-Container leer ist |
| löschen() | Löschen Sie Elemente im Container im unordered_map-Container |
Die C++11-Bibliothek bietet auch Funktionen zum Anzeigen der intern verwendeten Bucket-Anzahl und Bucket-Größe sowie der verwendeten Hash-Funktion und verschiedener Hash-Richtlinien, diese sind jedoch in realen Anwendungen weniger nützlich. Mit Iterator können wir alle Elemente von unordered_map durchlaufen.
C++
// C++ program to demonstrate> // Initialization, indexing,> // and iteration> #include> #include> using> namespace> std;> > // Driver code> int> main()> {> >// Declaring umap to be of> >// type key> >// will be of string type and> >// mapped value will be of double type> >unordered_mapdouble>umap = { //Element direkt in Map einfügen {'One', 1}, {'Two', 2}, {'Three', 3} }; // Werte mit [] einfügen Operator umap['PI'] = 3.14; umap['root2'] = 1.414; umap['root3'] = 1.732; umap['log10'] = 2.302; umap['loge'] = 1.0; // Wert durch Einfügefunktion einfügen umap.insert(make_pair('e', 2.718)); string key = 'PI'; // Wenn der Schlüssel im Map-Iterator nicht gefunden wird, // wird to end zurückgegeben, wenn (umap.find(key) == umap.end()) cout<< key << ' not found
'; // If key found then iterator to that // key is returned else cout << 'Found ' << key << '
'; key = 'lambda'; if (umap.find(key) == umap.end()) cout << key << ' not found
'; else cout << 'Found ' << key << endl; // iterating over all value of umap unordered_mapdouble>::iterator itr; cout<< '
All Elements :
'; for (itr = umap.begin(); itr != umap.end(); itr++) { // itr works as a pointer to // pair type // itr->speichert zuerst den Schlüsselteil und // itr->zweite speichert den Wertteil cout ' '<< itr->zweite<< endl; } }> |
>
>Ausgabe
Found PI lambda not found All Elements : e 2.718 loge 1 log10 2.302 Two 2 One 1 Three 3 PI 3.14 root2 1.414 root3 1.732>
Finden Sie Häufigkeiten einzelner Wörter
Bei einer gegebenen Wortfolge besteht die Aufgabe darin, die Häufigkeiten der einzelnen Wörter zu ermitteln:
Nachteile des Internets
Eingang: str = Geeks für Geeks Geeks Quiz Übung QA für;
Ausgabe: Häufigkeiten einzelner Wörter sind
(Übung, 1)
(für 2)
(qa, 1)
(Quiz, 1)
(Geeks, 3)
Nachfolgend finden Sie das C++-Programm zur Implementierung des oben genannten Ansatzes:
C++
// C++ program to find freq> // of every word using unordered_map> #include> using> namespace> std;> > // Prints frequencies of> // individual words in str> void> printFrequencies(>const> string &str)> {> >// declaring map of type,> >// each word is mapped to its frequency> >unordered_mapint>wordFreq; // Eingabe in ein Wort aufteilen mit // string stream // Wird zum Aufteilen von Wörtern verwendet stringstream ss(str); // Um einzelne Wörter zu speichern string word; while (ss>> Wort) wordFreq[Wort]++; // iteriert jetzt über Wort, Freq-Paar // und gibt sie im Format aus unordered_mapint>:: iterator p; for (p = wordFreq.begin(); p != wordFreq.end(); p++) cout<< '(' ', ' << p->zweite<< ')
'; } // Driver code int main() { string str = 'geeks for geeks geeks quiz ' 'practice qa for'; printFrequencies(str); return 0; }> |
>
>Ausgabe
(practice, 1) (for, 2) (qa, 1) (quiz, 1) (geeks, 3)>
Aktuelle Artikel auf unordered_map