The task, in general, is fundamental, but the question my question grows from the origins of olympiad programming, where speed is a key resource. That there were no problems in the clarity of the wording, I will attach the link. Here is [1] ( http://acm.timus.ru/problem.aspx?space=1&num=1992 )!

But in short, that is, an object to which you can add something and remove the same thing (roll back to the old version, older content), and then, similarly, restore rollbacks. But the most important thing is that you can clone an object with its entire rollback history and current state. This is where the question comes up: how to implement cloning in the most optimal way?

Of course, the simplest solution is simply full cloning ( .clone() , in java) with the implementation of the Cloneable or similar interface. After that, we will have two independent entities with which to work; The critical drawback is the amount of memory consumed and time, of course. There are ideas on how to improve and optimize the usual two-stack idea; or what alternative?
Thank!

    3 answers 3

    Another popular solution is immutable data structures. At the same time, you never need a deep copy, you can reuse the common parts, because they do not change.

    When you create a new state, you copy references to all the unchanged parts of the old one into an object that represents the new state (this is fast and does not require a lot of memory). The changed parts are created anew (or if you have this information, use it, since it is immutable). New state store in the list of "versions" of the state.

    Additional reading on the topic: Immutability in C # Part Two: A Simple Immutable Stack (yes, this is in C #, but the principles are the same).

      I draw attention to the fact that in requests for withdrawal it is necessary to name only the latest technology.

      They need a pointer to the ancestor in the tree. Even the tree itself is not needed.

      Each element has a value and a link to the same. The array of clones contains such elements. The deck array contains a sequence of rollbacks for a clone.

      It seems that's all. Any operation is performed in O (1).

        Option 1. ( Copy-on-Write )

        Create a copy as a link. When the original or copy changes, we perform a deep copy. If nothing changes, the memory is almost not consumed, the maximum that we need is a few bytes for the counter.

        Option 2

        But now the solution is more complicated. The change history of an object is actually a set of object states. These states can be ordered. Create an array in which we place the state of the object after the change. Each object will be associated with a vector of links to the state. The link vector in general requires less space than a set of states. Vector copy when copying an object.

        You can also hybridize both approaches by copying the vector of links only when objects change.