Wieso Iteratoren statt Zeigern oder statt Indizes?

Shade Of Mine

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.

Eisflamme

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?

Tachyon

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?

Bashar

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

Tachyon

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?

volkard

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?

Bashar

Tachyon schrieb:

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?

Ersetze im obigen Zitat "Wie willst du denn mappen?" durch "Wie willst du denn die Iterationsreihenfolge festlegen?". Bei einem Iterator musst du dich genauso entscheiden, wie der Container iteriert werden soll. Du versuchst, diese Entscheidung als willkürlich hinzustellen. Das ist sie in gewisser Weise auch, aber man trifft sie trotzdem irgendwie, zumeist findet sich auch ein natürlicher Kandidat.

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

Damit hast du doch Indizes festgelegt. x+k entspricht dem Index k.

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

Das scheitert aber nicht daran, dass man nicht weiß, wie man das Mapping festlegen soll. Das würde man einfach genauso machen wie mit dem Iterator. Man dürfte halt die Indizes nur sequentiell bearbeiten. Es ist halt unpraktisch, weil ein Stream selbst eine Abstraktion ist, die Random Access nicht zulässt.

Tachyon

Bashar schrieb:

Das scheitert aber nicht daran, dass man nicht weiß, wie man das Mapping festlegen soll. Das würde man einfach genauso machen wie mit dem Iterator. Man dürfte halt die Indizes nur sequentiell bearbeiten. Es ist halt unpraktisch, weil ein Stream selbst eine Abstraktion ist, die Random Access nicht zulässt.

Und was passiert bei einem Wraparound des Index? Wenn Du den sinnvoll zulassen willst, hast Du keinen Index mehr, sondern einen Iterator.

Mit dem Rest hast Du Recht. Das kann man auch so sehen.

volkard

Tachyon schrieb:

Und was passiert bei einem Wraparound des Index? Wenn Du den sinnvoll zulassen willst, hast Du keinen Index mehr, sondern einen Iterator.

Groß genug machen. 64 Bit. Das reicht bei 1000 Milliarden Zugriffen pro Sekunde, uups, nur ein halbes Jahr. 128 Bit reicht aber ne ganze Weile lang.

Bashar

BigNum Ich bestreite ja nicht, dass es unpraktisch ist.

Tachyon

volkard schrieb:

Tachyon schrieb:

Und was passiert bei einem Wraparound des Index? Wenn Du den sinnvoll zulassen willst, hast Du keinen Index mehr, sondern einen Iterator.

Groß genug machen. 64 Bit. Das reicht bei 1000 Milliarden Zugriffen pro Sekunde, uups, nur ein halbes Jahr. 128 Bit reicht aber ne ganze Weile lang.

Ich kann hier keine 64 Bit, geschweige denn 128 Bit. Lösung? Klasse basteln? -> Iteratoren.

Eisflamme

Okay. Bäume sind neben Random-Access und verketteten Listen ja eine weitere "Zugriffsart" (wenn man das so benennen möchte, zumindest muss man hier für neu überlegen und das möchte ich mit dem Begriff hier ausdrücken).

volkard:
Gut, das sehe ich ein, das wäre umständlich, inperformant oder speicherfressend. Der iterator wird sich einfach ein paar Infos merken und dann ist halt gut.

Hm... ja, da versagen Indizes dann schließlich in voller Breite. Dann mag ich Iteratoren jetzt vollkommen. Danke, das hat meinem Gesamtprogrammierverständnis ein klein wenig geholfen, glaub ich.

PS: Wieso lösen Iteratoren das Problem mit den 64 Bit? Wenn man nicht mehr adressieren kann, weil zu viel im Speicher liegt, hat man doch sowieso verloren?

volkard

Tachyon schrieb:

Ich kann hier keine 64 Bit, geschweige denn 128 Bit. Lösung? Klasse basteln? -> Iteratoren.

Och, aus 16-Bittern sich einen 128-Bitter zu basteln, der ++ kann und was ich hier nicht mache, + und -, das klingt nicht so schwer. * ist schon gemeiner und / ist gemein.

struct StreamIndex{
   unsigned short a,b,c,d;
   Index& operator++(){
      if(!++a)if(!++b)if(!++c)++d;
      return *this;
   }
   ...
};

Hmm, könnte recht lahm werden. Und natürlich, man kann nicht auf Streampositionen lesen, die schon gelesen wurden, also eigentlich ist es ein ForwardOnlyStreamIndex. Das ist schlimm, denn dann ist es doch nur ein Iterator, nur daß man nicht *i schreiben darf, sondern cont[i] schreiben muß und die Algorithmen mehr Übergabeparameter brauchen.

Tachyon

volkard schrieb:

[...]

Örks. Da finde ich es irgendwie einfacher, mir einen Iter... ach, lassen wir das.

Shade Of Mine

Eisflamme schrieb:

PS: Wieso lösen Iteratoren das Problem mit den 64 Bit? Wenn man nicht mehr adressieren kann, weil zu viel im Speicher liegt, hat man doch sowieso verloren?

Stell dir eine Liste vor, mit unendlich vielen Elementen. zB eine Liste die sich mit Daten aus einer Messstation füllt. Die Station misst ja konstant und liefert dir konstant Daten. Die verwendest du in einem Algorithmus.

Das Problem mit indizes ist nun: irgendwann stehst du an und musst von vorne anfangen mit dem zählen. Bei iteratoren machst du einfach immer ++ und fertig.

volkard

Eisflamme schrieb:

PS: Wieso lösen Iteratoren das Problem mit den 64 Bit? Wenn man nicht mehr adressieren kann, weil zu viel im Speicher liegt, hat man doch sowieso verloren?

Vorm Netzwerkstream kommen einfach Objekte, und mit ++it gehe ich in meinem lokalen(!) Puffer weiter und wenn der lokale Puffer ausgelesen ist, werden mit read() oder recv() wieder 4096 Bytes gelesen. Das kann endlos gehen und es gibt gar keinen Überlauf. Es gibt keine Probleme, weil if(it1<it2) gar nicht angeboten wurde. Man braucht nur begrenzten Speicher.
Edit: Und die 4096 Bytes Speicher braucht man nur, um die Sache zu beschleunigen. Es würde auch gehen, bei jedem op++ recv() aufzurufen und Speicher für nur ein Objekt vorzuhalten, das im op* dann herausgegeben wird.

Tachyon

Eisflamme schrieb:

Okay. Bäume sind neben Random-Access und verketteten Listen ja eine weitere "Zugriffsart" (wenn man das so benennen möchte, zumindest muss man hier für neu überlegen und das möchte ich mit dem Begriff hier ausdrücken).

Damit erklärst Du Dir ja eigentlich auch schon selbst, wo der Vorteil liegt. Du bist nun schon bei drei Zugriffsarten, während Du über Iteratoren gleichartig auf alles zugreifen kannst. Insbesondere für die generischen Algorithmen ist das schon sehr praktisch.

knivil

Indizes sind auch nur Iteratoren ... ich verstehe gar nicht, was das ganze Theater soll.

volkard

Shade Of Mine schrieb:

Stell dir eine Liste vor, mit unendlich vielen Elementen.

Aus Dir spricht der Mathematiker.

Eisflamme

volkard, ShadeOfMine:
Okay, so habe ich Container bislang noch nie genutzt. Ergibt aber Sinn.

Tachyon:
Meine Lösung über Indizes sagt ja, dass man alles in Indexzugriffsart übersetzen würde, damit hätte man einen einheitlichen Zugriff auch. Iteratoren bieten ebenfalls eine Zugriffsschicht, kennzeichnen das aber klarer als solche. Wenn jeder auf Indizes übersetzt, kann ich auch Indizes an Algorithmen übergeben, daher zählt das Argument für mich nicht.