Seite 3: Container und STL

Inhaltsverzeichnis

Verschieben zwischen Sets und Maps

Alle assoziativen und ungeordneten Container definieren neuerdings einen speziellen Subtype node_handle, mit dem Entwickler Elemente von einen Container in einen anderen schieben (splicen) können. Die Datenstruktur und der Elementtyp müsen dabei gleich sein. Das folgende Beispiel zeigt das Verschieben eines Elements in einem Multiset in ein anderes Set:

std::multiset<int> src{1, 1, 3, 5}; 
std::set<int> dst; 
dst.insert(src.extract(1));       // OK, splices first
                                  // element with value 1 

Der Vorteil ist, dass alle Operationen Speicherplatz weder freigegeben noch neu anfordern, da das von extract() gelieferte Objekt vom Typ std::multiset<int>::node_type den internen Speicherplatz hält, der dem Set dst übergeben wird.

Der erneute Versuch, ein Element mit dem Wert 1 zu übertragen, führt in dem Beispiel zu einem Fehler, da im Gegensatz zur Quelle im Ziel keine Duplikate erlaubt sind:

auto r = dst.insert(src.extract(1)); // Fehler, da keine 
                                     // Duplikate erlaubt

In dem Fall ist über r der Zugriff auf das temporär gehaltene Element möglich.

Den Mechanismus können Entwickler auch dazu verwenden, den Schlüssel einer (ungeordneten) Map ohne Speicherplatzoperationen zu verändern:

std::map<int, std::string> m{{1,"mango"}, 
                             {2,"papaya"}, 
                             {3,"guava"}}; 
auto nh = m.extract(2); 
nh.key() = 4; 
m.insert(std::move(nh));  // Fehler ohne move()

Danach hat die Map m den Wert "papaya" unter dem Schlüsselwert 4.

Parallel ausgeführte STL-Algorithmen

Schon lange gab es die Überlegung und Implementierungen, um bei der Ausführung von STL-Algorithmen (Standard Template Library) auszunutzen, dass Rechner mehrere Prozessoren haben können. Entsprechende Mechanismen unter dem Namen "Parallele STL" sind Bestandteil von C++17. Fast alle Algorithmen können jetzt wahlweise sequentiell, parallel oder vektoriell arbeiten.

Dabei müssen Entwickler darauf achten, dass durch die Parallelisierung beziehungsweise Vektorisierung kein undefiniertes Verhalten entsteht.

• "Sequenziell" führt die Algorithmen für alle Elemente wie bisher sequenziell aus.
• "Parallel" bedeutet, dass mehrere "Tasks" (Teilaufgaben oder Elementbearbeitungen) parallel laufen können. Das System führt jede Aufgabe oder Bearbeitung dabei aber jeweils von Anfang bis Ende durch. Entwickler dürfen keine Bearbeitung verwenden, bei der paralleler Zugriff zu einer Race Condition führen könnte.
• "Vektoriell" heißt, dass mehrere "Tasks" parallel ausgeführt und dabei sogar von Teilaufgaben anderer Tasks unterbrochen werden können. Ein Prozessor mag also mit der ersten Anweisung der ersten Teilaufgabe anfangen und dann mit der ersten Anweisung einer anderen Teilaufgabe fortfahren, bevor er die zweite Anweisung der ersten Teilaufgabe angeht.

Ein paar Beispiele sollen die unterschiedlichen Möglichkeiten und Voraussetzungen aufzeigen. Der folgende Code kann vektoriell laufen:

transform (std::execution::par_unseq,
           coll1.begin(),coll1.end(),   // Quelle
           coll2.begin(),               // Ziel
           [] (auto x) {                // Operation
                auto y = x * x;
                return y;
           }); 

Die Reihenfolge, in der die Transformierung der Elemente erfolgt, ist unbedeutend. Ebenso ist es unkritisch, wenn das System erst die erste und dann die zweite Anweisung für alle Elemente durchführt.

Der folgende Code kann parallel, aber nicht vektoriell laufen:

transform (std::execution::par,
           coll1.begin(),coll1.end(),   // Quelle
           coll2.begin(),               // Ziel
           [] (auto x) {                // Operation
             std::lock_guard<mutex> lg(m); 
             return x*x;
           });                     

Verschiedene parallel laufende Threads dürfen den gleichen Lock anfordern, womit sie auf die anderen Threads warten. Ein vektorieller Ansatz könnte jedoch nach Anforderung eines ersten Locks einen zweiten für ein anderes Element anfordern, ohne den ersten freigegeben zu haben. Das kann je nach Mutex zu einer Exception oder einem Deadlock führen.

Der Aufruf:

transform (std::execution::seq,
           coll1.begin(),coll1.end(),   // Quelle
           coll2.begin(),               // Ziel
           op);                         // Operation

entspricht dem bisherigen und natürlich weiter verfügbaren

transform (coll1.begin(),coll1.end(),   // Quelle
           coll2.begin(),               // Ziel
           op);                         // Operation