序言

大二下学期学校开了一门课：数据结构课程设计，要求三人组队完成一个简易的文本编辑器。底层数据结构都被老师规定好了不能改，也没什么可讲的，这篇文章主要谈其中用到的设计模式：Singleton模式（没有出现在最终版本中）、Command模式、Visitor模式。这也是我第一次使用设计模式。

顺带一提，《设计模式》真的是很好的OOP入门书，不要被它的名字吓到，GoF在书的最后也说了这本书是一本合适的入门指南，学习这些设计模式有助于新手理解已有的面向对象系统。第一次读看不懂全部内容很正常，即使这样也能从中学到很多的工程知识，没必要“取之尽锱铢”。

感谢我的队友 Dixeran 和 TMT，who提供了最强的支持。也很感谢杨俊老师提供的提供的这次锻练习机会。
抄手也很好吃。

我们课程设计的源代码在GayHub上开源：MiniEditor

Singleton模式

本来想用 Singleton 模式自己写一个剪切板的，但后来发现直接通过QT提供的接口用操作系统自带的剪切板更方便，就把这段代码删了，as I mentioned before。

先简单介绍一下 Singleton 模式：
按照《设计模式》中的说法，Singleton 模式保证一个类仅有一个实例，并提供一个访问它的全局访问点。它是对全局变量的一种改进，避免了那些存储唯一实例的全局变量污染命名空间。

全局只维护一个剪切板的实例是非常合情合理的设计，因此最初设计的时候会想用 Singleton 模式实现剪切板。这里采用的是 Scott Meyers 改进后的 Singleton 模式，与GoF书中的略有不同，一会儿会详细说明。下面是代码：

class ClipBoard
{
public:
    ClipBoard(const ClipBoard&) = delete;
    ClipBoard& operator = (const ClipBoard&) = delete;

    static ClipBoard& instance();

    QString getContent();           //getter
    void setContent(QString& str);  //setter

private:
    ClipBoard();
    QString content;
};


ClipBoard& ClipBoard::instance() { 
    static ClipBoard _instance;  
    return _instance; 
} 

QString ClipBoard::getContent(){   
    return content;
}

void setContent(QString& str) {
    content = str;
}

让构造函数是 private 的，是为了禁止用户自行创建ClipBoard的权利，从而控制该单件的访问点。这里全局维护的唯一一个ClipBoard实例被放在ClipBoard::instance()函数内部作为 local static 对象，该函数返回该局部对象的引用，用户代码可以这样使用ClipBoard:

1	QString content = ClipBoard::instance().getContent();

可以看看使用QT提供的操作系统剪切板的接口的使用方式：

1	QString content = QGuiApplication::clipboard()->text();

是不是非常像！可以看一下相关的文档描述（来自QClipboard）：

There is a single QClipboard object in an application, accessible as QGuiApplication::clipboard().

果然！QT也是用的 Singleton 模式实现的QClipboard，只不过访问点不由QClipboard类本身提供，而是由QGuiApplication提供。这也体现了 Singleton 模式的灵活性：我们可以控制单例的访问点。

比较 GoF Singleton 与 Meyers Singleton

再来比较一下 GoF 的 Singleton 模式与 Scott Meyers 改进后的 Singleton 模式：
先列出 GoF Singleton 的模样：

class Singleton {     
public:        
    static Singleton* Instance();
protected:         
    Singleton(); 
private:         
    static Singleton* _instance;     
}; 

Singleton* Singleton::_instance = 0;

Singleton* Singleton::Instance() { 
    if (_instance == 0) {            
         _instance = new Singleton;         
    }         
    return _instance;
}

Meyers Singleton 的例子就是上面Clipboard的代码。

GoF是让类来维护这个实例的指针，然后在Singleton::Instance ()中检查指针是否为空，若为空则创建对象（这个手法叫Lazy initialization），可以想到这么做（而不是在一开始就创建对象）的好处是，如果这个Singleton类在程序运行期间很少被用到，那么就减少了这种情形下的空间开销。但坏处是，假如经常用到这个类，那每次都要检查一遍该单件是否存在，又增大了开销。第二个坏处是，当这个单件不再用的时候，还要用户手动delete掉这个单件，不太方便，更可怕的是用户可能不小心错误地 delete 了该单例，那就真炸了，不想让用户犯这个错误，就不要给用户这个权力。（当然我还是很好奇 QT 中为什么要传出来全局唯一的QClipboard的指针给我，就不怕我 delete 了它么？也许是因为考虑了多线程的情况会有所影响？这里要提一下，我这里讨论的 Singleton 模式都是假定在单线程环境中的）

一种避免每次检查的改进方法是：考虑将类中的static Singleton* _instance;这句改为static Singleton _instance;，然后在Singleton::Instance()中也就不用检查了，代价之一是该单例不管用不用到，在程序运行期间会一直存在；第二是由于C++没有规定不同编译单元内的 non-local static 对象的初始化顺序，如果不同编译单元内的 non-local static 对象的初始化存在依赖关系，可能出现使用一个未初始化的对象去初始化另一个对象的情况。（如果想不明白可以参考《Effective C++》条款4的例子）

Meyers Singleton模式解决了上面的所有问题，它利用了C++语言的一条规则（摘自《Effective C++》条款4）：

C++保证，函数内的 local static 对象会在“该函数被调用期间”“首次遇上该对象定义式”时被初始化。

Meyers Singleton让单件成为函数内部的 local static 对象，所以只能通过函数返回出来的该对象的引用访问它，所以访问到单件时它一定是已被初始化的。而且返回出来的是引用而不是指针，也避免了让用户 delete 单件的成本与风险。

以上都是在单线程的前提下讨论的，多线程暂时超出我的能力范围，不予讨论（逃

Command 模式

Command 模式的核心是把行为封装成对象。其实像C++这样能把函数像变量一样传来传去的语言来说，Command 模式真的没多少用，尤其是自从C++11有了lambda、bind和function之后。相应地 Strategy 模式也没啥用。这里让编辑器支持撤销/重做操作算是 Command 模式一个为数不多的用处之一。

既然将行为封装成了对象，那么在执行这个命令（行为）时需要的参数也就可以放在对象里，因此想要撤销这个行为的动作时可以根据这些参数来恢复到执行命令前的情况，因为会有一连串的命令序列，用于记录用户的每一次编辑操作，这里将用std::list来储存该命令队列。如果只想支持“撤销”操作的话完全可以只用std::stack来储存它，但为了支持“重做”操作，只用栈还是不行的。

我们课程设计中用到的Command继承体系（UML类图）：
command

三个子类的功能如它们的名字一样。这里重载了函数调用运算符，不习惯的话也可以将函数调用运算符改成void do();，当成普通成员函数来调用，效果都是一样的。

撤销/重做的单元是单个文本文件，在我们的程序里被抽象为一个类TextFile：

class TextFile: public QObject
{
public:
    Q_INVOKABLE void undo();
    Q_INVOKABLE void redo();

    Q_INVOKABLE void insert(int row, int column, QChar character);          
    Q_INVOKABLE void erase(int row, int column);   
    Q_INVOKABLE void replaceAll(QString newString);                         
    ...
private:
    //add a command to 'historyList'
    void addCommand(std::unique_ptr<EditCommand> &&command);

    std::list<std::unique_ptr<EditCommand>> historyList;
    std::list<std::unique_ptr<EditCommand>>::iterator nextCommand;
    ...
};

使用std::unique_ptr的代价和raw pointer的开销几乎一样，也支持多态，还不用手动delete不用的对象，是现代C++的写法，不习惯的可以使用raw pointer来代替，没关系。

TextFile中维护一个command的列表（historyList，使用std::list封装的一串EditCommand），用于记录执行过的命令序列，辅助完成撤销/重做操作，nextCommand指向重做（redo）时要执行的下一条指令。
在未执行过撤销（undo）操作的情况下，nextCommand指向historyList的尾后位置（尾后迭代器），这个位置上是不存在EditCommand的，如图：

redo undo

在当前位置，执行两次撤销操作后，nextCommand会指向黄色的EditCommand：

redo undo

在这个位置上，如果执行撤销操作，则先将nextCommand往回推一步，指向紫色的EditCommand，再调用紫色EditCommand的undo()成员函数。
若执行重做操作，则先调用黄色EditCommand的redo()成员函数，再将nextCommand向后推一步，指向右边那个灰色的EditCommand。
若在此处执行普通的编辑操作，则会将nextCommand（包括它当前指向的黄色EditCommand）全部清除，再将新的指令压入historyList末尾，并将nextCommand后推一步，令它依旧是尾后迭代器。执行后的结果如下图：

undo redo

分析完毕后TextFile::undo()，TextFile::redo()和TextFile::addCommand的实现也很简单：

void TextFile::undo()
{
    if(nextCommand != historyList.begin()) {
        --nextCommand;
        (*nextCommand)->undo();
    }
}

void TextFile::redo()
{
    if(nextCommand != historyList.end()) {
        (*nextCommand)->redo();
        ++nextCommand;
    }
}

void TextFile::addCommand(std::unique_ptr<EditCommand> &&command)
{
    historyList.erase(nextCommand, historyList.end());
    historyList.push_back(std::move(command));
    nextCommand = historyList.end();
}

只要你愿意，还可以在TextFile::addCommand中控制历史列表（historyList）的长度。

使用这些 Command 时只要在相应的函数中构造 Command 对象，并调用其相应操作即可，如下：

void TextFile::insert(int row, int column, QChar character)
{
    auto insertCommand = std::make_unique<InsertCommand>(
               std::make_pair(row, column), character, text, this);
    (*insertCommand)();
    addCommand(std::move(insertCommand));
}

Visitor 模式

Visitor 模式被创造出来的目的主要是去弥补C++不支持双分派（double-dispatch），只支持单分派（single-dispatch）：

单分派：用哪种操作实现一个请求取决于两个方面：该请求的名称和一个接收者的类型。
双分派：执行的操作取决于请求的种类和两个接收者的类型。

这是 Visitor 模式的关键所在：得到执行的操作不仅决定于 Visitor 的类型还决定于它访问的 Element 类型。可以不将操作静态地绑定在 Element 接口中，而将其安放在一个Visitor 中，并使用 Accept 在运行时进行绑定。 ——《设计模式》

上面的“Accept”在我们的程序中对应的是“traverse”：

class TextStructure
{
public:
    bool traverse(AbstractVisitor &visitor); //inner iterator
    ...
};

bool TextStructure::traverse(AbstractVisitor &visitor)
{
    for( every element in TextStructure )    //pseudo-code
        if(!visitor.visit(element))
                return false;
    return true;
}

注：得到了最可爱的TMT的批准，以引用这些代码（包括下面那段），她是TextStructure和SearchVisitor的作者，我略微修改了一下格式。

接用 Visitor 模式，我们给底层结构增加一个（需要访问全部元素的）操作变得很简单，只需要从 Visitor 继承体系中派生出一个新类即可。

下面是编辑器中的 Visitor 继承体系（三个子类，三个功能）：

visitor

DisplayVisitor：用于将刚加载到内存中的文件显示在UI界面上。
SaveVisitor：用于将内存中的数据结构以文本文档(.txt)的形式储存到硬盘中。
SearchVisitor：用于完成搜索操作，内部融合了KMP算法。

前两个 Visitor 没什么好说的，这里展示一下 SearchVisitor 的关键部分实现代码，类的定义见上面的UML类图。

SearchVisitor::SearchVisitor(QString format, Qt::CaseSensitivity cs)
    :target(format)
    ,sensitivity(cs)
    ,next(new int [format.size()])
    ,index(0)        //模式串游标
    ,row_count(0)    //当前访问的字符位于第几行
    ,column_count(0) //当前访问的字符位于第几列
{
    int i = 0;
    next[0] = -1;    //next[0]初始化为-1.  -1表示不存在相同的最大前缀和最大后缀
    int j = -1;      //j初始化为-1
    while( i < format.size()-1 ) {
        if(j==-1 || equal(format[i],format[j] ) ) {
            i++;
            j++;
            next[i]=j;
        } else {
            j = next[j];
        }
    }
}

/*遍历kmp算法求匹配*/
bool SearchVisitor::visit(QChar& element) {   
    std::pair<int,int> position(0,0);
    if(element!='\n' && index < target.size()) {
       while( index != -1 && !equal(element,target[index]) )//匹配失败
           index=next[index];
       index++;
       if (index == target.size()) {  //若匹配成功，记录结果
           position.second = column_count-target.size()+1;
           position.first = row_count;
           result.push_back(position);
           index = 0;
       }
       column_count++;
       return true;
    } else if(element=='\n') {        //忽略换行符
        row_count++;
        column_count =0;
        index=0;
        return true;
    }
    return false;
}

这里在构造函数中计算next数组的值，通过 visit(QChar& element)函数在SearchVisitor内累积状态，以辅助实现匹配过程。KMP算法维护两个游标，一个标识主串字符位置，一个标识模式串字符位置，上面代码中index即为模式串上的游标，而主串上的游标是不用在SearchVisitor中手动推进的，而是通过TextStructure提供的traverse(AbstractVisitor &visitor)完成。
在进行搜索操作的时候，可以这样写：

QString fmt("format string");
Qt::CaseSensitivity cs = Qt::CaseSensitive;

//text is a instantiation of TextStructure
auto sv = SearchVisitor(fmt, cs);
text.traverse(searchVisitor);

auto result = sv.getResult();

另外两个Visitor：DisplayVisitor和SaveVisitor都非常简单，不在此展开叙述，有兴趣的同学可以参考我的GayHub