Thomas Hartwig 8 min 16.12.2020

C++ 20: Ranges

In diesem Blog-Beitrag finden wir heraus, was Ranges sind, besprechen die Vorteile und zeigen einige Beispiele, wie diese angewendet werden können.

C++20 ist die umfangreichste Revision der Programmiersprache seit über 10 Jahren und vergleichbar mit dem Einfluss, den C++11 hatte. Der Standard ist inhaltlich komplett und aktuell in den letzten Zügen der Veröffentlichung. Es wird eine Menge zum Teil sehr große, neue Features geben. Wir bekommen unter anderem Coroutines, Concepts, Modules, eine neue String Formatting Library und Ranges. Viele der Features werden sogar heute schon von einigen Compilern unterstützt.

Ranges basieren in ihrer Implementierung zum Teil auf Concepts und versprechen einen einfacheren, sichereren und komfortableren Umgang mit Containern in C++. Container sind ein integraler Bestandteil vieler Programme: Fehler im Umgang mit diesen sind nicht selten und teilweise nicht direkt offensichtlich.

Container und ihre Iteratoren

Prinzipiell sind alle Container wie z. B. std::vector bereits Ranges. Die Basisdefinition könnte lauten: Ranges sind abstrakte Ansammlungen von Objekten, über die iteriert werden kann. Um als Range klassifiziert werden zu können, müssen mindestens die Methoden begin() und end() vorhanden sein.
Fast alle Container haben diese Methoden, welche uns Iteratoren zurückgeben. Wenn wir auf einige oder alle Elemente von Containern bestimmte Algorithmen wie zum Beispiel std::sort anwenden wollen, dann sind bis heute Iteratoren das einzige Mittel der Wahl. Wobei Iteratoren keineswegs etwas Schlechtes sind, sind sie doch zuweilen etwas umständlich zu handhaben und leicht falsch zu verwenden. C++20 Ranges bauen auf den grundlegenden Konzepten von Iteratoren auf und geben uns so neue Möglichkeiten. Die C++20 Ranges sind keine Revolution zu Iteratoren, sondern eher eine Evolution.

Das folgende Beispiel zeigt, wie ein Vector heutzutage sortiert werden kann.

std::vector<int> vec{2, 5, 3, 1, 4, 8, 10};
std::sort(vec.begin(), vec.end());


Das ist natürlich nicht unfassbar schrecklich, allerdings auch nicht sonderlich gut. Zumal kein Compiler der Welt sich beschweren würde, wenn wir statt vec.end() vielleicht othervec.end() verwenden würden. Keine Compiler-Fehlermeldungen, sondern nur sehr komische Fehler zur Laufzeit. Mit der C++20 Ranges Library könnten wir diesen Fehler vollständig vermeiden und den Code sogar besser lesbar machen:

std::vector<int> vec{2, 5, 3, 1, 4, 8, 10};
std::ranges::sort(vec);


Einigen wird der neue Nested Namespace std::ranges dabei aufgefallen sein. Alle neuen coolen Features befinden sich unter diesem Nested Namespace, um euren alten Code weiterhin ganz normal lauffähig zu halten. Ranges sind also ein Opt-in Feature. Ihr müsst euch explizit dafür entscheiden diese zu verwenden. Sämtliche Algorithmen im <algorithm> Header bekommen mit C++20 Range based Overloads und können verwendet werden 🎉. Leider müssen Algorithmen aus <numeric> wohl noch bis C++23 warten.

#perfmatters

Performance, wer mag sie nicht? Wir alle lieben es, wenn unser Code schneller läuft! Auch dafür hat Ranges etwas parat. Zugegeben ist diese Anwendung etwas spezifisch, aber beschleunigt – wo anwendbar – euren Code. Gemeint sind Sentinels. Ein Sentinel ist im Prinzip kein Iterator, kann jedoch mit einem verglichen werden. Es gibt einige spezielle Sentinels, wir sprechen hier aber mal nur über einen: unreachable(). Dieser Sentinel ist, wie der Name schon sagt, niemals erreichbar und beschreibt damit eine unendliche Range. Wie genau kann das euren Code schneller machen? Wenn wir z. B. in einem Vector ein bestimmtes Element suchen, von dem wir wissen, dass dies auf jeden Fall im Vector existiert, würde man für gewöhnlich std::find verwenden.

int n = 3;
std::vector<int> v{0, 1, 2, 3, 4};
auto result = std::find(std::begin(v), std::end(v), n);
std::cout << n << "is at position" << result << '\n';


Schaut man sich diesen Code an ist ersichtlich, dass wir keine Möglichkeit haben std::find mitzuteilen, dass das gesuchte Element auch wirklich in dem Container ist. Wir enthalten dem Compiler Information vor. Tun wir das, dann kann er auch weniger optimieren. Eine typische std::find Implementierung würde vielleicht so aussehen:

template<class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}


Es ist ersichtlich, dass hier zwei Vergleiche gemacht werden müssen: Einmal der eigentlich wichtige Vergleich, ob das betrachtete Element das gesuchte Element ist – und dazu, ob man schon am Ende des Containers angekommen ist. Durch den Einsatz des unreachable() Sentinels kann man dem Compiler mitteilen, dass das Element auf jeden Fall gefunden werden wird.

int n = 3;
std::vector<int> v{0, 1, 2, 3, 4};
auto result = std::ranges::find(v.begin(), ranges:: unreachable_sentinel, n);
std::cout << n << "is at position" << result << '\n';


Was macht den Code hier schneller? Wird ein unreachable_sentinel mit irgendetwas verglichen, so ergibt dieses Ergebnis immer false! Wenn wir uns die Implementierung von std::find anschauen, erkennen wir, dass der erste Vergleich somit immer true ergeben wird. Dadurch wird der Compiler diesen Vergleich heraus optimieren und somit effizienteren Code erzeugen.

Projections

Wollen wir alle nicht schon mal einen Container nach einer bestimmten Eigenschaft ihrer Elemente sortieren? Zum Beispiel einen Vector von Angestellten nach ihrer Personalnummer oder dem Nachnamen? Wobei wir alle das natürlich schon hunderte Male getan haben, können wir das in Zukunft dank Projections um einiges eleganter tun!

Wie wir es bisher gemacht haben:

std::sort( employees, []( auto & a, auto & b ) { return a.id < b.id ; } ) ;


Wir haben also Lambdas verwendet, um unsere eigene Vergleichsfunktion zu schreiben. Dabei könnten folgende kleine Fehler unbeabsichtigt zum Problem werden:

// using a wrong comparison operator 
std::sort( employees, []( auto & a, auto & b ) { return a.id > b.id ; } ) ;

// It doesn't compare the two parameters.
std::sort( employees, []( auto & a, auto & b ) { return a.id < a.id ; } ) ;

// comparing wrong data members.
// the types are same so compiler don't warn it.
std::sort( employees, []( auto & a, auto & b ) { return a.id < b.account ; } ) ;


All diese Beispiele würde der Compiler freundlich durchwinken, da alles syntaktisch absolut korrekter Code ist. Probleme würden hier erst zur Laufzeit festgestellt werden. Wenn wir jetzt Projections verwenden, könnten wir es so lösen:

std::ranges::sort( employees, std::ranges::less{}, &Employee::id) ;


Wir können also sehr viel klarer zu verstehenden Code schreiben, der weniger anfällig für unbeabsichtigte Fehler ist! Wir können einfach std::ranges::less und einen Pointer auf ein Data Member als Argumente mitgeben und sind fertig. All das funktioniert unter der Haube durch die Magie von std::invoke. Auf die die Details dazu verzichten wir hier an dieser Stelle.

Views

Views selbst sind Ranges, die im Prinzip Subsets von anderen Ranges sind. Diese werden durch die Anwendung von Algorithmen oder anderen Operationen erzeugt. Wichtig ist hier, dass diese Elemente die Daten nicht besitzen, sondern nur in Abhängigkeit der originalen Range existieren. Sie bestehen quasi nur aus ihrem Algorithmus und der Zeit, die benötigt wird, um sie zu konstruieren. Sie sind daher extrem speichereffizient! Jegliche Transformation wird erst angewendet, wenn das spezifische Element angefragt wird und nicht wenn der View erstellt wird. Dieses Verhalten nennt man Lazy Evaluation.

std::vector vec{1, 2, 3, 4, 5, 6};
auto v = std::views::reverse(vec);


Der View v speichert bei diesem Beispiel keinerlei Daten. Dadurch ist die Zeit, die zur Erstellung benötigt wird, sowie die Größe im Speicher vollkommen unabhängig von der Größe des Vectors vec. Die Aufmerksamen unter euch haben bestimmt bemerkt, dass wir

auto v = std::views::reverse(vec);

anstatt

std::views::reverse v{vec};


geschrieben haben. Das liegt daran, dass std::views::reverse nicht der eigentliche View ist, sondern ein Adaptor, welcher die eigentliche Range – hier den Vector vec – nimmt und einen View über diesen Vector zurückgibt. Das wird hier durch die Verwendung von auto etwas verschleiert. Aber das ist auch gar nicht wichtig: Wichtig ist hier, dass diese Adaptoren verkettet werden können! Das Ganze passiert mittels des Pipe Operators, wie ihr ihn vielleicht von der Befehlszeile kennt. Eine solche Kette könnte wie folgt aussehen:

std::vector vec{1, 2, 3, 4, 5, 6};
auto v = vec | std::views::reverse | std::views::drop(2);

Der View v würde am Ende nur noch 4, 3, 2, 1 enthalten, da wir zuerst den Vector umdrehen und dann die ersten beiden Elemente entfernen.

Fazit

Durch die Macht, die C++20 Ranges bieten, lassen sich viele Anwendungen künftig einfacher und deutlich robuster implementieren. Man muss sich mit der neuen Syntax und den Konzepten etwas vertraut machen, der Aufwand lohnt sich jedoch auf jeden Fall! Euer Code wird ausdrucksstärker, robuster und um einiges kürzer!

Tanja Brodbeck 2 min 14.12.2020

Fragen an das Backend-Team

Wir haben mit Thomas, unserem Teamleiter der Backend Entwicklung über seine Arbeit und Erfahrungen in Projekten gesprochen. Seine Antworten dazu könnt ihr in unserem nachfolgenden Beitrag lesen.

Tanja Brodbeck 2 min 07.12.2020

Fragen an das Frontend-Team

Wir haben mit unserem Werkstudent David über seine Arbeit und seine Wertvorstellung als angehender Frontend-Entwickler gesprochen. Seine Antworten dazu könnt ihr in unserem nachfolgenden Beitrag lesen.

Timo Clasen 4 min 04.01.2017

homee 2017

Im Januar 2016 haben wir nach langer Entwicklungszeit homee 2.0 veröffentlicht 🚀