撤销和重做(Undo和Redo)的C++完美实现

jinye6 2011-06-23

展开全文

http://www./xml/more.asp?id=937(共9篇, 这里只录入前两篇)

经过一年多的时间的摸索，终于找到了一种比较完美的撤销和重做(Undo和Redo)的C++实现方案，因为现在很多的应用程序都需要这种功能，所以我将我的经历写出来让大家分享，同时也能够让更多的人帮助我来更加完善这种架构，同时也能够让更多的人能够利用这种架构更好的完成它的程序。这种架构充分利用了STL的容器和算法来简化代码，因此有着比较高的正确性和可读性。
在解析我的架构之前先分析一下（我所知道的）目前存在的一些实现撤销和重做的方案的优缺点。当前存在的撤销和重做的方案主要是：
撤销和重做的方案优点和缺点
撤销和重做方案

优点和缺点
将整个应用程序的状态序列化到文件撤销和重做的步骤数量一般不多，最常见的是只能够撤销和重做一步，因为步骤多了会占用非常多的磁盘空间，同时撤销和重做的操作消耗时间也非常多，但是代码组织却非常简单
自定义分配器管理内存池的方法有着非常复杂的内存分配算法，代码不容易理解，使用也有点不方便，方法和上面的序列化方案类似，只不过序列化到了内存中，代码组织也非常简单
仿函数保存反操作的方法
用仿函数保留每一步操作所对应的反操作，虽然占用的内存空间不大，操作消耗的时间也不多，但是为每一步操作都必须写出相应的反操作是一个非常繁重的任务，况且一些操作还不一定存在着反操作，因此必然导致采用其它的方法进行补充那些没有反操作或者即使有反操作，但是反操作也很难写出的情况。虽然有了时间和空间上的优点但是代码组织却比较混乱，不便于维护
从上面的撤销和重做方案中我们可以看出共同的毛病，撤销和重做机制消耗的时间和空间都比较大，但是都有着共性：撤销之前备份应用程序当前的状态信息，在撤销的时候就用这个备份的状态信息修改应用程序的当前状态，从而达到了撤销的功能，同样为了能够实现重做功能，也需要在重做之前备份应用程序的状态信息，在重做的时候使用这个备份的状态信息修改应用程序的当前状态，从而达到了重做的功能。
虽然大多数应用程序中都有撤销和重做的功能，但是仍然有许多的程序没有撤销和重做的功能，即使有也非常弱，原因当然是撤销和重做功能不易实现的原因了。
好了，对我所知道的这些撤销和重做的方案经过分析之后，可以看出比较理想的是最后一种，即：仿函数保存反操作的方法，但是这里面需要写非常多的反操作。为了减少书写反操作的代码，自己的方案里面采用和仿函数保存反操作类似的方法，但是又没有大量书写反操作的麻烦，同时代码组织非常简洁（通常来说撤销和重做机制可以以库的形式提供，使用该库的你仅仅只需要用仅有的几个封装的非常完美的操作来表达你的任意操作即可。这种表达方式和一般的编码过程非常类似，因而就不需要考虑反操作的问题）。这将在本系列的后续文章中详细讨论！

通过前面的讨论，我们所希望的是具备有“仿函数保存反操作法”的时间和空间优势，但是又不希望有“仿函数保存反操作法”的书写反操作的繁琐过程，另外还要保证代码的组织非常简洁，当然这是为了方便维护了：）
在前面的章节中讨论了目前常见的实现撤销和重做的方案，其中的仿函数保存反操作
的方案的空间和时间优势非常吸引人，但是需要为每一个操作实现一个反操作，这个过程
非常的繁琐，而且容易出错；更何况并不是每一个操作都有反操作存在的，必须要将当前
的信息保存下来，在撤销和重做的时候使用。
从前面的所有方案中我们可以总结出实现撤销和重做所必须遵守的一些规范如下：
(1)为了实现撤销操作必须在对对象修改之前保存原始信息备份
(2)为了实现重做操作必须在对对象修改的时候保存修改信息备份
有了上面的两条就可以保证任何操作（到目前为止我还没有发现不能用这种方式实现
撤销和重做的操作）都可以通过这两条规则实现撤销和重做的能力。好了，到目前为止，
有了实现撤销和重做方案的通用规则，并且这种规则的空间和时间效率都非常好，我们该
讨论一下三个基本操作和一个复合操作了。至于为什么只有三种基本操作和一个复合操作
，这就是我在编写这个撤销和重做框架的过程中慢慢积累起来的，至于严格的证明，恐怕
不是我现在可以处理的了的。
这个三个基本操作是：
(a)创建操作
(b)修改操作
(c)删除操作
一个复合操做是：
(d)复合操作
一共是四个操作，其中复合操作可以是三个基本操作的组合，也可以是三个基本操作
和复合操作的任意组合，也就是说：复合操作里面还有子复合操作，这种嵌套可以达到任
意的层次。这里面的组合就是千变万化的了！
好了，说了这么多，是该看看具体的代码是如何实现的了。值得说明的是：为了代码
的正确性和可读性，在实现的过程中尽量避免非常复杂的C++指针操作问题，当然对于避
免不了的指针问题，也要尽可能的使其简单；取而代之的是尽量使用STL中的容器和算法
来实现需要的功能。
首先看看三个基本操作的原始实现：

////////////////////////////////////////////////////////////////////////////////
//三个基本操作的初始代码实现
＃i nclude
＃i nclude
//对象类
class Object
{
public:
Object():_member(0){}
Object(int m):_member(m){}
private:
int _member;
};
int main()
{
typedef std::map MAP;
MAP m;//必须用这个容器来表示对象的存在状态，并且可以根据标识符得到对象
//首先创建两个Object对象，为了避免指针的出现，采用了标识号的方法
{//创建操作的撤销和重做
int id1=1,id2=2;//两个对象的标识号创建参数保存于此
Object obj(10);//对象创建参数保存于此
m.insert(std::make_pair(id1,obj));//创建标识号为id1的对象
m.insert(std::make_pair(id2,obj));//创建标识号为id2的对象
//创建操作的撤销非常容易实现
m.erase(id1);//创建标识号为id1的对象的撤销操作
m.erase(id2);//创建标识号为id2的对象的撤销操作
//创建操作的重做操作也非常容易实现，不过需要备份的创建参数
m.insert(std::make_pair(id1,obj));//重做创建标识号为id1的对象
m.insert(std::make_pair(id2,obj));//重做创建标识号为id2的对象
}
{//修改操作的撤销和重做
//当然如果需要修改操作的话，对象就必须一定已经存在了
/////////////////////////////////////////////////////////
int id1=1,id2=2;//两个对象的标识号创建参数保存于此
Object obj(10);//对象创建参数保存于此
m.insert(std::make_pair(id1,obj));//创建标识号为id1的对象
m.insert(std::make_pair(id2,obj));//创建标识号为id2的对象
/////////////////////////////////////////////////////////
//下面才能够开始实现修改操作
//为了能够实现撤销操作而必须保存的信息
Object OBK1 = m[id1];//备份标识号为id1的对象的原始信息
Object OBK2 = m[id2];//备份标识号为id2的对象的原始信息
//为了能够实现重做操作而必须保存的信息
Object OM1(20);//备份标识号为id1的对象的修改参数信息
Object OM2(50);//备份标识号为id2的对象的修改参数信息
//开始对对象实现修改操作
m[id1] = OM1;//修改标识号为id1的对象
m[id2] = OM2;//修改标识号为id2的对象
//开始对对象实现撤销操作
m[id1] = OBK1;//撤销修改标识号为id1的对象
m[id2] = OBK2;//撤销修改标识号为id2的对象
//开始对对象实现重做操作
m[id1] = OM1;//重做修改标识号为id1的对象
m[id2] = OM2;//重做修改标识号为id2的对象
}
{//删除操作的撤销和重做
//当然如果需要删除操作的话，对象就必须一定已经存在了
/////////////////////////////////////////////////////////
int id1=1,id2=2;//两个对象的标识号创建参数保存于此
Object obj(10);//对象创建参数保存于此
m.insert(std::make_pair(id1,obj));//创建标识号为id1的对象
m.insert(std::make_pair(id2,obj));//创建标识号为id2的对象
/////////////////////////////////////////////////////////
//下面才能够开始实现删除操作
//为了能够实现撤销操作而必须保存的信息
Object OBK1 = m[id1];//备份标识号为id1的对象的原始信息
Object OBK2 = m[id2];//备份标识号为id2的对象的原始信息
//开始对对象实现删除操作
m.erase(id1);//删除标识号为id1的对象
m.erase(id2);//删除标识号为id2的对象
//开始对对象实现撤销操作
m.insert(std::make_pair(id1,OBK1));//创建标识号为id1的对象
m.insert(std::make_pair(id2,OBK2));//创建标识号为id2的对象
//开始对对象实现重做操作
m.erase(id1);//重做删除标识号为id1的对象
m.erase(id2);//重做删除标识号为id2的对象
}
{//复合操作
//由于复合操作需要对三个基本操作进行保存，也需要对子复合操作
//进行保存，在这里不方便给出，所以在后续的章节对这三个基本操
//作进行了封装之后才能够讨论。
}
return 0;
}
////////////////////////////////////////////////////////////////////////////////
从代码中可以看出，为了表示对象的创建和删除，必须用另外一个map容器来表示，当
容器中有指定标识号的对象存在时，表示对象被创建了；当容器中没有指定的标识号的对象
存在时，则表示对象被删除了。很明显，表示对象的存在状态必须通过另外的方式来表达，
在本文中采用的是STL中的map容器，因为该容器有很方便的查找功能，另外也是和我们需要
的用标识符作为关键字来查询对象的概念的。因此后续的文档中都会以map容器为基础进行
容器演变。
本章完！
在下一章里面将会对这三个基本命令进行总结封装，并进一步的实现了复合操作的封装
。有了复合操作的封装之后，才可以更深入的讨论撤销和重做机制的其它内容。