C++20: Funktionale Pattern mit der Ranges-Bibliothek

Modernes C++  –  26 Kommentare

In meinem letzten Artikel C++20: Die Ranges-Bibliothek habe ich den ersten Einblick in die Ranges-Bibliothek gegeben. Heute geht es um die funktionale Pattern Funktionskomposition und Bedarfsauswertung. Beide werden Bürger erster Klasse in C++20.

Die Algorithmen der Standard Template Library (STL) sind manchmal etwas umständlich zu verwenden. Sie benötigen Begin- und End-Iteratoren, was oft unnötigen Schreibaufwand bedeutet:

#include <numeric>
#include <iostream>
#include <vector>

int main() {

std::vector<int> myVec{1, 2, 3, 4, 5, 6, 7, 8, 9};
auto res = std::accumulate(std::begin(myVec), std::end(myVec), 0);
// std::accumulate(myVec, 0); // (1)
std::cout << res << std::endl; // 45

}

Wäre es nicht angenehm, wenn der Algorithmus std::accumulate direkt auf dem Container wie in Zeile (1) ausgeführt werden könnte?

Direkt auf dem Container

Das folgende Programm erzeugt direkte Views auf den Schlüsseln (Zeile 1) und Werten (Zeile 2) einer std::unordered_map:

// rangesEntireContainer.cpp

#include <iostream>
#include <ranges>
#include <string>
#include <unordered_map>


int main() {

std::unordered_map<std::string, int> freqWord{ {"witch", 25},
{"wizard", 33}, {"tale", 45}, {"dog", 4}, {"cat", 34}, {"fish", 23} };

std::cout << "Keys" << std::endl;
auto names = std::views::keys(freqWord); // (1)
for (const auto& name : names){ std::cout << name << " "; };
std::cout << std::endl;
for (const auto& name : std::views::keys(freqWord)){
std::cout << name << " ";
}; // (2)

std::cout << "\n\n";

std::cout << "Values: " << std::endl;
auto values = std::views::values(freqWord); // (3)
for (const auto& value : values){ std::cout << value << " "; };
std::cout << std::endl;
for (const auto& value : std::views::values(freqWord)){
std::cout << value << " ";
} // (4)

}

Natürlich lassen sich die Schlüssel und Werte auch direkt ausgeben (Zeilen 2 und 4). Die Ausgabe ist identisch:

Das direkte Arbeiten auf dem Container ist keine Revolution in C++, Funktionskomposition und Bedarfsauswertung aber sehr wohl.

Funktionskomposition

Im nächsten Beispiel kommt die std::map zum Einsatz, den die Ordnung der Schlüssel ist in diesem Fall entscheidend:

// rangesComposition.cpp

#include <iostream>
#include <ranges>
#include <string>
#include <map>


int main() {

std::map<std::string, int> freqWord{ {"witch", 25}, {"wizard", 33},
{"tale", 45}, {"dog", 4}, {"cat", 34}, {"fish", 23} };

std::cout << "All words: "; // (1)
for (const auto& name : std::views::keys(freqWord)) {
std::cout << name << " ";
};

std::cout << std::endl;

std::cout << "All words reverse: "; // (2)
for (const auto& name : std::views::keys(freqWord)
| std::views::reverse) { std::cout << name << " "; };

std::cout << std::endl;

std::cout << "The first 4 words: "; // (3)
for (const auto& name : std::views::keys(freqWord)
| std::views::take(4)) { std::cout << name << " "; };

std::cout << std::endl;

std::cout << "All words starting with w: "; // (4)
auto firstw = [](const std::string& name){ return name[0] == 'w'; };
for (const auto& name : std::views::keys(freqWord)
| std::views::filter(firstw)) { std::cout << name << " "; };

std::cout << std::endl;
// (5)
auto lengthOf = [](const std::string& name){ return name.size(); };
auto res = ranges::accumulate(std::views::keys(freqWord)
| std::views::transform(lengthOf), 0);
std::cout << "Sum of words: " << res << std::endl;

}

Jetzt interessieren mich nur die Schlüssel. Das Programm stellt alle Schlüssel in Zeile (1) dar, sie dann in Zeile (2) umgekehrt sortiert und darauf in Zeile (3) die ersten vier und in Zeile (4) nur die Schlüssel, die mit 'w' beginnen. Zum Abschluss berechnet Zeile (5) die Summe aller Wortlängen.

Das Pipe Symbol | ist Syntactic Sugar für die Funktionskomposition. Damit lässt sich C(R) einfacher als R | C schreiben. Konsequenterweise sind die nächsten zwei Zeilen äquivalent:

auto rev2 = std::views::reverse(ranges::views::keys(freqWord));
auto rev = std::views::keys(freqWord) | ranges::views::reverse;

Zum Abschluss ist hier die Ausgabe des Programms:

Bedarfsauswertung (Lazy Evaluation)

In meinem Beispiel kommt std::views::iota zum Einsatz. Diese Funktion ist eine Zahlenfabrik, die eine Sequenz von Zahlen erzeugt, in dem ein initialer Wert sukzessiv inkrementiert wird. Diese Sequenz kann endlich oder unendlich sein. Das folgende Beispiel füllt einen std::vector mit 10 ints, die bei 0 starten:

// rangesIota.cpp

#include <iostream>
#include <numeric>
#include <ranges>
#include <vector>

int main() {

std::cout << std::boolalpha;

std::vector<int> vec;
std::vector<int> vec2;

for (int i: std::views::iota(0, 10)) vec.push_back(i); // (1)

for (int i: std::views::iota(0)
| std::views::take(10)) vec2.push_back(i); // (2)

std::cout << "vec == vec2: " << (vec == vec2) << '\n'; // true

for (int i: vec) std::cout << i << " "; // 0 1 2 3 4 5 6 7 8 9

}

Der erste iota-Aufruf (Zeile 1) erzeugt alle Zahlen von 0 bis 9 durch sukzessives Inkrementieren um 1. Der zweite iota-Aufruf (Zeile 2) generiert einen unendlichen Datenstrom, der mit 0 startet und die nächste um 1 inkrementierte Zahl zurückgibt. std::views::iota(0) ist lazy. Der Ausdruck gibt nur den nächsten Wert zurück, wenn ich danach frage. Genau zehnmal frage ich danach. Damit sind beide Vektoren identisch.

Jetzt möchte ich mir eine kleine Herausforderung stellen. Ich möchte die ersten 20 Primzahlen finden, die bei 1.000.000 beginnen:

// rangesLazy.cpp

#include <iostream>
#include <ranges>


bool isPrime(int i) {
for (int j=2; j*j <= i; ++j){
if (i % j == 0) return false;
}
return true;
}

int main() {
// (1)
std::cout << "Numbers from 1000000 to 1001000 (dispayed each 100th): " << std::endl;
for (int i: std::views::iota(1000000, 1001000)) {
if (i % 100 == 0) std::cout << i << " ";
}

std::cout << "\n\n";
// (2)
auto odd = [](int i){ return i % 2 == 1; };
std::cout << "Odd numbers from 1000000 to 1001000 (displayed each 100th): " << std::endl;
for (int i: std::views::iota(1000000, 1001000) | std::views::filter(odd)) {
if (i % 100 == 1) std::cout << i << " ";
}

std::cout << "\n\n";
// (3)
std::cout << "Prime numbers from 1000000 to 1001000: " << std::endl;
for (int i: std::views::iota(1000000, 1001000) | std::views::filter(odd)
| std::views::filter(isPrime)) {
std::cout << i << " ";
}

std::cout << "\n\n";
// (4)
std::cout << "20 prime numbers starting with 1000000: " << std::endl;
for (int i: std::views::iota(1000000) | std::views::filter(odd)
| std::views::filter(isPrime)
| std::views::take(20)) {
std::cout << i << " ";
}

}

Dies ist meine schrittweise Strategie:

  1. Natürlich weiß ich nicht, wann ich die 20 Primzahlen erhalte werde, die größter als 1.000.000 sind. Um sicherzugehen, erzeugt ich 1000 Zahlen. Aus offensichtlichen Gründen stelle ich nur jede 100te Zahl dar.
  2. Die gewünschten Zahlen müssen natürlich ungerade sein. Daher entferne ich die geraden Zahlen.
  3. Jetzt ist es Zeit für den nächsten Filter. Das Prädikat isPrime gibt zurück, ob die Zahl eine Primzahl ist. Wie im folgenden Screenshot zu sehen ist, war ich zu gierig. Ich habe 75 Primzahlen erhalten.
  4. Faulheit ist eine Tugend. Ich wende nun std::iota als unendlichen Zahlengenerator an, der bei 1.000.000 startet und frage ihn direkt nach 20 Primzahlen.

Wie geht's weiter?

Ich werde ein Experiment in meinem nächsten Artikel wagen. Python besitzt sehr viele praktische Funktionen wie range, map, filter, reduce und zip. Natürlich muss ich noch List Comprehension und den Slice Operator erwähnen. All diese Funktion sind eager in Python 2; map, filter und reduce sind hingegen lazy in Python 3. Welche der Funktionen kann ich mit ähnlicher Funktionalität in C++ anwenden, indem ich die Ranges-Bibliothek verwende?