Abstract classes issue in C++ undo/redo implementation

Question

I have defined an "Action" pure abstract class like this:

class Action {
 public:
    virtual void execute () = 0;
    virtual void revert () = 0;
    virtual ~Action () = 0;
};

And represented each command the user can execute with a class.

For actual undo/redo I would like to do something like this:

Undo

Action a = historyStack.pop();
a.revert();
undoneStack.push(a);

Redo

Action a = undoneStack.pop();
a.execute();
historyStack.push(a);

The compiler obviously does not accept this, because "Action" is an abstract class which can not be istantiated.

So, do I have to redesign everything or is there a simple solution to this problem?

Answer 1

You should store pointers to performed operations in the queue.

For instance:

std::vector<Action*> historyStack;
std::vector<Action*> undoneStack;

Then:

Action* a = historyStack.pop_back(); 
a->revert(); 
undoneStack.push_back( a ); 

And:

Action* a = undoneStack.pop_back(); 
a->execute(); 
historyStack.push_back(a); 

Of course you should use new and delete to create and free memory for actual Action objects and I don't think you can use *auto_ptr* with standard containers so you have to manage your memory manually or implement some other method. But this should not be a big problem if you wrap undo buffer in a class.

Answer 2

You should store actions as pointers, that will keep the compiler happy.

std::vector<Action*> historyStack;
/*...*/
historyStack.push_back(new EditAction(/*...*/));
Action* a = historyStack.pop();
a->revert();
undoneStack.push(a);

There is another reason why std::vector<Action> historyStack; will not work and that's slicing. When adding objects of derived classes to the vector they will be cast to the base class and loose all their polymorphism. More about it here: http://stackoverflow.com/questions/274626/what-is-the-slicing-problem-in-c

EDIT Look into using ptr_vector to manage the lifetime of the objects in the vector: http://www.boost.org/doc/libs/1_37_0/libs/ptr_container/doc/tutorial.html

Answer 3

Polymorphic dispatch only happens through pointers or references in C++ anyway. You may not be able to create a value of Action, but you will find you'll be able to create references and pointers to Actions.

pop merely needs to return a (possibly smart) pointer, or a reference, to an Action. One approach might be to use std::auto_ptr and boost::ptr_deque, this will (with correct usage) ensure that the actions are appropriately cleaned up after.

std::auto_ptr<Action> a = historyStack.pop_front();
a->revert();
undoneStack.push_front(a);

Another option could be a std::stack of boost::shared_ptr<Action> or similar. Or you can just use raw pointers, but you must be careful that ownership is managed correctly.