Wie hilft die neue bereichsbasierte for-Schleife in C ++ 17 Ranges TS?

71

Das Komitee änderte die bereichsbezogene for-Schleife von:

  • C ++ 11:

    {
       auto && __range = range_expression ; 
       for (auto __begin = begin_expr, __end = end_expr; 
           __begin != __end; ++__begin) { 
           range_declaration = *__begin; 
           loop_statement 
       }
    } 
    
  • zu C ++ 17:

    {        
        auto && __range = range_expression ; 
        auto __begin = begin_expr ;
        auto __end = end_expr ;
        for ( ; __begin != __end; ++__begin) { 
            range_declaration = *__begin; 
            loop_statement 
        } 
    }
    

Und die Leute sagten, dass dies die Implementierung von Ranges TS erleichtern wird. Können Sie mir einige Beispiele geben?

Dimitar Mirchev
quelle
6
Der einzige Unterschied, den ich sehen kann, ist, dass 1. die Implementierung erfordert, dass __begin und __end vom gleichen Typ sind. Eine zweite Implementierung ist nicht erforderlich.
Michał Walenciak
7
Ja. Der Vorschlag selbst besagt in der Motivation: Die vorhandene bereichsbasierte for-Schleife ist zu stark eingeschränkt. Der Enditerator wird niemals inkrementiert, dekrementiert oder dereferenziert. Das Erfordernis, ein Iterator zu sein, hat keinen praktischen Zweck. Durch das Lösen der Typanforderungen der bereichsbasierten for-Schleife erhalten Benutzer des Ranges TS die bestmögliche Erfahrung. Ich frage mich, wie diese bestmögliche Erfahrung aussieht. open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0184r0.html
Dimitar Mirchev
1
Hauptsächlich zur Unterstützung von Proxy-End-Iteratoren, nehme ich an.
Red XIII
1
Bereiche ermöglichen Sentinels als Endmarkierungen (z. B. in nullterminierten Zeichenfolgen). Dies war nicht möglich, wenn sowohl __begin als auch __end Iteratoren waren.
Mr.WorshipMe

Antworten:

54

C ++ 11/14 Bereich - forwar überfordert ...

Das WG21-Papier hierfür ist P0184R0, das die folgende Motivation hat:

Die vorhandene bereichsbasierte for-Schleife ist zu stark eingeschränkt. Der Enditerator wird niemals inkrementiert, dekrementiert oder dereferenziert. Das Erfordernis, ein Iterator zu sein, hat keinen praktischen Zweck.

Wie Sie dem von Ihnen veröffentlichten Standardese entnehmen können, wird der endIterator eines Bereichs nur in der Schleifenbedingung verwendet __begin != __end;. Daher muss endnur die Gleichheit vergleichbar sein mit beginund es muss nicht dereferenzierbar oder inkrementierbar sein.

... was operator==für begrenzte Iteratoren verzerrt .

Welchen Nachteil hat das? Nun, wenn Sie einen durch Sentinel getrennten Bereich haben (C-String, Textzeile usw.), müssen Sie die Schleifenbedingung in den Iterator einbinden operator==, im Wesentlichen wie folgt

#include <iostream>

template <char Delim = 0>
struct StringIterator
{
    char const* ptr = nullptr;   

    friend auto operator==(StringIterator lhs, StringIterator rhs) {
        return lhs.ptr ? (rhs.ptr || (*lhs.ptr == Delim)) : (!rhs.ptr || (*rhs.ptr == Delim));
    }

    friend auto operator!=(StringIterator lhs, StringIterator rhs) {
        return !(lhs == rhs);
    }

    auto& operator*()  {        return *ptr;  }
    auto& operator++() { ++ptr; return *this; }
};

template <char Delim = 0>
class StringRange
{
    StringIterator<Delim> it;
public:
    StringRange(char const* ptr) : it{ptr} {}
    auto begin() { return it;                      }
    auto end()   { return StringIterator<Delim>{}; }
};

int main()
{
    // "Hello World", no exclamation mark
    for (auto const& c : StringRange<'!'>{"Hello World!"})
        std::cout << c;
}

Live-Beispiel mit g ++ -std = c ++ 14 ( Assembly mit gcc.godbolt.org)

Das obige operator==für StringIterator<>ist in seinen Argumenten symmetrisch und hängt nicht davon ab, ob der Bereich für begin != endoder ist end != begin(andernfalls könnten Sie den Code betrügen und halbieren).

Für einfache Iterationsmuster kann der Compiler die verschlungene Logik im Inneren optimieren operator==. In der Tat wird für das obige Beispiel das operator==auf einen einzigen Vergleich reduziert. Aber funktioniert dies auch weiterhin für lange Pipelines mit Bereichen und Filtern? Wer weiß. Es ist wahrscheinlich, dass heldenhafte Optimierungsstufen erforderlich sind.

C ++ 17 lockert die Einschränkungen, wodurch begrenzte Bereiche vereinfacht werden ...

Wo genau manifestiert sich die Vereinfachung? In operator==, das jetzt zusätzliche Überladungen aufweist, die ein Iterator / Sentinel-Paar erfordern (in beiden Reihenfolgen für Symmetrie). Die Laufzeitlogik wird also zur Kompilierzeitlogik.

#include <iostream>

template <char Delim = 0>
struct StringSentinel {};

struct StringIterator
{
    char const* ptr = nullptr;   

    template <char Delim>
    friend auto operator==(StringIterator lhs, StringSentinel<Delim> rhs) {
        return *lhs.ptr == Delim;
    }

    template <char Delim>
    friend auto operator==(StringSentinel<Delim> lhs, StringIterator rhs) {
        return rhs == lhs;
    }

    template <char Delim>
    friend auto operator!=(StringIterator lhs, StringSentinel<Delim> rhs) {
        return !(lhs == rhs);
    }

    template <char Delim>
    friend auto operator!=(StringSentinel<Delim> lhs, StringIterator rhs) {
        return !(lhs == rhs);
    }

    auto& operator*()  {        return *ptr;  }
    auto& operator++() { ++ptr; return *this; }
};

template <char Delim = 0>
class StringRange
{
    StringIterator it;
public:
    StringRange(char const* ptr) : it{ptr} {}
    auto begin() { return it;                      }
    auto end()   { return StringSentinel<Delim>{}; }
};

int main()
{
    // "Hello World", no exclamation mark
    for (auto const& c : StringRange<'!'>{"Hello World!"})
        std::cout << c;
}

Live-Beispiel mit g ++ -std = c ++ 1z ( Assembly mit gcc.godbolt.org, die fast identisch mit dem vorherigen Beispiel ist).

... und wird in der Tat ganz allgemeine, primitive "D-Style" -Bereiche unterstützen.

Das WG21-Papier N4382 enthält den folgenden Vorschlag:

C.6 Range Facade- und Adapter-Dienstprogramme [future.facade]

1 Bis es für Benutzer trivial wird, ihre eigenen Iteratortypen zu erstellen, bleibt das volle Potenzial von Iteratoren unrealisiert. Die Bereichsabstraktion macht dies erreichbar. Mit den richtigen Bibliothekskomponenten, sollte es möglich sein , für die Benutzer einen Bereich mit einer minimalen Schnittstelle zu definieren (zB current, doneund nextMitglieder), und haben Iteratortypen automatisch generiert. Eine solche Vorlage für eine Fassadenklasse bleibt als zukünftige Arbeit übrig.

Im Wesentlichen ist dies gleich D-Stil Bereiche (wobei diese Primitive genannt werden empty, frontund popFront). Ein begrenzter Zeichenfolgenbereich mit nur diesen Grundelementen würde ungefähr so ​​aussehen:

template <char Delim = 0>
class PrimitiveStringRange
{
    char const* ptr;
public:    
    PrimitiveStringRange(char const* c) : ptr{c} {}
    auto& current()    { return *ptr;          }
    auto  done() const { return *ptr == Delim; }
    auto  next()       { ++ptr;                }
};

Wenn man die zugrunde liegende Darstellung eines primitiven Bereichs nicht kennt, wie kann man Iteratoren daraus extrahieren? Wie kann man dies an einen Bereich anpassen, der mit range- verwendet werden kann for? Hier ist eine Möglichkeit (siehe auch die Reihe von Blog-Posts von @EricNiebler) und die Kommentare von @TC:

#include <iostream>

// adapt any primitive range with current/done/next to Iterator/Sentinel pair with begin/end
template <class Derived>
struct RangeAdaptor : private Derived
{      
    using Derived::Derived;

    struct Sentinel {};

    struct Iterator
    {
        Derived*  rng;

        friend auto operator==(Iterator it, Sentinel) { return it.rng->done(); }
        friend auto operator==(Sentinel, Iterator it) { return it.rng->done(); }

        friend auto operator!=(Iterator lhs, Sentinel rhs) { return !(lhs == rhs); }
        friend auto operator!=(Sentinel lhs, Iterator rhs) { return !(lhs == rhs); }

        auto& operator*()  {              return rng->current(); }
        auto& operator++() { rng->next(); return *this;          }
    };

    auto begin() { return Iterator{this}; }
    auto end()   { return Sentinel{};     }
};

int main()
{
    // "Hello World", no exclamation mark
    for (auto const& c : RangeAdaptor<PrimitiveStringRange<'!'>>{"Hello World!"})
        std::cout << c;
}

Live-Beispiel mit g ++ -std = c ++ 1z ( Assembly mit gcc.godbolt.org)

Schlussfolgerung : Sentinels sind nicht nur ein nützlicher Mechanismus, um Trennzeichen in das Typsystem zu drücken, sie sind allgemein genug, um primitive Bereiche im "D-Stil" (die selbst möglicherweise keine Vorstellung von Iteratoren haben) als Null-Overhead-Abstraktion für das neue C zu unterstützen ++ 1z Bereich für.

TemplateRex
quelle
39

Die neue Spezifikation erlaubt __beginund __endkann von unterschiedlichem Typ sein, solange __enddies mit __beginUngleichheit verglichen werden kann . __endmuss nicht einmal ein Iterator sein und kann ein Prädikat sein. Hier ist ein dummes Beispiel mit einer Strukturdefinition beginund endMitgliedern, wobei letzteres ein Prädikat anstelle eines Iterators ist:

#include <iostream>
#include <string>

// a struct to get the first word of a string

struct FirstWord {
    std::string data;

    // declare a predicate to make ' ' a string ender

    struct EndOfString {
        bool operator()(std::string::iterator it) { return (*it) != '\0' && (*it) != ' '; }
    };

    std::string::iterator begin() { return data.begin(); }
    EndOfString end() { return EndOfString(); }
};

// declare the comparison operator

bool operator!=(std::string::iterator it, FirstWord::EndOfString p) { return p(it); }

// test

int main() {
    for (auto c : {"Hello World !!!"})
        std::cout << c;
    std::cout << std::endl; // print "Hello World !!!"

    for (auto c : FirstWord{"Hello World !!!"}) // works with gcc with C++17 enabled
        std::cout << c;
    std::cout << std::endl; // print "Hello"
}
rgmt
quelle
Ja. Das ist ein schönes Beispiel, danke. Aber ich habe versucht, ein spezifisches Beispiel für Ranges TS zu finden.
Dimitar Mirchev
4
@ DimitarMirchev: Der Bereich TS definiert eigentlich keine Bereiche. Es definiert eine Reihe von Algorithmen, die auf Bereiche einwirken, und Konzepte TS-Konzepte, mit denen Code geschrieben werden kann, der Bereiche verwendet. Der Bereich TS v1 bietet jedoch keine tatsächlichen Bereichstypen . Es gibt also keine Beispiele, die angegeben werden können.
Nicol Bolas
@NicolBolas Warum ist es mit Ranges TS verwandt? Ich denke , es liegt daran , dass Rang TS unterstützt diese asymmetrische Iterator / Sentinel - Bereiche.
Yakk - Adam Nevraumont
1
@Yakk: Ja, der Range TS definiert Bereichskonzepte, die eine Iterator / Sentinel-Paarung ermöglichen. Es werden jedoch keine tatsächlichen Bereiche definiert, in denen sie verwendet werden. Das einzige, was man vom Range TS zeigen kann, ist ein Konzept. Was einfach sagt "Iterator / Sentinel-Paarungen sind in Ordnung", was wir bereits wissen. Es zeigt kein Beispiel für ihre Verwendung .
Nicol Bolas
2
Ich habe ein Beispiel in n4128 gegeben . Siehe auch den Anhang zu Sentinels und Codegenerierung .
Eric Niebler