“是历史。”
0%

撤销重做的简单实现c++

发表于 更新于 分类于 Valine：

这学期的数据结构程序设计课里有一个自制文本编辑器的小作业，文本编辑器的增删改查涉及的算法知识不是很难，不过撤销和重做的实现倒是一个难点。这里我只是浅显地在字符串处理的层面实现了一下，比较简陋。

首先思考，每按一次撤销，就将文本返回到一定操作之前的阶段，每一个可供返回的状态作为一个元素，那么使用栈来存储状态是很不错的。重做则只要把每个从撤销队列里弹出的元素压到重做栈即可。另外想到，撤销不可能无限地进行下去，撤销栈应有一个最大元素数量。当到达这个数量，应该删掉栈底的状态，那么双向队列是很方便的选择。

声明一下我们的撤销类

文本编辑器我是用 MFC 写的，MFC 的各种 dialog 类其实自带撤消重做和序列化的接口，但我太笨了不会用（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MyUndo {
#define ADD_TEXT 1
#define DEL_TEXT 0

private:

    // 我的撤销类是和主窗口类紧密耦合的，很烂(   
    // 这是和窗口中内容同步更新的存储文本
	CStringW text;
	// 撤销栈，三个元素分别代表这个可撤销状态 进行的操作、在文本中的位置和这一段字符的内容
    deque<pair<int, pair<int, CStringW>>> undoStack;
	deque<pair<int, pair<int, CStringW>>> redoStack;
    // 最大撤销数
	const int maxUndo = 100;

public:
	MyUndo(CStringW value);
	MyUndo();
	CStringW GetText();
	void SetText(CStringW text);

    // 我的主窗口中文本内容发生更改时，调用这个函数，更新可撤销状态
	void ExternUpdateText(int state, int pos, CStringW add);
    // 这是进行撤销或重做或单纯进行文本更新时，MyUndo对象内部调用的函数
    // 反正是自己写的垃圾代码也就没管访问权限了(
	void InternUpdateText(int state, int pos, CStringW add, bool isUndo);
	// 清空栈用
    void ResetRedo();
	void ResetUndo();
	void init();
    // 撤销或重做时调用
	bool Undo();
	bool Redo();

};

看一下我们的 ExternUpdateText 函数

这里我的逻辑是，如果这一次更改的内容恰好与上一次更改的内容连接，比如这次输入的文字恰好在上一次输入的文件末尾，或这次删除的文字恰好在上一个删除的字符之前，那么它们就是同一个可撤销元素的内容，达到长按删除一大段之后撤销，所有内容都变回来的效果。注意主窗口 edit 控件响应 ON_EN_CHANGE 消息肯定是每输入一个字符就响应一次，所以更新文本其实每次只更新了一个字符，要是每次响应都创建一个可撤销状态，撤销起来就太慢了。你也可以改成你自己的逻辑，比如每隔一段时间就算新输入的字符在上一个可撤销状态的末尾，也重新新建一个状态，简而言之就是不让一个状态包含的字符串太长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
void MyUndo::ExternUpdateText(int state, int pos, CStringW add)
{
    // 撤销栈为空直接插入新元素
    if (undoStack.empty()) {

        undoStack.push_back(make_pair(state, make_pair(pos, add)));
        InternUpdateText(state, pos, add, false);
        return;
    }

    pair<int, pair<int, CStringW>>& last = undoStack.back();
    if (ADD_TEXT == state) {

        // 本次操作为增加字符
        // 如果增加的字符与之前最后添加的字符相连，就把这次增加的字符接在最新撤销对象的后边
        if (ADD_TEXT == last.first && pos == last.second.first + last.second.second.GetLength()) {

            last.second.second += add;
            InternUpdateText(state, pos, add, false);
        }
        else {

            // 如果是在别的位置增加新字符，就新建撤销对象
            if (undoStack.size() > maxUndo) {

                // 如果撤销栈已满，则弹出最之前的可撤销对象
                undoStack.pop_front();
            }

            undoStack.push_back(make_pair(state, make_pair(pos, add)));
            InternUpdateText(state, pos, add, false);
        }
    }
    else {

        // 本次操作为删除字符
        // 每次删除操作要使对应pos减相应长度
        if (DEL_TEXT == last.first && last.second.first == pos + 1) {

            last.second.first -= add.GetLength();
            last.second.second = (add + last.second.second);
            InternUpdateText(state, pos, add, false);
        }
        else {

            if (undoStack.size() > maxUndo) {

                // 如果撤销栈已满，...
                undoStack.pop_front();
            }

            undoStack.push_back(make_pair(state, make_pair(pos, add)));
            InternUpdateText(state, pos, add, false);
        }
    }
}

观察到 InterUpdateText 函数被多次调用，我们来看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 四个参数，分别是 进行的操作，操作的起点，操作对应的字符串，是否以撤销模式修改文本
void MyUndo::InternUpdateText(int state, int pos, CStringW add, bool isUndo)
{
    CStringW firstHalf = this->text.Left(pos);
    CStringW secondHalf = this->text.Mid(pos);

    if (!isUndo) {

        // 非撤销模式调用此函数，说明只是正常地修改字符串，在对应位置对text作修改即可
        if (ADD_TEXT == state) {

            firstHalf += add;
        }
        else if (DEL_TEXT == state) {

            secondHalf = secondHalf.Mid(add.GetLength());
        }
    }
    else {

        // 撤销模式调用此函数，说明要根据位置信息重现上一状态，可以发现这里的操作与上方相反
        if (ADD_TEXT == state) {

            secondHalf = secondHalf.Mid(add.GetLength());
        }
        else if (DEL_TEXT == state) {

            firstHalf += add;
        }
    }

    text = (firstHalf + secondHalf);
}

可以发现这里调用这个函数纯粹就是把主窗口添加的字符添加到我们的撤销类里的备份的相应位置，使两者保持统一。而撤销的时候其实也是修改的撤销类中的备份内容，然后主窗口拿到修改之后的备份内容去替代原先的内容。

结束了，其他你只要在你想要设置的撤销节点调用 ExterUpdateText 函数，然后想撤销的时候调用 Undo 函数，再取得撤销对象更新后的 text 属性内容，替换原来主窗口内容就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool MyUndo::Undo()
{
    if (undoStack.empty()) {
        return false;
    }

    // 根据撤销栈最上方的信息对内容进行重现
    pair<int, pair<int, CStringW>>& minus = undoStack.back();
    InternUpdateText(minus.first, minus.second.first, minus.second.second, true);

    // 并将此元素压入重做栈
    redoStack.push_back(minus);
    undoStack.pop_back();

    return true;
}

​