Verbesserte Container mit C++17

Modernes C++  –  6 Kommentare

C++11 besitzt acht assoziative Container. Mit C++17 wird es möglich, komfortabler neue Elemente hinzuzufügen, bestehende Container zusammenzuführen oder sogar Elemente von einem assoziativen in den anderen Container zu verschieben. Das ist aber noch nicht alles. Der Zugriff auf assoziative und sequenzielle Container wurde vereinheitlicht.

Bevor ich aber in die Details abtauche, muss ich noch eine Frage beantworten. Wann sind assoziative Container ähnlich? In Summe enthält C++ acht assoziative Container. Hier sind sie:

Mit ähnlich meine ich, dass die Container dieselbe Struktur und die gleichen Datentypen besitzen. Die Elemente von std::set und std::multiset, std::unordered_set und std::unordered_multiset, std::map und std::multimap und zum Abschluss std::unordered_map und std::unordered_multimap haben dieselbe Struktur.

Zugegeben, das war nur ein High-Level-Überblick zu den acht assoziativen Containern – aus zwei Gründen. Erstens will ich über das verbesserte Interface der assoziativen Container schreiben. Zweiten lassen sich die ganzen Details in meinen Artikel zu Hashtabellen nachlesen.

Das verbesserte Interface der assoziativen Container

Am einfachsten lässt sich das neue Interface mit einem ausführlichen Beispiel beschreiben:

// accociativeContainers.cpp

#include <iostream>
#include <map>
#include <string>
#include <utility>

using namespace std::literals; // 1

template <typename Cont>
void printContainer(const Cont& cont, const std::string& mess){ // 2
std::cout << mess;
for (const auto& pa: cont){
std::cout << "(" << pa.first << ": " << pa.second << ") ";
}
std::cout << std::endl;
}

int main(){

std::map<int, std::string> ordMap{{1, "a"s}, {2, "b"}}; // 3
ordMap.try_emplace(3, 3, 'C');
ordMap.try_emplace(3, 3, 'c');

printContainer(ordMap, "try_emplace: ");

std::cout << std::endl;

std::map<int, std::string> ordMap2{{3, std::string(3, 'C')}, // 4
{4, std::string(3, 'D')}};
ordMap2.insert_or_assign(5, std::string(3, 'e'));
ordMap2.insert_or_assign(5, std::string(3, 'E'));

printContainer(ordMap2, "insert_or_assign: "); // 5

std::cout << std::endl;

ordMap.merge(ordMap2); // 6

std::cout<< "ordMap.merge(ordMap2)" << std::endl;

printContainer(ordMap, " ordMap: ");
printContainer(ordMap2, " ordMap2: ");

std::cout << std::endl;

std::cout << "extract and insert: " << std::endl;

std::multimap<int, std::string> multiMap{{2017, std::string(3, 'F')}};

auto nodeHandle = multiMap.extract(2017); // 7
nodeHandle.key() = 6;
ordMap.insert(std::move(nodeHandle));

printContainer(ordMap, " ordMap: ");
printContainer(multiMap, " multiMap: ");

}

Ich verwende im Beispiel eine std::map, den diese ist meist die erste Wahl, wenn ein assoziativer Container benötigt wird. Falls der assoziative Container sehr groß ist und die Performanz zählt, sollte man natürlich über einen std::unordered_map nachdenken. Im Artikel "Hashtabellen – Ein einfacher Performanzvergleich" präsentiere ich ein paar Performanzzahlen.

Um mir das Leben einfach zu machen, habe ich das Funktions-Template printContainer (2) implementiert. Es erlaubt mir, alle Container mit einem kurzen Titel auszugeben. Die gleiche Argumentation trifft auch auf den Ausdruck using namespace std::literals (1) zu. Dank ihm kann ich das neue C++-String built-in Literal verwenden. In Ausdruck (3) verwende ich es im Schlüssel/Wert Paar: {1, "a"s }. "a"s ist das C++-String Literal, dass seit C++14 zur Verfügung steht. Man muss lediglich den Buchstabe s zu dem C-String Literale "a" hinzufügen. um ein C++-String Literale zu erhalten.

Jetzt gehe ich genauer auf das Programm ein. Um es einfacher nachzuvollziehen, hilft es sicherlich, die Ausgabe im Augenwinkel zu beobachten.

Es gibt zwei neue Arten, Elemente zu assoziativen Container hinzuzufügen: try_emplace. und insert_or_assign.ordMap.try_emplace(3, 3, 'C') versucht, ein neues Element zu dem ordMap hinzuzufügen. Die erste 3 ist der Schlüssel des Elements und die folgende 3 und das 'C' wird direkt vom Konstruktor des Wertes verwendet. In diesem Fall ist der Wert ein std::string. Die Methode heißt try. Daher passiert nichts, wenn der Schlüssel bereits in der std::map ist. ordMap2.insert_or_assign(5, std::string(3, 'e')) (4) verhält sich anders. Der erste Aufruf (4) fügt das Schlüssel/Wert-Paar 5, std::string("eee") hinzu, der zweite Aufruf weist dem Schlüssel 5 den neuen Wert std::string("EEE") zu.

Mit C++17 lassen sich assoziative Container zusammenführen (6). ordMap.merge(ordMap2) führt den assoziativen Container ordMap2 mit ordMap zusammen. Das bedeutet, dass jeder Knoten aus ordMap2 – jeder Knoten besteht aus einem Schlüssel/Wert-Paar – extrahiert und zu ordMap hinzugefügt wird. Formal wird der Vorgang im Englischen splice genannt. Dieses Hinzufügen der Knoten findet aber nur statt, wenn der Schlüssel in ordMap noch nicht existiert. Unter der Decke kommt keine Copy- oder Move-Semantik zum Einsatz. Alle Zeiger und Referenzen der transferierten Knoten bleiben gültig. Du kannst zwischen ähnlichen Container-Knoten transferieren. Assoziative Container müssen dieselbe Struktur und die gleichen Datentypen besitzen.

Das Extrahieren und Einfügen geht weiter (7). Wie ich bereits erwähnte, besitzen jetzt assoziative Container einen neuen Untertyp: einen sogenannten Knoten node_type. Ich habe ihn implizit bereits verwendet, um einen assoziativen Container zu einem anderen hinzuzufügen (6). Der Knoten lässt sich aber auch dazu verwenden, um den Schlüssel eines Schlüssel/Wert-Paares zu verändern. Genau das passiert in (7). auto nodeHandle multiMap.extract(2017) extrahiert den Knoten mit dem Schlüssel 2017 von der std::multimap<int, std::string>. In der anschließenden Zeile ändere ich den Schlüssel auf 6: nodeHandle.key() = 6 und füge ihn zum ordMap hinzu. Dazu muss ich den Knoten verschieben, denn Kopieren ist nicht möglich.

Selbstverständlich kann ich aber auch mit C++17 einen Knoten aus einem assoziativen Container wie std::map, std::unordered_map, std::multimap oder std::unordered_multimap extrahieren und den Schlüssel ändern (A) oder den Knoten einfach nur extrahieren (B). Es lässt sich aber auch der dem Schlüssel assoziierte Wert ändern (C).

auto nodeHandle = multiMap.extract(2017);          // A                      
nodeHandle.key() = 6;
multiMap.insert(std::move(nodeHandle));

auto nodeHandle = multiMap.extract(2017); // B
ordMap.insert(std::move(nodeHandle));

auto nodeHandle = multiMap.extract(2017); // C
nodeHandle.key() = 6;
ordMap.insert(std::move(nodeHandle));
ordMap[6] = std::string("ZZZ");

Falls du einen Knoten von einem assoziativen Container extrahierst (A), der vom Typ std::map, std::multimap, std::unordered_map oder std::unordered_multimap ist, erhältst du einen Knoten nodeHandleMap, auf dem du nodeHandleMap.key() aufrufen kannst. Es gibt aber keine Methode nodeHandleMap.value(), um den assoziierten Wert zu ändern. Es wird noch lustiger. Falls du einen Knoten nodeHandleSet von einem std::set oder einer seiner drei Geschwister extrahierst, kannst du den Schlüssel durch den Aufruf nodeHandleSet.value() ändern.

C++17 erhält drei neue, globale Funktionen, um auf einen Container zuzugreifen.

Vereinheitlichter Zugriff auf einen Container

Die drei neuen Funktionen heißen std::size, std::empty und std::data.

  • std::size: gibt die Länge eines STL-Containers, eines C++-Strings oder eines C++-Arrays zurück.
  • std::empty: gibt zurück, ob der STL-Container, der C++-String oder das C++-Array leer ist.
  • std::data: gibt einen Zeiger auf den Speicherbereich zurück, der die Elemente enthält. Der Container muss die Methode data besitzen. Das trifft auf std::vector, std::string und std::array zu.

Wie geht's weiter?

Gut zehn Artikel habe ich zu C++17 verfasst. Hier sind sie: "Kategorie C++17". Damit bin ich fertig. In den letzten zwei Jahre habe ich sehr viele Artikel über Multithreading geschrieben. Diese Artikel erklärten die Theorie, die Anwendung, Gleichzeitigkeit mit C++17 und C++20 und das Speichermodell. Ich habe ein paar Artikel im Kopf, um meine bestehenden Artikel abzurunden. Daher werde ich die nächsten Artikel über Multithreading im bestehenden und Gleichzeitigkeit in den zukünftigen C++-Standards schreiben. Zuerst muss ich ein paar Begriffe definieren. Daher werde ich über data race versus race condition schreiben. Leider verwenden wir im Deutschen für die zwei Phänomene den einen Begriff kritischer Wettlauf. Das ist sehr unglücklich, denn bei Gleichzeitigkeit ist eine exakte Begrifflichkeit absolut notwendig.