Die Ranges-Bibliothek in C++20: Designentscheidungen
Die Ranges-Bibliothek vereinfacht die Arbeit mit der Standard Template Library (STL). Sie bringt einige wichtige Designentscheidungen mit.
(Bild: SergioVas/Shutterstock)
- Rainer Grimm
Dank der Ranges-Bibliothek ist die Arbeit mit der Standard Template Library (STL) viel komfortabler und leistungsfähiger geworden. Zunächst einmal sind die Algorithmen der Ranges-Bibliothek lazy, können direkt auf dem Container arbeiten und lassen sich zusammensetzen. Außerdem hat die Ranges-Bibliothek ein paar besondere Designentscheidungen getroffen, die man kennen muss.
Bevor ich näher auf die Ranges-Bibliothek in C++20 eingehe, möchte ich die drei wichtigsten Features der Ranges in ein paar Sätzen zusammenfassen: Die Algorithmen der Ranges können direkt auf dem Container operieren, ihre Argumente bei Bedarf auswerten und sie können komponiert werden.
Direkt auf dem Container
Die Ranges-Bibliothek ermöglicht es, dass ein Container wie std::ranges::sort direkt auf dem Container operieren kann:
// 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
}Im Gegensatz dazu agiert der klassische std::sort auf einem Bereich, der durch zwei Iteratoren definiert ist: std:sort(myVec.begin(), myVec.end()).
Die Ranges-Algorithmen sind lazy und können komponiert werden.
Lazy Evaluation und Funktionskomposition
Das folgende Programm primesLazy.cpp wendet beide Features an. Es 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 Funktionszusammensetzung ist von links nach rechts zu lesen: Ich erzeuge einen unendlichen Datenstrom, der mit 1'000'000 beginnt (std::views::iota(1'000'000)) und wende zwei Filter an. Jeder Filter braucht ein Prädikat. Der erste Filter lässt ungerade Elemente passieren (std::views::filter(odd)), und der zweite Filter lässt die Primzahlen passieren (std::views::filter(isPrime)). Nach zehn Zahlen (std::views::take(10)) beende ich den unendlichen Datenstrom. Zum Abschluss sind hier die ersten zehn Primzahlen, die mit einer Million beginnen.
Das wirft die Frage auf, wer die Verarbeitung dieser Datenpipeline beginnt. Nun, es geht von rechts nach links. Die Datensenke (std::views::take(10)) möchte den nächsten Wert haben und fragt seinen Vorgänger an. Diese Anfrage wird so lange fortgesetzt, bis die Range-based for-Schleife den nächsten Wert liefert. Die Schleife kann einen unendlichen Datenstrom produzieren, tut dies aber nur auf Anfrage. Das ist Lazy Evaluation.
Das war meine kurze Zusammenfassung. Wer mehr über die Ranges-Bibliothek, einschließlich Sentinels, Projektion und Concepts, erfahren möchte, liest meine früheren Artikel:
- Die Ranges Bibliothek
- Funktionale Pattern mit der Ranges-Bibliothek
- Die Ranges Bibliothek in C++20: Mehr Details
- Projektionen mit Ranges
- Sentinels und Concepts mit Ranges
- Verbesserte Iteratoren mit Ranges
- Pythonisch mit der Ranges-Bibliothek: range und filter
- Pythons range-Funktion, die zweite
- Die map-Funktion von Python
Jetzt möchte ich aber über etwas Neues schreiben.
Designentscheidungen
Aus Gründen der Effizienz hat die Ranges-Bibliothek einige einzigartige Designentscheidungen gefällt. Es ist wichtig, sie zu kennen und zu befolgen.
Wer die begin-Mitgliedsfunktion von std::ranges::filter_view studiert, findet einen Code, der dem folgenden entspricht:
if constexpr (!ranges::forward_range<V>)
return /* iterator */{*this, ranges::find_if(base_, std::ref(*pred_))};
else
{
if (!begin_.has_value())
begin_ = ranges::find_if(base_, std::ref(*pred_)); // caching
return /* iterator */{*this, begin_.value())};
}Die verschachtelte if-Struktur verdient eine Analyse: Zuerst prüft der Compiler, ob begin_.has_value() true ist. Wenn nicht, bestimmt er begin_. Das bedeutet, dass diese Mitgliedsfunktion das Ergebnis innerhalb des std::ranges::filter_view-Objekts zwischenspeichert, um es bei späteren Aufrufen zu verwenden. Dieses Zwischenspeichern besitzt interessante Konsequenzen. Ich möchte dies anhand eines Code-Schnipsels verdeutlichen.
// cachingRanges.cpp
#include <numeric>
#include <iostream>
#include <ranges>
#include <vector>
int main() {
std::vector<int> vec(1'000'000);
std::iota(vec.begin(), vec.end(), 0);
for (int i: vec | std::views::filter([](auto v) { return v > 1000; })
| std::views::take(5)) {
std::cout << i << " "; // 1001 1002 1003 1004 1005
}
}Der erste Aufruf von std::views::filter([](auto v) { return v > 1000; }) bestimmt den Beginn-Iterator und verwendet ihn in den folgenden Aufrufen wieder. Der Vorteil dieser Zwischenspeicherung ist offensichtlich: Viele nachfolgende Iterationen der Pipeline werden vermieden. Aber es gibt auch gravierende Nachteile: Cache-Probleme und Probleme mit der Konstantheit.
Cache
Hier sind die zwei wichtigsten Cache-Regeln für Ranges:
- Verwende keinen View für einen geänderten Range!
- Kopiere keinen View!
Folgende Änderung des vorherigen Programms cachingRanges.cpp bricht beide Regeln:
// cachingIssuesRanges.cpp
#include <concepts>
#include <forward_list>
#include <iostream>
#include <numeric>
#include <ranges>
#include <vector>
void printElements(std::ranges::input_range auto&& rang) {
for (int i: rang) {
std::cout << i << " ";
}
std::cout << '\n';
}
int main() {
std::cout << '\n';
std::vector<int> vec{-3, 10, 4, -7, 9, 0, 5, -5}; // (1)
std::forward_list<int> forL{-3, 10, 4, -7, 9, 0, 5, -5}; // (2)
auto first5Vector = vec | std::views::filter([](auto v) { return v > 0; }) // (3)
| std::views::take(5);
auto first5ForList = forL | std::views::filter([](auto v) { return v > 0; }) // (4)
| std::views::take(5);
printElements(first5Vector); // 10 4 9 5 // (5)
printElements(first5ForList); // 10 4 9 5 // (6)
std::cout << '\n';
vec.insert(vec.begin(), 10);
forL.insert_after(forL.before_begin(), 10);
printElements(first5Vector); // -3 10 4 9 5
printElements(first5ForList); // 10 4 9 5
std::cout << '\n';
auto first5VectorCopy{first5Vector}; // (7)
auto first5ForListCopy{first5ForList}; // (8)
printElements(first5VectorCopy); // -3 10 4 9 5
printElements(first5ForListCopy); // 10 10 4 9 5
std::cout << '\n';
}
Um das Problem besser nachvollziehen zu können, habe ich die Ausgabe direkt in den Quellcode geschrieben. Das Programm führt die folgenden Schritte mit einem std::vector und einer std::forward_list durch. Zuerst werden beide Container mit der Initialisierungsliste {-3, 10, 4, -7, 9, 0, 5, -5} initialisiert (1) und (2). Dann erstelle ich zwei Views (3) und (4). Die beiden Views first5Vector und first5ForList bestehen aus den ersten fünf Elementen, die größer als 0 sind. In (5) und (6) werden die entsprechenden Werte angezeigt.
Nun breche ich die erste Regel: "Verwende keine View auf geänderte Bereiche". Ich füge am Anfang der beiden Container die Zahl 10 ein. Danach zeigt first5Vector die -3 an und first5ForList ignoriert die eingefügte 10. Nach dem Bruch der zweiten Regel "Don't copy a view" in (7) und (8) wird der Cache von first5ForListCopy ungültig. first5VectorCopy zeigt immer noch die falschen Zahlen an. Zum Abschluss ist hier die Ausgabe des Programms.
Hier ist eine einfache Faustregel: Verwende Views direkt, nachdem du sie definiert hast!
Die Funktion printElements nimmt ihre Argumente per Universal Referenz, auch bekannt als Forwarding-Referenz, entgegen.
Wie geht's weiter?
In meinem nächsten Artikel schreibe ich, warum eine Funktion eine beliebigen View per Universal Referenz annehmen sollte.
Hier noch eine Anmerkung in eigener Sache
Ich muss euch leider mitteilen, dass ich an ALS, einem sehr schwerwiegenden fortschreitenden Nervenleiden erkrankt bin. Daher bin ich mir nicht sicher, wie lange ich diesen Blog noch weiterführen kann. Gegenwärtig kann ich nur noch mit der Hilfe meiner Frau zu Schulungen oder Konferenzen verreisen. Wir (meine Familie und ich) haben uns dazu entschieden, offensiv mit dieser Herausforderung umzugehen. Daher war es mir ein wichtiges Anliegen, euch als meine treuen Leser in meine Krankheit einzuweihen. (rme)
