C++20: Die map-Funktion von Python

16.03.2020 07:07 Uhr Rainer Grimm

Mit der map-Funktion endet das kleine Experiment, beliebte Funktionen aus Python in C++ umzusetzen.

Heute endet das kleine Experiment, beliebte Funktionen aus Python in C++ umzusetzen. Bisher habe ich mir die Funktionen filter, range und xrange genauer angeschaut. Nun geht es um die map-Funktion.

In meinem letzten Artikel "C++20: Pythons range-Funktion [1]" setzte ich eine "lazy" Variante der range-Funktion um: xrange. Einige deutschsprachige Leser haben zurecht moniert, dass meine Implementierung sich nicht wie Pythons xrange-Funktion verhalte. Meine Implementierung setze konstante Ausdrücke für den Anfang und das Ende der erzeugten Zahlen vor:

auto res = xrange<1, 10>();                    
for (auto i: res) std::cout << i << " ";  // 1 2 3 4 5 6 7 8 9

In dem Beispiel sind die Zahlen 1 und 10 die konstanten Ausdrücke. Das bedeutet, dass der folgende Ausdruck nicht gültig ist:

int begin = 1; int end = 10; auto res = xrange<begin, end>();

Pythons range-Funktion, die dritte

Dank des Lesers Clocktown kann ich heute die finale Version von xrange vorstellen. Sie ist lazy und nimmt auch Argumente für die Grenzen an, die nicht notwendigerweise konstante Ausdrücke sein müssen:

// xrange2.hpp

#include <stdio.h>
#include <range/v3/all.hpp>
 
namespace view = ranges::views;

auto xrange(long long begin, long long end, long long step = 1) {
    if(step == 0) {
        throw std::invalid_argument("Step cannot be 0");
    }
    auto Step = begin < end ? step : -step;
    auto Begin = std::min(begin, end);
    auto End = Step < 0 ? Begin : std::max(begin, end);
    return view::iota(Begin, End)
    | view::stride(std::abs(Step))
    | view::transform([begin, end](std::size_t i){
        return begin < end ? i : end - (i - begin);
    });
}

auto xrange(long long end) {
    return xrange(0, end, 1);
}

Die entscheidende Idee dieser Implementierung ist es, dass view::transform die Berechnung gegebenenfalls in eine umgedrehte Berechnung transformiert. xrange lässt sich mit ein, zwei oder drei Argumenten aufrufen. Der Default-Wert für das erste Argument ist 0 und der für das dritte Argument ist 1. Natürlich möchte ich die xrange-Funktion jetzt einsetzen. Ich habe einfach in meinem Beispiel des letzten Artikels die xrange-Funktion mit dieser verbesserten xrange-Implementierung ausgetauscht:

// range2.cpp

#include "xrange2.hpp"

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

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

    auto res = xrange(1, 10);
    for (auto i: res) std::cout << i << " ";
    
    std::cout << "\n\n";
    
    res = xrange(1, 50, 5);
    for (auto i: res) std::cout << i << " ";
    
    std::cout << "\n\n";
    
    auto res2 = xrange(20, 10, -1);
    for (auto i: res2) std::cout << i << " ";
    
    std::cout << "\n\n";
    
    res2 = xrange(50, 10, -5);
    for (auto i: res2) std::cout << i << " ";
    
    std::cout << "\n\n";
    
    res = xrange(1, 1'000'000'000'000'000'000);
    // for (auto i: res) std::cout << i << " ";
    
    for (auto i: res | ranges::views::take(10)) std::cout << i << " ";
    
    std::cout << "\n\n";
    
    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";
    
}

Wie zu erwarten, erhalte ich die gleiche Ausgabe:

Bisher gibt es nichts Neues. Nun folgen aber die Anwendungsfälle, die nur die neue, verbesserte Implementierung unterstützten: begin und end sind keine konstanten Ausdrücke und xrange lässt sich mit einem Argument verwenden:

int main() {

  int begin = 3;
  int end = 7;

  for(auto x: xrange(end)) {
      std::cout << x << " ";  // 0 1 2 3 4 5 6
  }

  for(auto x: xrange(begin, end)) {
      std::cout << x << " ";  // 3 4 5 6

  for(auto x: xrange(end, begin, -2)) {
      std::cout << x << " ";  // 7 5
  }
  
}

Jetzt kann ich endlich die Fortsetzung zur Funktion range abschließen. Dafür geht es jetzt in diesem Artikel mit der Funktion map weiter.

map

Zuerst einmal meine vereinfachte Definition der map-Funktion in Python 2. Ich schränkte sie auf eine Sequenz sein.

map(func, seq): gibt eine Liste zurück, indem die Funktion func auf jedes Element der Sequenz seq angewandt wird.

Wenn du darüber nachdenkst, lauert in dieser Funktion eine Herausforderung. Im Gegensatz zur filter-Funktion von Python (s. C++20: Pythonisch mit der Ranges-Bibliothek [2]) kann die map-Funktion den Typ der Eingabesequenz ändern:

// map.cpp

#include "range.hpp"

#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <range/v3/all.hpp>
#include <string>
#include <vector>
#include <utility>


template <typename Func, typename Seq>
auto map(Func func, Seq seq) {
    
    typedef typename Seq::value_type value_type;
    using return_type = decltype(func(std::declval<value_type>()));     // (4)

    std::vector<return_type> result{};
    for (auto i :seq | ranges::views::transform(func)) result.push_back(i);
    
    return result;
}

int main() {
    
    std::cout << std::endl;
    
    // map(lambda i: i * i, range(1, 10))                               // (1)
    auto res = map([](int i){ return i * i; }, range(1, 10) );          
    
    for (auto v: res) std::cout << v << " ";
    
    std::cout << "\n\n";
                                                                        // (2)
    // map(lambda word: (len(word), word), ["Only", "for", "testing", "purpose."])
    std::vector<std::string> myStrings{"Only", "for", "testing", "purpose"};
    auto res2 = map([](const std::string& s){ return std::make_pair(s.size(), s); }, myStrings);
    
    for (auto p: res2) std::cout << "(" <<  p.first << ", " << p.second << ") " ;
    
    std::cout << "\n\n";
                                                                         // (3)
    // freqWord = map(lambda word: (len(word), word), open("/etc/services").read().split("\n"))
    // freqWord.sort(reverse = True)
    // freqWord[:3]    
    std::ifstream file("/etc/services", std::ios::in);
    std::stringstream buffer;
    buffer << file.rdbuf();
    std::string text = buffer.str();

    std::vector<std::string> words = text | ranges::views::split('\n');   // (4)
    auto lengthWords = map([](const std::string& s){ return std::make_pair(s.size(), s); }, words);
    std::sort(std::begin(lengthWords), std::end(lengthWords), std::greater);
    std::for_each(std::begin(lengthWords), std::begin(lengthWords) + 3, [](const auto& p) {
        std::cout << p.first << " " << p.second << std::endl;
    });
       
    std::cout << std::endl;
    
}

Die Zeile (4) deduziert den Rückgabetyp return_type. Dieser ist der Datentyp, in dem alle Elemente der Eingabesequenz transformiert werden, wenn die Funktion func auf sie angewandt wird. std::declval<value_type>() gibt eine Rvalue-Referenz zurück, die decltype verwendet, um den Rückgabetyp zu deduzieren.

Die auskommentierten Zeilen entsprechen wieder dem Python-Code.

bildet jedes Element auf sein Quadrat ab.
bildet jedes Wort auf ein Paar Länge des Worts und das Wort ab.
liest jede Zeile aus der Datei "/etc/services", bildet jede Zeile auf ein Paar bestehend aus Länge und Zeile ab, sortiert die Sequenz in umgekehrter Reihenfolge und gibt die drei längsten Zeilen aus.

Der Screenshot zeigt die Ausgabe des Programms:

Jetzt habe ich fast vergessen, einen zusätzlichen Punkt zu erwähnen, der mich vor ein größeres Problem gestellt hat, die Funktion map zu implementieren. Der Aufruf std::vector<std::string> words = text | ranges::views::split('\n'); (Zeile 4) ist "deprecated". Stattdessen sollte ich den Konvertierungsoperator ranges::to anwenden. ranges::to ist aber kein Bestandteil von C++20. Daher fragte ich Eric Niebler, den Autor der Ranges-Bibliothek. Er schlug mir eine recht wortreiche Lösung vor, die einen GCC Bugrepot triggert (93936 [3]). Letztlich habe ich die Deprecated-Variante im Beispiel verwendet.

Die Funktion map stellt nicht das Ende meiner Experimente dar. Die Funktionen map und filter lassen sich einfach in einer Funktion kombinieren. Das Ergebnis ist dann eine Funktion, die sich ähnlich wie List Comprehension in Python verwenden lässt. Ehrlich gesagt, bin ich nicht hunderprozentig zufrieden mit meinem Ergebnis.

Ein Hauch von List Comprehension

Meine Funktion mapFilter kann im Gegensatz zum Python-Pendant nur mit einer Sequenz umgehen:

// mapFilter.cpp

#include "range.hpp"

#include <algorithm>
#include <cctype>
#include <fstream>
#include <functional>
#include <iostream>
#include <range/v3/all.hpp>
#include <string>
#include <vector>
#include <utility>

template <typename T>
struct AlwaysTrue {                        // (1)
    constexpr bool operator()(const T&) const {
        return true;
    }
};
                                            // (2)
template <typename Map, typename Seq, typename Filt = AlwaysTrue<typename Seq::value_type>>
auto mapFilter(Map map, Seq seq, Filt filt = Filt()) {
    
    typedef typename Seq::value_type value_type;
    using return_type = decltype(map(std::declval<value_type>()));  

    std::vector<return_type> result{};
    for (auto i :seq | ranges::views::filter(filt) 
                     | ranges::views::transform(map)) result.push_back(i);
    return result;
}

int main() {
    
    std::cout << std::endl; 
                                              // (3)
    // [ i * i for i in range(1, 10) ] 
    auto res = mapFilter([](int i){ return i * i; }, range(1, 10) );
    
                                              // (4)
    // [ i * i for i in range(1, 10) if i % 2 == 1 ]
    res = mapFilter([](int i){ return i * i; }, range(1, 10) , 
                    [](auto i){ return i % 2 == 1; });
    
    for (auto v: res) std::cout << v << " ";
    
    std::cout << "\n\n";
    
                                                // (3)  
    // [(len(word), word) for word in ["Only", "for", "testing", "purpose."]]
    std::vector<std::string> myStrings{"Only", "for", "testing", "purpose"};
    auto res2 = mapFilter([](const std::string& s){ return std::make_pair(s.size(), s); }, myStrings);
    
                                                // (5)
    // [(len(word), word) for word in ["Only", "for", "testing", "purpose."] if word[0].isupper()]
    myStrings = {"Only", "for", "testing", "purpose"};
    res2 = mapFilter([](const std::string& s){ return std::make_pair(s.size(), s); }, myStrings, 
                     [](const std::string& word){ return std::isupper(word[0]); });
    
    for (auto p: res2) std::cout << "(" <<  p.first << ", " << p.second << ") " ;
    
    std::cout << "\n\n";
    
                                                 // (3) 
    // freqWord = [(len(line), line) for line in open("/etc/services").read().split("\n")]
    // freqWord = map(lambda word: (len(word), word), open("/etc/services").read().split("\n"))
    // freqWord.sort(reverse = True)
    // freqWord[:3]    
    std::ifstream file("/etc/services", std::ios::in);
    std::stringstream buffer;
    buffer << file.rdbuf();
    std::string text = buffer.str();

    std::vector<std::string> words = text | ranges::views::split('\n');
    auto lengthWords = mapFilter([](const std::string& s){ return std::make_pair(s.size(), s); }, words);
    std::sort(std::begin(lengthWords), std::end(lengthWords), std::greater());
    
                                                   // (6)
    // len([line for line in open("/etc/services").read().split("\n") if 100 < len(line) < 150])
    words = text | ranges::views::split('\n');
    auto allLines = mapFilter([](const std::string& line){ return line; }, words, 
                              [](const std::string& line){ return 100 < line.size() && line.size() < 150; });
    std::cout << "Number of lines: " << allLines.size();
    
    std::cout << "\n\n";
}

Das Default-Prädikat, das die filter-Funktion anwendet (Zeile 2), gibt immer true zurück (Zeile 1). "Immer true" bedeutet, das die mapFilter-Funktion sich per Default wie die map-Funktion verhält. Wenn du die Zeilen (3) studierst, fällt dir kein Unterschied zum vorherigen Programm map.cpp auf. Nun beginnt aber der Unterschied. Den entsprechenden Python-Code, der List Comprehension verwendet, habe ich auskommentiert.

Zeile (4) berechnet die Quadrate der Zahlen, die ungerade sind.
Zeile (5) gibt die Paare (Länge des Worts, Wort) für die Wörter zurück, die mit einem Großbuchstaben beginnen.
Zeile (6) gibt einen Vektor aller Zeilen der Datei "/etc/services" zurück, die zwischen 100 und 150 Zeichen besitzen.

Wie geht's weiter?

Dieser Artikel war länger als gewöhnlich. In meinem nächsten geht es um verallgemeinerte Funktionen, die unterbrochen und wieder gestartet werden können. Um es kurz zu machen: Mein nächster Artikel behandelt das nächste Feature aus C++20: Coroutinen. ( [4])

URL dieses Artikels:
https://www.heise.de/-4682291

Links in diesem Artikel:
[1] https://heise.de/-4678264
[2] https://heise.de/-4671777
[3] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93936
[4] mailto:rainer@grimm-jaud.de