© Tatsiana Yatsevich / 123RF.com

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

Dank der Ranges-Bibliothek in C++20 wird der Umgang mit der Standard Template Library (STL) deutlich angenehmer, und ihre Ausdrucksmöglichkeiten wachsen. Die Algorithmen der Ranges-Bibliothek sind lazy, agieren direkt auf den Containern und lassen sich verknüpfen. All diese positiven Eigenschaften beruhen auf ihren funktionalen Ideen.

Eine erste Berührung

Jeder Artikel zu Ranges sollte mit einem “Hello-World”-Pendant für die Bibliothek beginnen. Listing 1 übernimmt diese Aufgabe. Den Ausdruck ab Zeile 7 muss man von links nach rechts lesen. Das Pipe-Symbol steht für die Verknüpfung von Funktionen: Zuerst akzeptieren die Zeilen 8 bis 10 alle Elemente, die gerade sind (Zeile 9). Danach wird jedes ausgefilterte Element verdoppelt (Zeilen 11 bis 13).

Dieses kleine Beispiel demonstriert bereits zwei neue Features der Ranges-Bibliothek: Hier kommt zum einen eine Funktionskomposition zum Einsatz, zum anderen agiert diese Funktionskomposition direkt auf dem Container. Zeile 14 des Listings enthält die Ausgabe direkt als Kommentar.

Das war das “Hello World” von Ranges. Nun ist es 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

Zuerst einmal enthält die Ranges-Bibliothek zwei sehr interessante Concepts [1]: Ranges und Views.

Eine Range ist eine Menge von Elementen, über die man iterieren kann. Diese Range verfügt über einen Begin-Iterator und einen Sentinel (das Abschlusselement). Selbstverständlich handelt es sich bei den Containern der Standard Template Library um Ranges.

Ein View lässt sich auf eine Range anwenden, wobei eine Operation stattfindet. Views besitzen keine Daten, konsequenterweise sind ihre Copy-, Move- und Zuweisungsoperationen konstant.

In Listing 1 ist »numbers« die Range, während »std::views::filter« und »std::views::transform« für die Views stehen. Freilich besitzt C++20 deutlich mehr Views als die beiden im Beispiel verwendeten. Die Tabelle “Views in C++20” stellt alle Varianten kurz und kompakt vor.

Die meisten Views lassen sich über einen alternativen Namen ansprechen. So kann man anstelle von »std::views::transform« auch den Namen »std::transform_view« verwenden. Views werden auch gern Range Adaptors genannt. Die genaue Beschreibung der Views und der mit C++23 eingeführten neuen Views liefert in bekannter Manier Cppreference.com [2].

Die drei herausragenden Features von Ranges sind, dass man sie auf den Container direkt anwenden kann und dass sie zum einen die Komposition und zum anderen die Bedarfsauswertung unterstützen. Das direkte Arbeiten auf dem Container ist in C++ keine Revolution, Funktionskomposition und Bedarfsauswertung aber sehr wohl.

Direkt auf dem Container

Das Programm aus Listing 2 erzeugt direkte Views auf den Schlüsseln und Werten einer »std::unordered_map«. Hier agieren sowohl die Zeilen 15 und 19 als auch die Zeilen 26 und 30 direkt auf dem Container. Während die Zeilen 15 und 19 die Schlüssel der »std::unordered_map<std::string, int>« ansprechen, sind es in den Zeilen 26 und 30 deren Werte. Abbildung 1 zeigt die Ausgabe des Programms.

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

#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, denn die Ordnung der Schlüssel ist in diesem Fall entscheidend. Dabei dreht sich alles um die Keys der »std::map<std::string, int>«. Zuerst stellt der Codeblock ab Zeile 13 alle Schlüssel dar, der ab Zeile 19 sortiert sie umgekehrt. Hingegen interessiert sich der Code ab Zeile 26 nur für die ersten vier Keys und der ab Zeile 33 ausschließlich für jene, die mit dem Buchstaben “w” beginnen. Abbildung 2 zeigt die Ausgabe des Programms.

Abbildung 2: Funktionskomposition mit der Ranges-Bibliothek.

#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";
}

Das Pipe-Symbol »|« bietet Syntactic Sugar [3] für die Funktionskomposition. Damit lässt sich »C(R)« einfacher als »R | C« schreiben. Die zwei Zeilen aus Listing 4 sind also äquivalent.

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

Bedarfsauswertung

Im nächsten Beispiel kommt »std::views::iota« zum Einsatz. Diese Funktion dient als Fabrik, die eine Sequenz von Zahlen erzeugt, indem sie einen Ausgangswert 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. Dieses 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 stellt dazu eine iterative Strategie in vier Schritten vor.

Um sicherzugehen, dass die erzeugten Zahlen die ersten 20 Primzahlen enthalten, erzeugt der Code ab Zeile 14 mittels »std::views::iota(1000000:1001000)« 1000 Zahlen und gibt jede hundertste aus. Die gewünschten Zahlen müssen selbstredend ungerade sein. Daher entfernt der Block ab Zeile 20 die geraden Zahlen und gibt jede hundertste ungerade Zahl aus.

Jetzt ist es Zeit für den nächsten Filter (ab Zeile 28). Das Prädikat »isPrime« (ab Zeile 4) prüft, ob es sich bei der Zahl um eine Primzahl handelt. Dabei kommt als Strategie das Sieb des Eratosthenes [5] zum Einsatz. Die Ausgabe des Programms in Abbildung 3 demonstriert unzweifelhaft, dass die gewählte Strategie zu gierig war: Die 1000 gefundenen Zahlen enthalten nicht weniger als 75 Primzahlen.

Abbildung 3: Iterative Bestimmung der ersten 20 Primzahlen, die mit 1 000 000 beginnen.

Faulheit ist eine Tugend. Jetzt kommt im Codeblock ab Zeile 36 »std::views::iota« als unendlicher Zahlengenerator zum Einsatz, der bei 1 000 000 startet. Dieser Generator wird durch den View »std::views::take(20)« (Zeile 40) angestoßen, der genau 20 Zahlen anfordert.

#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";
}

Wie geht es weiter?

Die Ranges-Bibliothek zählt zu den wichtigsten vier Features von C++20. Daher sollte es nicht verwundern, dass es in den kommenden Folgen dieser Serie noch viel dazu zu erzählen gibt. Der nächste Artikel dreht sich um Projektionen, Sentinels, Concepts und Sicherheit. (jcb/jlu)