Wieso Iteratoren statt Zeigern oder statt Indizes?



  • Hi,

    Wieso hat man für C++ das Iteratorkonzept gebaut? Zeiger sind blöd, wenn die Daten im Speicher nun Mal nicht linear liegen und operator++ daher nicht für einen Zeiger stimmt. Indizes könnten aber wiederum gemappt werden, sodass man container.get(index) sagen könnte.

    Auf das Argument, dass man dann das Mapping speichern müsste, würde ich entgegnen, dass man das ja sowieso auch braucht, es sei denn, jedes Element kennt seinen Nachfolger. D.h. für verkettete Listen sehe ich da Nachteile, für lineare Container dann aber wiederum nicht unbedingt.

    Gibt es noch mehr Argumente?



  • Mir scheint bezüglich Zeigern hast du deine eigene Frage beantwortet, also nur zu Indizes. Indizes sind nur sinnvoll, wenn du Random Access hast. Schau dir also einfach mal exemplarisch alle Iteratoren der C++ Standard Library an, die nicht Random Access sind, und überlege, warum das so ist.



  • Einfach ein Buch nehmen und nachlesen: Die C++ Programmiersprache. Kapitel 19: Iteratoren und Allokatoren.



  • 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 für Vorteile sollten Indizes haben?



  • Eisflamme schrieb:

    Wieso hat man für C++ das Iteratorkonzept gebaut? Zeiger sind blöd, wenn die Daten im Speicher nun Mal nicht linear liegen und operator++ daher nicht für einen Zeiger stimmt. Indizes könnten aber wiederum gemappt werden, sodass man container.get(index) sagen könnte.

    Da ziehst Du aber willkürlich eine Grenze. Denn der Indexoperator bei Zeigern ist ja gerade per Definition eine Abkürzung für Zeigerarithmetik, also

    ptr[idx]
    *(ptr+idx)
    

    Dass Du das "Mapping von Indizes" okay findest aber ++/-- auf lineares Vor/Zurückspringen (bzgl Speicheradressen) beschränken willst, ist IMHO inkonsequent.

    Abgesehen davon, ist die Frage aber eine sehr gute. Die kann man wohl größtenteils mit "aus histotischen Gründen" erklären oder ein "Warum nicht?". Zum Zeitpunkt der Standardisierung gab es scheinbar keine "schöneren" Alternativen. Trotzdem muss das nicht heißen, dass es nicht auch besser geht. Beispielsweise hat Andrei Alexandrescu (sp?) ein anderes Konzept vorgestellt, welches er "Range" nannte (Achtung: Der Range Begriff ist überladen. Boost definiert zB ein etwas anderes Range-Konzept). Angeblich war Andrei in der Lage, all die STL Algorithmen basierend auf seinem Range-Konzept zu implementieren, welche auch eleganter nutzbar und weniger fehleranfällig seien. Es müsste im Netz dazu ein Vortragsvideo geben und die Vortragsfolien. Der Titel war irgendwas provokatives à la "Iterators must go" oder so.

    kk



  • volkard schrieb:

    Eisflamme schrieb:

    ...

    ...

    Iteratoren bieten also eine einheitliche Schnittstelle für den Zugriff auf (unterschiedliche) Datenstrukturen und können diesen sogar vereinfachen. Außerdem lassen sich die Datenstrukturen leichter untereinander austauschen.

    Schönes Beispiel... könnte man das nicht in die FAQ aufnehmen?



  • Hi,

    Okay, das hat meine Frage schon zum großen Teil beantwortet. 🙂 Ich bohr noch ein wenig nach.

    Das mit den verketteten Listen hatte ich auch als Argument gegen Indizes angesehen, weil man hier die interne Struktur nutzen kann. Aber - nur zum Verständnis - wenn man jetzt Mal von diesen absieht, gibt es dann noch Vorteile?

    Wie gesagt, wenn es random access nicht gibt, kann man das mapping speichern, was man eh braucht, es sei denn man eine verkettete Liste hat, richtig?

    @krümelkacker: Ich bin aber nicht ganz sicher, ob ich dich in der Aussage, ich sei inkonsequent verstehe. Geht es darum, dass ich einerseits Speicher vermeiden will (durch Indizes), andererseits aber das Speichern von Mappings ok finde? Das sehe ich als inkonsequent an, aber operator++/-- habe ich jetzt nicht verboten, sondern nur fest gestellt, dass bei nicht-linearer Datenablage das mit einfachen Zeigern nicht klappt. 🙂



  • Eisflamme schrieb:

    [...]

    Wie willst Du z.B. bei einem std::set ein Element eindeutig einem Index zuordenen?



  • "Sie entkoppeln Algorithmen von den Containern, so dass diese typenunabhängig formuliert werden können."

    Quelle: http://de.wikipedia.org/wiki/C%2B%2B-Standardbibliothek#Iteratoren



  • Artchi schrieb:

    "Sie entkoppeln Algorithmen von den Containern, so dass diese typenunabhängig formuliert werden können."

    Quelle: http://de.wikipedia.org/wiki/C%2B%2B-Standardbibliothek#Iteratoren

    Trifft auch auf Indizes zu...

    Tachyon:
    Wenn operator++ überladen werden kann, kann man auch so ein Mapping erstellen. Wie gesagt, das muss man natürlich auch tun. Es sei denn, da liegt ne verkettete Liste hinter... aber das ist ja alles schon hier besprochen.



  • Eisflamme schrieb:

    Trifft auch auf Indizes zu...

    Nein. Weil nicht alle Datenstrukturen Random Access bieten.

    Für Datenstrukturen wo es einen sinvollen index gibt, sind indizes natürlich eine gute Lösung - aber viele Datenstrukturen bietet das einfach nicht. Es macht oft auch keinen Sinn - zB bei Streaming Algorithmen.
    Weiters hat man kein Problem mit underflow/overflow bei iteratoren - bei indizes kann das ein Problem werden. Auch muss man bei indizes wissen wieviele Elemente man hat -> das weiss man aber auch nicht immer.

    indizes sind nix anderes als random access iteratoren - iteratoren bieten aber mehr.

    Weiters kann man iteratoren kapseln um zB backwards iteratoren zu bekommen. Dann auch zB insert iteratoren.

    und und und - iteratoren sind ein abstraktes Konzept. Sie ermöglichen viele Sachen. indizes sind eine konkrete Implementierung.

    PS:
    "Es sei denn, da liegt ne verkettete Liste hinter"

    Die meisten Datenstrukturen haben keinen Random Access. Nur sehr wenige bieten Random Access an und das zu einem hohen Preis.



  • Nein. Weil nicht alle Datenstrukturen Random Access bieten.

    Also das mit dem Random Access hab ich so langsam verstanden. Trotzdem könnte man - ich sage nicht, dass das eine gute Lösung ist - Indizes durch eine Mappingtabelle verwenden.

    template<class T>
    class queue
    {
    private:
    // mapping in irgendeiner Form
    
    public:
    const T& get(std::size_t index) const {return *mapping[index];}
    const T& operator[](std::size_t index) const {return get(index);}
    // o.ä.
    };
    
    queue<int> oneQueue;
    // Steck was rein
    for(int std::size_t n = 0; n < oneQueue.size(); ++n)
        std::cout << oneQueue.get(n) << '\n';
    

    Und nochmal. Wenn da verkettete Listen im Spiel sind, sehe ich ein, dass das blöd ist, weil man operator++ einfach implementieren kann. Falls das aber nicht vorliegt, benötigt man doch ohnehin irgend eine Art von Mapping, richtig?

    Weiters hat man kein Problem mit underflow/overflow bei iteratoren - bei indizes kann das ein Problem werden. Auch muss man bei indizes wissen wieviele Elemente man hat -> das weiss man aber auch nicht immer.

    [...]

    Weiters kann man iteratoren kapseln um zB backwards iteratoren zu bekommen. Dann auch zB insert iteratoren.

    Okay, das sehe ich ein. 🙂



  • Die Reverse-Iteratoren sind auch cool, um einen Container rückwärts zu durchlaufen.
    Bei Indizies muß ich dagegen meinen Algorithmus umbauen, z.B. aus i++ ein i-- machen und die End-Bedingung auch noch ändern. 😡

    Mit Iteratoren brauche ich bloß rbegin() anstatt begin() und rend() anstatt end() an den Algorithmus übergeben. 👍

    Indizies benutze ich trotzdem gerne. Sie sind ja nicht verhasst. Nur halt nicht so flexibel wie Iteratoren.



  • Eisflamme schrieb:

    Und nochmal. Wenn da verkettete Listen im Spiel sind, sehe ich ein, dass das blöd ist, weil man operator++ einfach implementieren kann. Falls das aber nicht vorliegt, benötigt man doch ohnehin irgend eine Art von Mapping, richtig?

    Du tust immer so, als wäre die verkettete List ein Spezialfall. Der Spezialfall ist Random Access. Wie soll denn dieses Mapping z.B. bei einem Set oder einer Map aussehen? Von Input/Output-Iteratoren fang ich gar nicht erst an ...



  • Eisflamme schrieb:

    Also das mit dem Random Access hab ich so langsam verstanden. Trotzdem könnte man - ich sage nicht, dass das eine gute Lösung ist - Indizes durch eine Mappingtabelle verwenden.

    Nicht immer. Und es kostet ja auch was.

    Wenn du zB nicht weisst wieviele Elemente du hast, dann ist ein mapping garnichtmal so einfach. Gibt es zB das Element 27? Du weisst es zB erst wenn du Element 26 angelegt hast.

    Indizes sind ein spezialfall: nämlich random access iteratoren.

    Geh mal den anderen Weg: welchen Vorteil bieten indizes die du mit iteratoren nicht hast? Vielleicht verstehst du es so eher.

    Bedenke: iteratoren funktionieren immer - egal welche struktur. indizes nur manchmal. weiters bieten indizes keinen vorteil gegenüber random access iteratoren.



  • Vielleicht verstehst du es so eher.

    Ok, bei allem Respekt, aber zum wiederholten Mal: Ich habe es verstanden, aber ich will das Thema einfach ein wenig erschöpfen. Nur weil es zwei Argumente für Iteratoren und nur eins dagegen gibt und das somit reichen würde, heißt das ja nicht, dass es nicht noch mehr Argumente gibt, die ich auch alle gerne hören würde. Ist das so schwer nachzuvollziehen? 🙂 Bitte verwechselt meinen Perfektionismus nicht mit Dummheit, Sturheit, Uneinsichtigkeit oder gar Undankbarkeit.

    Aber ich denke, das ist jetzt auch so gut wie erschöpft, Iteratoren bieten tatsächlich sehr viele Vorteile. Danke für die Geduld!

    Du tust immer so, als wäre die verkettete List ein Spezialfall.

    Ich bin einfach zu blöd zu schreiben, was ich eigentlich wissen will. Mir ging es darum, ob für etwaige andere Zugriffsmethoden als random access und verkettete Listen die Indexmethode nicht auch einfach umsetzbar sein könnte. Die Frage ist aber, ob es andere Zugriffsmethoden überhaupt gibt?



  • Eisflamme schrieb:

    Wenn operator++ überladen werden kann, kann man auch so ein Mapping erstellen. Wie gesagt, das muss man natürlich auch tun. Es sei denn, da liegt ne verkettete Liste hinter... aber das ist ja alles schon hier besprochen.

    Wie willst Du denn mappen? Auf welcher Grundlage? Die Reihenfolge der Einfügung von Elementen? Aufgrund der Sortierung? Aufgrund irgendeines Prädikates? Was ist sinnvoll, und was nicht? Und wer entscheidet das?
    Bei assoziativen Containern hast Du bereits einen Index, welcher aber nicht numerisch sein muss. Was tust Du bei exotischen Index-Typen?



  • Tachyon schrieb:

    Wie willst Du denn mappen? Auf welcher Grundlage? Die Reihenfolge der Einfügung von Elementen? Aufgrund der Sortierung? Aufgrund irgendeines Prädikates? Was ist sinnvoll, und was nicht? Und wer entscheidet das?

    Du argumentierst gerade gegen Iteratoren 😉



  • Bashar schrieb:

    Tachyon schrieb:

    Wie willst Du denn mappen? Auf welcher Grundlage? Die Reihenfolge der Einfügung von Elementen? Aufgrund der Sortierung? Aufgrund irgendeines Prädikates? Was ist sinnvoll, und was nicht? Und wer entscheidet das?

    Du argumentierst gerade gegen Iteratoren 😉

    Wieso das? Bei Iteratoren muss ich mich gar nicht um irgendein Mapping scheren. Ich iteriere von x bis x+n mit n < N und gut ist.

    Noch ein gutes Beispiel: Wie soll der Index für in einem Stream aussehen? Insbesondere z.B. in der Standardeingabe?



  • Das mit dem Index kann man nur über zwei Wege lösen, fürchte ich:
    a) Sie immer mitführen. Das hieße bei einem Baum aber Fürchterliches! Damit Einfügen effizient bleibt, kann kein Array benutzt werden, und es müßte als Index ein paralleler Baum geführt werden. Ich glaube, das fällt schon mal aus.
    b) Der Index ist kurzlebig und Teil des Iteratores. Also beim Konstruieren des Iterators wird der Baum in-order-traversiert, was mit einer rekursiven Funktion eleganz geht, und ein Index-Array gebastelt. Aber oh, weh! Alle sublinearen Algorithmen, die auf diesem Index-Array laufen würden, würden bereits eine lineare Indizierungsphase bezahlen müssen.

    Wie hast Du vor, einen Index für einen Baum zu machen?


Log in to reply