| 23.4.4 | Partielles Sortieren |
Teilweises Sortieren bringt die M kleinsten Elemente nach vorn, der Rest bleibt unsortiert. Der Algorithmus verlangt jedoch nicht die Zahl M, sondern einen Iterator middle auf die entsprechende Position, sodass M = middle - first gilt. Die Prototypen sind:
Der im letzten Fall zurückgegebene Iterator ist r.end(). Die Komplexität ist ca. O(NlogM). Der Programmauszug für einen Vektor v zeigt die teilweise Sortierung. Im Ergebnis sind in der ersten Hälfte alle Elemente kleiner als in der zweiten. In der ersten Hälfte sind sie darüber hinaus sortiert, in der zweiten jedoch nicht.
Beide Varianten gibt es auch in einer kopierenden Form, wobei result_first beziehungsweise result_last sich auf den Zielcontainer beziehen. Die Anzahl N der sortierten Elemente ergibt sich aus der kleineren der beiden Differenzen result_last - result_first bzw. last - first. Der Ausgabebereich enthält also die ersten N Elemente in einer comp entsprechenden sortierten Reihenfolge.
Der zurückgegebene Random-Access-Iterator zeigt auf das Ende des beschriebenen Bereichs, also auf (result_first + N). Die ranges-Variante ist:
copy_result enthält {in: r1.end(), out: r2.begin() + N}. Das Listing 23.45 zeigt die Anwendung der Algorithmen.
Listing 23.45: Partielles Sortieren (cppbuch/k23/sortieren/partialsort.cpp)
#include <Random.h> #include <algorithm> #include <showContainer.h> #include <vector> using namespace std; int main() { vector<int> v(10); Random zufall(1000); for (auto& wert : v) { // Vektor mit Zufallswerten initialisieren wert = zufall(); } cout << "Vektor:˽"; showContainer(v); auto mitte {ssize(v)/2}; ranges::partial_sort(v, v.begin() + mitte ); cout << "Die˽" << mitte << "˽kleinsten˽Werte˽liegen˽sortiert˽in˽der˽ersten˽Hälfte,\n" "der˽Rest˽ist˽unsortiert:\n"; showContainer(v); constexpr int groessten {3}; vector<int> vmax(groessten); ranges::partial_sort_copy(v, vmax, greater<int>{}); cout << "Die˽" << groessten << "˽größten˽Elemente˽sind˽"; showContainer(vmax); }
| 23.4.5 | Das n.-größte oder n.-kleinste Element finden |
Das n.-größte oder n.-kleinste Element einer Sequenz mit Random-Access-Iteratoren kann mit nth_element() gefunden werden.
Der Iterator nth wird auf die gewünschte Stelle gesetzt, zum Beispiel auf den Beginn des Containers. Nach Aufruf von nth_element() ist das kleinste Element an diese Stelle gerutscht. Die Reihenfolge der Elemente im Container wird also geändert. Falls nth vor Aufruf zum Beispiel auf die Position v.begin() + 6 zeigt, steht dort anschließend das siebtkleinste Element.
Nach Aufruf des Algorithmus stehen links von nth alle Elemente, die kleiner oder gleich (*nth) sind. Der Aufwand des Algorithmus ist im Durchschnitt linear (O(N)). Das Beispiel ermittelt das kleinste und das größte Element sowie den Medianwert. Der Medianwert teilt eine Folge, sodass die eine Hälfte der Werte größer gleich und die andere Hälfte der Werte kleiner gleich dem Medianwert ist.
Listing 23.46: n.-größtes und n.-kleinstes Element finden (cppbuch/k23/sortieren/nth.cpp)
#include <Random.h> #include <algorithm> #include <deque> #include <showContainer.h> using namespace std; int main() { deque<int> d; Random zufall(100); for (unsigned int i = 0; i < 15; ++i) { d.push_front(zufall()); } showContainer(d); auto nth = d.begin(); ranges::nth_element(d, nth); cout << "Kleinstes˽Element:˽" << (*nth) << ’\n’; // Das Standardvergleichsobjekt greater dreht die Reihenfolge um. // In diesem Fall steht das größte Objekt an der ersten Position. // Hier ist immer noch nth == d.begin(). ranges::nth_element(d, nth, greater<>()); cout << "Größtes˽Element˽:˽" << (*nth) << ’\n’; // Mit dem < -Operator steht das größte Element am Ende: nth = d.end(); --nth; // zeigt nun auf das letzte Element ranges::nth_element(d, nth); cout << "Größtes˽Element˽:˽" << (*nth) << ’\n’; // Median nth = d.begin() + ssize(d) / 2; ranges::nth_element(d, nth); cout << "Medianwert˽:˽" << (*nth) << ’\n’; }
| 23.4.6 | Verschmelzen (merge) |
Verschmelzen, auch Mischen genannt, ist ein Verfahren, zwei sortierte Sequenzen zu einer zu vereinigen. Dabei werden schrittweise die jeweils ersten Elemente beider Sequenzen verglichen und das kleinere (oder größere, je nach Sortierkriterium) Element in die Ausgabesequenz gepackt. Die Prototypen sind:
Zurückgegeben wird result.end(). Der Rückgabetyp der ranges-Variante ist eine Struktur mit drei Iteratoren, wie partition_copy_result auf Seite 758.
merge() setzt eine vorhandene Ausgabesequenz voraus, die ausreichend Platz haben muss. Falls eine der beiden Eingangssequenzen erschöpft ist, wird der Rest der anderen in die Ausgabe kopiert. Ein kleines Programm soll dies zeigen:
Listing 23.47: Sortieren durch Verschmelzen (cppbuch/k23/sortieren/merge0.cpp)
#include <algorithm> #include <showContainer.h> #include <vector> using namespace std; int main() { vector<int> folge1{0, 1, 2, 3, 4, 5}; showContainer(folge1); vector<int> folge2{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; showContainer(folge2); vector<int> result(folge1.size() + folge2.size()); // Platz schaffen // Verschmelzen zweier Folgen v1 und v2, Ablage in result ranges::merge(folge1, folge2, result.begin()); showContainer(result); }
Das Ergebnis des Programms in Listing 23.47 ist:
Vom Prinzip her erlaubt das Verschmelzen sehr schnelles Sortieren der Komplexität O(NlogN) nach dem rekursiven Schema:
1. Teile die Liste in zwei Hälften.
2. Falls die Hälften mehr als ein Element haben, sortiere beide Hälften mit diesem Verfahren (Rekursion).
3. Beide Hälften zur Ergebnisliste verschmelzen.
Eine nichtrekursive Variante ist natürlich möglich. Die Sortierung ist stabil. Der Nachteil besteht im notwendigen zusätzlichen Speicher für das Ergebnis. Zum Vergleich mit dem obigen Schema ist der Merge-Sort genannte Algorithmus mit den Mitteln der C++-Standardbibliothek in der Datei cppbuch/k23/sortieren/mergesort.h (nicht abgedruckt) formuliert (ohne dass er selbst dazugehört!). Der Vorteil des hier beschriebenen Algorithmus gegenüber stable_sort() besteht darin, dass nicht nur Container, die mit Random-Access-Iteratoren zusammenarbeiten, sortiert werden können. Es genügen bidirektionale Iteratoren, sodass v im obigen Programm auch eine Liste sein kann. Sie kann mit push_front() gefüllt werden. Voraussetzung ist nur, dass eine Liste buffer vorhanden ist, die mindestens so viele Elemente wie v hat. Die Anwendung auf eine Liste finden Sie in der Datei cppbuch/k23/sortieren/mergesortlist.cpp.
Verschmelzen an Ort und Stelle (inplace_merge)
Hier wird der Pufferspeicher intern und implementationsabhängig bereitgestellt, sodass man sich nicht selbst darum kümmern muss. Die Funktion inplace_merge() mischt Sequenzen so, dass das Ergebnis an die Stelle der Eingangssequenzen tritt. Die Prototypen sind:
Listing 23.48: inplace_merge() (cppbuch/k23/sortieren/merge1.cpp)
#include <algorithm> #include <showContainer.h> #include <vector> int main() { std::vector<int> v(16); // gerade Zahl const auto middle = ssize(v) / 2; for (int i = 0; i < middle; ++i) { v[i] = 2 * i; // gerade v[middle + i] = 2 * i + 1; // ungerade } showContainer(v); std::ranges::inplace_merge(v, v.begin() + middle); showContainer(v); }
Die erste Hälfte eines Vektors wird hier mit geraden Zahlen belegt, die zweite mit ungeraden. Nach dem Verschmelzen enthält derselbe Vektor alle Zahlen, ohne dass explizit ein Ergebnisbereich angegeben werden muss:
| 23.5 | Suchen und Finden |
| 23.5.1 | Element finden |
Der Algorithmus find() tritt in zwei Arten auf: ohne und mit erforderlichem Prädikat (als find_if() und find_if_not()). Es wird die Position in einem Container gesucht, an der ein bestimmtes Element zu finden ist. Ggf. muss das Prädikat gelten (find_if()) oder nicht gelten (find_if_not()). Das Ergebnis ist ein Iterator, der auf die gefundene Stelle zeigt oder gleich dem Ende-Iterator end() ist. Die Prototypen sind:
Im folgenden Beispiel wird nur die ranges-Variante von find_if() gezeigt. Es wird die erste ungerade Zahl im Vektor v gesucht. Statt der Lambda-Funktion wäre ein Funktor einsetzbar.
Listing 23.49: Erste ungerade Zahl suchen (cppbuch/k23/finden/findif.cpp)
#include <algorithm> #include <iostream> #include <showContainer.h> #include <vector> using namespace std; int main() { vector<int> v{2, 4, 6, 8, 99, 12, 14}; // enthält ungerade Zahl showContainer(v); // nach ungerader Zahl suchen auto iter = ranges::find_if(v, [](int x) { return x % 2 != 0; }); if (iter != v.end()) { cout << "Die˽erste˽ungerade˽Zahl˽(" << *iter << ")˽wurde˽an˽Position˽" << (iter - v.begin()) << "˽gefunden.\n"; } else { cout << "Keine˽ungerade˽Zahl˽gefunden.\n"; } }
| 23.5.2 | Element einer Menge in der Folge finden |
Der Algorithmus findet das erste Auftreten eines Elements einer Menge innerhalb einer Sequenz. Die Prototypen sind:
Das Intervall [first1, last1) ist der zu durchsuchende Bereich, das Intervall [first2, last2) beschreibt einen Bereich mit zu suchenden Elementen. Zurückgegeben wird der erste Iterator i im zu durchsuchenden Bereich, der auf ein Element zeigt, das auch im zweiten Bereich vorhanden ist. Es sei angenommen, dass ein Iterator j auf das Element im zweiten Bereich zeigt. Dann gilt
Falls kein Element aus dem ersten Bereich im zweiten Bereich gefunden wird, gibt der Algorithmus last1 zurück. Die Komplexität ist O(N1 ∗ N2), wenn N1 und N2 die Längen der Bereiche sind. Die ranges-Variante ist:
Der Bereich r1 ist der zu durchsuchende Bereich, der Bereich r2 derjenige mit den zu suchenden Elementen. Das Programm in Listing 23.50 gibt aus:
Listing 23.50: Erstes Auftreten finden (cppbuch/k23/finden/findfirstof.cpp)
#include <algorithm> #include <showContainer.h> #include <vector> using namespace std; int main() { vector<int> folge{0, 2, 4, 6, 8, 10, 12, 14}; vector<int> menge1{1, 5, 7}; vector<int> menge2{1, 6, 7}; // Zwei Tests: for (int testnummer = 0; testnummer < 2; ++testnummer) { const auto& menge = (testnummer == 0 ? menge1 : menge2); cout << "Ist˽eines˽der˽Elemente˽der˽Menge˽("; showContainer(menge, ""); cout << ")˽in˽der˽Folge\n"; showContainer(folge, ""); cout << "˽enthalten?\n"; // Suche nach Element, das auch in der Menge enthalten ist auto iter = ranges::find_first_of(folge, menge); if (iter != folge.end()) { cout << "Ja.˽Element˽" << *iter << "˽ist˽in˽beiden˽Bereichen˽vorhanden.˽Sein˽erstes˽Vorkommen" "˽in˽der˽Folge˽ist˽Position˽" << (iter - folge.begin()) << ".\n"; } else { cout << "Nein.\n"; } } }
| 23.5.3 | Teilfolge finden |
Der Algorithmus search() durchsucht eine Sequenz, ob eine zweite in ihr enthalten ist. Es wird ein Iterator auf die Position innerhalb der ersten Sequenz zurückgegeben, an der die zweite Sequenz beginnt, sofern sie in der ersten enthalten ist. Andernfalls wird ein Iterator auf die last1-Position der ersten Sequenz zurückgegeben. Die Prototypen sind:
Geht es darum, das letzte Auftreten einer Teilfolge zu finden, bietet sich der Algorithmus find_end() an (siehe unten). Ein Beispiel für search():
Listing 23.51: Teilfolge finden (cppbuch/k23/finden/search.cpp)
#include <algorithm> #include <cstdlib> // abs() #include <iostream> #include <showContainer.h> #include <vector> using namespace std; int main() { vector<int> folge{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; cout << "Folge˽=˽"; showContainer(folge); vector<int> teilfolge(folge.begin() + 5, folge.begin() + 9); // 5 6 7 8 cout << "Teilfolge˽=˽"; showContainer(teilfolge); // Teilfolge in Folge suchen auto iter = ranges::search(folge, teilfolge).begin(); if (iter != folge.end()) { cout << "˽Die˽Teilfolge˽ist˽in˽der˽Folge˽ab˽Position˽" << (iter - folge.begin()) << "˽enthalten.\n"; } else { cout << "Die˽Teilfolge˽ist˽nicht˽in˽der˽Folge˽enthalten.\n"; } // Fall2: binäres Prädikat. Dafür negative Zahlen setzen for (auto& el : teilfolge) { el = -el; // -5 -6 -7 -8 } cout << "Teilfolge˽=˽"; showContainer(teilfolge); // Teilfolge in Folge suchen, dabei Vorzeichen ignorieren iter = ranges::search(folge, teilfolge, [](int x, int y) { return abs(x) == abs(y); }).begin(); if (iter != folge.end()) { cout << "˽Die˽Teilfolge˽ist˽in˽der˽Folge˽ab˽Position˽" << (iter - folge.begin()) << "˽enthalten.˽Vorzeichen˽wurden˽ignoriert.\n"; } else { cout << "Die˽Teilfolge˽ist˽nicht˽in˽der˽Folge˽enthalten.\n"; } }
| 23.5.4 | Teilfolge mit speziellem Algorithmus finden |
Dieser Algorithmus leistet dasselbe wie der vorherstehende, nur dass ein spezieller Algorithmus für den Suchvorgang übergeben wird. Der Prototyp ist:
Mögliche Objekte des Typs Searcher sind:
default_searcher (implementierungsabhängiger Algorithmus)
boyer_moore_searcher (Boyer-Moore-Algorithmus)
boyer_moore_horspool_searcher (Boyer-Moore-Horspool-Algorithmus)
Diese Algorithmen eignen sich für sehr lange Folgen. Eine weitergehende Beschreibung übersteigt den Rahmen dieses Buchs.
Letztes Auftreten einer Teilfolge finden
Der Algorithmus findet das letzte Auftreten einer Teilfolge innerhalb einer Sequenz. Die Prototypen sind:
Das Intervall [first1, last1) ist der zu durchsuchende Bereich, das Intervall [first2, last2) beschreibt die zu suchende Folge. Zurückgegeben wird der letzte Iterator im zu durchsuchenden Bereich, der auf den Beginn der Teilfolge zeigt. Falls die Teilfolge nicht gefunden wird, gibt der Algorithmus last1 zurück. Falls der zurückgegebene Iterator mit i bezeichnet wird, gilt
für alle n im Bereich 0 bis (last2-first2). Die Komplexität ist O(N2(N1 – N2)), wenn N1 und N2 die Länge des zu durchsuchenden Bereichs bzw. der zu suchenden Teilfolge sind. Die ranges-Variante ist
Die Benutzung entspricht der von search(), sodass hier nur ein Auszug eines Beispiels gezeigt wird:
| 23.5.5 | Bestimmte benachbarte Elemente finden |
Zwei gleiche, direkt benachbarte (englisch adjacent) Elemente werden mit der Funktion adjacent_find() gefunden. Es gibt auch hier zwei überladene Varianten – eine ohne und eine mit binärem Prädikat. Die erste Variante vergleicht die Elemente mit dem Gleichheitsoperator ==, die zweite benutzt das Prädikat. Die Prototypen sind:
Der zurückgegebene Iterator zeigt auf das erste der beiden Elemente, sofern ein entsprechendes Paar gefunden wird. Beispiel:
Listing 23.53: Gleiche benachbarte Elemente finden (cppbuch/k23/finden/adjacentfind.cpp)
#include <algorithm> #include <showContainer.h> #include <vector> using namespace std; int main() { vector<int> v{0, 2, 4, 6, 99, 99, 8, 10, 12}; // 2 gleiche benachbarte Elemente (99) showContainer(v); auto iter = ranges::adjacent_find(v); // finde gleiche Nachbarn if (iter != v.end()) { cout << "Die˽ersten˽gleichen˽benachbarten˽Zahlen˽(" << *iter << ")˽wurden˽an˽Position˽" << (iter - v.begin()) << "˽gefunden.\n"; } else { cout << "Keine˽gleichen˽Nachbarn˽gefunden.\n"; } }
Wenn zum Beispiel nach einem doppelt so großen Nachfolger gesucht werden soll, kommt ein binäres Prädikat zum Einsatz. Der entsprechende Aufruf, um den doppelt so großen Nachfolger zu finden, lautet mit einer Lambda-Funktion:
Die Auswertung kann wie oben mit der Iterator-Differenz (iter - v.begin()) geschehen.
| 23.5.6 | Bestimmte aufeinanderfolgende Werte finden |
Der Algorithmus search_n() durchsucht eine Sequenz daraufhin, ob eine Folge von gleichen Werten in ihr enthalten ist. Die Prototypen sind:
Zurückgegeben wird von der ersten Funktion der Iterator auf den Beginn der ersten Folge mit wenigstens count Werten, die gleich value sind. Falls eine derartige Folge nicht gefunden wird, gibt die Funktion last zurück. Die zweite Funktion prüft nicht auf Gleichheit, sondern wertet das binäre Prädikat aus. Im Erfolgsfall muss für wenigstens count aufeinanderfolgende Werte X das Prädikat binary_pred(X, value) gelten. Die ranges-Variante ist
Im Listing 23.55 wird erst gesucht, ob der Wert 4 mindestens dreimal nacheinander auftritt. Dann wird gesucht, ob es mindestens dreimal nacheinander Werte gibt, die größer als vier sind:
Listing 23.55: Aufeinanderfolgende Werte suchen, die einer Bedingung genügen (cppbuch/k23/finden/searchn.cpp)
#include <algorithm> #include <showContainer.h> #include <vector> using namespace std; int main() { vector<int> folge{0, 1, 3, 4, 4, 4, 5, 6, 7, 8, 1, 3}; // Die Folge enthält drei aufeinanderfolgende gleiche Werte cout << "Folge˽=˽"; showContainer(folge); constexpr int wert{4}; constexpr int wieoft{3}; auto position {ranges::search_n(folge, wieoft, wert).begin()}; if (position != folge.end()) { cout << wert << "˽wird˽" << wieoft << "-mal˽nacheinander˽ab˽Position˽" << (position - folge.begin()) << "˽gefunden.\n"; } else { cout << wert << "˽wird˽nicht˽" << wieoft << "-mal˽nacheinander˽gefunden.\n"; } position = ranges::search_n(folge, wieoft, wert, greater<>()).begin(); if (position != folge.end()) { cout << "Ab˽Position˽" << (position - folge.begin()) << "˽werden˽" << wieoft << "-mal˽nacheinander˽Werte˽größer˽als˽" << wert << "˽gefunden.\n"; } else { cout << wieoft << "-mal˽nacheinander˽Werte˽größer˽als˽" << wert << "˽sind˽nicht˽vorhanden.\n"; } }
| 23.5.7 | Binäre Suche |
Alle Algorithmen dieses Abschnitts sind Variationen der binären Suche. Wenn ein wahlfreier Zugriff mit einem Random-Access-Iterator auf eine sortierte Folge mit n Elementen möglich ist, ist die binäre Suche sehr schnell. Es werden maximal 1+log2n Zugriffe benötigt, um das Element zu finden oder festzustellen, dass es nicht vorhanden ist. Falls ein wahlfreier Zugriff nicht möglich ist, wie zum Beispiel bei einer Liste, in der man sich von Element zu Element hangeln muss, um ein bestimmtes Element zu finden, ist die Zugriffszeit von der Ordnung O(n). Die C++-Standardbibliothek stellt die Algorithmen binary_search, lower_bound, upper_bound und equal_range bereit, die im Zusammenhang mit dem Suchen und Einfügen in sortierte Folgen sinnvoll sind und sich algorithmisch sehr ähneln:
binary_search
Dies ist die eigentliche binäre Suche. Die Funktion gibt true zurück, falls der Wert value gefunden wird. In der ersten Variante wird der Operator < benutzt, indem die Beziehung
betrachtet wird (Äquivalenz). i ist ein Iterator im Bereich [first, last). Falls ein Bereich mit einem Vergleichsobjekt comp sortiert wurde, muss dies bei der Suche berücksichtigt werden (zweite Variante). Es wird entsprechend
ausgewertet. Die Äquivalenzbeziehung entspricht nicht in jedem Fall der Gleichheit. Beim Vergleich ganzer Zahlen mit dem <-Operator fallen beide Begriffe zusammen. Aber: Im Duden werden Umlaute bei der Sortierung wie Selbstlaute behandelt. Die Wörter Mucke und Mücke stehen beide vor dem Wort mucken. Obwohl ungleich, sind sie doch äquivalent bezüglich der Sortierung. Ein Beispiel für binary_search() wird nach Vorstellung der nächsten drei Algorithmen gezeigt.
lower_bound
Dieser Algorithmus findet die erste Stelle, an der ein Wert value eingefügt werden kann, ohne die Sortierung zu stören. Der zurückgegebene Iterator, er sei hier i genannt, zeigt auf diese Stelle, sodass ein Einfügen ohne weitere Suchvorgänge mit insert(i, value) möglich ist. Für alle Iteratoren j im Bereich [first, i) gilt, dass *j < value ist bzw. comp(*j, value) == true. Die Prototypen sind:
upper_bound
Dieser Algorithmus findet die letzte Stelle, an der ein Wert value eingefügt werden kann, ohne die Sortierung zu stören. Der zurückgegebene Iterator i zeigt auf diese Stelle, sodass ein schnelles Einfügen mit insert(i, value) möglich ist. Die Prototypen sind:
equal_range
Dieser Algorithmus ermittelt den größtmöglichen Bereich, innerhalb dessen an jeder beliebigen Stelle ein Wert value eingefügt werden kann, ohne die Sortierung zu stören. Bezüglich der Sortierung enthält dieser Bereich also äquivalente Werte. Die Prototypen sind:
Die Elemente p.first und p.second des zurückgegebenen Iteratorpaars, hier p genannt, begrenzen den Bereich. Für jeden Iterator k, der die Bedingung p.first ≤ k ≤ p.second erfüllt, ist schnelles Einfügen mit insert(k, value) möglich.
Das zurückgegebene Ergebnis ist ein Bereich von Iteratoren. Die range-Varianten der beschriebenen Algorithmen werden anhand des Listings 23.56 demonstriert, wobei die Funktion upper_bound() wegen der Ähnlichkeit mit lower_bound() nicht aufgeführt ist. Die Sortierung des Containers muss gewährleistet sein, weil alle Algorithmen dieses Abschnitts dies voraussetzen.
Listing 23.56: binary_search() und Verwandte (cppbuch/k23/finden/binarysearch.cpp)
#include <algorithm> #include <showContainer.h> #include <string> #include <string_view> #include <vector> using namespace std; int main() { vector<string_view> staedte{"Bremen", "Paris", "Mailand", "Hamburg"}; ranges::sort(staedte); // Wichtige Vorbedingung! showContainer(staedte); string stadt(""); cout << "Welche˽Stadt˽eintragen/suchen?˽"; cin >> stadt; if (ranges::binary_search(staedte, stadt)) { cout << stadt << "˽existiert.\n"; } else { cout << stadt << "˽existiert˽noch˽nicht.\n"; } cout << stadt << "˽wird˽eingefügt:\n"; auto i = ranges::lower_bound(staedte, stadt); // an der richtigen Stelle einfügen staedte.insert(i, stadt); showContainer(staedte); auto r = ranges::equal_range(staedte, stadt); // Bereich gleicher Werte // Die zwei Iteratoren des Bereichs r begrenzen den Bereich, in dem stadt vorkommt. auto n = distance(r.begin(), r.end()); cout << stadt << "˽ist˽" << n << "˽mal˽im˽Vector˽enthalten\n"; }
| 23.6 | Mengenoperationen auf sortierten Strukturen |
Die folgenden Algorithmen beschreiben die grundlegenden Mengenoperationen wie Vereinigung, Durchschnitt usw. auf sortierten Strukturen. In der C++-Standardbibliothek basiert auch die Klasse set auf sortierten Strukturen (siehe Abschnitt 27.4.1). Die Komplexität der Algorithmen ist O(N1 + N2), wobei N1 und N2 die jeweilige Anzahl der Elemente der beteiligten Mengen sind. Mengenoperationen auf sortierten Strukturen sind nur unter bestimmten Bedingungen sinnvoll und Randbedingungen sind zu beachten.
Standardcontainer aus Kapitel 27: vector, list, deque
Der Ergebniscontainer bietet ausreichend Platz. Nachteil: Nach dem Ende der Ergebnissequenz stehen noch alte Werte im Container, falls der Platz mehr als genau ausreichend ist.
Der Output-Iterator darf nicht identisch mit v1.begin() oder v2.begin() sein. v1 und v2 sind die zu verknüpfenden Mengen.
Der Ergebniscontainer ist leer. In diesem Fall ist ein Insert-Iterator als Output-Iterator zu nehmen.
Assoziative Container: set, map
Grundsätzlich ist ein Insert-Iterator zu nehmen. Der Inhalt eines Elements darf nicht direkt, das heißt über eine Referenz auf das Element, geändert werden. So würde sich ein nicht einfügender Output-Iterator verhalten und die Sortierung innerhalb des Containers und damit seine Integrität würde verletzt.
| 23.6.1 | Teilmengenrelation |
Die Funktion includes gibt an, ob jedes Element einer zweiten sortierten Struktur S2 in der ersten Struktur S1 enthalten ist, also eine Teilmenge der ersten ist. Der Rückgabewert ist true, falls S2 ⊆ S1 gilt, ansonsten false. Die Prototypen sind:
Das Listing 23.57 initialisiert einige set-Objekte als sortierte Strukturen. Man kann an deren Stelle natürlich auch schlichte Vektoren nehmen, vorausgesetzt, sie sind sortiert. Weil das Beispiel in den weiteren Abschnitten aufgegriffen wird, enthält es bereits hier mehr, als für includes() notwendig ist. Im Unterschied zu den meisten Beispielen dieses Abschnitts enthalten die folgenden Listings die Algorithmen aus dem Namespace std, nicht die aus dem Namespace std::ranges. Der Grund ist, dass die Ergebnisse ebenfalls Sets sein sollen. Die zum Erzeugen verwendete inserter()-Funktion bestückt die Ergebnismenge mit genau der richtigen Anzahl von Einträgen, kann aber bei den ranges-Algorithmen nicht verwendet werden. Letztere würden als Ergebnistyp, für den ein Ausgabe-Iterator angegeben wird, einen Vektor oder ein C-Array akzeptieren, die von vornherein mit ausreichend Platz ausgestattet sind. Nicht genutzter Platz bleibt allerdings bestehen, d.h., ab einem bestimmten Index gibt es undefinierte Elemente. Meines Erachtens ist es sinnvoll, wenn Operationen auf Sets selbst wieder Sets ergeben.
Listing 23.57: Operationen auf Mengen (Auszug aus cppbuch/k23/setalgorithmen.cpp)
#include <algorithm> #include <set> #include <showContainer.h> using namespace std; int main () { // Sets initialisieren. Vergleichsobjekt: less<int>() (implizite automatische Sortierung). set<int> s1 {1, 2, 3, 4}; set<int> s2 {0, 1, 2, 3, 4, 5, 7, 99, 13}; set<int> s3 {-2, 5, 12, 7, 33}; if (includes(s2.begin(), s2.end(), s1.begin(), s1.end())) { showContainer(s1); // 1 2 3 4 cout << "˽ist˽eine˽Teilmenge˽von˽"; showContainer(s2); // 0 1 2 3 4 5 7 99 } // Fortsetzung nächster Abschnitt
| 23.6.2 | Vereinigung |
Die Funktion set_union bildet eine sortierte Struktur, in der alle Elemente enthalten sind, die in wenigstens einer von zwei anderen sortierten Strukturen S1 und S2 vorkommen. Es wird die Vereinigung beider Strukturen gebildet:
S = S1 ∪ S2
Voraussetzung ist, dass die aufnehmende Struktur genügend Platz bietet oder dass sie leer ist und ein Insert-Iterator als Output-Iterator verwendet wird. Die Prototypen sind:
Der zurückgegebene Iterator hat den Wert result.end();
Die zurückgegebene Struktur set_result enthält drei Iteratoren mit den Werten {in1: r1.end(), in2: r2.end(), out: result.end()}.
Die Ergebnismenge result (siehe unten) ist anfangs leer. Im folgenden Beispiel muss der Output-Iterator ein Insert-Iterator sein. Dazu wird die Funktion inserter(), die auf Seite 902 beschrieben ist, in der Parameterliste aufgeführt. Sie gibt einen Insert-Iterator zurück. Nur result.begin() als Output-Iterator zu verwenden, führt bei sets zu Fehlern.
Listing 23.58: Fortsetzung des Listings 23.57
set<int> result; // leere Menge // inserter() verlangt als zweiten Parameter einen Iterator. Da result // ein set ist, ist der Wert irrelevant, kann also auch result.end() sein. set_union(s1.begin(), s1.end(), s3.begin(), s3.end(), inserter(result, result.begin())); showContainer(s1); // 1 2 3 4 cout << "˽vereinigt˽mit˽"; showContainer(s3); // -2 5 7 12 33 cout << "˽ergibt˽"; showContainer(result); // -2 1 2 3 4 5 7 12 33 // Fortsetzung nächster Abschnitt
| 23.6.3 | Schnittmenge |
Die Funktion set_intersection bildet eine sortierte Struktur, in der alle Elemente enthalten sind, die sowohl in der einen als auch in der anderen von zwei sortierten Strukturen S1 und S2 vorkommen. Es wird die Schnittmenge oder der Durchschnitt beider Strukturen gebildet:
S = S1 ∩ S2
Die Prototypen sind:
Zu den Rückgabetypen siehe Abschnitt 23.6.2. Um die alten Ergebnisse zu löschen, wird clear() aufgerufen. Andernfalls würden sie mit ausgegeben.
Listing 23.59: Fortsetzung des Listings 23.58
result.clear(); // zuerst Set leeren set_intersection(s2.begin(), s2.end(), s3.begin(), s3.end(), inserter(result, result.begin())); showContainer(s2); // 0 1 2 3 4 5 7 99 cout << "˽geschnitten˽mit˽"; showContainer(s3); // -2 5 7 12 33 cout << "˽ergibt˽"; showContainer(result); // 5 7 // Fortsetzung des Listings im nächsten Abschnitt
| 23.6.4 | Differenz |
Die Funktion set_difference bildet eine sortierte Struktur, in der alle Elemente enthalten sind, die in der ersten Struktur S1, aber nicht in einer zweiten sortierten Struktur S2 vorkommen. Es wird die Differenz S1 – S2 beider Strukturen gebildet, auch als S1\S2 geschrieben. Die Prototypen sind:
Zu den Rückgabetypen siehe Abschnitt 23.6.2. Das Beispiel folgt dem obigen Muster:
Listing 23.60: Fortsetzung des Listings 23.59
result.clear(); set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(), inserter(result, result.begin())); showContainer(s2); // 0 1 2 3 4 5 7 99 cout << "˽minus˽"; showContainer(s1); // 1 2 3 4 cout << "˽ergibt˽"; showContainer(result); // 0 5 7 99 // Fortsetzung des Listings im nächsten Abschnitt
| 23.6.5 | Symmetrische Differenz |
Die Funktion set_symmetric_difference bildet eine sortierte Struktur, in der alle Elemente enthalten sind, die entweder in der ersten Struktur S1 oder in einer zweiten sortierten Struktur S2 vorkommen, aber nicht in beiden. Es wird die symmetrische Differenz beider Strukturen gebildet, auch als Exklusiv-Oder bezeichnet. Mit den vorangegangenen Operationen kann die symmetrische Differenz ausgedrückt werden:
S = (S1 – S2) ∪ (S2 – S1) oder S = (S1 ∪ S2) – (S2 ∩ S1). Die Prototypen sind:
Zu den Rückgabetypen siehe Abschnitt 23.6.2. Das letzte Beispiel dieser Art zeigt die symmetrische Differenz:
Listing 23.61: Fortsetzung und Ende des Listings von oben
result.clear(); set_symmetric_difference(s2.begin(), s2.end(), s3.begin(), s3.end(), inserter(result, result.begin())); showContainer(s2); // 0 1 2 3 4 5 7 99 cout << "˽˽exklusiv˽oder˽"; showContainer(s3); // -2 5 7 12 33 cout << "˽ergibt˽"; showContainer(result); // -2 0 1 2 3 4 12 33 99 } // Ende von cppbuch/k23/setalgorithmen.cpp
| 23.7 | Heap-Algorithmen |
Die in Abschnitt 27.3.3 beschriebene Priority-Queue basiert auf einem binären Heap (englisch für Haufen oder Halde). Vor der Beschreibung der Heap-Algorithmen seien kurz die wichtigsten Eigenschaften der Datenstruktur Heap (nicht zu verwechseln mit dem ebenfalls Heap genannten Freispeicher) charakterisiert:
Die N Elemente eines Heaps liegen in einem kontinuierlichen Array auf den Positionen 0 bis N – 1. Es wird vorausgesetzt, dass ein wahlfreier Zugriff möglich ist (Random-Access-Iterator).
Die Art der Anordnung der Elemente im Array entspricht einem vollständigen binären Baum, bei dem alle Ebenen mit Elementen besetzt sind. Die einzig mögliche Ausnahme bildet die unterste Ebene, in der alle Elemente auf der linken Seite erscheinen. Abbildung 23.1 zeigt die Array-Repräsentation eines Heaps H mit 14 Elementen, wobei die Zahlen in den Kreisen die Array-Indizes darstellen (nicht die Elementwerte). Das Element H[0] ist also stets die Wurzel und jedes Element H[j] mit (j > 0) hat einen Elternknoten H[(j – 1)/2].
Jedem Element H[j] ist eine Priorität zugeordnet, die größer oder gleich der Priorität der Kindknoten H[2j + 1] und H[2j + 2] ist. Hier und im Folgenden sei zur Vereinfachung angenommen, dass große Zahlen hohe Prioritäten bedeuten. Im Allgemeinen kann es auch umgekehrt sein oder es können gänzlich andere Kriterien die Priorität bestimmen. Abbildung 23.2 zeigt beispielhafte Elementwerte eines Heaps: H[0] ist gleich 98 usw.
Beachten Sie, dass der Heap nicht vollständig sortiert ist, sondern dass es nur auf die Prioritätsrelation zwischen Eltern- und zugehörigen Kindknoten ankommt.
Ein Array H mit N Elementen ist genau dann ein Heap, wenn H[(j – 1)/2] ≥ H[j] für 1 ≤ j < N gilt. Daraus folgt automatisch, dass H[0] das größte Element ist. Eine Priority-Queue entnimmt einfach immer das oberste Element eines Heaps. Anschließend wird er restrukturiert, das heißt, das nächstgrößte Element wandert an die Spitze. Bezogen auf die Abbildungen 23.1 und 23.2 wäre dies das Element Nr. 2 mit dem Wert 57.
Die C++-Standardbibliothek bietet Heap-Algorithmen für alle Container, auf die mit Random-Access-Iteratoren zugegriffen werden kann.
pop_heap() entfernt das Element mit der höchsten Priorität.
push_heap() fügt ein Element einem vorhandenen Heap hinzu.
make_heap() arrangiert alle Elemente innerhalb eines Bereichs, sodass dieser Bereich einen Heap darstellt.
sort_heap() verwandelt einen Heap in eine sortierte Folge.
Diese Algorithmen müssen keine Einzelheiten über die Container wissen. Ihnen werden lediglich zwei Iteratoren übergeben, die den zu bearbeitenden Bereich markieren. Zwar ist less<T> als Prioritätskriterium vorgegeben, aber vielleicht wird ein anderes Kriterium gewünscht. Daher gibt es für jeden Algorithmus eine überladene Variante, welche die Übergabe eines Vergleichsobjekts erlaubt.
pop_heap
Die Funktion pop_heap() entnimmt ein Element aus einem Heap. Der Bereich2 [first, last) sei dabei ein gültiger Heap. Die Prototypen sind:
ranges::pop_heap() gibt r.end() zurück. In den folgenden Listings werden die Heap-Algorithmen des Namespace std verwendet, nicht die des Namespace std::ranges. Letztere verlangen etwas mehr Codieraufwand, wie der Vergleich der Dateien heap.cpp mit heapranges.cpp im Verzeichnis cppbuch/k23/ zeigt.
Die Entnahme besteht nur darin, dass der Wert mit der höchsten Priorität, der an der Stelle first steht, mit dem Wert an der Stelle (last -1) vertauscht wird. Anschließend wird der Bereich [first, last-1) in einen Heap verwandelt. Die Komplexität von pop_heap() ist O(log(last – first)). Anwendung für einen Vektor v:
Listing 23.62: Heap-Operationen (Auszug aus cppbuch/k23/heap.cpp)
make_heap(v.begin(), v.end()); //gültigen Heap erzeugen (Seite 784) // Die beiden Zahlen mit der höchsten Priorität anzeigen und entnehmen: auto last = v.end(); cout << *v.begin() << ’\n’; pop_heap(v.begin(), last--); cout << *v.begin() << ’\n’; pop_heap(v.begin(), last--);
Hinweis
Bitte beachten Sie, dass nicht mehr v.end() das Heap-Ende anzeigt, sondern der Iterator last. Der Bereich dazwischen ist bezüglich der Heap-Eigenschaften von v undefiniert.
push_heap
Die Funktion push_heap() fügt ein Element einem vorhandenen Heap hinzu. Wie die Prototypen zeigen, werden der Funktion nur zwei Iteratoren und gegebenenfalls ein Vergleichsobjekt übergeben. Das einzufügende Element tritt hier nicht auf:
Es muss die Vorbedingung gelten, dass der Bereich [first, last) ein gültiger Heap ist. push_heap() kümmert sich nicht selbst um den einzutragenden Wert. An die Stelle last wird deshalb vorher der auf den Heap abzulegende Wert eingetragen. Der anschließende Aufruf von push_heap(first, ++last) sorgt dafür, dass nach dem Aufruf der Bereich [first, last) ein Heap ist. Die Komplexität von push_heap() ist O(log(last–first)). In den Beispiel-Heap werden nun zwei Zahlen wie beschrieben eingefügt (das vorhergehende Beispiel wird fortgesetzt):
Beim Einfügen muss beachtet werden, dass last nicht über v.end() hinausläuft. Durch die Tatsache, dass bei der Entnahme immer der Wert mit der höchsten Priorität an die Spitze gesetzt wird, ist die Ausgabe sortiert:
make_heap
make_heap() sorgt dafür, dass die Heap-Bedingung für alle Elemente innerhalb eines Bereichs gilt. Die Prototypen sind:
Die Komplexität ist proportional zur Anzahl der Elemente zwischen first und last. Das Beispiel von oben zeigt die Anwendung auf einem Vektor als Container:
sort_heap
sort_heap() verwandelt einen Heap in eine sortierte Sequenz. Die Sortierung ist nicht stabil, die Komplexität ist O(NlogN), wenn N die Anzahl der zu sortierenden Elemente ist. Die Prototypen sind:
Die Sequenz ist aufsteigend sortiert. Damit ist gemeint, dass die Elemente hoher Priorität an das Ende der Sequenz kommen:
Übung
23.1 Gegeben sei die Template-Klasse Heap mit den folgenden Schnittstellen:
Die letzte Methode gibt den Heap-Inhalt als sortierten Vektor zurück. Implementieren Sie die Klasse unter Verwendung einiger Algorithmen des Abschnitts 23.7. Testen Sie die Klasse, indem Sie nach jeder Änderung prüfen, ob die Heap-Eigenschaft noch gilt. Dazu lässt sich der Algorithmus is_heap des folgenden Abschnitts einsetzen.
is_heap
is_heap() gibt zurück, ob ein Bereich den Heap-Kriterien genügt. Gegebenenfalls kann ein Vergleichsobjekt übergeben werden.
Ergänzend dazu gibt es die Algorithmen is_heap_until(first, last) und is_heap_until( first, last, comp), die den letzten Iterator im Bereich [first, last) zurückgeben, bis zu dem der Bereich als Heap angesehen werden kann.
| 23.8 | Vergleich von Containern auch ungleichen Typs |
| 23.8.1 | Unterschiedliche Elemente finden |
mismatch() überprüft zwei Container auf Übereinstimmung ihres Inhalts, wobei einige Varianten ein binäres Prädikat benutzen. Die Prototypen sind:
Falls last2 nicht explizit angegeben wird, wird last2 == first2 + (last1 - first1) angenommen. Falls der zweite Bereich weniger Elemente hat, ist das Ergebnis fehlerhaft. Deswegen gibt es diese zusätzlichen Varianten:
Diese Varianten stellen sicher, dass nur so viele Vergleiche stattfinden, dass keiner der Bereiche überschritten wird. Die Algorithmen geben jeweils ein Paar P von Iteratoren zurück, die auf die erste Stelle der Nichtübereinstimmung in den jeweiligen korrespondierenden Containern zeigen. Im Fall der std-Algorithmen ist es ein pair-Objekt mit den Elementen {first, second}, im Fall des std::ranges-Algorithmus eine Struktur mit den Elementen {in1, in2}. Bei Übereinstimmung gilt, wobei die Größen der Bereiche mit size1 (= last1 - first1) und size2 (= last2 - first2) abgekürzt seien:
Die Container müssen nicht vom selben Typ sein. In dem Beispiel wird ein Vektor v mit einem Set s verglichen:
Listing 23.63: Prüfung auf (Nicht-)Übereinstimmung (cppbuch/k23/mismatch.cpp)
#include <algorithm> #include <set> #include <showContainer.h> #include <vector> using namespace std; int main() { vector<int> v{0, 2, 4, 6, 8, 10, 12, 14}; // sortierte Folge set<int> s(v.begin(), v.end()); // Set initialisieren v[3] = 7; // Nichtübereinstimmung erzeugen showContainer(v); // Anzeige showContainer(s); // Prüfung mit Iterator Paar wo // auto: pair<vector<int>::iterator, set<int>::iterator> auto wo{mismatch(v.begin(), v.end(), s.begin())}; if (wo.first == v.end()) { cout << "Inhalt˽der˽Container˽stimmt˽überein.\n"; } else { cout << "Der˽erste˽Unterschied˽(" << *wo.first << "˽!=˽" << *wo.second << ")˽wurde˽an˽Position˽" << (wo.first - v.begin()) << "˽gefunden.\n"; } }
Eine indexartige Position ist in einem Set nicht definiert, deswegen ist ein Ausdruck der Art (wo.second - s.begin()) ungültig. Zwar zeigt wo.second auf die Stelle der Nichtübereinstimmung in s, aber die Arithmetik ist nicht erlaubt. Wenn man die relative Nummer bezüglich des ersten Elements in s unbedingt benötigt, kann man distance() verwenden.
Die Variante mit dem binären Prädikat ist geeignet, wenn es um nicht exakte Übereinstimmung geht. Wenn etwa berechnete Resultate, die mit Rundungsfehlern behaftet sind, verglichen werden sollen, genügt es, wenn die Ergebnisse innerhalb einer gewissen Genauigkeit übereinstimmen. Im folgenden Beispiel werden zwei nicht genau gleiche Container als übereinstimmend betrachtet. Wenn der Schwellenwert 0.01 auf z.B. 0.005 abgesenkt wird, werden Unterschiede angezeigt.
Listing 23.64: Prüfung mit binärem Prädikat (cppbuch/k23/mismatchranges.cpp)
#include <Random.h> #include <algorithm> #include <cmath> // fabs() #include <showContainer.h> #include <vector> using namespace std; int main() { vector<double> v1(8); vector<double> v2(8); Random zufall(100); for (auto i {0z}; i < ssize(v1); ++i) { v1[i] = i + zufall() / 10000.0; v2[i] = i + zufall() / 10000.0; } showContainer(v1); // Anzeige showContainer(v2); // Prüfung auf einen Schwellenwert 0.01 mit Iterator Paar wo: auto wo = ranges::mismatch(v1, v2, [](auto x, auto y) { return fabs(x - y) < 0.01; }); if (wo.in1 == v1.end()) { cout << "Inhalt˽der˽Container˽stimmt˽innerhalb˽der˽Toleranz˽überein.\n"; } else { cout << "Der˽erste˽Unterschied˽(" << *wo.in1 << "˽!=˽" << *wo.in2 << ")˽wurde˽an˽Position˽" << (wo.in1 - v1.begin()) << "˽gefunden.\n"; } }
| 23.8.2 | Prüfung auf gleiche Inhalte |
equal() überprüft zwei Container auf Übereinstimmung ihres Inhalts, wobei eine Variante ein binäres Prädikat benutzt. Im Unterschied zu mismatch() wird jedoch kein Hinweis auf die Position gegeben. Wie am Rückgabetyp bool erkennbar, wird nur festgestellt, ob die Übereinstimmung besteht oder nicht. Die Prototypen sind:
Wie im vorherigen Abschnitt und mit derselben Begründung gibt es auch die robusteren Varianten mit einem zusätzlichen End-Iterator. Diese Varianten geben auf jeden Fall false zurück, wenn die Bereiche unterschiedlich groß sind.
| 23.9 | Rechnen mit komplexen Zahlen: Der C++-Standardtyp complex |
Tabelle 23.1 enthält die Funktionen, die mit komplexen Zahlen verwendet werden können. Komplexe Zahlen werden in den Natur- und Ingenieurwissenschaften viel verwendet. Sie bestehen aus dem Real- und dem Imaginärteil, die beide von einem der möglichen Typen für reelle Zahlen sein können (float, double, long double). Der Standarddatentyp für komplexe Zahlen ist deshalb kein Grunddatentyp, sondern zusammengesetzt. Weil die beiden Bestandteile eines complex-Objekts von einem der Typen float, double oder long double sein können, sind komplexe Zahlen als Klassen-Template realisiert.
Die für den Compiler nötigen Informationen enthält der Header <complex>. Einige Beispiele zeigen, wie mit komplexen Zahlen in C++ gerechnet wird. Die Verwendung des Suffixes i erlaubt eine abkürzende Schreibweise. Die Grundlagen für diese Technik kennen Sie von Abschnitt 8.9.2. Statt i ist auch il (für complex<long double>) oder if (für complex<float>) einsetzbar.
Tabelle 23.1: Mathematische Funktionen für complex-Zahlen
Schnittstelle |
mathematische Entsprechung |
T real(const C& x) |
Realteil von x (= x.real()) |
T imag(const C& x) |
Imaginärteil von x (= x.imag()) |
T abs(const C& x) |
Betrag von x |
T arg(const C& x) |
Phasenwinkel von x in rad |
T norm(const C& x) |
Betragsquadrat von x |
C conj(const C& x) |
zu x konjugiert-komplexe Zahl |
C proj(const C& x) |
Projektion von x auf die Riemann-Kugel |
C polar(const T& rho, const T& theta) |
Zahl entsprechend Betrag rho und Phase theta |
C acos(const C& x) |
acos x |
C acosh(const C& x) |
acosh x |
C asin(const C& x) |
asin x |
C asinh(const C& x) |
asinh x |
C atan(const C& x) |
atan x |
C atanh(const C& x) |
atanh x |
C cos(const C& x) |
cos x |
C cosh(const C& x) |
cosh x |
C exp(const C& x) |
ex |
C log(const C& x) |
ln x |
C log10(const C& x) |
log10 x |
C pow(const C& x, const T& y) |
xy |
C pow(const T& x, const C& y) |
xy |
C pow(const C& x, const C& y) |
xy |
C sin(const C& x) |
sin x |
C sinh(const C& x) C sqrt(const C& x) |
sinh x |
C tan(const C& x) |
tan x |
C tanh(const C& x) |
tanh x |
+Abkürzungen: T = einer der Typen float, double oder long double, C = complex<T>
Mit komplexen Zahlen kann wie mit reellen Zahlen gerechnet werden. Ausgenommen sind nur die Operatoren ++, -- und %. Auch die Prüfung auf Gleichheit (==) oder Ungleichheit (!=) ist möglich. Die anderen Vergleichsoperatoren ergeben bei komplexen Zahlen keinen Sinn.
Übung
23.2 Schreiben Sie ein Programm zur Lösung der quadratischen Gleichung x2 + px + q = 0, wobei Sie komplexe √Zahlen für das √Ergebnis verwenden. Die Lösungsformeln: 
Eine komplexe Lösung ergibt sich, wenn D < 0 ist.
| 23.10 | Vermischtes |
| 23.10.1 | Erkennung eines Datums |
Mithilfe eines regulären Ausdrucks soll überprüft werden, ob ein Datum der Form tt.mm.jjjj gültig ist. Dabei soll es auch möglich sein, nur eine Ziffer für den Tag bzw. den Monat einzugeben. Da hier nur die Gültigkeit interessiert und nicht, wo sich ein gültiges Datum innerhalb einer Zeichenkette befindet, genügt die Abfrage mit regex_match(). Ein passender regulärer Ausdruck (von vielen möglichen) ist \d\d?\.\d\d?\.\d\d\d\d. Das Listing 23.66 zeigt die Anwendung; auf mögliche Probleme wird danach eingegangen.
Listing 23.66: Syntaktische Gültigkeit eines Datums (cppbuch/k23/vermischtes/regex/datumsyntaxpruefen.cpp)
#include <iostream> #include <regex> #include <string> [[nodiscard]] bool datumok(const std::string& eingabe) { std::regex datumregex("\\d\\d?\\.\\d\\d?\\.\\d\\d\\d\\d"); return std::regex_match(eingabe, datumregex); } using namespace std; int main(int argc, char* argv[]) { if (2 != argc) { cout << "Gebrauch:˽" << argv[0] << "˽Datum,˽z.B.˽tt.mm.jjjj\n"; } else { try { if (datumok(argv[1])) { cout << argv[1] << "˽ist˽ein˽syntaktisch˽gültiges˽Datum.\n"; } else { cout << argv[1] << "˽ist˽kein˽gültiges˽Datum.\n"; } } catch (regex_error& re) { cerr << "Fehler:˽" << re.what() << ’\n’; } } }
Syntax oder Semantik?
Am obigen Beispiel wird sofort ein Problem klar: 00.0.0000 ist ein ungültiges Datum, wird aber vom Programm als gültiges Datum interpretiert. Der Grund liegt darin, dass das Programm nur die vorgegebene Syntax prüft, aber die Semantik (Bedeutung) des Inhalts ignoriert. Was tun? Es gibt verschiedene Abstufungen der Prüfung:
1. Die einfachste Syntaxprüfung ist die oben dargestellte. Um die Gültigkeit zu prüfen, müssen Tag, Monat und Jahr aus dem String extrahiert werden, um dann die Gültigkeit zu prüfen.
2. Man kann aber auch in Erwägung ziehen, bereits bei der syntaktischen Analyse die Gültigkeit der Daten zu überprüfen. Für den Tag gibt es folgende Möglichkeiten:
Wenn der Tag einstellig ist, liegt die Ziffer im Bereich [1-9].
Ist die erste Ziffer eine 0, liegt die zweite im Bereich [1-9].
Ist die erste Ziffer eine 1 oder eine 2, liegt die zweite im Bereich [0-9].
Ist die erste Ziffer eine 3, liegt die zweite im Bereich [0-1].
Der erste und der zweite Punkt werden mit dem regulären Ausdruck 0?[1-9] realisiert, der dritte mit (1|2)\d, der vierte mit 3[01]. Der reguläre Ausdruck für den Tag einschließlich des Punkts kann damit als (0?[1-9])|((1|2)\d)|(3[01])\. formuliert werden. Für den Monat gilt:
Wenn der Monat einstellig ist oder mit einer 0 beginnt, liegt die Ziffer vor dem Punkt im Bereich [1-9].
Wenn der Monat zweistellig ist, kann die erste Ziffer nur eine 1 sein und die zweite liegt im Bereich [0-2].
Der reguläre Ausdruck für den Monat einschließlich des Punkts kann damit als (0?[1-9])|(1[0-2])\. formuliert werden.
3. Mit der vorstehenden Lösung ist aber noch nicht alles erreicht, denn manche Monate haben nur 30 Tage, der Februar sogar nur 28 bzw. 29 in einem Schaltjahr. 30 oder 28 Tage lassen sich mit einigem Aufwand in der Syntax berücksichtigen, aber das Schaltjahr nur noch mit sehr großem, unverhältnismäßigem Aufwand.
Man sieht, dass der Aufwand recht hoch getrieben werden kann. Bei der Überprüfung von Dialogeingaben oder von einer Datei eingelesenen Informationen ist daher abzuwägen, wie der Gesamtaufwand aus Syntaxprüfung und inhaltlicher Prüfung minimiert werden kann.
Empfehlung
Einfache reguläre Ausdrücke bevorzugen, ergänzt durch eine inhaltliche Prüfung.
Diese Empfehlung entspricht dem obigen Punkt 1. Sie erspart Planungs- und Rechenzeitaufwand. Die Funktion datumok() des obigen Listings wird dazu ersetzt durch die folgende:
Listing 23.67: Gültigkeit eines Datums (Auszug aus cppbuch/k23/vermischtes/regex/datumpruefen.cpp)
[[nodiscard]] bool datumok(const std::string& eingabe) { std::regex datumregex("\\d\\d?\\.\\d\\d?\\.\\d\\d\\d\\d"); bool ergebnis = std::regex_match(eingabe, datumregex); if (ergebnis) { // Syntax ok, Inhalt prüfen auto v = splitAsVector(eingabe, "."); Datum(std::stoi(v[0]), std::stoi(v[1]), std::stoi(v[2])); // Exception bei Fehler } return ergebnis; }
| 23.10.2 | Erkennung einer IPv4-Adresse |
Die Lösung dieses Problem lässt sich auf das vorhergehende zurückführen. Eine IPv4-Adresse hat vier durch einen Punkt getrennte Felder, wobei jedes Feld aus einer vorzeichenlosen Zahl mit maximal drei Ziffern besteht. Ein möglicher regulärer Ausdruck ist \d\d?\d?\.\d\d?\d?\.\d\d?\d?\.\d\d?\d? oder kürzer (?:\d\d?\d?\.){3}\d\d?\d?. Es gilt die Bedingung, dass jede Zahl höchstens den Wert 255 annehmen kann. Im Folgenden ist nur die überprüfende Funktion gezeigt:
Listing 23.68: Gültigkeit einer IPv4-Adresse (Auszug aus cppbuch/k23/vermischtes/regex/IPv4adressepruefen.cpp)
bool ip4ok(const std::string& eingabe) { std::regex datumregex("(?:\\d\\d?\\d?\\.){3}\\d\\d?\\d?"); bool ergebnis = std::regex_match(eingabe, datumregex); if (ergebnis) { // Syntax ok, Inhalt prüfen auto v = split(eingabe, "."); // split() siehe S. 714 for (auto i = 0u; i < v.size(); ++i) { ergebnis = ergebnis && std::stoi(v[i]) < 256; } } return ergebnis; }
| 23.10.3 | Erzeugen von Zufallszahlen |
[ISOC++] enthält einen großen Abschnitt über die Erzeugung von (Pseudo-)Zufallszahlen. Der Abschnitt ist für dieses Buch zu umfangreich und eher aus mathematischer Sicht als aus programmiersprachlicher Sicht interessant. Deshalb beschränke ich mich auf die am häufigsten genutzten Möglichkeiten:
1. ganze gleichverteilte Zufallszahlen
2. reelle gleichverteilte Zufallszahlen
3. zufällig erzeugte Wahrheitswerte
4. normalverteilte Zufallszahlen
Die Erzeugung der Zufallszahlen wird von einem Generator übernommen. Es gibt nach [ISOC++] mehrere Generatoren. In diesem Buch wird der Zufallszahlengenerator mt19937 verwendet. Es gibt auch andere, die zum Teil mit etwas weniger Rechenzeit und Speicher auskommen, aber nicht ganz so hohen Ansprüchen an die Zufälligkeit genügen, etwa default_random_engine. Auch sie wären für die Zwecke dieses Buchs geeignet. Der Generator erzeugt unsigned int-Zahlen:
Das ist natürlich nicht komfortabel. Daher gibt es Verteilungen, denen der gewünschte Zahlenbereich mitgegeben wird. Beim Aufruf wird der entsprechende Generator übergeben, wie Sie unten in den Beispielen sehen.
Reproduzierbarkeit
Für alle gezeigten Verfahren gilt, dass die berechneten Zufallswerte reproduzierbar, also pseudo-zufällig sind. Erneutes Starten eines Programms liefert dieselbe Zahlenfolge. Entscheidend für die Reihenfolge der Zahlen ist die Initialisierung des Zufallszahlengenerators mit den Funktionen seed(unsigned seed). Die Reproduzierbarkeit erleichtert das Testen. Um bei jedem Programmstart eine andere Zahlenfolge zu erreichen, kann man den Generator mit random_device initialisieren:
Alternativ kann rd() der seed-Funktion übergeben werden.
Gleichverteilung ganzer Zahlen
Der Gleichverteilung ganzer Zahlen wird mit uniform_int_distribution realisiert. Dem Konstruktor der Verteilung wird der gewünschte Bereich übergeben. In vielen Beispielen dieses Buchs werden gleichverteilte ganze Zufallszahlen benötigt. Deshalb wird die Erzeugung in einer eigenen Klasse Random gekapselt. Die Datei Random.h liegt im include-Verzeichnis der Beispiele. Ein Random-Objekt wird mit den Grenzwerten bzw. dem Grenzwert initialisiert. Gegebenenfalls kann mit setSeed(size_t newseed) ein Anfangswert für eine andere Zufallsfolge eingestellt werden. Durch Überladen des ()-Operators kann das Objekt wie eine Funktion benutzt werden.
Listing 23.70: Zufallszahlengenerator (cppbuch/include/Random.h)
#ifndef RANDOM_H #define RANDOM_H #include <limits> #include <random> class [[nodiscard]] Random { public: explicit Random(int min, int max) : verteilung(min, max) {} explicit Random(int max = std::numeric_limits<int>::max()) : verteilung(0, max) {} void setSeed(unsigned int newseed) { generator.seed(newseed); } [[nodiscard]] int operator()() { return verteilung(generator); // Pseudo-Zufallszahl zwischen min und max } private: std::mt19937 generator; std::uniform_int_distribution<> verteilung; // <>: Vorgabe ist int }; #endif
Die Eigenschaft »Funktionsobjekt« kann gut zusammen mit manchen Standardalgorithmen benutzt werden, siehe zum Beispiel generate_n() in Abschnitt 23.3.3. Im folgenden Beispiel werden 100000 Zufallszahlen zwischen 10 und 20 erzeugt. Zur Kontrolle werden die Häufigkeiten für jeden Wert und der berechnete Mittelwert ausgegeben.
Listing 23.71: Erzeugung gleichverteilter int-Zufallszahlen (cppbuch/k23/zufallszahlen/gleichverteilungInt.cpp)
#include <Random.h> #include <iostream> #include <vector> using namespace std; int main() { constexpr int minimum{10}; constexpr int maximum{20}; static_assert(maximum > minimum, "maximum˽muss˽>˽minimum˽sein!"); constexpr int iterationen{100000}; vector<int> haeufigkeit(maximum - minimum + 1, 0); Random zufall(minimum, maximum); random_device rd; // zufall.setSeed(rd()); // ohne ’//’: keine Reproduzierbarkeit // Zufallszahl erzeugen, dabei die Häufigkeit hochzählen: for (int i = 0; i < iterationen; ++i) { ++haeufigkeit[zufall() - minimum]; } // Häufigkeiten und Mittelwert ausgeben double summe = 0.0; for (auto i {0z}; i < ssize(haeufigkeit); ++i) { auto wert = i + minimum; cout << wert << ":˽" << haeufigkeit[i] << ’\n’; summe += wert * haeufigkeit[i]; } cout << "Mittelwert:˽" << summe / iterationen << ’\n’; }
Gleichverteilung reeller Zahlen
Die Gleichverteilung reeller Zahlen wird mit uniform_real_distribution realisiert. Der Datentyp kann double, long double oder float sein. Das Beispiel zeigt die Erzeugung gleichverteilter double-Zahlen im Bereich [0, 1]. Der Mittelwert liegt dann bei etwa 0.5.
Listing 23.72: Erzeugung gleichverteilter double-Zufallszahlen (cppbuch/k23/zufallszahlen/gleichverteilungReal.cpp)
#include <iostream> #include <random> int main() { std::mt19937 zufall; std::uniform_real_distribution<double> verteilung(0.0, 1.0); constexpr int iterationen{1000000}; double summe{0.0}; for (int i = 0; i < iterationen; ++i) { summe += verteilung(zufall); } std::cout << "Mittelwert:˽" << summe / iterationen << ’\n’; }
Normalverteilung
Neben der Gleichverteilung ist die Normalverteilung am bekanntesten, charakterisiert durch die Gaußsche Glockenkurve. Sie wird insbesondere in der Messtechnik verwendet. So gehorchen die Abweichungen vom Sollmaß bei der industriellen Herstellung von Werkstücken der Normalverteilung. Das folgende Beispiel berechnet 1000000 normalverteilte Zufallszahlen, wobei zur Veranschaulichung das Ergebnis auf der Konsole ausgegeben wird (Abbildung 23.3).
Listing 23.73: Erzeugung normalverteilter Zufallszahlen (cppbuch/k23/zufallszahlen/normalverteilung.cpp)
#include <algorithm> #include <cmath> #include <iostream> #include <random> #include <vector> using namespace std; int main() { constexpr double minimum{-3.0}; // darzustellender Bereich constexpr double maximum{3.0}; constexpr int intervalle{80}; // Auflösung der Ausgabe (Spalten) constexpr int zeilen = 20; // Auflösung der Ausgabe (Zeilen) constexpr double intervallbreite{(maximum - minimum) / intervalle}; constexpr int iterationen = 1000000; vector<int> haeufigkeit(intervalle, 0); normal_distribution<> gauss(0.0, 1.0); // Mittelwert, Standardabweichung mt19937 generator; random_device rd; generator.seed(rd()); // jedes Mal neue Werte // Zufallszahl erzeugen, dabei die Häufigkeit hochzählen for (int i = 0; i < iterationen; ++i) { double wert = gauss(generator); if (wert > minimum && wert < maximum) { auto index = lround((wert - minimum) / intervallbreite); // runden ++haeufigkeit[index]; } // else.. Außenbereiche ignorieren } // Grobe Darstellung der Glockenkurve auf der Konsole int max = *max_element(haeufigkeit.begin(), haeufigkeit.end()); for (int i = 0; i < zeilen; ++i) { for (int j = 1; j < intervalle; ++j) { double grenze = static_cast<double>(haeufigkeit[j]) * zeilen / max + 0.5; cout << (grenze <= (zeilen - i) ? ’˽’ : ’*’); } cout << ’\n’; } }
Zufällig erzeugte Wahrheitswerte
Manchmal möchte man, dass ein Ereignis mit einer gewissen Wahrscheinlichkeit eintritt, zum Beispiel bei der Simulation eines Sechser-Wurfs beim Würfeln. Dazu ist die Bernoulli-Verteilung geeignet. Sie liefert true mit einer Wahrscheinlichkeit p und false mit einer Wahrscheinlichkeit 1 – p. Falls p nicht angegeben wird, gilt p = 0.5.
Listing 23.74: Wahrscheinlichkeit, sechs Augen zu würfeln (cppbuch/k23/zufallszahlen/wuerfel.cpp)
#include <iostream> #include <random> #include <vector> int main() { std::mt19937 zufall; std::bernoulli_distribution verteilung(1.0 / 6.0); constexpr int iterationen{1000000}; int anzahl_der_Sechsen{0}; // oder Einsen, oder Zweien ... for (int i = 0; i < iterationen; ++i) { if (verteilung(zufall)) { // 6 Augen? anzahl_der_Sechsen++; } } std::cout << "Bei˽" << iterationen << "˽Wuerfen˽wurde˽" << anzahl_der_Sechsen << "˽mal˽die˽6˽geworfen˽(" << (100.0 * anzahl_der_Sechsen / iterationen) << "˽%).\n"; }
Diese Verteilung lässt sich alternativ mit der Verteilung uniform_real_distribution realisieren, wenn der Zahlenbereich 0.0 bis 1.0 ist. Das Ergebnis ist dann true, wenn die Zufallszahl < p ist.
| 23.10.4 | for_each — auf jedem Element eine Funktion ausführen |
Die Algorithmen for_each bzw. for_each_n bewirken, dass auf jedem Element eines Containers im Intervall [first, last) bzw. [first, first + n) eine Funktion ausgeführt wird. Die Deklarationen sind:
f kann sowohl eine Funktion (aber keine Methode einer Klasse) als auch ein Funktionsobjekt sein und wird nach Gebrauch zurückgegeben.
for_each_result ist eine Struktur mit den Elementen {in, F} und dem Wert {r.end(), std::move(f)}. Das Listing 23.75 zeigt die Ausgabe aller Elemente eines Vektors. Der Rückgabewert wird hier ignoriert, im Listing 23.76 jedoch ausgewertet.
Listing 23.75: Algorithmus for_each (cppbuch/k23/vermischtes/foreach.cpp)
#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { vector<int> v{ 77, 5, 6, 1, 2, 9, 10}; for_each(v.begin(), v.end(), [](int x) { cout << x << ’˽’;}); cout << "˽˽˽std::for_each()\n"; ranges::for_each(v, [](int x) { cout << x << ’˽’;}); cout << "˽˽˽std::ranges::for_each()\n"; }
Das Listing 23.76 zeigt die Auswertung des zurückgegebenen Funktors, der in diesem Fall alle Werte aufsummiert.
Listing 23.76: for_each und Funktorauswertung (cppbuch/k23/vermischtes/foreach1.cpp)
#include <algorithm> #include <iostream> #include <vector> struct Sum { void operator()(int x) { std::cout << x << ’˽’; summe += x; } int summe = 0; }; using namespace std; int main() { vector<int> v{ 77, 5, 6, 1, 2, 9, 10}; auto f = for_each(v.begin(), v.end(), Sum()); cout << "Summe˽=˽" << f.summe << ’\n’; auto [last, f1] = ranges::for_each(v, Sum()); cout << "Summe = " << f1.summe << ’\n’; }
| 23.10.5 | Verschiedene Möglichkeiten, Container-Bereiche zu kopieren |
Der Algorithmus copy() kopiert die Elemente eines Quellbereichs in den Zielbereich, wobei das Kopieren am Anfang oder am Ende der Bereiche (mit copy_backward()) beginnen kann. Falls der Zielbereich nicht überschrieben, sondern in ihn eingefügt werden soll, ist als Output-Iterator ein Iterator zum Einfügen (Insert-Iterator) zu nehmen. Der Algorithmus copy() ist immer dann zu nehmen, wenn Ziel- und Quellbereich sich nicht oder so überlappen, dass der Anfang des Quellbereichs im Zielbereich liegt. result muss zu Beginn auf den Anfang des Zielbereichs zeigen. Zur Verdeutlichung der Wirkungsweise sind hier ausnahmsweise nicht die Prototypen, sondern mögliche Definitionen gezeigt:
Der Algorithmus copy_backward() ist immer dann zu nehmen, wenn Ziel- und Quellbereich sich so überlappen, dass der Anfang des Zielbereichs im Quellbereich liegt. result muss anfangs auf das Ende des Zielbereichs zeigen.
Auch hier gilt wie allgemein in der C++-Standardbibliothek, dass last nicht die Position des letzten Elements bezeichnet, sondern die Position nach dem letzten Element. result darf niemals zwischen first und last liegen. Wie Abbildung 23.4 zeigt, sind drei Fälle zu berücksichtigen:
a) Die Bereiche sind vollständig getrennt. Die Bereiche können in demselben oder in verschiedenen Containern liegen. result zeigt auf den Beginn des Zielbereichs. copy() kopiert den Quellbereich beginnend mit *first. Zurückgegeben wird result + (last - first), also die Position nach dem letzten Element des Zielbereichs.
b) Die Bereiche überlappen sich so, dass der Zielbereich vor dem Quellbereich beginnt. result zeigt auf den Beginn des Zielbereichs. copy() kopiert den Quellbereich beginnend mit *first. Wie bei a) wird die Position nach dem letzten Element des Zielbereichs zurückgegeben.
c) Die Bereiche überlappen sich so, dass der Zielbereich mitten im Quellbereich beginnt. Um die Daten nicht zu zerstören, muss vom Ende her beginnend kopiert werden. result zeigt auf die Position direkt nach dem Ende des Zielbereichs. copy_backward() kopiert den Quellbereich, indem zuerst *(--last) an die Stelle --result kopiert wird. Hier wird result - (last - first) zurückgegeben, also die Position des zuletzt kopierten Elements im Zielbereich.
Listing 23.77: Beispiele für verschiedene Fälle
// v1 nach v2 kopieren copy(v1.begin(), v1.end(), v2.begin()); // oder ranges::copy(v1, v2.begin()); // v1 nach v2 kopieren, dabei am Ende beginnen copy_backward(v1.begin(), v1.end(), v2.end()); // oder ranges::copy_backward(v1, v2.end()); // v1 nach cout kopieren, Separator * ostream_iterator<int> ausgabe(cout, "*"); copy(v1.begin(), v1.end(), ausgabe);
Kopieren mit Bedingung
In Analogie zu anderen Algorithmen gibt es auch den Algorithmus copy_if(), der nur Elemente kopiert, die einer bestimmten Bedingung genügen. Der Prototyp ist
Zurückgegeben wird (result + N), wobei N die Zahl der kopierten Elemente ist.
Zu copy_result siehe Abschnitt 23.3.1. In Listing 23.78 werden alle Elemente größer als 10 von container1 am Ende von container2 eingefügt.
Listing 23.78: copy_if (cppbuch/k23/vermischtes/copyif.cpp)
#include <algorithm> #include <iostream> #include <numeric> #include <showContainer.h> #include <vector> using namespace std; int main() { vector<int> container1(20); iota(container1.begin(), container1.end(), 1); // 1, 2, ... 20 showContainer(container1); vector<int> container2(5, 0); // Container mit 5 Nullen anlegen // alle Elemente > 10 am Ende einfügen: copy_if(container1.begin(), container1.end(), back_inserter(container2), [](int x) { return x > 10; }); showContainer(container2); }
Kopieren einer bestimmten Zahl von Elementen
copy_n() kopiert eine bestimmte Anzahl von Elementen. Der Prototyp ist
| 23.10.6 | Vertauschen von Elementen, Bereichen und Containern |
Der Algorithmus swap() vertauscht Elemente von Containern oder Container selbst. Er tritt in Varianten auf:
swap() vertauscht zwei Container oder einzelne Elemente. Die beiden Elemente können in verschiedenen, in demselben oder in keinem Container sein. swap() ist im Header <utility>, iter_swap() und swap_ranges() sind im Header <algorithm>.
iter_swap() nimmt zwei Iteratoren und vertauscht die dazugehörenden Elemente. Die beiden Iteratoren können zu verschiedenen oder zu demselben Container gehören.
swap_ranges() vertauscht zwei Bereiche.
first1 zeigt auf den Anfang des ersten Bereichs, last1 auf die Position nach dem letzten Element des ersten Bereichs. Der Anfang des zweiten Bereichs wird durch first2 gegeben. Die Anzahl der auszutauschenden Elemente wird durch die Größe des ersten Bereichs gegeben. Die Bereiche können in demselben Container sein, dürfen sich jedoch nicht überlappen. std::swap_ranges() gibt einen Iterator auf das Ende des zweiten Bereichs zurück. Die ranges-Variante ist
Es wird eine Struktur mit den Elementen {in1, in2} und dem Wert {r1.begin(), r2.begin() + N} zurückgegeben, wobei N die Größe des kleineren Bereichs ist.
swap() ist für diejenigen Container spezialisiert, die eine Methode swap() zum Vertauschen bereitstellen, also array, deque, list, vector, set, map, multiset und multimap. Diese Methoden sind mit Ausnahme von array::swap() sehr schnell (O(1)), weil nur Verwaltungsinformationen ausgetauscht werden. swap() ruft intern die Methoden der Container auf.
exchange()
Der Algorithmus exchange() weist dem Objekt obj den neuen Wert newValue zu und gibt den alten Wert zurück. Die Deklaration ist:
Die Funktion ist im Header <utility>. Die Datei cppbuch/k23/vermischtes/exchange.cpp zeigt ein Beispiel.
| 23.10.7 | Elemente transformieren |
Wenn es darum geht, nicht nur etwas zu kopieren, sondern dabei gleich umzuwandeln, ist transform() der richtige Algorithmus. Die Umwandlung kann sich auf nur ein Element oder auf zwei Elemente gleichzeitig beziehen. Dementsprechend gibt es überladene Formen:
Hier wird auf jedes Element von first bis ausschließlich last die Operation op angewendet und das Ergebnis in den mit result beginnenden Bereich kopiert. result darf identisch mit first sein, wobei dann die Elemente durch die transformierten ersetzt werden. Der Rückgabewert ist ein Iterator auf die Position nach dem Ende des Zielbereichs. Die ranges-Variante ist
Die zurückgegebene Struktur copy_result hat den Wert {r1.begin() + N, result + N}. Im Beispiel
werden alle Großbuchstaben eines Strings in Kleinbuchstaben umgewandelt. Die Funktion tolower() ist im Header <cctype> deklariert.
In der zweiten Form werden zwei Bereiche betrachtet. Der erste ist das Intervall [first1, last1), der zweite das Intervall [first2, first2 + last1 - first1), das heißt, der zweite Bereich ist genauso groß wie der erste. Die Operation binop nimmt jeweils ein Element aus jedem der zwei Bereiche und legt ihr Ergebnis in result ab. result darf identisch mit first1 oder first2 sein, wobei dann die Elemente durch die transformierten ersetzt werden. Der Rückgabewert ist ein Iterator auf die Position nach dem Ende des Zielbereichs. Die ranges-Variante ist
binary_transform_result ist eine Struktur mit den Elementen {in1, in2, out} und dem Wert {r1.begin() + N, r2.begin() + N, result + N}. Das Listing 23.80 zeigt, wie jeweils zwei Strings verkettet werden. Dabei werden sowohl eine unäre Operation als Funktion eingesetzt wie auch eine binäre Operation als Funktor. Erstere wandelt alle Buchstaben eines C++-Strings in Großbuchstaben um und gibt den veränderten String zurück. Der Funktor verkettet zwei String-Objekte miteinander und fügt dabei das Wort »und« ein.
Listing 23.80: transform() (cppbuch/k23/vermischtes/transformranges.cpp)
#include <algorithm> #include <cctype> #include <showContainer.h> #include <string> #include <vector> [[nodiscard]] std::string upper_case(std::string s) // unäre Operation als Funktion { std::ranges::transform(s, s.begin(), toupper); return s; } struct Verketten { // binäre Operation als Funktor [[nodiscard]] std::string operator()(const std::string& a, const std::string& b) const { return a + "˽und˽" + b; } }; using namespace std; int main() { vector<string> maedels{"Annabelle", "Scheherazade", "Julia"}; vector<string> jungs{"Nikolaus", "Amadeus", "Romeo"}; if (maedels.size() != jungs.size()) { cout << "Paarbildung˽nicht˽möglich!\n"; } else { vector<string> paare(maedels.size()); ranges::transform(jungs, jungs.begin(), // Ziel == Quelle upper_case); // in Großbuchstaben wandeln ranges::transform(maedels, jungs, paare.begin(), Verketten()); showContainer(paare, "", "\n"); // gebildete Paare ausgeben } }
| 23.10.8 | Ersetzen und Varianten |
Der Algorithmus replace() ersetzt in einer Sequenz jeden vorkommenden Wert old_value durch new_value. Alternativ ist mit replace_if() eine bedingungsgesteuerte Ersetzung mit einem unären Prädikat möglich:
Die kopierenden Varianten unterscheiden sich im Namen durch ein hinzugefügtes _copy:
Das Beispiel zeigt die vier Algorithmen replace(), replace_if(), replace_copy() und replace_copy_if() in der jeweiligen ranges-Variante:
Listing 23.81: replace() mit Varianten (cppbuch/k23/vermischtes/replaceranges.cpp)
#include <algorithm> #include <showContainer.h> #include <string_view> #include <vector> auto istZitrusfrucht = [](std::string_view a) { return a == "Zitrone" || a == "Apfelsine" || a == "Limone"; }; using namespace std; int main() { vector<string_view> obstkorb{"Apfel", "Apfelsine", "Zitrone"}; showContainer(obstkorb); // Apfel Apfelsine Zitrone cout << "replace:˽Apfel˽durch˽Quitte˽ersetzen:\n"; ranges::replace(obstkorb, string_view("Apfel"), string_view("Quitte")); showContainer(obstkorb); // Quitte Apfelsine Zitrone cout << "replace_if:˽Zitrusfrüchte˽durch˽Pflaumen˽ersetzen:\n"; ranges::replace_if(obstkorb, istZitrusfrucht, string_view("Pflaume")); showContainer(obstkorb); // Quitte Pflaume Pflaume cout << "replace_copy:˽kopieren˽und˽ersetzen˽der˽Pflaumen˽durch˽Limonen:\n"; vector<string_view> kiste(obstkorb.size()); ranges::replace_copy(obstkorb, kiste.begin(), string_view("Pflaume"), string_view("Limone")); showContainer(kiste); // Quitte Limone Limone cout << "replace_copy_if:˽kopieren˽und˽ersetzen˽der˽Zitrusfrüchte˽durch˽" "Tomaten:\n"; ranges::replace_copy_if(kiste, obstkorb.begin(), istZitrusfrucht, string_view("Tomate")); showContainer(obstkorb); // Quitte Tomate Tomate }
| 23.10.9 | Elemente herausfiltern |
Der Algorithmus verschiebt alle Elemente aus einer Sequenz, die gleich einem Wert value sind beziehungsweise einem Prädikat pred genügen, an das Ende. Hier sind die Prototypen einschließlich der kopierenden Varianten aufgeführt:
Das Wort »remove« heißt eigentlich »entfernen«. Es bedeutet hier nur, dass die zu löschenden Elemente an das Ende geschoben werden. remove() gibt einen Iterator auf den Anfang des Teilbereichs mit den gelöschten Elementen zurück. Dabei ist zu beachten, dass die gesamte Länge der Sequenz sich nicht ändert! Falls nicht kopiert wird, enthält der Bereich zwischen dem zurückgegebenen Iterator und last nur noch bedeutungslos gewordene Elemente. Wenn sie tatsächlich entfernt werden sollen, ist für den Container erase() ab diesem Iterator bis zum Ende auszuführen. Das Listing 23.82 zeigt nur die nicht kopierenden Varianten:
Listing 23.82: remove() mit Varianten (cppbuch/k23/vermischtes/remove.cpp)
#include <algorithm> // remove #include <iostream> #include <numeric> // iota #include <showContainer.h> #include <string_view> #include <vector> using namespace std; int main() { vector<char> v(26); iota(v.begin(), v.end(), ’a’); // Alphabet mit Kleinbuchstaben erzeugen showContainer(v, "\n"); cout << "remove˽’t’:˽"; auto last = remove(v.begin(), v.end(), ’t’); // last = neues Ende nach der Verschiebung, v.end() bleibt unverändert! // Nur die Zeichen von begin() bis last sind von Bedeutung. showContainer(v.begin(), last); // Anzeige nur bis last // Vokale entfernen: last = remove_if(v.begin(), last, [](char c) { return string_view {"aeiouyAEIOUY"}.find(c) != std::string_view::npos;}); cout << "nur˽noch˽Konsonanten˽übrig:˽"; showContainer(v.begin(), last); // bcdfghjklmnpqrsvwxz cout << "\nVollständige˽Sequenz˽einschließlich˽bedeutungsloser˽" "Elemente˽am˽Ende:\n"; showContainer(v, "\n"); }
Der Vollständigkeit halber sind die ranges-Varianten hier aufgeführt. Die nicht abgedruckte Datei cppbuch/k23/vermischtes/removeranges.cpp zeigt das Programm aus Listing 23.82 mit den ranges-Algorithmen.
Tücken bei modifizierenden Funktionen
Nehmen wir ein Beispiel: In einem Vektor sollen alle Werte gelöscht werden, die gleich dem ersten Element sind, hier also alle Nullen:
Diese Lösung ist falsch! Tatsächlich wird nur die erste Null gelöscht. Der Grund: Der letzte Parameter wird per Referenz übergeben und der Indexoperator gibt eine Referenz zurück. Nach dem ersten Schritt ist v[0] damit gleich 2. Mit diesem Wert wird weiter gesucht – aber den gibt es nach der Position 0 nicht mehr. Richtig ist daher
Seit C++23 gibt es die Möglichkeit, die Zwischenkopie mit auto() einzusparen. auto(x) bewirkt die Umwandlung des Arguments x in einen reinen R-Wert.
Die Wirkung entspricht hier remove(v.begin(), v.end(), 0);. Statt auto(x) kann auto{x} geschrieben werden. Die Datei cppbuch/k23/vermischtes/removeProblem.cpp zeigt ein vollständiges Programm.
Merke:
Bei Funktionen, die einen Container modifizieren, können Referenzparameter, die in dem zu modifizierenden Bereich liegen, zu Problemen führen.
| 23.10.10 | Grenzwerte von Zahltypen |
Im Header <limits> wird die Template-Klasse numeric_limits definiert. Sie hat Spezialisierungen für die ganzzahligen Grunddatentypen bool, char, signed char, unsigned char, short, unsigned short, int, unsigned int, long, unsigned long sowie für die Gleitkommazahltypen float, double und long double. Für diese Grunddatentypen beschreiben die Spezialisierungen verschiedene implementationsabhängige Funktionen und Eigenschaften, die alle public sind und von denen die wichtigsten in der Tabelle 23.2 aufgelistet sind. Eine Anwendung wird in Listing 1.6 (Seite 48) gezeigt.
Tabelle 23.2: <limits>: Attribute und Funktionen (Auszug). T = Typ der Zahl
Schnittstelle |
Bedeutung |
bool is_specialized |
true nur für Grunddatentypen, für die eine Spezialisierung vorliegt, false für alle anderen |
T min() |
minimal möglicher Wert |
T max() |
maximal möglicher Wert |
int radix |
Zahlenbasis, normal 2 (Ausnahme z.B. BCD-Zahlen) |
int digits |
Ganzzahlen: Anzahl der Bits (ohne Vorzeichen-Bit) Gleitkommazahlen: Anzahl der Mantissenbits |
int digits10 |
Anzahl signifikanter Dezimalziffern bei Gleitkommazahlen, zum Beispiel 6 bei float, 15 bei double |
bool is_signed |
true bei vorzeichenbehafteten Zahlen |
bool is_integer |
true bei Ganzzahltypen |
bool is_exact |
true bei exakten Zahlen, z.B. ganze oder rationale Zahlen – nicht aber Gleitkommazahlen |
T epsilon() |
kleinster positiver Wert x, für den die Maschine die Differenz zwischen 1.0 und (1.0 + x) noch unterscheidet |
T round_error() |
maximaler Rundungsfehler |
int min_exponent |
kleinster negativer Exponent für Gleitkommazahlen |
int min_exponent10 |
kleinster negativer 10er-Exponent für Gleitkommazahlen (≤ –37) |
int max_exponent |
größtmöglicher Exponent für Gleitkommazahlen |
int max_exponent10 |
größtmöglicher 10er-Exponent für Gleitkommazahlen (≥ +37) |
T infinity() |
Repräsentation von +∞, falls vorhanden |
bool has_infinity |
true, falls der Zahltyp eine Repräsentation für +∞ hat |
bool is_iec559 |
true, falls der Zahltyp dem IEC 559(= IEEE 754)-Standard genügt |
bool is_bounded |
true für alle Grunddatentypen, false wenn die Menge der darstellbaren Werte unbegrenzt ist, z.B. bei Typen mit beliebiger Genauigkeit |
bool is_modulo |
true, falls bereichsüberschreitende Operationen wieder eine gültige Zahl ergeben. Z.B. ergibt die Addition einer Zahl auf die größtmögliche Integerzahl bei den meisten Maschinen wieder eine Integerzahl, die kleiner als die größtmögliche ist. Dies gilt im Allgemeinen nicht für Gleitkommazahlen. |
round_style |
Art der Rundung. Ganzzahlen: round_toward_zero (= 0) Gleitkommazahlen: round_to_nearest (= 1) |
| 23.10.11 | Minimum und Maximum |
Die Templates min() und max() geben jeweils das kleinste (bzw. das größte) von zwei oder mehr Elementen zurück. Bei Gleichheit wird das erste Element zurückgegeben. Die Prototypen für nur zwei zu vergleichende Elemente sind:
minmax() gibt ein pair-Objekt zurück, das den kleineren Wert an der Stelle first und den größeren an der Stelle second enthält:
Die genannten Algorithmen gibt es auch mit einer Initialisierungsliste oder einem Bereich als Parameter. Damit können mehr als zwei Elemente verglichen werden:
range_value_t<R> ist der Datentyp der Elemente des Bereichstyps R.
minmax_result ist eine Struktur mit den Elementen {min, max}. Das folgende kleine Programm zeigt einige Möglichkeiten.
Listing 23.83: Minimum und Maximum (cppbuch/k23/vermischtes/minmax.cpp)
#include <algorithm> #include <cstdlib> #include <iostream> #include <vector> using namespace std; int main() { cout << "Das˽Minimum˽der˽Zahlen˽1˽und˽2˽ist˽" << min(1, 2) << ".\nDas˽Maximum˽der˽Zahlen˽3.4˽und˽-2.2˽ist˽" << max(3.4, -2.2) << ".\nVon˽den˽Zahlen˽100˽und˽700˽ist" << minmax(100, 700).first << "˽die˽kleinere˽und˽" << minmax(100, 700).second << "˽die˽größere.\nMit˽initializer_list:" << "\nDas˽Minimum˽der˽Zahlen˽{6,-8,1,2,3}˽ist˽" << min({6, -8, 1, 2, 3}) << ".\nDas˽Maximum˽der˽Zahlen˽{6,-8,1,2,3}˽ist˽" << max({6, -8, 1, 2, 3}) << "\nVon˽den˽Zahlen˽{6,-8,1,2,3}˽ist˽" << minmax({6, -8, 1, 2, 3}).first << "˽die˽kleinste˽und˽" << minmax({6, -8, 1, 2, 3}).second << "˽die˽größte.\nWenn˽das˽Vorzeichen˽ignoriert˽werden˽soll˽" "(Absolutbetrag):\nVon˽den˽Zahlen˽{6,-8,1,2,3}˽ist˽"; auto ergebnis = minmax({6, -8, 1, 2, 3}, [](int x, int y) { return abs(x) < abs(y); }); cout << ergebnis.first << "˽die˽kleinste˽und˽" << ergebnis.second << "˽die˽größte.\n"; vector<int> vec{6,-8,1,2,3}; cout << "ranges::minmax():˽min˽=˽" << ranges::minmax(vec).min << "˽˽˽max˽=˽" << ranges::minmax(vec).max << ’\n’; }
| 23.10.12 | Wert begrenzen |
Der Algorithmus clamp() begrenzt einen Wert. Die Schnittstelle ist:
Dabei ist val der zu begrenzende Wert, lo die Untergrenze und hi die Obergrenze. Optional kann ein Vergleichsobjekt comp übergeben werden, wenn nicht mit dem <-Operator verglichen werden soll. Zurückgegeben wird lo, wenn val < lo ist, und hi, wenn val >= hi ist. Ist keine der Bedingungen erfüllt, wird val zurückgegeben. Im Beispiel werden verschiedene Werte auf die Bereiche -128..127 und 0..255 begrenzt.
Listing 23.84: Begrenzte Werte (cppbuch/k23/vermischtes/clamp.cpp)
#include <algorithm> #include <iomanip> #include <iostream> #include <vector> int main() { std::vector<int> werte{-300, 200, -50, -1, 0, 1, 50, 200, 300}; std::cout << "Wert˽˽˽-128˽..127˽˽˽0..255\n"; for (int w : werte) { std::cout << std::setw(4) << w << std::setw(13) << std::clamp(w, -128, 127) << std::setw(9) << std::clamp(w, 0, 255) << ’\n’; } }
Das Programm gibt aus:
| 23.10.13 | ggT, kgV und Mitte |
ggT und kgV sind die gängigen Abkürzungen für »größter gemeinsamer Teiler« (englisch greatest common divisor, abgekürzt gcd) und »kleinstes gemeinsames Vielfaches« (englisch least common multiple, abgekürzt lcm). midpoint(T a, T b) ergibt die Hälfte der Summe, midpoint(T* p, T* q) zeigt auf das mittlere Element in einem Array, wenn p und q Zeiger auf Elemente dieses Arrays sind. Die Schnittstellen sind:
Die Typen M und N müssen ganzzahlig sein. common_type_t<M,N> ist ein Typ, der Werte beider Typen M und N abbilden kann. Wenn zum Beispiel ein Typ short und der andere int ist, ist das Ergebnis vom Typ int. gcd(0, 0) ergibt 0. lcm(a, b) ergibt 0, wenn wenigstens eines der beiden Argumente 0 ist.
Die Datei cppbuch/k23/vermischtes/gcdlcmmidpoint.cpp (hier nicht abgedruckt) zeigt die Anwendung aller vier Algorithmen.
| 23.11 | Parallelisierbare Algorithmen |
Zu den meisten Algorithmen der C++-Standardbibliothek gibt es überladene parallelisierbare Varianten. So eine Variante kann schematisch aus der jeweiligen Schnittstelle abgeleitet werden. In den tabellarischen Übersichten in Abschnitt 29.2 sind die nicht-parallelisierbaren Algorithmen mit einem * markiert. Die parallelisierbaren Formen sind nur bei wirklich sehr großen Datenmengen effizienter, sollten also auf Basis einer Laufzeitmessung eingesetzt werden.
Jeder der überladenen parallelisierbaren Algorithmen hat einen zusätzlichen Parameter des Typs ExecutionPolicy an erster Stelle. Ein möglicherweise vorhandenes constexpr entfällt. Das sei am Beispiel von min_element() gezeigt:
Beim Aufruf muss also ggf. ein ExecutionPolicy-Objekt übergeben werden. Dieses Schema gilt für alle parallelisierbaren Algorithmen. Es gibt drei globale ExecutionPolicy-Objekte:
std::execution::seq besagt, dass der Algorithmus nicht parallelisiert werden soll.
std::execution::par sagt dem Compiler, dass der Algorithmus parallelisiert werden kann. Das Wort »kann« drückt aus, dass eine Parallelisierung nicht zwingend vorgenommen wird, etwa weil die Anzahl der zu bearbeitenden Elemente zu klein ist.
std::execution::par_unseq bedeutet, dass der Algorithmus parallelisiert und vektorisiert3 werden kann.
Der Namespace ist std::execution, der Header ist <execution>. Die Objekte sind von jeweils verschiedenen Typen und beim Überladen für einen Compiler eindeutig zuzuordnen. Beispiel für einen Aufruf:
Sie müssen selbst darauf achten, dass eine Parallelisierung kein data race verursacht, etwa durch nichtsynchronisiertes Schreiben von Daten.
2 Siehe Eintrag »Intervall« im Glossar Seite 980.
3 Ein SIMD-Prozessor kann eine Operation parallel auf vielen Daten ausführen. SIMD = single instruction, multiple data.