C++20: Pythons range-Funktion, die zweite

Inhaltsverzeichnis

Im letzten Artikel "C++20: Pythonisch mit der Ranges-Bibliothek" begann mein Experiment, die beliebten Python-Funktionen range und filter mit der Ranges-Bibliothek zu implementieren. Aufgrund zweier interessanter Kommentare möchte ich mir die Funktion range nochmals genauer anschauen.

Zugegeben, es hat einige Zeit gedauert, bis ich mit der Ranges-Bibliothek vertraut wurde. Die investierte Zeit war aber gut angelegt. Zuerst gibt es eine kleine Erinnerungshilfe. Der Aufruf range(begin, end, step) erzeugt in Python 2 alle Ganzzahlen von begin bis end in step Schrittweite. begin ist inklusive und end ist exklusive. step ist per Default 1.

Over-Engineering

Meine Implementierung der range-Funktion im letzten Artikel war zu kompliziert, wie ein Leser meines deutschen Artikels bemerkte. Der folgende Codeschnipsel zeigt sowohl die zu komplizierte als auch die verbesserte Variante der range-Funktion:

std::vector<int> range(int begin, int end, int stepsize = 1) {
    std::vector<int> result{};
    if (begin < end) {                                     
        auto boundary = [end](int i){ return i < end; };    
        for (int i: ranges::views::iota(begin)               // (2)
                  | ranges::views::stride(stepsize) 
                  | ranges::views::take_while(boundary)) {   // (1)
            result.push_back(i);
        }
    }
    else {                                                
        begin++;
        end++;
        stepsize *= -1;
        auto boundary = [begin](int i){ return i < begin; }; 
        for (int i: ranges::views::iota(end)                
                  | ranges::views::take_while(boundary)      
                  | ranges::views::reverse 
                  | ranges::views::stride(stepsize)) {
            result.push_back(i);
        }
    }
    return result;
}  

std::vector<int> range(int begin, int end, int stepsize = 1) {
    std::vector<int> result{};
    if (begin < end) {
        for (int i: ranges::views::iota(begin, end)         // (3)
                 | ranges::views::stride(stepsize)) {
            result.push_back(i);
        }
    }
    else {
        begin++;
        end++;
        stepsize *= -1;
        for (int i: ranges::views::iota(end, begin)         
                  | ranges::views::reverse 
                  | ranges::views::stride(stepsize)) {
            result.push_back(i);
        }
    }
    return result;
}

Ich habe die Randbedingung (Zeile 1) in der ersten Implementierung entfernt und den unendlichen Zahlenerzeuger ranges::views::iota(begin) (Zeile 2) in einen endlichen Zahlenerzeuger ranges::views::iota(begin, end) (Zeile 3) umgeschrieben. Natürlich wende ich die gleichen Vereinfachungen auch auf den else-Zweig der Bedingung an.

Von range zu xrange

Die vorgestellte range-Funktion ist eager (gierig). Sie erzeugt einen std::vector<int>. Aleksei Guzev erinnerte mich daran, dass Python 2 auch eine lazy (faule) xrange-Funktion besitzt. Diese entspricht der range-Funktion in Python 3. Er hat Recht. Nun bin ich ausreichend vertraut mit der Ranges-Bibliothek, um diese funktionalen Konzepte auf C++ anzuwenden. Wenn dich die Ausdrücke "eager" und "lazy" irritieren, lies meinen vorherigen Artikel "C++20: Funktionale Pattern mit der Ranges-Bibliothek".

Das folgende Beispiel zeigt eine Variante der range-Funktion, die die Bedarfsauswertung (lazy) umsetzt. Konsequenterweise nenne ich die Funktion xrange:

// xrange.hpp

#include <range/v3/all.hpp>

template <long long Begin, long long End>           // (3)
auto xrange(int stepsize = 1) {
    if constexpr (Begin < End) {                    // (2)
        return ranges::views::iota(Begin, End)      // (1)
               | ranges::views::stride(stepsize); 
    }
    else {
        long long end  = End + 1;                   // (4)
        long long begin = Begin + 1;                // (4)
        stepsize *= -1; 
        return ranges::views::iota(end, begin)      // (1)
               | ranges::views::reverse 
               | ranges::views::stride(stepsize);
    }
}

Die Implementierung der lazy xrange-Funktion ist deutlich komplizierter als die eager range-Funktion. Diese Komplexität zahlt sich aber aus. Die folgenden Zahlen entsprechen den Zahlen im Sourcecode:

1. Die xrange-Funktion gibt keinen std::vector<int>, sondern eine Funktionskomposition zurück. Um mir die Aufgabe zu erleichtern, verwende ich den Rückgabetyp auto. Mit ihm beginnt die erste Herausforderung. Die Rückgabetypen des if- und else-Zweigs der Bedingung unterscheiden sich. Funktionen mit verschiedenen Rückgabetypen sind in C++ nicht möglich.
2. Um diese Herausforderung zu meistern, setze ich ein C++17-Feature ein: constexpr if. Es ermöglicht das bedingte Kompilieren. Wenn der Ausdruck constexpr (Begin < End) zu true evaluiert, wird der if-Zweig kompiliert, ansonsten der else-Zweig. Damit die Bedingung gültig ist, müssen Begin und End konstante Ausdrücke sein.
   
3. Begin und End sind jetzt Nicht-Typ-Template-Parameter. Damit lassen sie sich in constexpr if (Zeile 2) verwenden. Ich verwende Nicht-Typ-Template-Parameter vom Typ long long, um mit großen Zahlen umgehen zu können.
   
4. Konstante Ausdrücke wie Begin und End können nicht modifiziert werden. Daher muss ich die Variablen begin und end verwenden, um die Grenzen für den ranges::views::iota-Aufruf anzupassen.
   

Jetzt bin ich neugierig. Hier ist die xrange-Funktion in Anwendung:

// range.cpp

#include "xrange.hpp"

#include <iostream>
#include <range/v3/all.hpp>
#include <vector>

        
int main() {
    
    std::cout << std::endl;

    auto res = xrange<1, 10>();                    // (1)
    for (auto i: res) std::cout << i << " ";
    
    std::cout << "\n\n";
    
    res = xrange<1, 50>(5);                        // (2)
    for (auto i: res) std::cout << i << " ";
    
    std::cout << "\n\n";
    
    auto res2 = xrange<20, 10>(-1);                // (3)
    for (auto i: res2) std::cout << i << " ";
    
    std::cout << "\n\n";
    
    res2 = xrange<50, 10>(-5);                     // (4)
    for (auto i: res2) std::cout << i << " ";
    
    std::cout << "\n\n";
    
    res = xrange<1, 1'000'000'000'000'000'000>();  // (5)
    // for (auto i: res) std::cout << i << " ";    // (6)
    
    
                                                   // (7)
    for (auto i: res | ranges::views::take(10)) std::cout << i << " ";
    
    std::cout << "\n\n";
    
                                                  // (8)
    for (auto i: res | ranges::views::drop_while([](int i){ return i < 1'000'000; })
                     | ranges::views::take_while([](int i){ return i < 1'000'010; })) {
        std::cout << i << " ";
    }
    
    std::cout << "\n\n";
    
}

Die Zeilen (1) bis (4) zeigen, dass sich die Funktion xrange wie die Funktion range verhält. Der einzige Unterschied ist es, dass aus den Funktions- Template-Argumente wurden. Wenn ich alle Zahlen bis zu einer Trillion anfordere (Zeile 6), muss ich das Programm hart beenden.

Die Verwendung von Tics für Zahlen (1'000'000'000'000'000'000) (Zeile 5) ist seit C+14 zulässig und macht große Zahlen deutlich lesbarer. Ich sollte nicht alle Zahlen auf einmal anfordern. Wenn ich nur an zehn Ganzzahlen (Zeile 7) oder an allen Ganzzahlen zwischen 1'000'000 und 1'000'010 (Zeile 8) interessiert bin, funktioniert der xrange-Aufruf wie erwartet. Lediglich die Zahlen werden erzeugt, die nachgefragt werden.

Wie geht's weiter?

Wie bereits in meinem letzten Artikel "C++20: Pythonisch mit der Ranges-Bibliothek" angekündigt, stelle ich im nächsten Beitrag die map-Funktion von Python vor. Sie erlaubt es, eine Funktion auf Sequenzen auszuführen. Aus praktischen Gründen werde ich die Funktion map und filter auch in einer Funktion anbieten. ()