C++23: Vier neue assoziative Container
Insgesamt gibt es für C++ nun zwölf assoziative Container. In C++23 haben wir sie aus zwei Gründen: Speicherverbrauch und Performanz.
(Bild: rawf8/Shutterstock.com)
- Rainer Grimm
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.
Mit C++23 haben wir 12 assoziative Container. Zwölf? Richtig!
- C++98
: std::map, std::set, std::multimapundstd::multiset - C++11
: std::unordered_map, std::unordered_set, std::unordered_multimapundstd::unordered_multiset - C++23
: std::flat_map, std::flat_set, std::flat_multimapundstd::flat_multiset
Hier tut Systematik dringend Not. Ich beginne mit den assoziativen Containern von C++98 und C++11.
Assoziative Container
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:
- Sind die Schlüssel sortiert?
- Hat der Schlüssel einen zugehörigen Wert?
- Kann ein Schlüssel mehr als einmal vorkommen?
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.
Geordnete assoziative Container
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 Schlüssel muss eine Ordnungsbeziehung unterstützen.
- Assoziative Container werden in der Regel als Red-Black Trees implementiert. Dies sind bilanzierte binäre Suchbäume.
- Die Zugriffszeit auf den Schlüssel und damit auch auf den Wert ist logarithmisch.
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:
Ungeordnete assoziative Container
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.
- Die Hash-Funktion für den Schlüssel muss verfügbar sein.
- Die Schlüssel müssen einen Gleichheitsvergleich unterstützen, um mit Kollisionen umgehen zu können.
- Da die Ausführungszeit der Hash-Funktion eine Konstante ist, ist die Zugriffszeit auf die Schlüssel eines ungeordneten assoziativen Containers konstant, wenn die Schlüssel gleichmäßig verteilt sind.
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.
Container-Adaptoren
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.
Vergleich der flach geordneten Container und ihrer nicht-flachen Pendants
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" aktualisieren, wenn std::flat_map verfügbar ist.
Wie geht's weiter?
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)
