Undo/Redo Stack



  • Abend,

    ich will in C++ für meinen Editor eine Undo/Redo Funktionalität bauen und wollte das so machen:
    Ich habe 2 Stacks stack<Action*>, einen für Undo und Redo. Macht der Benutzer eine Aktion, push ich die auf den Undo Stack. Will er die Aktion rückgängig machen, dann pop ich sie aus dem Undo Stack, führ action->undo() aus und push sie auf den Redo Stack. Bei Redo pop ich die Aktion aus dem Redo Stack, führ action->redo() aus und push sie wieder auf den Undo Stack.

    Meine 2 Fragen:
    1. Ist das eine gute Idee. Wird das so klappen?
    2. Ich bin mir nicht ganz sicher was ich in folgender Situation machen soll: Sagen wir der Benutzer hat 10 Aktionen gemacht und drückt nun 2mal Undo. Ich habe auf dem Undo Stack also 8 Actions und auf dem Redo Stack 2. Was mache ich nun, wenn der Benutzer eine neue Aktion macht? Hau ich die wie gewohnt auf den Undo Stack? Was mache ich mit dem Redo Stack?

    Danke!



  • 1. Ja, sollte so gehen.
    2. Ich würde den Redo-Stack leeren. Da std::stack so genial durchdacht ist, musst du selbst einen Container wrappen und clear() bereitstellen oder Ineffizienz in Kauf nehmen.

    Wieso eigentlich Zeiger? Wer ist für die Speicherverwaltung verantwortlich?



  • Danke für die schnelle Antwort.

    Nexus schrieb:

    2. Ich würde den Redo-Stack leeren. Da std::stack so genial durchdacht ist, musst du selbst einen Container wrappen und clear() bereitstellen oder Ineffizienz in Kauf nehmen.

    Wollte mir eh was eigenes basteln, da der std::stack irgendwie ... net so das Wahre is.

    Nexus schrieb:

    Wieso eigentlich Zeiger? Wer ist für die Speicherverwaltung verantwortlich?

    Naja, mein "Stack" soll ja verschiedenste Aktionen speichern können, wobei jede auf ihre Weise was anderes in undo(), redo Macht. Ergo hab ich eine abstrakte Oberklasse Action und brauche folglich Zeiger.



  • Hochstapler schrieb:

    Naja, mein "Stack" soll ja verschiedenste Aktionen speichern können, wobei jede auf ihre Weise was anderes in undo(), redo Macht. Ergo hab ich eine abstrakte Oberklasse Action und brauche folglich Zeiger.

    Okay. Schau, dass du die Speicherverwaltung möglichst gut kapselst, also wenn möglich direkte delete -Aufrufe bei der Anwendung vermeiden (aber den Speicher natürlich trotzdem aufräumen!). Eventuell wären Smart-Pointers etwas. Oder du löschst gleich beim pop() . Für das Verschieben von Undo- zu Redo-Stack würde ich eine Art transfer() -Funktion schreiben, die nur den Zeiger kopiert, den Speicher dahinter aber nicht antastet.

    Nur so als ein paar Vorschläge, denn rohe Zeiger sind immer ein Risiko. 😉



  • btw find ich, dass stack völlig ausreichend ist - das einzige, was du vrmtl noch brauchst, ist ein clear... (und das kann man ja einfach als freie fkt bereitstellen - muss ja auch nicht wirklich eine member-fkt sein)

    template<typename T>
    void clear(std::stack<T> &these)
    {
      while(!these.empty())
        these.pop();
    }
    

    mehr braucht man imho nicht...

    da du aber nicht alle aktionen des nutzers speichern willst (oder?) würde sich vll ein Ringpuffer besser machen...
    auch zu denken wäre nur einen Container zu verwenden und einfach iwas zu speichern, womit man feststellen kann, wo der andere bereich anfängt (iterator oder size_type)...

    bb



  • unskilled schrieb:

    btw find ich, dass stack völlig ausreichend ist - das einzige, was du vrmtl noch brauchst, ist ein clear... (und das kann man ja einfach als freie fkt bereitstellen - muss ja auch nicht wirklich eine member-fkt sein)

    template<typename T>
    void clear(std::stack<T> &these)
    {
      while(!these.empty())
        these.pop();
    }
    

    Das meinte ich mit Ineffizienz. Natürlich macht es in den meisten Fällen kaum etwas aus, aber ich finde es dennoch nicht ganz okay, dass std::stack einen zu so einer Lösung zwingt.



  • Du könntest auch ein richtig mächtiges Undo bauen wie es Emacs hat: dort wird bei einem Undo nichts vom Undo-Buffer gepoppt sondern eine Aktion gepusht welche die Aktion rückgängig macht. D.h. du hast zwei Zeiger: einen auf das letzte Element und einen auf den aktuellen Stand und bei einem Undo wird eine inverse Operation zu der auf die der aktuelle Zeiger zeigt an das Ende angefügt und der Zeiger auf das aktuelle Element um eines in die Vergangenheit verschoben.
    Das ganze ist als Ringpuffer implementiert. Dadurch verliert man keinerlei Information so lange der Ringpuffer genügend Speicherplatz hat 🙂


Log in to reply