Reverse Iterator



  • Hallo,
    ich habe eine Single Linked List implementiert.
    Ich möchte nun einen Reverse Iterator implementieren ohne die Liste zu drehen.
    Der normale Iterator funktioniert soweit.
    Mein Problem ist, dass ich die operatorfunktion--() nicht implementieren kann, da ich keinen Verweiß auf den Vorgänger besitze.
    Gibt es eine möglichkeit dies ohne Vorgänger zu lösen?

    Grüße
    Kolwe96


  • |  Mod

    Manche Datenstrukturen können eben nur in eine Richtung iteriert werden.



  • In der STL ist dies aber Verfügbar.



  • @kolwe96 sagte in Reverse Iterator:

    In der STL ist dies aber Verfügbar.

    Falls du auf die "std::list" anspielst: Die ist eine DoubleLinkedList, wenn mich nicht alles täuscht.



  • @kolwe96 sagte in Reverse Iterator:

    In der STL ist dies aber Verfügbar.

    Du mußt in Deinem Iterator den Kopf der Liste merken.
    Die next zeiger so lange durchgehen bis du zur aktuellen Position kommst
    den letzten davor als aktuelle position merken und zurückgeben.

    Als Übung OK. Mehr aber nicht.

    mfg Martin


  • |  Mod

    @It0101 sagte in Reverse Iterator:

    @kolwe96 sagte in Reverse Iterator:

    In der STL ist dies aber Verfügbar.

    Falls du auf die "std::list" anspielst: Die ist eine DoubleLinkedList, wenn mich nicht alles täuscht.

    So ist es.

    @mgaeckler sagte in Reverse Iterator:

    @kolwe96 sagte in Reverse Iterator:

    In der STL ist dies aber Verfügbar.

    Du mußt in Deinem Iterator den Kopf der Liste merken.
    Die next zeiger so lange durchgehen bis du zur aktuellen Position kommst
    den letzten davor als aktuelle position merken und zurückgeben.

    Als Übung OK. Mehr aber nicht.

    mfg Martin

    Würde ich nicht empfehlen. Zu einer guten Übung gehört auch einzusehen, was sinnvoll ist und was nicht. Ein Iterator mit solcher Laufzeitkomplexität ist ein Wahnsinn. Das muss man erkennen, warum man das nicht implementieren sollte. std::vector bietet auch kein push_front an, obwohl es ein leichtes zu implementieren wäre, einfach weil es sich nicht gehört, an den Anfang eines vector zu pushen und die Schnittstelle dies abbilden sollte.



  • @mgaeckler sagte in Reverse Iterator:

    Du mußt in Deinem Iterator den Kopf der Liste merken.
    Die next zeiger so lange durchgehen bis du zur aktuellen Position kommst
    den letzten davor als aktuelle position merken und zurückgeben.

    Ja ist aber halt vom Rechenaufwand enorm. Kann man mal programmieren. Der Iterator ist dann aber derart teuer, dass den keiner nutzen würde, der mehr als 1 Element in seiner Liste hat... 😅

    @kolwe96
    Gibt es denn einen plausiblen Grund, warum es keine Double-Linked-List sein soll oder darf?



  • @It0101 ist eine Übungsaufgabe.
    Man soll die Reihenfolge des Iterators umdrehen.
    Die Laufzeit sollte O(n) bleiben.



  • @kolwe96 sagte in Reverse Iterator:

    @It0101 ist eine Übungsaufgabe.
    Man soll die Reihenfolge des Iterators umdrehen.
    Die Laufzeit sollte O(n) bleiben.

    D.h. die Aufgabe gibt vor, dass du eine Single-Linked-List mit effizientem Reverse-Iterator bauen sollst?

    Ist nur die Komplexität des Reverse-Iterators vorgegeben, oder muss die Komplexität der anderen Zugriffsfunktionen ( insert, remove, Iterator ) auch so bleiben, wie sie ist, oder dürfen die schlechter werden?



  • @It0101 Nicht direkt.
    Die Grundaufgabe war der Vorwärts Iterator
    Dann wird gefragt: Was muss geändert werden um die Reihenfolge des Iterators zu drehen.

    Ich wollte es aber mal implementieren und bin dann an das Problem gestoßen.



  • @kolwe96 sagte in Reverse Iterator:

    Dann wird gefragt: Was muss geändert werden um die Reihenfolge des Iterators zu drehen.

    Da kommt es auf den genauen Wortlauf der Aufgabe an. Darfst du den normalen Iterator entsorgen und dafür nur den ReverseIterator anbieten? In dem Fall würde man quasi die Liste von vornherein verkehrt herum aufbauen. Das ist zwar irgendwie Betrug, aber wenn die Aufgabe das als Möglichkeit nicht ausschließt, sollte das zulässig sein.


  • |  Mod

    Oder die richtige Antwort ist "eine doppelt verkettete Liste daraus machen". Kommt wirklich auf die genaue Aufgabenstellung an.



  • Also ist meine Erkenntnis,dass es keine Möglichkeit gibt rückwärts durch eine einfach verkettete Liste zu iterieren mit einer Laufzeit von O(n).



  • @kolwe96 sagte in Reverse Iterator:

    Also ist meine Erkenntnis,dass es keine Möglichkeit gibt rückwärts durch eine einfach verkettete Liste zu iterieren mit einer Laufzeit von O(n).

    Hängt wie gesagt von der Aufgabenstellung ab, wie weit du schummeln darfst.



  • @kolwe96 sagte in Reverse Iterator:

    Also ist meine Erkenntnis,dass es keine Möglichkeit gibt rückwärts durch eine einfach verkettete Liste zu iterieren mit einer Laufzeit von O(n).

    Doch sicher geht das. Mach einen vector von liste.size() iteratoren, speichere alle Iteratoren vorwärts laufend in dem vector (n schritte) und iteriere rückwärts durch den vector (nochmal n Schritte). Gut, du hast dann auch O(n) Speicherverbrauch...



  • @wob sagte in Reverse Iterator:

    @kolwe96 sagte in Reverse Iterator:

    Also ist meine Erkenntnis,dass es keine Möglichkeit gibt rückwärts durch eine einfach verkettete Liste zu iterieren mit einer Laufzeit von O(n).

    Doch sicher geht das. Mach einen vector von liste.size() iteratoren, speichere alle Iteratoren vorwärts laufend in dem vector (n schritte) und iteriere rückwärts durch den vector (nochmal n Schritte). Gut, du hast dann auch O(n) Speicherverbrauch...

    Das ist die Art von "Betrug", die mir auch vorschwebte... Wenn die Aufgabenstellung dem nicht widerspricht, kann er das so tun.



  • Okay,Danke



  • ich würde ne double linked list daraus machen. Das wäre nämlich der einzig vernünftige Weg diese Aufgabe zu lösen.



  • @wob sagte in Reverse Iterator:

    Doch sicher geht das. Mach einen vector von liste.size() iteratoren, ...

    Oder man borgt sich den Speicher einfach von Stack. z.B. indem man die Iterationsfunktion rekursiv aufruft. Die Reihenfolge ergibt sich dann daraus ob man das aktuelle Element vor dem Rekursiven auswerter (vorwärts), oder danach (rückwärts).
    Bei der vorwärts Iteration bekommt man dann ne Tail-Rekursion. Die man trivial wegoptimieren kann, was dann eine klassische Iterations-Schleife ergibt.



  • @spiri sagte in Reverse Iterator:

    ich würde ne double linked list daraus machen. Das wäre nämlich der einzig vernünftige Weg diese Aufgabe zu lösen.

    +1
    Ich kann mir auch nicht vorstellen, dass irgendwas anderes im Sinne der Aufgabe gemeint sein könnte.


Anmelden zum Antworten