Wieso Iteratoren statt Zeigern oder statt Indizes?



  • Tachyon schrieb:

    Naja, im Prinzip hast Du das doch mit boost.range . Inzwischen gibt es da sogar die Adaptoren (seit 1.44, glaube ich) mit denen man ein paar zusätzliche nette Konzepte bekommt:
    [...]

    Ich muss gestehen, dass ich mich bisher nicht allzu intensiv mit Boost.Range auseinander gesetzt habe. Mir ist nur der Unterschied aufgefallen, dass das Boost-Konzept einer "Range" keine Kopiersemantik beinhaltet. Auf der einen Seite ist das praktisch, da man so die Grenzen zwischen Iterator-artigen Ranges (Referenzsemantik) und Container-artigen Ranges (Wertesemantik) vermischen kann. Auf der anderen Seite ist das natürlich auch ein Nachteill -- würd eich zumindest vermuten. Da find ich Andreis Ansatz schon okay (Referenzsemantik so wie bei Iteratoren).

    Ich könnte mir aber auch vorstellen, dass es Spezialisierungen des Range-Konzepts gibt bzgl Kopiersemantik, die man dann per traits-Klasse abfragen kann. Müsste ich mal wieder Reingucken, in die Doku...

    Gruß,
    kk



  • krümelkacker schrieb:

    Tachyon schrieb:

    Naja, im Prinzip hast Du das doch mit boost.range . Inzwischen gibt es da sogar die Adaptoren (seit 1.44, glaube ich) mit denen man ein paar zusätzliche nette Konzepte bekommt:
    [...]

    Ich muss gestehen, dass ich mich bisher nicht allzu intensiv mit Boost.Range auseinander gesetzt habe. Mir ist nur der Unterschied aufgefallen, dass das Boost-Konzept einer "Range" keine Kopiersemantik beinhaltet.
    ...

    Ah, und natürlich gibt es beim Boost-Range-Konzepr wieder Iteratoren. Andrei's Ansatz verzichtet auf Iteratoren (daher auch "iterators must go" als Titel seiner Präsentation). Und das hat die Sache IMHO interessant gemacht.



  • krümelkacker schrieb:

    Ah, und natürlich gibt es beim Boost-Range-Konzepr wieder Iteratoren. Andrei's Ansatz verzichtet auf Iteratoren (daher auch "iterators must go" als Titel seiner Präsentation). Und das hat die Sache IMHO interessant gemacht.

    Du hast Recht, das ist eine sehr interessante Sache mit sehr interessanten Beispielen. Wie ich das sehe, sind diese Ranges aber nicht in der Lage, Iteratoren vollständig oder vollständig elegant zu ersetzen. Nämlich immer dann, wenn ich mit Iteratoren nicht einen Bereich, sondern nur eine Position angeben will.

    Das Beispiel mit find hat Andrei schon benutzt. Hier hat er fix den Rückgabewert von Iterator auf gefundenes Element zu Range von gefundenen Element bis Ende geändert. Das mag in den meisten Anwendungen ausreichend oder genau richtig sein, ist aber schon irgendwie willkürlich. Nehmen wir an, ich wöllte die Range vom Beginn bis zum gefundenen Element. Mit Iteratoren einfach, ich merke mir den Anfangs-Iterator. Auch mit Boost.Range einfach, das kapselt ja auch nur Iteratoren. Aber bei Andrei? Ich sehe jetzt nicht, wie man unter der Voraussetzung find einfach implementieren könnte, die Ranges sind hier einfach zu starr.

    Nehmen wir unique . Hier wäre es es wirklich sinnvoll, eine Range von Beginn bis gefundenen Iterator zu haben, damit ich darauf weiter arbeiten kann. Das geht also schonmal nicht. Aber nehmen wir die Implementeirung von unique an sich. Fällt dir spontan ein, wie man die recht einfache Impementierung von http://www.cplusplus.com/reference/algorithm/unique/ auf Ranges übertragen könnte? Ich hänge mich da gerade am result -Iterator auf. Oder hast du stattdessen eine ähnlich einfache rangespezifische Implementierung?
    Edit: Ok, man kann am Anfang die Range kopieren und dann mit beiden Ranges arbeiten. Zwar etwas erhöhter Speicherbedarf, aber akzeptabel. Vergiss also den Punkt.

    Betrachten wir die Conatiner-Funktion erase . Die könnte man mit Ranges so formulieren, dass sie den zu löschenden Bereich übernimmt. Dadurch spart man sich sogar beide Overloads. Nun möchte ich aber das zweite Element löschen. Wie bekomme ich schnell und einfach eine Range, die nur das zweite Element enthält? Bei Iteratoren müsste ich nur den Beginn-Iterator inkrementieren.

    Noch schlimmer wirds bei insert . Ich brauche einen Iterarator für die Einfügeposition. Wie soll man das logisch durch eine Range darstellen? Alles, was mir jetzt so einfiehle (z.B. Range von Einfügeposition bis irgendwohin) ist pure Willkür.

    Außerdem sind Ranges, wenn man sie denn mal hat, toll, aber beim Erstellen sind sie zu unflexibel. Ich möchte z.B. mal angenommen aus einer Range eine kleinere Range "ausschneiden", erhalte also 2 Ranges, die vor bzw. hinter der ausgeschnittenen Range liegen. Mit Iteratoren kein Problem und praktisch kostenlos, egal welcher Iteratortyp. Aber mit Ranges? Und ich bin sicher, ähnliche Beispiele lassen sich manche finden. Die Container müssten dafür alle eigene Funktionen anbieten, weil nur sie Zugriff auf die rangeinternen Beginn- und End-Zeiger bzw. -Iteratoren haben und alle generischen Algorithmen nicht. Denn da sind wir auch schon beim letzten Punkt. Bei der compilerspezifischen Rangeimplementierung braucht man wieder Iteratoren, die Anfang und Ende der Range markieren. Das können auch Zeiger sein, man muss sie z.B. nicht inkrementieren können, aber eigentlich ist es das Gleiche. Und wenn das so ist, brauch man diese auch nicht in der Range zu verstecken und das Konzept als genial neu verkaufen, sondern kann sie gleich öffentlich machen und erschenkt sich damit sehr viel Flexibilität.

    Zusammengefasst finde ich die Ranges sehr interessant, ich befürworte auch sehr, statt 2 Iteratoren nur noch eine Range haben zu müssen. Am Ende sind die Ranges aber zu unfexibel, wenn man nicht doch wieder Iteratoren benutzt. Deshalb finde ich Ansätze wie Boost.Range bessser.



  • Tja, keine Ahnung. Angeblich hätte er all die Funktionalitäten der C++ STL mit "seinen Ranges" nachgebaut.

    Ich könnte mir vorstellen, dass er dazu auch Operationen anbietet, die aus zwei Ranges, die eine gemeinsame Grenze haben, eine neue erzeugt. Beispiel:

    |-range1-----------|
                    |-range2-|
    -->
          |-range3--|
    

    ("XOR")

    Dann könntest Du in deinem find-Beispiel schreiben

    auto range3 = allof(numbers) ^ find(allof(numbers),42);
    

    unique könnte man ja ähnlich wie in C++ implementieren:

    template<class ForwardRange>
    ForwardRange unique(ForwardRange rng)
    {
      if (rng.empty()) return rng;
      ForwardRange result = rng;
      for (;;) {
        rng.pop_front();
        if (rng.empty()) break;
        if (!(rng.front()==result.front())) {
          result.pop_front();
          result.front() = rng.front();
        }
      }
      result.pop_front();
      return result;
    }
    

    Falls ich da jetzt keine Fehler gemacht habe, liefert unique eine Range für die Elemente zurück, die man dann direkt per container.erase(...) löschen kann, also

    vector<int> numbers = ...;
    sort( allof(numbers) );
    numbers.erase( unique(allof(numbers)) );
    

    Mit der xor-Funktion kann man sich aber auch eine andere range basteln:

    vector<int> numbers = ...;
    sort( allof(numbers) );
    show( allof(numbers) ^ unique(allof(numbers)) );
    

    (entsprechende Funktionen erase,sort,show vorausgesetzt)

    insert fügt in C++ ja das Element vor dem Element ein, auf das der Iterator zeigt. Das lässt sich genauso übertragen. container.insert(range,42) würde dann die 42 vor der range einfügen. So gesehen ist ein Iterator nur ein Spezialfall einer Range mit einem oder keinem Element. Der Unterschied: Ein Iterator weiß nicht, ob er gültig ist (oder der end-Iterator ist), wobei eine Range weiß, ob sie leer ist. Aus Sicherheitsgründen kann man Ranges auch nur verkleinern (pop_front, pop_back). Und trotzdem scheint man alles damit machen zu können. Wie so etwas ohne so ein Range-XOR gehen soll, weiß ich allerdings auch nicht. Ich schätze, dass das schon notwendig ist.

    Mal überlegen, ob ich die Zahl der Operationen auf Ranges möglichst klein kriege, ohne dass sie damit weniger mächtig werden als Iteratoren:

    Signatur                                  Bedingung(en)
    ------------------------------------------------------------------------
    allof : container c --> range r
    empty : range x --> bool b
    pop_front : range x --> range y           !empty(x)
    pop_back : bidi_range x --> bidi_range y  !empty(x)
    front : range x --> T&                    !empty(x)
    back : bidi_range x --> T&                !empty(x)
    size : range x --> int i                  x ist "endlich"
    at : (ra_range x, index i) --> T&         0 <= i,
                                              x ist unendlich oder i<size(x)
    
    xor : (range x, range y) --> range z      x und y haben eine gemeinsame Grenze
      (liefert eine dritte Range z, die die Elemente umfasst,
       welche nur entweder in x oder in y enthalten sind.)
    

    Kommt man damit aus?

    Leider finde ich die D-Implementierung seiner Container/Range Bibliothek nicht auf Anhieb.



  • krümelkacker schrieb:

    Ich könnte mir vorstellen, dass er dazu auch Operationen anbietet, die aus zwei Ranges, die eine gemeinsame Grenze haben, eine neue erzeugt.

    Nette Idee. Ich habe zusätzlich zu den Ranges wieder Iteratoren zugelassen, weil ich zu oft Sachen wie einen Dateipuffer hatte, mit begin/readpos/end, und beide Ranges werden irgendwo gebraucht. Wichtiger als der Operator wäre überhaupt die BorderSharingDoubleRange. Gegen andere Grenzen bin ich noch nicht gestoßen, wenn ich mich recht erinnere.
    Und was passiert mit Quicksort, wo wir vier Iteratoren und drei Ranges mit zwei gemeinsamen Grenzen haben? Vielleicht auch so eine Klasse machen und mal schauen, wie es sich anfühlt.



  • volkard schrieb:

    krümelkacker schrieb:

    Ich könnte mir vorstellen, dass er dazu auch Operationen anbietet, die aus zwei Ranges, die eine gemeinsame Grenze haben, eine neue erzeugt.

    ...
    Und was passiert mit Quicksort, wo wir vier Iteratoren und drei Ranges mit zwei gemeinsamen Grenzen haben?

    Soweit habe ich noch nicht gedacht. Ich würde als erstes versuchen, partition zu implementieren:

    template<class BidiRange, class Predicate>
    BidiRange partition(BidiRange r, Predicate p);
    

    und dann Quicksort

    template<class BidiRange>
    void quicksort(BidiRange r)
    {
      if (r.empty() || r.size()==1) return;
      auto pivotelement = r.front();
      BidiRange t = partition(r, ...x<pivotelement... );
      quicksort(t);
      quicksort(t^r);
    }
    

    Es ist zugegebenermaßen ein Umdenken. Ich befürchte, dass man nicht drum herum kommt, einige Ranges als Iteratoren zu missbrauchen. Bei partition bräuchte ich zwei Ranges, statt zwei Iteratoren:

    template<class BidiRange, class Predicate>
    BidiRange partition(BidiRange r, Predicate p)
    {
      BidiRange u = r; // u = "unchecked"
      // Invarianten:
      //   |----r----|
      //       |--u--|
      //   u ist in r enthalten (teilen sich ein gemeinsames Ende)
      //   r "schrumpft rechts" (die rechte Grenze wird verschoben)
      //   u "schrumpft beisdeitig"
      //   p(x) für alle x aus r^u
      for (;;) {
        while (!u.empty() &&  p(u.front()) {
          u.pop_front();
        }
        while (!u.empty() && !p(u.back()) {
          u.pop_back();
          r.pop_back();
        }
        if (!u.empty()) {
          swap( u.front(), u.back() );
          u.pop_front();
          u.pop_back();
          r.pop_back();
        } else {
          break;
        }
      }
      return r; // erste Haelfte
    }
    

    (alles ungetestet)



  • Interessante Diskussion 🙂

    Ich müsste mich auch mal ausführlich mit Boost.Range befassen. Ich denke aber ebenfalls, manchmal wäre es praktisch, vom Iterator zu abstrahieren (oder geht das bereits?). Denn oft würde wahrscheinlich ein

    range<int>
    

    reichen (eventuell noch mit Zugriff/Traversal-Kategorie). Der Vorteil wäre einerseits, dass man sich so Abhängigkeiten spart, da man nicht den ganzen Container und dessen Iterator kennen muss, andererseits ist man durch die Abstraktion auch flexibler und kann z.B. verschiedene Container in eine Range packen. Oder sogar Dinge, die gar keine Container sind und auch keine Iteratoren haben. Der Nachteil wäre, dass die Umsetzung mit Type Erasure Polymorphie benötigt und dadurch die Dereferenzierung langsamer wird. Ausserdem würde man Low-Level-Informationen verlieren.

    Alexandrescu geht in die Richtung, oder? Gibts dazu irgendwelche Implementierungen? Beim kurzen Suchen bin ich auf ITL und RangeLib gestossen, habt ihr vielleicht schon welche genauer angeschaut?

    Und krümelkacker, ich fände ehrlich gesagt ein Minus intuitiver als ein XOR (es sei denn man will effektiv eine Art symmetrische Differenz) 😉



  • krümelkacker schrieb:

    volkard schrieb:

    krümelkacker schrieb:

    Ich könnte mir vorstellen, dass er dazu auch Operationen anbietet, die aus zwei Ranges, die eine gemeinsame Grenze haben, eine neue erzeugt.

    ...
    Und was passiert mit Quicksort, wo wir vier Iteratoren und drei Ranges mit zwei gemeinsamen Grenzen haben?

    Soweit habe ich noch nicht gedacht. Ich würde als erstes versuchen, partition zu implementieren:

    Mein "wo wir vier Iteratoren und drei Ranges mit zwei gemeinsamen Grenzen haben" war anders gemeint.
    Sorry, "3-way partitioning is the method of choice".
    http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf



  • Nexus schrieb:

    Interessante Diskussion 🙂

    Heheh 🙂
    Ja, auch wenn das vielleicht n bissel thread-hijacking ist ...
    ich find's interessant.

    Nexus schrieb:

    Ich müsste mich auch mal ausführlich mit Boost.Range befassen.

    Nur damit das klar ist, ich spreche von Ranges a la Andrei, die als Ersatz für Iteratoren gedacht sind. Logisch gesehen verhalten sie sich wie ein Iterator-Paar mit folgenden Einschränkungen:

    • den ersten kann man nur inkrementieren (bis er gleich dem zweiten wird)
    • den zweiten kann man nur dekrementieren (bis er gleich dem ersten wird und falls es keine ForwardRange ist)
    • man kann die Iteratoren aus dem Paar nicht extrahieren(!). Der Zugriff auf die Elemente geschieht über entsprechende Funktionen front/back für erstes und letztes Element der Range und man kann das Range-Objekt fragen, ob es "leer" ist (und ggf auch die Elementanzahl falls bekannt).

    Motivation, soweit ich das verstehe, war es, einerseits ein sichereres Primitiv zu erzeugen. (Iteratoren sind dumm. Man kann sie nicht fragen, ob sie auf etwas gültges zeigen, oder ob man ++ bzw -- noch aufrufen darf) und andererseits ist es praktisch, wenn man nicht zwei Objekte braucht, um eine Sequenz zu beschreiben.

    Nexus schrieb:

    Ich denke aber ebenfalls, manchmal wäre es praktisch, vom Iterator zu abstrahieren (oder geht das bereits?). Denn oft würde wahrscheinlich ein

    range<int>
    

    reichen (eventuell noch mit Zugriff/Traversal-Kategorie). Der Vorteil wäre einerseits, dass man sich so Abhängigkeiten spart, da man nicht den ganzen Container und dessen Iterator kennen muss,

    Ahh... Dann denkst Du da aber gerade an etwas anderes als ich. Worauf Du anspielst, ist Type-Erasure für Ranges/Iteratoren.

    Nexus schrieb:

    Alexandrescu geht in die Richtung, oder?

    Nein.

    Nexus schrieb:

    Gibts dazu irgendwelche Implementierungen? Beim kurzen Suchen bin ich auf ITL und RangeLib gestossen, habt ihr vielleicht schon welche genauer angeschaut?

    Noch nicht. Ich will jetzt auch nicht behaupten, dass Andrei's Idee super toll wäre. Dass mich da keiner falsch versteht. 🙂

    Nexus schrieb:

    Und krümelkacker, ich fände ehrlich gesagt ein Minus intuitiver als ein XOR (es sei denn man will effektiv eine Art symmetrische Differenz) 😉

    Es ist ja gar keine Differenz. Du kannst per XOR auch sich berührende Ranges zusammenführen. Damit da aber wieder eine Range rauskommt, müssen die beiden Eingabe-Ranges mindestens eine gemeinsame Grenze haben. So erschlägt man IMHO viel Funktionalität mit nur einer Funktion. Ob das überhaupt praktikabel ist, ist eine andere Frage. Wenn ich da so darüber nachdenke, wie man das implementieren könnte, komme ich zum Schluss, dass es in einigen Fällen nötig ist, Grenzen zu vergleichen, wenn man die Funktion komplett symmetrisch bauen will. Also, man muss bei sich überlappenden Ranges herausfinden, welches die größere ist. Und das geht bei verkettenen Listen nur dann, wenn man sich zusätzlich die Größe der Range merkt. Ich komme außerdem auf 14 verschiedene Fälle, die zwischen zwei Ranges auftreten können, von denen nur 9 für XOR zulässig wären. Das ist ein saftiger Haufen von Fallunterscheidungen. 😞 Vielleicht ist das mit XOR doch keine so gute Idee und man sollte sich speziellere Funktionen überlegen, bei denen man nicht so viele Fälle betrachten muss. Irgendwie kommt mir der Anrei-Ranges-Ansatz nicht mehr so elegant vor wie damals, als ich das Video dazu gesehen hatte.



  • krümelkacker schrieb:

    Nur damit das klar ist, ich spreche von Ranges a la Andrei, die als Ersatz für Iteratoren gedacht sind.

    Ich meinte mehr, ich müsste mal eine Implementierung anschauen, denn Ranges kenn ich eigentlich nur aus der Theorie 😉

    krümelkacker schrieb:

    Nexus schrieb:

    Alexandrescu geht in die Richtung, oder?

    Nein.

    Hmm, das Gefühl hatte ich wohl, weil in Iterators Must Go die Iteratoren komplett wegabstrahiert sind (und man ja trotzdem an die STL anknüpfen muss). Aber wahrscheinlich ist das nur ein theoretisches (hätte es nie Iteratoren gegeben) oder vereinfachtes Beispiel.

    template<class T> // <- hier T und nicht I
    struct InputRange {
       bool empty() const;
       void popFront();
       T& front() const;
    };
    

    krümelkacker schrieb:

    Es ist ja gar keine Differenz. Du kannst per XOR auch sich berührende Ranges zusammenführen. Damit da aber wieder eine Range rauskommt, müssen die beiden Eingabe-Ranges mindestens eine gemeinsame Grenze haben. So erschlägt man IMHO viel Funktionalität mit nur einer Funktion.

    Okay, das stimmt. Wobei man wie du andeutest auch vorsichtig sein muss, dass man nicht zu viel Funktionalität in eine einzelne Funktion packt (selbst abgesehen von der Fallunterscheidungs-Performance).



  • Nexus schrieb:

    template<class T> // <- hier T und nicht I
    struct InputRange {
       bool empty() const;
       void popFront();
       T& front() const;
    };
    

    Ja, das ist einfach nur komisch aufgeschrieben. Was er damit meinte war

    concept InputRange<class R>
    {
      typename reference;
      bool R::empty() const;
      void R::pop_front();
      reference R::front() const;
    }
    

    🙂



  • volkard schrieb:

    Eisflamme schrieb:

    ...

    Hier mal ein Iterator für verkettete Listen:

    struct It{
       Node* pos;
       It(Liste& l):pos(l.anchor){
       }
       Data& operator*(){
          return pos->data;
       }
       It operator++(){
          pos=pos->next;
          return *this;
       }
       friend bool operator!=(It a,It b){
          return a.pos!=b.pos;
       }
    

    Sieh, daß es schnell ist. Zero abstraction overhead wiedermal.
    Mit Indizes kriegste sowas nicht hin.
    Oder hier mal einen für eine lustigere Datenstruktur, sowas wie eine Queue, eine verkettete Liste von "Seiten", die je ein Array mit Daten drin haben.

    Data& operator*(){
          return page->arr[readIndex];
       }
       It operator++(){
          ++readIndex;
          if(readIndex==Page::SIZE){
             page=page->next;
             readIndex=0;
          }
       }
       friend bool operator!=(It a,It b){
          return a.page==b.page && a.readIndex==b.readIndex;
       }
    

    Ist noch nicht optimiert, aber wie man sieht, auf Anhieb nicht sehr lahm.

    Was soll das beweisen, wenn du zwei Beispiele machst, die was unterscheidliches machen?



  • ?????? schrieb:

    Was soll das beweisen, wenn du zwei Beispiele machst, die was unterscheidliches machen?

    Beide Beispiele zeigen in die selbe Richtung; sie verstärken sich gegenseitig.



  • naja, neben operator++() fehlt noch operator++(int). Neben operator!= fehlt noch operator==. Neben op* fehlt noch op->. Defaultkonstruktor fehlt auch. Und typedefs für std::iterator_traits fehlen auch. Da man aber all die Operatoren für einen ForwardIterator basierend auf drei Grundoperationen (dereference, increment, equal) erzeugen kann und das Definieren entsprechender typedefs auch automatisieren kann, bietet sich so etwas wie Iterator Facade an. Damit würde volkard's erstes Beispiel so aussehen:

    class It : public iterator_facade<It,Data,forward_traversal_tag>
    {
       Node* pos;
    public:
       It():pos(0){}
       explicit It(Liste& l):pos(l.anchor){}
    
       Data& dereference() const {return pos->data;}
       void increment() {pos=pos->next;}
       bool equal(It x) const {return pos==x.pos;}
    };
    

    (It wird automatisch op++(), op++(int), op==, op!=, op*, op-> und entsprechende typedefs für std::iterator_traits anbieten)

    kk



  • krümelkacker schrieb:

    Nexus schrieb:

    template<class T> // <- hier T und nicht I
    struct InputRange {
       bool empty() const;
       void popFront();
       T& front() const;
    };
    

    Ja, das ist einfach nur komisch aufgeschrieben. Was er damit meinte war

    concept InputRange<class R>
    {
      typename reference;
      bool R::empty() const;
      void R::pop_front();
      reference R::front() const;
    }
    

    🙂

    Sind concepts nicht raus? 😞



  • Eisflamme schrieb:

    Sind concepts nicht raus? 😞

    Jepp. Besser ohne als unausgegoren, IMHO.



  • Sehe ich auch so. Und für mich persönlich sind Concepts auch nicht gerade das Feature, auf das ich sehnlichst gewartet habe. Da gibt es interessante Neuerungen 😉


Anmelden zum Antworten