Unsortierte Assoziativ-Container
Außer den sortierten Assoziativ-Container gibt es noch die unsortierten Set- und Map-Varianten. Der Unterschied zwischen der sortierten und unsortierten Variante liegt, abgesehen von der Sortierung, in der Ausführungsgeschwindigkeit beim Suchen und Einfügen von Elementen. Bei den sortierten Varianten wird in der Regel ein red-black tree durchlaufen, um ein Element im Container zu finden. Und je nach Anzahl der Elemente sind mehrere Elemente entlang des Baumes zu vergleichen, bis das gewünschte Element gefunden wird. Bei den unsortierten Varianten kommt dagegen ein Hash-Algorithmus zum Einsatz. Vereinfacht ausgedrückt wird beim Hash-Algorithmus aus dem Schlüssel ein Index berechnet und über diesen auf das Element zugegriffen. D.h., bei Containern mit vielen Elementen ist der Zugriff auf ein Element bei der unsortierten Variante schneller als bei der sortierten, da die Anzahl der Vergleiche geringer ist.
Auf eine Besonderheit der unsortierten Assoziativ-Container sein hingewiesen: Sie lassen sich nicht vergleichen. D.h., die für alle anderen Containertypen zur Verfügung stehenden Vergleichsoperatoren sind für die unsortierten Container nicht definiert.
Und auch für die unsortierten Assoziativ-Container gelten ansonsten weiterhin die Aussagen des Kapitels Gemeinsame Container-Eigenschaften und -Operationen.
Containertypen
unordered_set und unordered_multiset
Einzubindende Header-Datei: unordered_set
unordered_set bzw. unordered_multiset definieren einen Container, der nur aus einem Schlüssel besteht. Der Unterschied zwischen unordered_set und unordered_multiset besteht darin, dass in einem unordered_set ein Schlüssel nur einmal vorhanden sein darf, während ein unordered_multiset mehrere gleiche Schlüssel zulässt.
unordered_map und unordered_multimap
Einzubindende Header-Datei: unordered_map
unordered_map bzw. unordered_multimap definieren einen Container, der außer einem Schlüssel ein zusätzliches beliebiges Datum enthält. Der Unterschied zwischen einer unordered_map und einer unordered_multimap besteht ebenfalls darin, dass in der map der Schlüssel nur einmal vorhanden sein darf, während die multimap mehrere gleiche Schlüssel zulässt.
Objekte definieren
Objekte vom Typ eines unsortierten Assoziativ-Containers werden wie nachfolgend aufgeführt definiert. cont gibt den Containertyp an und KVTYP den Datentyp der im Container abzulegenden Elemente. Bei einem unordered_set oder unordered_multiset enthält KVTYP den Datentyp des Schlüssels und bei einer unordered_map oder unordered_multimap die Datentypen für den Schlüssel und das Datum.
cont<KVTYP> obj;
Container ohne Elemente (leerer Container).
cont<KVTYP> obj(iiter first, iiter last);
Kopiert die Daten aus dem Bereich [first...last) in den Container. Für die Bereichsangabe können sowohl Zeiger wie auch Iteratoren verwendet werden. Enthält der zu kopierende Bereich bei einem Set bzw. einer Map mehrere gleiche Schlüssel, ist nicht definiert, welcher Schlüssel übernommen wird.
cont<KVTYP> obj(const cont<KVTYP>& other);
Kopiert den Inhalt des Containers other in den Container.
cont<KVTYP> obj(ilist args);
Kopiert die Initialisiererliste args in den Container.
// double Feld definieren/initialisieren
double initArray[3] {33.3,11.1,22.2};
// Leere unsortierted Map
std::unordered_map<int,float> floatMap;
// Unsortiertes double set mit double Feld init.
std::unordered_set<double> dblSet (initArray, initArray+3);
// Unsortierte Multimap Initialisererliste init.
std::unordered_multimap<int,CData4> demoMMap
{{1,CData4{"eins"s}},{2,CData4{"zwei"s}},
{3,CData4{"drei"s}},{4,CData4{"vier"s}}};Container und Iteratoren
Auf die Elemente eines unsortierten Assoziativ-Containers kann nur über forward-Iteratoren zugegriffen werden. Für die Initialisierung des Iterators stehen die bekannten Funktionen wie begin() oder cbegin() zur Verfügung.
Zu beachten ist, dass der Iterator einer unsortierte Map auf ein pair-Datum verweist, dessen Member first den Schlüssel enthält und second das zusätzliche Datum.
#include <print>
#include <unordered_map>
using namespace std::string_literals;
import CData4;
int main()
{
// Unsortierte Multimap
// und mit Initialisererliste initialisieren
std::unordered_multimap<int,CData4> demoMap
{{1,CData4{"eins"s}},{2,CData4{"zwei"s}},
{3,CData4{"drei"}}};
// Unsortierte Multimap über Iterator ausgeben
for (auto iter = demoMap.begin();
iter != demoMap.end(); ++iter)
std::print("{}:{}, ", iter->first, iter->second);
std::println("");
// Einfacher geht's mit range-for
for (auto [key,value]: demoMap)
std::print("{}:{}, ",key, value);
}
3:drei, 2:zwei, 1:eins,
3:drei, 2:zwei, 1:eins,
Elemente einfügen und löschen
Zum Einfügen und Löschen von Elementen in die unsortierten Assoziativ-Container stehen die gleichen Methoden wie bei den sortierten Assoziativ-Container zur Verfügung. Für eine Beschreibung sehen Sie dort unter Elemente einfügen und löschen nach.
Elementzugriff
Auch der Zugriff auf die Elemente eines unsortierten Assoziativ-Containers erfolgt analog zum Zugriff auf die sortierten Assoziativ-Container. Der einzige Unterschied besteht darin, dass beim Zugriff auf die unsortierten Varianten nur ein forward-Iterator eingesetzt werden kann und kein bidirektionaler Iterator. Mehr zum Zugriff im Abschnitt Elementzugriff.
Suchen im Container
Auch die unsortierten Assoziativ-Container sind daraufhin optimiert, um Daten schnell über einen Schlüssel zu finden.
size_type count (const KTYP& key);
Liefert die Anzahl der Elemente mit dem Schlüssel key zurück.
iter find (const KTYP& key);
Sucht nach dem ersten Element mit dem Schlüssel key und liefert einen Iterator darauf zurück. Ist das gesuchte Element nicht im Container vorhanden, wird die Position end() zurückgeliefert.
std::pair<iter,iter> equal_range (const DKEY& key);
Liefert im pair-Element first einen Iterator auf das erste Element mit dem Schlüssel key und im pair-Element second einen Iterator auf das danach folgenden Element mit einem Schlüssel ungleich key. Wird kein Element mit dem Schlüssel key gefunden, enthalten beide Iteratoren einen Verweis auf das Containerende (end()).
#include <print>
#include <unordered_set>
int main()
{
std::unordered_multiset<int> mySet{1,2,2,4,2,10,11};
// Suche alle Daten mit dem Wert 2
auto iter_pair = mySet.equal_range(2);
// Falls Daten vorhanden sind
if (iter_pair.first != mySet.end())
{
// Alle Daten ausgeben
for (auto iter = iter_pair.first;
iter != iter_pair.second;++iter)
std::print("{}, ",*iter);
}
}2, 2, 2,
Containerkapazität
Es sind die gleichen Methoden wie bei den sortierten Assoziativ-Container verfügbar.