Assoziative Container

Wenn man auf ein Element außerhalb eines Containers der Standard Template Library (STL) zugreift, ist das Ergebnis ungewiss. Der Effekt kann ein Fehler oder undefiniertes Verhalten sein. Undefiniertes Verhalten bedeutet, dass keine Aussagen über das Programm mehr möglich sind.

Hier geht es direkt zum Artikel auf Heise Developer: https://heise.de/-4442896.

Modernes C++ besitzt acht assoziative Container, aber die zwei Container std::map und std::unordered_map sind besonders. Warum? Genau diese Frage beantwortet dieser Artikel.

Hier geht's direkt zum Artikel auf Heise Developer: https://heise.de/-4435976.

Mein letzter Artikel zu den C++ Core Guidelines "To Switch or not to Switch, that is the Question" wurde sehr intensiv diskutiert. Der Einsatz einer Hashtabelle anstelle einer switch Anweisung scheint ein sehr emotionales Thema zu sein. Daher habe ich meinen ursprünglichen Plan geändert. Heute werde ich verschiedene Kontrollstrukturen vorstellen. Los geht es mit der if und switch Anweisung, weiter mit der Hashtabelle und zum Abschluss werde ich auf dynamischen und statischen Polymorphismus eingehen. Zusätzlich werde ich die verschiedenen Kontrollstrukturen bzgl. ihrer Pflege und Performanz vergleichen.

Die Hashfunktion bildet die potentiell unendliche Anzahl von Schlüssel auf eine endliche Anzahl von Buckets ab. Welche Strategie dabei die C++-Laufzeit verfolgt und wie diese angepasst werden kann, zeigt dieser Artikel.

Der entscheidende Grund für die konstante Zugriffszeit der ungeordneten assoziativen Container sind deren Hashfunktionen. In bekannter Manier bietet C++ viele Stellschrauben für Hashfunktionen an. Einerseits bringt C++ einen reichen Satz an Hashfunktionen mit, andererseits lassen sich auch eigene Hashfunktionen verwenden. Selbst die Verteilung der Hashwerte auf die Buckets kann angepasst werden.

Bevor ich das Interface der Hashtabellen - offiziell ungeordnete assoziative Container genannt- genauer betrachte, will ich ihre Performanz mit der der geordneten assoziativen Container vergleichen. Die idealen Kandidaten dafür sind die std::unordered_map und ihr geordneter Pendant die std::map, da sie von allen assoziativen Containern am häufigsten zum Einsatz kommen.

Hashtabellen wurden in C++ lange vermisst. Versprechen sie doch konstante Zugriffszeit auf ihre Elemente. C++11 besitzt jetzt Hashtabellen in vier Variationen. Offiziell heißen sie ungeordnete assoziative Container, inoffiziell werden sie auch Dictionaries oder einfach nur assoziative Arrays genannt.