设计模式中，Visitor模式可以实现数据结构和数据操作的分离，主要适用以下场景：
- 数据结构稳定，但是针对数据的操作需求多样化;
- 在对数据进行操作过程中，不期望改变数据结构的组织方式。
在编译器设计中，源码经过词法分析、语法分析和语义分析后会生成抽象语法树(AST)。然后基于AST做一些分析转换，比如转换到IR结构或者进行一些优化。在这个过程中，AST数据结构是稳定的;但是在变换过程中需要对AST中的同一元素有不同的处理需求。这种场景非常适合使用Visitor模式来处理。
Visitor模式实现
Visitor模式中主要角色：
- Element: 数据结构元素基类，声明数据结构相关接口；
- ConcreteElement：具体元素，数据结构相关方法实现；
- Visitor：访问者基类，用于实现访问者接口方法；
- ConcreteVisitor：具体访问者，访问者对于数据操作的实现接口；
- ObjectStructure：用于组织元素结构，便于访问者遍历元素。
下文以cpp代码模拟一个简单文件系统中，Visitor模式遍历目录树的实现，方便对Visitor模式的理解。
元素类实现
代码语言：javascript复制class Element {
public:
virtual ~Element() {}
virtual void Accept(Visitor *visitor) = 0;
};
class Entry : public Element {
public:
virtual ~Entry() {}
virtual std::string GetName() const = 0;
virtual int GetSize() const = 0;
virtual void AddEntry(Entry *entry) {}
virtual void PrintList(const std::string &str) = 0;
void PrintList() {
PrintList("");
}
std::string ToString() const {
return GetName() " (" std::to_string(GetSize()) ")";
}
};
class File : public Entry {
public:
File(const std::string &name, int size) : m_name(name), m_size(size) {}
virtual std::string GetName() const override {
return m_name;
}
virtual int GetSize() const override {
return m_size;
}
virtual void PrintList(const std::string &str) override {
std::cout << str << "/" << ToString() << std::endl;
}
virtual void Accept(Visitor *visitor) override {
visitor->Visit(this);
}
private:
std::string m_name;
int m_size;
};
class Directory : public Entry {
public:
Directory(const std::string &name) : m_name(name) {}
~Directory() {
for (auto it : m_dirs) {
delete it;
}
m_dirs.clear();
}
virtual std::string GetName() const override {
return m_name;
}
virtual int GetSize() const override {
int size = 0;
for (auto it : m_dirs) {
size = it->GetSize();
}
return size;
}
virtual void AddEntry(Entry *entry) override {
m_dirs.push_back(entry);
}
const std::vector<Entry *> &GetEntryList() const {
return m_dirs;
}
virtual void PrintList(const std::string &str) override {
std::cout << str << "/" << ToString() << std::endl;
for (auto it : m_dirs) {
it->PrintList(str "/" m_name);
}
}
virtual void Accept(Visitor *visitor) override {
visitor->Visit(this);
}
private:
std::string m_name;
std::vector<Entry *> m_dirs;
};上述代码实现中，Element为元素几类，声明了元素的操作接口Accept；然后ConcreteElement中包含了File和Directory，二者都继承自Entry，它是作为ObjectStructure的一部分，用于组织元素结构的；Entry类和Directory共同完成了数据结构的组织。
接下来是访问者的代码实现：
代码语言：javascript复制class Visitor {
public:
virtual ~Visitor() {}
virtual void Visit(File *file) = 0;
virtual void Visit(Directory *dir) = 0;
virtual void Visit(Entry *entry) {
std::cout << "Visit Base Entry." << std::endl;
}
};
class ListVisitor : public Visitor {
public:
virtual void Visit(File *file) override {
std::cout << m_currentDir << "/" << file->GetName() << " " << file->GetSize() << std::endl;
}
virtual void Visit(Directory *dir) override {
std::cout << m_currentDir << "/" << dir->GetName() << " " << dir->GetSize() << std::endl;
std::string saved = m_currentDir;
m_currentDir = "/" dir->GetName();
auto entryList = dir->GetEntryList();
for (auto it : entryList) {
it->Accept(this);
}
m_currentDir = saved;
}
virtual void Visit(Entry *entry) {
std::cout << "Visit Default Entry." << std::endl;
}
private:
std::string m_currentDir;
};上述代码中，Visitor接口中声明了对各种数据元素的访问接口。在ListVisitor中重载了Visit方法，实现了相应的操作；特别是在Directory中还实现了对元素的遍历操作。
在所有代码中，Element中有一个Accept方法比较奇怪：如果只是想遍历访问数据结构的话，只用Visitor中的Visit方法即可实现，Accept方法似乎有点冗余。这里就需要探究一下Visitor模式中的双重分发(Double Distribution)机制了。
Visitor模式中的双重分发(Double Distribution)
双重分发其实就是分别利用了c 中的多态和重载特性，分实现了对数据元素的遍历与访问。考虑以下代码：
代码语言：javascript复制 Directory *root = new Directory("root");
Directory *bin = new Directory("bin");
Entry *tmp = new Directory("tmp");
Entry *usr = new Directory("usr");
root->AddEntry(bin);
root->AddEntry(tmp);
root->AddEntry(usr);
File *vi = new File("vi", 3000);
Entry *latex = new File("latex", 2000);
bin->AddEntry(vi);
bin->AddEntry(latex);
auto list1 = new ListVisitor;
list1->Visit(root)如果没有在Element中实现Accept方法，则Visitor中的遍历方式会写成：
代码语言：javascript复制virtual void Visit(Directory *dir) override {
std::cout << m_currentDir << "/" << dir->GetName() << " " << dir->GetSize() << std::endl;
std::string saved = m_currentDir;
m_currentDir = "/" dir->GetName();
auto entryList = dir->GetEntryList();
for (auto it : entryList) {
// it->Accept(this);
Visit(it); // 此处it为Entry*类型
}
m_currentDir = saved;
}在for循环的Visit函数中，GetEntryList()获得的是指向Entry*的指针，因此Visit方法调用的是Visit(Entry *entry)。要想访问具体的Directory节点或者File节点，还需要判断一下节点类型，转换成对应类型的指针再进行Visit，这显然不够优雅。
而Element中的Accept方法则借助了子类重载的特性，Visitor指针虽然保存了父类指针，但是由于子类重载了对应函数，从而能正确调用目标Visitor的函数；而在Accept方法中，this指向的是子类对象的地址，因而Visit也能够调用到对应子类的方法。
个人理解双重分发：
- 第一重分发是Visitor中Visit()方法的多态实现将不同数据的处理逻辑进行了一次分发；
- 第二重分发是Element中Accept()方法利用类Visitor中子类重载父类Visit方法特点，使得Element能正确被子类Visitor的相应Visit方法所处理。
总结：
Visitor模式中双重分发机制是该模式巧妙之处，具体在实现时需要注意几点：
- 在Visitor中正确实现元素的遍历逻辑（Visit和Accept调用）
- 子类Visitor中实现Visit函数会导致父类中同名函数被隐藏。
本文使用 Zhihu On VSCode 创作并发布
