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?

score 8 · Accepted Answer · edited May 23 '17 at 12:25

8

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: What is object slicing?

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

edited May 23 '17 at 12:25

Community

1
1

answered Jan 12 '10 at 00:57

Igor Zevaka

74,528
26
112
128

1

Don't forget to delete. Smart pointers help, as would pointer-specific containers like Boost Pointer Containers. – GManNickG Jan 12 '10 at 00:59
Yes, thank you, a smart pointer container will definitely be needed here. – Igor Zevaka Jan 12 '10 at 01:00
Though with those functions you want a `stack`, not `vector`. :) – GManNickG Jan 12 '10 at 01:11
But there isn't a boost::ptr_stack, and a std::stack over a ptr_vector wouldn't do the right thing even if it's possible, because we need to be able to pop things off and take ownership back. std::stack has a different pop() operation than ptr_vector. – Steve Jessop Jan 12 '10 at 01:48
std::vector> would be a nice way to store pointers that way... we can take them out taking ownership this way, too – IceFire Jan 05 '16 at 18:25

Mladen Janković · Answer 2 · 2010-01-12T01:12:29.090

0

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.

edited Jan 12 '10 at 01:12

answered Jan 12 '10 at 00:56

Mladen Janković

7,867
3
22
26

Or boost::shared_ptr ot std::tr1::shared_ptr if you want to be cautious about memory leasks. Theres a lot of recommendations to not store raw pointers in STL containers unless you really cant avoid it. – Michael Anderson Jan 12 '10 at 01:00
Is there any particular reason for such recommendation except standard one that raw pointers are hard to handle? – Mladen Janković Jan 12 '10 at 01:06
Probably not. Hard to handle means making it easy to handle, which also saves time. – GManNickG Jan 12 '10 at 01:19
Certainly as far as I know, the only reason is the difficulty of managing lifecycle. Saying "don't store raw pointers with ownership" might be better than "don't store raw pointers". Pointers without ownership are fine: `std::map m; m['n'] = "north"; m['s'] = "south";` etc. – Steve Jessop Jan 12 '10 at 01:55

score 0 · Answer 3 · answered Jan 12 '10 at 01:03

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.

Be careful, you should never store auto_ptr in a STL container. Data can be lost when the container resizes automatically. See http://www.devx.com/tips/Tip/13606 Note that Logan is not suggesting this, but it would be easy to make that mistake. — Michael Anderson, Jan 12 '10 at 01:07

Abstract classes issue in C++ undo/redo implementation

3 Answers3