Voraussetzung: std::map , std::unordered_map
Wenn es um Effizienz geht, gibt es einen großen Unterschied zwischen Karten und ungeordneten Karten.
Wir müssen die interne Funktionsweise beider kennen, um entscheiden zu können, welches verwendet werden soll.
Unterschied :
| map | unordered_map --------------------------------------------------------- Ordering | increasing order | no ordering | of keys(by default) | Implementation | Self balancing BST | Hash Table | like Red-Black Tree | search time | log(n) | O(1) ->Durchschnittlich | | O(n) -> Worst-Case-Einfügezeit | log(n) + Neuausgleich | Identisch mit Suche Löschzeit | log(n) + Neuausgleich | Identisch mit Suche>
Verwenden Sie std::map, wenn
- Sie benötigen geordnete Daten.
- Sie müssten die Daten ausdrucken bzw. darauf zugreifen (in sortierter Reihenfolge).
- Sie benötigen Vorgänger/Nachfolger von Elementen.
- Weitere Fälle finden Sie unter Vorteile von BST gegenüber Hash Table.
CPP
for-Schleife in Bash
// CPP program to demonstrate use of std::map> #include> int> main()> {> >// Ordered map> >std::map<>int>,>int>>bestellen;> >// Mapping values to keys> >order[5] = 10;> >order[3] = 500;> >order[20] = 100;> >order[1] = 1;> >// Iterating the map and> >// printing ordered values> >for> (>auto> i = order.begin(); i> >!= order.end(); i++) {> >std::cout << ' : ' '
'; } }> |
Kat Timpf Vermögen
>
>Ausgabe
Java-Eingabezeichenfolge
1 : 1 3 : 500 5 : 10 20 : 100>
Verwenden Sie std::unordered_map, wenn
- Sie müssen einige Daten zählen (Beispiel: Zeichenfolgen) und es ist keine Reihenfolge erforderlich.
- Sie benötigen Zugriff auf ein einzelnes Element, d. h. keine Durchquerung.
CPP
Blasensortierung in Java
// CPP program to demonstrate use of> // std::unordered_map> #include> int> main()> {> >// Unordered map> >std::unordered_map<>int>,>int>>bestellen;> >// Mapping values to keys> >order[5] = 10;> >order[3] = 500;> >order[20] = 100;> >order[1] = 1;> >// Iterating the map and> >// printing unordered values> >for> (>auto> i = order.begin();> >i != order.end(); i++)> >{> >std::cout << ' : ' '
'; } }> |
>
>Ausgabe
1 : 1 20 : 100 3 : 500 5 : 10>
Sehen wir uns die Unterschiede in tabellarischer Form an:
| Karte | unordered_map | |
| 1. | Die Karte ist in der #include-Headerdatei definiert | unordered_map ist in der #include-Headerdatei definiert |
| 2. | Es wird umgesetzt von rot-schwarzer Baum . | Es wird mithilfe einer Hash-Tabelle implementiert. |
| 3. | Es ist langsam. | Es ist schnell. |
| 4. | Zeitkomplexität für Operationen ist O(log N) | Die Zeitkomplexität für Operationen beträgt O(1) |
| 5. | Map wird verwendet, um Elemente als Schlüssel-Wert-Paare in der Reihenfolge sortiert nach Schlüssel zu speichern. | unordered_map wird verwendet, um Elemente als Schlüssel-Wert-Paare in nicht sortierter Reihenfolge zu speichern. |