© Elvira Koneva / 123RF.com

Die Ranges-Bibliothek, eine zweite Variante der Standard Template Library, öffnet C++20 für ganz neue Ideen aus der funktionalen Welt.

Die Ranges-Bibliothek in C++20 macht den Umgang mit der Standard Template Library deutlich angenehmer und mächtiger. Ihre Algorithmen sind lazy (dazu im Folgenden mehr), agieren direkt auf den Containern und lassen sich verknüpfen. Um es kurz zu machen: Die Bequemlichkeit und Mächtigkeit der Ranges-Bibliothek beruht auf ihren funktionalen Ideen.

Eine erste Berührung

Jeder Artikel zu Ranges sollte mit einem “Hello, World” zu Ranges beginnen. Listing 1 übernimmt diese Aufgabe.

Den Ausdruck in den Zeilen 7 bis 9 müssen Sie von links nach rechts lesen. Das Pipe-Symbol »|« steht für die Verknüpfung von Funktionen. Zuerst akzeptiert »std::views::filter(…)« alle geradzahligen Elemente. Danach verdoppelt »std::views::transform(…)« jedes verbleibende Element. Zeile 10 des Listings enthält die Ausgabe des Programms als Kommentar.

Dieses kleine Beispiel zeigt bereits zwei neue Features der Ranges-Bibliothek. Zum einen demonstriert es die Funktionskomposition, zum anderen agiert diese Funktionskomposition direkt auf dem Container. Nach diesem Einstieg in die Welt von Ranges ist es nun an der Zeit, tiefer in die Materie einzutauchen.

#include <iostream>
#include <ranges>
#include <vector>
int main() {
  std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
  auto results = numbers |
    std::views::filter([](int n){ return n % 2 == 0; }) |
    std::views::transform([](int n){ return n * 2; });
  for (auto v: results) std::cout << v << " ";     // 4 8 12
}

Ranges und Views

Neben der Funktionskomposition bietet die Ranges-Bibliothek zwei sehr interessante Concepts [1]: die namensgebenden Ranges sowie Views.

Als Range bezeichnet man eine Menge von Elementen, über die iteriert werden kann. Ein solcher Range verfügt über einen Begin-Iterator und einen Sentinel (Abschlusselement). Selbstverständlich handelt es sich bei den Containern der Standard Template Library um Ranges.

Ein View lässt sich auf einen Range anwenden, wobei eine Operation ausgeführt wird. Views besitzen keine Daten. Konsequenterweise sind ihre Copy-, Move- und Zuweisungsoperationen konstant.

In Listing 1 ist »numbers« der Range, während »std::views::filter()« und »std::views::transform()« für die Views steht. Freilich besitzt C++20 deutlich mehr Views als nur diese beiden. Die Tabelle “Views in C++20” stellt sie kurz und kompakt vor.

Die meisten Views lassen sich über einen alternativen Namen ansprechen. So können Sie anstelle »std::views::transform()« den Bezeichner »std::transform_view()« verwenden. Views werden auch gern als Range Adaptors bezeichnet. Eine genaue Beschreibung aller C++20-Views und der mit C++23 neu eingeführten Varianten liefert in bekannter Manier die Webseite Cppreference.com [2].

Als die drei herausragenden Feature von Ranges kann man zusammenfassen, dass sie sich direkt auf den Container anwenden lassen und Komposition sowie Bedarfsauswertung unterstützen.

Auf dem Container

Das Programm aus Listing 2 erzeugt direkte Views auf den Schlüsseln und Werten einer »std::unordered_map«.

Dabei agieren sowohl die Zeilen 13 und 16 als auch die Zeilen 21 und 24 direkt auf den Container. Während erstere die Schlüssel der »std::unordered_map<std::string, int>« ansprechen, erledigen letztere das für die Werte. Abbildung 1 zeigt die Ausgabe des Programms.

Abbildung 1: Direktes Agieren auf dem Container mit der Ranges-Bibliothek.

Das direkte Arbeiten auf dem Container an sich stellt noch keine Revolution in C++ dar, Funktionskomposition und Bedarfsauswertung aber schon.

#include <iostream>
#include <ranges>
#include <string>
#include <unordered_map>
int main() {
  std::cout << '\n';
  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);
  for (const auto& name : names){ std::cout << name << " "; };
  std::cout << std::endl;
  for (const auto& name : std::views::keys(freqWord)){
    std::cout << name << " ";
  };
  std::cout << "\n\n";
  std::cout << "Values: " << std::endl;
  auto values = std::views::values(freqWord);
  for (const auto& value : values){ std::cout << value << " "; };
  std::cout << std::endl;
  for (const auto& value : std::views::values(freqWord)){
    std::cout << value << " ";
  }
  std::cout << "\n\n";
}

Funktionskomposition

In Listing 3 kommt eine »std::map« zum Einsatz. In diesem Fall kommt es auf die Ordnung der Schlüssel an. Dabei dreht sich alles um die Keys der »std::map<std::string, int>«. Zuerst stellt Zeile 11 alle Schlüssel dar, Zeile 16 sortiert sie umgekehrt. Dagegen interessiert sich der Block ab Zeile 20 nur für die ersten vier Schlüssel und der Code ab Zeile 24 nur für jene Exemplare, die mit dem Buchstaben “w” beginnen. Abbildung 2 zeigt die Ausgabe des Programms.

#include <iostream>
#include <ranges>
#include <string>
#include <map>
int main() {
 std::cout << std::endl;
 std::map<std::string, int> freqWord{
  {"witch", 25}, {"wizard", 33}, {"tale", 45},
  {"dog", 4}, {"cat", 34}, {"fish", 23} };
  std::cout << "All words: ";                     /
  for (const auto& name : std::views::keys(freqWord)) {
   std::cout << name << " ";
  };
  std::cout << std::endl;
  std::cout << "All words reverse: ";
  for (const auto& name : std::views::keys(freqWord) |
   std::views::reverse) { std::cout << name << " "; };
  std::cout << std::endl;
  std::cout << "The first 4 words: ";
  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: ";
  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 << "\n\n";
}

Abbildung 2: Eine Funktionskomposition mithilfe der Ranges-Bibliothek.

Das Pipe-Symbol »|« fungiert als Syntactic Sugar [3] für die Funktionskomposition. Damit lässt sich »C(R)« in der einfacheren Form »R | C« schreiben. Listing 4 demonstriert die beiden funktional identischen Schreibweisenvarianten.

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

Bedarfsauswertung

In Listing 5 kommt »std::views::iota()« zum Einsatz. Diese Funktion betätigt sich als Zahlenfabrik. Dazu erzeugt sie eine Sequenz von Zahlen, indem sie einen initialen Wert sukzessiv inkrementiert. Diese Sequenz kann endlich oder unendlich sein. Der Aufruf »std::view::iota(0)« erzeugt einen unendlichen Datenstrom, der bei »0« startet und auf Anfrage die nächste Zahl erzeugt. Das Produzieren eines Werts auf Anfrage nennt man Bedarfsauswertung oder Lazy Evaluation [4].

Dank Bedarfsauswertung und Funktionskomposition lässt sich die Ranges-Bibliothek sehr elegant einsetzen, um die ersten 20 Primzahlen zu finden, die bei 1 000 000 beginnen. Listing 5 tut dazu nur das Nötigste und verwendet eine iterative Strategie in vier Schritten.

#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() {
 std::cout << '\n';
 std::cout << "Numbers from 1000000 to 1001000 (displayed each 100th): " << std::endl;
   for (int i: std::views::iota(1000000, 1001000)) {
     if (i % 100 == 0) std::cout << i << " ";
 }
 std::cout << "\n\n";
 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";
 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";
 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 << " ";
 }
 std::cout << "\n\n";
}

Um sicherzugehen, dass die erzeugten Zahlen die gesuchten 20 Primzahlen auch enthalten, generiert Zeile 14 mittels »std::views::iota(1000000)« 1000 Zahlen und gibt jede hundertste davon aus. Die gewünschten Zahlen müssen natürlich ungerade sein. Daher entfernt Zeile 18 die geraden Zahlen und gibt jede hundertste ungerade Zahl aus.

Jetzt kommt der nächste Filter an die Reihe. Das Prädikat »isPrime« aus Zeile 4 gibt zurück, ob es sich bei der Zahl um eine Primzahl handelt. Dabei kommt das Sieb des Eratosthenes [5] als Strategie zum Einsatz. Abbildung 3 zeigt schön, dass die gewählte Strategie zu gierig war: Die 1000 Zahlen enthalten nicht weniger als 75 Primzahlen.

Faulheit ist eine Tugend. Jetzt kommt »std::views::iota()« in Zeile 35 als unendlicher Zahlengenerator zum Einsatz, der bei 1 000 000 startet. Den Anstoß dazu gibt der View »std::views::take(20)« (Zeile 38), der genau 20 Zahlen erhalten will.

Abbildung 3: Iterative Bestimmung der ersten 20 Primzahlen ab dem Startwert 1 000 000.

Wie geht es weiter?

Die Ranges-Bibliothek ist eines der vier zentralen Features von C++20. Da verwundert es nicht wirklich, dass es zur Ranges-Bibliothek im nächsten Artikel dieser Serie noch einiges zu erzählen gibt. Dabei dreht sich dann alles um Projektionen, Sentinels, Concepts und Sicherheit. (jlu)