Sentinels und Concepts mit Ranges

Die Ranges-Bibliothek in C++20 unterstützt Sentinels. Sentinels stehen für das Ende eines Ranges und können als verallgemeinerte End-Iteratoren betrachtet werden.

Ein Range, der durch einen Beginn-Iterator und einen End-Sentinel bereitgestellt wird, ist eine Menge von Elementen, über die sich iterieren lässt. Die Container der STL sind Ranges, weil ihr End-Iterator das Ende des Ranges markiert.

Modernes C++ – Rainer Grimm

Rainer Grimm ist seit vielen Jahren als Softwarearchitekt, Team- und Schulungsleiter tätig. Er schreibt gerne Artikel zu den Programmiersprachen C++, Python und Haskell, spricht aber auch gerne und häufig auf Fachkonferenzen. Auf seinem Blog Modernes C++ beschäftigt er sich intensiv mit seiner Leidenschaft C++.

Sentinel

Das folgende Beispiel verwendet Sentinels für eine C-Zeichenkette und einen std::vector<int>.

// sentinel.cpp

#include <iostream>
#include <algorithm>
#include <compare>
#include <vector>

struct Space {                        // (1)
bool operator== (auto pos) const {
        return *pos == ' '; 
    }
};

struct NegativeNumber {               // (2)
    bool operator== (auto num) const {
        return *num < 0;   
    }
};

struct Sum {                          // (7)
    void operator()(auto n) { sum += n; }
    int sum{0};
};

int main() {

    std::cout << '\n';

    const char* rainerGrimm = "Rainer Grimm";
   
    std::ranges::for_each(rainerGrimm, Space{}, [] (char c) { std::cout << c; });  // (3)
    std::cout << '\n';
    for (auto c: std::ranges::subrange{rainerGrimm, Space{}}) std::cout << c;      // (4)
    std::cout << '\n';

    std::ranges::subrange rainer{rainerGrimm, Space{}};                            // (5)
    std::ranges::for_each(rainer, [] (char c) { std::cout << c << ' '; });         // (6)
    std::cout << '\n';
    for (auto c: rainer) std::cout << c << ' ';
    std::cout << '\n';
  

    std::cout << "\n";


    std::vector<int> myVec{5, 10, 33, -5, 10};

    for (auto v: myVec) std::cout << v << " ";
    std::cout << '\n';

    auto [tmp1, sum] = std::ranges::for_each(myVec, Sum{});
    std::cout << "Sum: " << sum.sum << '\n';                                   // (8)

    auto [tmp2, sum2] = std::ranges::for_each(std::begin(myVec), NegativeNumber{}, 
                                              Sum{} );            
    std::cout << "Sum: " << sum2.sum << '\n';                                   // (9)

    std::ranges::transform(std::begin(myVec), NegativeNumber{},                 // (10)
                           std::begin(myVec), [](auto num) { return num * num; });
    std::ranges::for_each(std::begin(myVec), NegativeNumber{},                  // (11)
                          [](int num) { std::cout << num << " "; });
    std::cout << '\n';
    for (auto v: std::ranges::subrange{ std::begin(myVec), NegativeNumber{}}) { // (12)
        std::cout << v << " ";
    }

    std::cout << "\n\n";
    
}

Das Programm definiert zwei Sentinels: Space (Zeile 1) und NegativeNumber (Zeile 2). Beide definieren den Gleichheitsoperator. Dank des <compare>-Headers generiert der Compiler automatisch den Nicht-Gleichheitsoperator. Der Nicht-Gleichheitsoperator wird benötigt, wenn Algorithmen wie std::ranges_for_each oder std::ranges::transform mit einem Sentinel verwendet werden. Beginnen wir mit dem Sentinel Space.

Zeile 3 wendet den Sentinel Space{} direkt auf den C-String "rainerGrimm" an. Das Erstellen eines std::ranges::subrange (Zeile 4) ermöglicht es, den Sentinel in einer Range-basierten for-Schleife zu verwenden. Du kannst auch einen std::ranges::subrange definieren und ihn direkt in dem Algorithmus std::ranges::for_each (Zeile 5) oder in einer Range-basierten for-Schleife (Zeile 6) einsetzen.

Mein zweites Beispiel verwendet einen std::vector<int>, der die Werte {5, 10, 33, -5, 10} besitzt. Der Sentinel NegativeNumber prüft, ob eine Zahl negativ ist. Zuerst summiere ich alle Werte mit dem Funktionsobjekt Sum (Zeile 7) auf. std::ranges::for_each gibt ein Paar (it, func) zurück. it ist der Nachfolger des Sentinels und func das Funktionsobjekt, das auf den Range angewendet wird. Dank structured binding kann ich die Variablen sum und sum2 direkt definieren und ihre Werte anzeigen (Zeilen 8 und 9). std::ranges::for_each verwendet den Sentinel NegativeNumber. Folglich hat sum2 die Summe der Zahlen bis zum Sentinel. Der Aufruf std::ranges::transform (Zeile 10) wandelt jedes Element in sein Quadrat um: [](auto num){ return num * num}. Die Transformation endet mit dem Sentinel NegativeNumber. In Zeile 11 und 12 werden die transformierten Werte angezeigt.

Hier ist die Ausgabe des Programms:

Du fragst dich vielleicht, ob ich einen klassischen Algorithmus der STL oder das Ranges-Pendant auf einen Container anwenden soll? Lass mich diese Frage beantworten, indem ich beide miteinander vergleiche.

std-Algorithmen versus std::ranges-Algorithmen

Bevor ich in die Details meines Vergleichs eintauche, möchte ich das Gesamtbild vorstellen:

Ranges unterstützt nicht <numeric>-Algorithmen

Die Ranges unterstützen zwar die Funktionen des <functional> und des <algorithm> Headers, aber nicht die des <numeric> Headers. Der <numeric> Header umfasst mathematische Funktionen wie std::gcd, std::midpoint, std::iota oder std::accumulate.

Lass mich über die interessanteren Unterschiede schreiben.

Unterstützung der Concepts

Die std::ranges-Algorithmen sind das Paradebeispiel für Concepts. Beginnen möchte ich meinen Vergleich mit dem klassischen std::sort und dem neuen std::ranges::sort. std::sort und std::ranges::sort benötigen einen Iterator mit wahlfreiem Zugriff und können damit in konstanter Zeit auf jedes Element ihres Ranges zugreifen. Hier sind die beiden verwendeten Überladungen für std::sort und std::ranges::sort.

• std::sort

template< class RandomIt >
constexpr void sort( RandomIt first, RandomIt last );

• std:ranges::sort

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 = {});

Was passiert, wenn du std::sort oder std::ranges::sort mit einem Container wie std::list aufrufst, der nur einen bidirektionalen Iterator unterstützt?

// sortVector.cpp

#include <algorithm>
#include <list>
 
int main() {
   
   std::list<int> myList{1, -5, 10, 20, 0};
   std::sort(myList.begin(), myList.end());
    
}

Das Kompilieren des Programms sortVector.cpp mit dem GCC verursacht eine epische Fehlermeldung von 1090 Zeilen.

// sortRangesVector.cpp

#include <algorithm>
#include <list>
 
int main() {
   
   std::list<int> myList{1, -5, 10, 20, 0};
   std::ranges::sort(myList.begin(), myList.end());
    
}

Die Verwendung von std::ranges::sort anstelle von std::sort reduziert die Länge der Fehlermeldung drastisch. Jetzt erhalte ich nur 57 Fehlerzeilen.

Ehrlich gesagt, sollte die Fehlermeldung des GCC einfacher zu lesen sein, aber hier möchte ich nicht tadeln, da wir uns noch im Anfangsstadium der Unterstützung von Concepts befinden. Dies sind die ersten 10 der 57 Zeilen. Ich habe die kritische Meldung in Rot markiert.

Wie geht es weiter?

Ich habe meinen Vergleich zwischen den std-Algorithmen und ihren Ranges-Pendants noch nicht abgeschlossen. In meinem nächsten Artikel werde ich über die vereinheitlichten Lookup-Regeln, die die Tanges-Algorithmen bieten, und über zusätzliche Sicherheitsgarantien schreiben. (map)