zurück zum Artikel

C++23: Vier neue assoziative Container

Rainer Grimm

(Bild: rawf8/Shutterstock.com)

Insgesamt gibt es für C++ nun zwölf assoziative Container. In C++23 haben wir sie aus zwei Gründen: Speicherverbrauch und Performanz.​

Die vier assoziativen Container std::flat_map, std::flat_multimap, std::flat_set und std::flat_multiset in C++23 sind ein einfacher Ersatz für die geordneten assoziativen Container std::map, std::multimap, std::set und std::multiset. In C++23 haben wir sie aus zwei Gründen: Speicherverbrauch und Performanz.

Modernes C++ – Rainer Grimm

Rainer Grimm ist seit vielen Jahren als Softwarearchitekt, Team- und Schulungsleiter tätig. Er schreibt gerne Artikel zu den Programmiersprachen C++, Python und Haskell, spricht aber auch gerne und häufig auf Fachkonferenzen. Auf seinem Blog Modernes C++ beschäftigt er sich intensiv mit seiner Leidenschaft C++.

Mit C++23 haben wir 12 assoziative Container. Zwölf? Richtig!

Hier tut Systematik dringend Not. Ich beginne mit den assoziativen Containern von C++98 und C++11.

Alle assoziativen Container haben gemeinsam, dass sie einen Schlüssel mit einem Wert verknüpfen. Daher kann man den Wert mithilfe des Schlüssels erhalten. Die assoziativen Container von C++98 sind geordnete assoziative Container, die von C++11 ungeordnete assoziative Container.

Um die assoziativen Container zu klassifizieren, muss man drei einfache Fragen beantworten:

Die folgende Tabelle mit 2³ = 8 Zeilen beantwortet die drei Fragen. Ich beantworte eine vierte Frage in der Tabelle. Wie schnell ist die Zugriffszeit im durchschnittlichen Fall?

Gerne möchte ich mehr Informationen zu den assoziativen Containern geben, um ihre Performanz-Eigenschaften zu verstehen.

Die Schlüssel der geordneten assoziativen Container sind geordnet. Standardmäßig wird die kleinere Relation (<) verwendet und die Container werden in aufsteigender Reihenfolge sortiert.

Diese Ordnung hat interessante Konsequenzen.

Der am häufigsten verwendete geordnete assoziative Container ist std::map:

std::map<int, std::string> int2String{ 
  {3, "three"}, {2, "two"}, {1, "one"},
  {5, "five"}, {6, "six"}, {4, "four"}, 
  {7, "seven"} };

Der bilanzierte binäre Suchbaum kann die folgende Struktur haben:

Der Kerngedanke der ungeordneten assoziativen Container ist, dass der Schlüssel mithilfe der Hash-Funktion auf den Bucket abgebildet wird. Der Wert wird einfach an den Schlüssel angehängt.

Die ungeordneten assoziativen Container speichern ihre Schlüssel in Buckets. In welchen Bucket der Schlüssel kommt, hängt von der Hash-Funktion ab, die den Schlüssel auf eine eindeutige Zahl abbildet. Diese Zahl wird durch die Anzahl der Buckets modulo geteilt. Wenn verschiedene Schlüssel demselben Bucket zugeordnet werden, spricht man von einer Kollision. Bei einer guten Hash-Funktion werden die Schlüssel gleichmäßig verteilt. Der Wert wird einfach mit dem Schlüssel verknüpft.

Die Verwendung der Hash-Funktion hat wichtige Konsequenzen für den ungeordneten assoziativen Container.

Entsprechend zu std::map ist std::unordered_map der am häufigsten verwendete ungeordnete assoziative Container.

std::unordered_map<std::string, int> str2Int{ 
  {"Grimm",491634333356}, 
  {"Grimm-Jaud", 49160123335}, 
  {"Schmidt",4913333318},
  {"Huber",490001326} };

Die Grafik zeigt die Zuordnung der Schlüssel zu ihrem Bucket mithilfe der Hash-Funktion.

Die vier assoziativen Container std::flat_map, std::flat_multimap, std::flat_set und std::flat_multiset in C++23 sind ein einfacher Ersatz für die geordneten assoziativen Container std::map, std::multimap, std::set und std::multiset.

Die flach geordneten assoziativen Container in C++23 besitzen die gleiche Schnittstelle wie ihre Pendants in C++98.

Die flach geordneten assoziativen Container heißen Containeradapter, weil sie separate sequenzielle Container für ihre Schlüssel und Werte benötigen. Dieser sequenzielle Container muss einen Iterator mit wahlfreiem Zugriff unterstützen. Standardmäßig wird ein std::vector verwendet, aber auch ein std::array oder ein std::deque ist möglich.

Der folgende Codeschnipsel zeigt die Deklaration von std::flat_map und std::flat_set:

template<class Key, class T, 
        class Compare = less<Key>,
        class KeyContainer = vector<Key>, 
        class MappedContainer = vector<T>>
class flat_map;

template<class Key, 
         class Compare = less<Key>, 
         class KeyContainer = vector<Key>>
class flat_set;

Der Grund für die flach geordneten assoziativen Container ist die Performanz.

Die flach geordneten assoziativen Container bieten eine andere Zeit- und Speicherkomplexität als die geordneten Container an. Sie benötigen weniger Speicherplatz und sind schneller zu lesen als ihre nicht flach geordneten Pendants. Sie bieten einen Iterator mit wahlfreiem Zugriff an.

Die nicht-flach geordneten assoziativen Container verbessern die Performanz beim Einfügen oder Löschen von einem Element. Außerdem garantieren sie, dass die Iteratoren nach dem Einfügen oder Löschen eines Elements gültig bleiben. Sie unterstützen einen bidirektionalen Iterator.

Bisher kann ich noch keine Zahlen zeigen, weil kein Compiler die flachen geordneten assoziativen Container unterstützt. Ich werde meinen Performanz-Test "Mehr besondere Freunde mit std::map und std::unordered_map [2]" aktualisieren, wenn std::flat_map verfügbar ist.

Ein std::mdspan ist eine nicht-besitzende mehrdimensionale Ansicht einer zusammenhängenden Folge von Objekten (non-owning multidimensional view of a contiguous sequence of objects). Diese zusammenhängende Folge von Objekten kann ein einfaches C-Array, ein Zeiger mit einer Größe, ein std::array, ein std::vector oder ein std::string sein. (rme [3])


URL dieses Artikels:
https://www.heise.de/-9291846

Links in diesem Artikel:
[1] https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
[2] https://www.heise.de/blog/Mehr-besondere-Freunde-mit-std-map-und-std-unordered-map-4435976.html
[3] mailto:rme@ix.de