Die Ranges Bibliothek in C++20: Mehr Details
Dank der Ranges-Bibliothek ist die Arbeit mit der Standard Template Library (STL) viel komfortabler und leistungsfähiger.
- Rainer Grimm
Bevor ich in die Ranges-Bibliothek in C++20 eintauche, möchte ich in ein paar Sätzen die drei Hauptmerkmale der Ranges rekapitulieren: Die Algorithmen der Ranges können direkt auf dem Container operieren, ihre Argumente lazy auswerten und sie können komponiert werden.
Direkt auf dem Container
Die klassischen Algorithmen der Standard Template Library (STL) sind manchmal ein wenig umständlich. Sie brauchen einen Anfangs- und einen End-Iterator. Das ist oft mehr, als man schreiben möchte:
// sortClassical.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> myVec{-3, 5, 0, 7, -4};
std::sort(myVec.begin(), myVec.end()); // (1)
for (auto v: myVec) std::cout << v << " "; // -4, -3, 0, 5, 7
}Wäre es nicht schön, wenn std::sort (1) für den gesamten Container ausgeführt werden könnte? Dank der Ranges-Bibliothek ist das in C++20 möglich.
// sortRanges.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> myVec{-3, 5, 0, 7, -4};
std::ranges::sort(myVec); // (1)
for (auto v: myVec) std::cout << v << " "; // -4, -3, 0, 5, 7
}std::ranges::sort (1) arbeitet direkt auf dem Container.
Lazy Evaluation
std::views::iota ist ein Zahlengenerator, der eine Folge von Elementen durch sukzessives Erhöhen eines Anfangswertes erzeugt. Diese Folge kann endlich oder unendlich sein. Die Elemente des Zahlengenerators werden nur bei Bedarf erstellt.
// lazyRanges.cpp
#include <iostream>
#include <ranges>
int main() {
std::cout << "\n";
for (int i: std::views::iota(1'000'000, 1'000'010)) { // (1)
std::cout << i << " ";
}
std::cout << "\n\n";
for (int i: std::views::iota(1'000'000) // (2)
| std::views::take(10)) {
std::cout << i << " ";
}
std::cout << "\n\n";
for (int i: std::views::iota(1'000'000) // (3)
| std::views::take_while([](auto i)
{ return i < 1'000'010; } )) {
std::cout << i << " ";
}
std::cout << "\n\n";
}Das kleine Programm zeigt den Unterschied zwischen der Erzeugung eines endlichen Datenstroms (1) und eines unendlichen Datenstroms (2 und 3). Wer einen unendlichen Datenstrom erstellt, braucht eine Randbedingung. In (2) wird dafür der View std::views::take(10) verwendet und in (3) die View std::views::take_while.Sie erfordert ein Prädikat. Ein Lambda-Ausdruck ist ein idealer Kandidat für ein Prädikat: [](auto i) { return i < 1'000'010; }. Seit C++14 kann man einfache Anführungszeichen als Trennzeichen in ganzzahligen Literalen verwenden: 1'000'010. Alle drei std::views::ranges-Aufrufe ergeben die gleichen Zahlen.
Ich habe den Pipe-Operator (|) in diesem Beispiel bereits für die Funktionskomposition verwendet und gehe nun einen Schritt weiter.
Funktionskomposition
Das folgende Programm primesLazy.cpp erzeugt die ersten zehn Primzahlen, beginnend mit einer Million.
// primesLazy.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() {
std::cout << '\n';
auto odd = [](int i){ return i % 2 == 1; };
for (int i: std::views::iota(1'000'000)
| std::views::filter(odd)
| std::views::filter(isPrime)
| std::views::take(10)) {
std::cout << i << " ";
}
std::cout << '\n';
}Die Funktionskomposition sind von links nach rechts zu lesen: Ich erstelle einen unendlichen Datenstrom, der mit 1'000'000 beginnt (std::views::iota(1'000'000)) und wende zwei Filter auf ihn an. Jeder Filter benötigt ein Prädikat. Der erste Filter lässt das ungerade Element (std::views::filter(odd)) und der zweite Filter lässt die Primzahlen passieren (std::views::filter(isPrime)). Um den unendlichen Datenstrom zu beenden, halte ich nach 10 Zahlen an (std::views::take(10)). Zum Schluss stellt der folgende Screenshot die ersten zehn Primzahlen da, die mit einer Million beginnen.
Das wirft die Frage auf, wer die Verarbeitung dieser Datenpipeline beginnt. Nun, der Prozess geht von rechts nach links. Die Datensenke (std::views::take(10)) fordert den nächsten Wert an und fragt deshalb seinen Vorgänger. Diese Anfrage geht weiter bis zur ranges-based for-Schleife, da die Datenquelle eine Zahl produzieren kann.
Dies war meine kurze Zusammenfassung. Mehr zur Ranges-Bibliothek findet sich in meine früheren Artikeln:
- Die Ranges Bibliothek
- Funktionale Pattern mit der Ranges-Bibliothek
- Pythonisch mit der Ranges-Bibliothek: range und filter
- Pythons range-Funktion, die zweite
- Die map-Funktion von Python
Jetzt ist es an der Zeit, über etwas Neues zu schreiben.
std Algorithmen versus std::ranges Algorithmen
Die Algorithmen der algorithm Bibliothek und der memoy Bibliothek besitzen Ranges-Pendants. Sie beginnen mit dem Namespace std::ranges. Die numeric Bibliothek besitzt kein Ranges-Pendant. Das wirft die Frage auf, ob man den klassischen std-Algorithmus oder den neuen std::ranges-Algorithmus verwenden sollte? Für die Antwort vergleiche ich die den klassischen Algorithmus std::sort mit dem neuen std::ranges::sort. Hier sind zunächst die verschiedenen Überladungen von std::sort und std::ranges::sort.
template< class RandomIt >
constexpr void sort( RandomIt first, RandomIt last );
template< class ExecutionPolicy, class RandomIt >
void sort( ExecutionPolicy&& policy,
RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
constexpr void sort( RandomIt first, RandomIt last, Compare comp );
template< class ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy,
RandomIt first, RandomIt last, Compare comp );std::sort hat in C++20 vier Überladungen. Schauen wir mal, was ich aus den Namen der Funktionsdeklarationen ableiten kann. Alle vier Überladungen nehmen einen Bereich an, der durch einen Anfangs- und End-Iterator angegeben wird. Die Iteratoren müssen wahlfreiem Zugriff haben. Die erste und die dritte Überladung werden als constexpr deklariert und können daher zur Compilezeit ausgeführt werden. Die zweite und vierte Überladung erfordern eine Execution Policy. Damit lässt sich festlegen, ob das Programm sequentiell, parallel oder vektorisiert ausgeführt werden soll. In den letzten beiden Überladungen, (8 und 11) kann man außerdem die Sortierstrategie festlegen. Compare muss ein binäres Prädikat sein: ein Callable, das zwei Argumente entgegennimmt und etwas zurückgibt, das in ein bool umgewandelt werden kann. Meine Analyse erinnert an Concepts, aber es gibt einen großen Unterschied: Die Namen in der std::sor4 stehen nicht für Concepts, sondern dienen nur der Dokumentation. In std::ranges::sort hingegen, sind die Namen Concepts.
template <std::random_access_iterator I, std::sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity>
requires std::sortable<I, Comp, Proj>
constexpr I sort(I first, S last, Comp comp = {}, Proj proj = {});
template <ranges::random_access_range R, class Comp = ranges::less,
class Proj = std::identity>
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R> sort(R&& r, Comp comp = {}, Proj proj = {});Wer die beiden Überladungen ansieht, bemerkt, dass ein sortierbarer Bereich R (2 und 4) benötigt wird, der entweder durch einen begin iterator und end sentinel (1) oder durch einen ranges::random_access_range (3) gegeben ist. Der Iterator und der Range müssen den wahlfreien Zugriff unterstützen. Zusätzlich nehmen die Überladungen ein Prädikat Comp und eine Projektion Proj an. Das Prädikat verwendet standardmäßig ranges::less, und die Projektion die Identität std::identity. Eine Projektion ist eine Abbildung einer Menge in eine Teilmenge. In C++20 unterstützt std::ranges::sort keine Execution Policies.
Wie geht's weiter?
In meinem nächsten Artikel werde ich die Überladungen von std::ranges::sort genauer analysieren und insbesondere auf Projektionen und Sentinels eingehen.
()
