Modern C++

Unter der sehr ironischen Überschrift ist zunächst die Suche nach so genannten „Happy Numbers”, also glücklichen Zahlen, zu verstehen. Damit sind, ausgehend von einer natürlichen Zahl als Startwert, solche Zahlen gemeint, für die eine bestimmte Iterationsvorschrift nach endlich vielen Iterationsschritten zum Wert 1 führt. Wenn wir dieses Thema näher betrachten, stellen wir fest, dass wir auch manchmal mit Zahlenfolgen konfrontiert sind, die Zyklen enthalten und damit endlos sind. Beim Umschiffen dieser Stolperfalle kommen Schildkröten und Hasen ins Spiel, aber dazu später noch mehr.

Schlussendlich überlegen wir uns, ob constepr auch ein gangbarer Weg sein könnte, um derartige Zahlen zu suchen, eben dann mit dem Übersetzer und nicht mit in Maschinencode gegossenen CPU-Anweisungen.

In dieser Fallstudie stellen wir mehrere Lösungsvarianten zur Berechnung glücklicher Zahlen vor. In einem Nebenschauplatz gehen wir auf Zyklen in verketteten Listen ein. Hashtabellen und die schon zitierten Hasen und Schildkröten helfen uns dabei, die Zyklen zu entdecken und damit das Traversieren von unendlichen Zahlenfolgen zu vermeiden.

Viele Objekte im täglichen „C++”–Alltag zeichnen sich dadurch aus, dass ihre Daten über die beiden Speicherbereiche Stack und Heap verteilt sind. Für das Kopieren derartiger Objekte bedeutet dies, dass es nicht genügt, die auf dem Stack liegenden Verwaltungsdaten „flach” zu kopieren. Auch die Daten auf dem Heap wollen kopiert werden, zumindest wenn man von einer echten („tiefen”) Kopie sprechen möchte.

Interessanter Weise kann man sich eine dritte Art des Kopierens vorstellen, einen Mittelweg zwischen flacher und tiefer Kopie: Wie wäre es, bei einer Kopieranforderung dem Benutzer von Objekt und Objektkopie (hinter den Kulissen) zunächst einmal datentechnisch dasselbe Objekt in die Finger zu geben. Solange keines dieser beiden Objekte verändert wird, besteht ja kein zwingender Handlungsbedarf, eine neue, unabhängige Kopie zu erstellen. Problematisch wird der „faule” Ansatz erst dann, wenn es an einem der beteiligten Objekte zu Änderungen kommt. Jetzt laufen Objekt und Objektkopie inhaltlich auseinander. Es wäre aber immer noch Zeit vorhanden, verspätet – aber eben nicht zu spät – eine echte Kopie des Objekts zu erzeugen, das soeben Änderungen erfährt.

Diesen Ansatz des Kopierens könnte man als „Lazy Copy” bezeichnen, nur hat sich dieser Begriff nicht so wirklich durchgesetzt. Wir sprechen hier meistens von der so genannten „Copy-On-Write”-Strategie. Sprich das Erstellen einer Kopie wird erst dann angegangen, wenn es zu schreibenden Zugriffen auf das Objekt kommt.

Wir betrachten eine „Copy-On-Write”-Realisierung für Zeichenketten in dieser Fallstudie. Neben einem Vergleich der Performanz zwischen der std::string-Klasse aus der STL und unserer selbstgeschriebenen CowString-Klasse kommt auch ein Anwendungsbeispiel zum Zuge.

Und wieder steht etwas Schulmathematik auf dem Programm, dieses Mal geht es um rechtwinklige Dreiecke. Für derartige Dreiecke gibt es den Satz des Pythagoras, er fällt eine Aussage zu den Seitenlängen solcher Dreiecke. Wir wollen im Folgenden nur Dreiecke betrachten, deren Seitenlängen ganzzahlig sind.

Schreiben Sie ein C++–Programm, das für folgende Fragestellung eine Antwort findet: Für welchen Umfang p mit p <= 2000 ist die Anzahl der verschiedenen rechwinkligen Dreiecke mit ganzzahligen Seitenlängen a, b und c am größten?

Hinweis: Die Aufgabenstellung stammt aus dem Repository „Project Euler”: Project Euler ist eine englischsprachige Website, sie enthält eine Reihe von Problemstellungen, die mit Hilfe von Mathematik und Programmierung gelöst werden können. Die Aufgabenstellung dieser Fallstudie finden Sie unter „Problem 39” vor.

Welche Parallelisierungsansätze sind für diese Aufgabenstellung denkbar? Implementieren Sie einen parallelen Algorithmus und vergleichen Sie die Laufzeiten der beiden Varianten. Mit Hilfe der Klassen std::thread, std::function, std::mutex und std::lock_guard gehen wir auf die Realisierung einer Funktion parallel_for ein.

Mit dem Kettenrechnen kehren wir zu den Ursprüngen unserer Grundschulzeit zurück. Für diejenigen unter Ihnen, die dieses Thema aus Ihrem Gedächtnis verdrängt haben: Jede Kettenrechnung beginnt mit einer normalen Rechenaufgabe (z.B. „1 + 3”). Das Resultat muss im Gedächtnis behalten werden, denn es folgt eine weitere Operation (z.B. „* 5”), welche jeweils zum vorhergehenden Resultat gerechnet wird. Das neue Zwischenresultat merkt man sich ebenfalls wieder für die nächste Operation usw. usw. So verlängert sich die „Rechenkette” immer weiter. Im Beispiel der Kettenrechnung 1 + 3 * 5 - 2 * 2 - 8 / 2 sollte man 14 als Endergebnis erhalten.

Entwickeln Sie eine Funktion calc, die eine Kettenrechnung als Parameter übergeben bekommt und ihr Resultat zurückliefert:

int calc (const std::string& chain);

Offensichtlich führen viele Wege zum Ziel einer ansprechenden Realisierung. Im Lösungsteil finden Sie Lösungsansätze vor, die generische Funktionen, heterogene STL-Container, reguläre Ausdrücke und vieles mehr anwenden.

Beginnend mit C++ 11 haben eine Reihe von neuen Sprachfeatures Einzug in die Programmiersprache C++ gefunden, die wir in ihrer Gesamtheit unter dem Begriff C++ 20 subsumieren können:

• Lambda-Funktionen
• Generische Funktionen
• Folding
• Variadische Templates
• Parameter Packs
• Rekursive Parameter Pack Expansion
• IIFE

Sicherlich muss man all diese Konzepte erst einmal alleinstehend für sich betrachten und studieren, um sie zu erfassen und zu verstehen. Dies setze ich für das Studium dieser Fallstudie voraus. Mir kommt es darauf an, all diese Techniken miteinander zu verknüpfen! Genau dies wollen wir an Hand einer Reihe von Beispielen in dieser Fallstudie näher betrachten.

Das Beispiel der dinierenden Philosophen ist eines der populärsten Standardprobleme aus dem Bereich der Parallelprogrammierung. Es erlaubt, die Kooperation der beteiligten Threads in einer lebendigen Simulation darzustellen.

Wir stellen eine Standard-Lösung für dieses Problem vor und gehen dabei vor allem auf die Klasse std::mutex und das RAII-Idiom näher ein. Basiswerkzeuge zur nebenläufigen Programmierung in C++ wie std::async, std::future oder auch std::scoped_lock werden eingesetzt.

Ist eine Menge von n Elementen gegeben, so bezeichnet man die möglichen Anordnungen aller dieser n Elemente als Permutationen (lat. permutare: vertauschen). Die Berechnung der Permutationen einer beliebigen Menge von Elementen steht im Mittelpunkt dieser Fallstudie. Als Elemente verwenden wir zunächst Zeichen, also char-Variablen. Dies soll aber verallgemeinerbar sein, also auch für Variablen eines beliebigen Datentyps funktionieren.

Für zwei Zeichen A und B gibt es nur die zwei Permutationen AB und BA. Drei Zeichen, angenommen A, B und C, können hingegen in sechs verschiedenen Permutationen dargestellt werden: ABC, ACB, BAC, BCA, CAB und CBA. Sind alle n Elemente voneinander verschieden, was wir in dieser Aufgabe zu Grunde legen, so gibt es dafür n! Anordnungen (n-Fakultät).

Die Fakultät ist in der Mathematik eine Funktion, die einer natürlichen Zahl n das Produkt aller natürlichen Zahlen kleiner und gleich dieser Zahl zuordnet: n! = 1 * 2 * 3 * … * n. In der Kombinatorik spielt die Fakultät ebenfalls eine große Rolle, weil n! die Anzahl der Möglichkeiten ist, unterschiedliche Gegenstände der Reihe nach anzuordnen. Bei diesen Überlegungen kommen auch Binomialkoeffizienten ins Spiel. Sie geben an, auf wie viele verschiedene Arten man k Objekte aus einer Menge von n verschiedenen Objekten auswählen kann.

Sowohl Fakultäten als auch Binomialkoeffizienten weisen eine unangenehme Eigenschaft auf: Ihre Werte können sehr schnell sehr groß werden – und sind damit in Variablen des Typs long oder size_t nicht mehr darstellbar. Ein Satz von Legendre verschafft hier Abhilfe: Er befasst sich mit der Frage, wie oft ein Primfaktor in der Primfaktorzerlegung von n! für ein n ∈ N vorkommt – um damit eine alternative Darstellung für Fakultäten und Binomialkoeffizienten zu ermöglichen, die das Problem des Überlaufs umgehen kann.

Wir betrachten in dieser Fallstudie die Berechnung von Fakultäten und Binomialkoeffizienten sowohl in ihrer klassischen Definition als auch mit Hilfe des Satzes von Legendre als Produkt von Primfaktorzerlegungen.

Die Notation eines mathematischen Ausdrucks, wie wir ihn aus der Mathematik kennen, zum Beispiel 2 * (7 + 5), bezeichnet man als Infix-Notation. Das Gegenstück dazu heißt Postfix-Notation oder UPN (umgekehrte polnische Notation, engl. reverse polish notation oder abgekürzt RPN). Die umgekehrte polnische Notation wurde 1920 von dem Polen Jan Lukasiewicz erfunden, um mathematische Ausdrücke ohne Vorrangregeln (Klammern) schreiben zu können.

In dieser Fallstudie behandeln wir einen Taschenrechner für arithmetische Ausdrücke in UPN-Darstellung. Reguläre Ausdrücke (std::sregex_iterator, smatch) und Type Traits (std::is_integral, std::is_floating_point) fließen neben anderen Modern C++–Sprachmitteln in der Implementierung mit ein.

Wir betrachten in dieser Fallstudie das Thema „Expression Templates” und damit in Zusammenhang stehend die Technik der genannten „Lazy Evaluation”. Auf einen einfachen Nenner gebracht: „Expression Templates” sind ein Anwendungsfall der Metaprogrammierung. Sie verschieben die Aus­wertung von Ausdrücken in eine separate Funktion, die zu einem späteren Zeitpunkt ausgeführt werden kann. An dieser Stelle wird der Begriff der „Lazy Evaluation” verständlich. Wir betrachten das Thema am Beispiel der Verknüpfung von Zeichenketten, also beispielsweise an einem Ausdruck in der Art

std::string result = "123"s + "ABC"s + "456"s + "XYZ"s + "789"s;

Mit „Expression Templates” lernen Sie einen alternativen Ansatz kennen, einen geschachtelten (arithmetischen) Ausdruck zu berechnen mit dem Vorteil, nahezu alle temporären Objekte zu vermeiden, die bei der klassischen Berechnung eines solchen Ausdrucks entstehen würden.