Bumping ancient thread but the easiest way I've found to solve this problem, at least in complex scenarios, is to just copy every damn thing prior to the user operation...
... sounds wasteful, right? Except if it is really wasteful, then your next step is to make copying cheaper so that parts that won't be changed in the next step will not be deep copied.
In my case I'm often working with gigabytes of data but the user often only touches megabytes for an operation, so copying everything would normally be extremely expensive and ridiculously wasteful.... but I've set up these data structures revolving around shallow copying what doesn't change, and I find this the easiest solution and it also opens up a lot of new possibilities, like immutable persistent data structures, safer multithreading, nodal networks which input something and output something new, non-destructive editing, instancing objects (being able to shallow copy, say, their expensive mesh data but having the clone have its own unique position in the world while barely taking memory), etc.
store all scene/application state in undo
perform user operation
on undo/redo:
swap stored state with application state
Every project since has followed this basic pattern instead of having to carefully record every little state change and for dozens of different types of data that didn't fit into a homogeneous model (image/texture painting, property changes, mesh changes, weight changes, hierarchical scene changes, shader changes that weren't property-related like swapping one with another, envelope changes, etc etc etc). Instead if that's too wasteful in terms of memory and time, then we don't come up with a fancier undo system, instead we seek to optimize the copying so that partial copies can be made in all the most expensive data structures. That leaves it as an optimization detail where you can have a correctly-functioning undo implementation right away that will always stay correct, and always staying correct is awesome when, in the past, undo systems were among the hardest parts of the software to keep correct.
The other way is to record the deltas (changes) individually, and I used to do that in the past, but for very complex large-scale software, it was often very error-prone and tedious since it was really easy for a plugin developer to forget recording some change in the undo stack when they introduced brand new concepts into the system.
Now one thing regardless of whether you copy the entire game state or record deltas is to avoid pointers (assuming C or C++) when possible or else it'll complexify things a lot. If you use indices, everything becomes simpler instead, since indices don't invalidate with copies (either of the entire application state or a part of it). As an example with a graph data structure, if you want to copy it in its entirety or just record deltas when users make new connections or break connections in the graph, the state will want to store links to the old nodes and you can run into issues with invalidation and things of that sort. It's much easier if the connections use relative indices into an array, since its much easier to keep those indices from invalidating than pointers.