Double Dispatch : Visitor Design Pattern in Modern C++

In software engineering, Behavioural Design Patterns deal with the assignment of responsibilities between objects. That in turn, make the interaction between the objects easy & loosely coupled. In this article of the design pattern series, we’re going to take a look at Visitor Design Pattern in Modern C++ which is also known as a classic technique for recovering lost type information(using Double Dispatch[TODO]). Visitor Design Pattern is used to perform an operation on a group of similar kind of objects or hierarchy. In this article, we will not only see the classical example but also leverage the std::visit from the standard library to cut-short the implementation time of the Visitor Design Pattern.

By the way, If you haven’t check out my other articles on Behavioural Design Patterns, then here is the list:

The code snippets you see throughout this series of articles are simplified not sophisticated. So you often see me not using keywords like override, final, public(while inheritance) just to make code compact & consumable(most of the time) in single standard screen size. I also prefer struct instead of class just to save line by not writing “public:” sometimes and also miss virtual destructor, constructor, copy constructor, prefix std::, deleting dynamic memory, intentionally. I also consider myself a pragmatic person who wants to convey an idea in the simplest way possible rather than the standard way or using Jargons.

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don’t have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

Intent

To define a new operation on a group of similar kind of objects or hierarchy.

The classical Visitor Design Pattern has some component which we call a visitor. That is allowed to traverse the entire inheritance hierarchy. But before that what you have to do is you have to implement a single method called visit()in the entire hierarchy once.
And from then on you don’t have to touch the hierarchy anymore. So the hierarchy can exist on its own and you can create extra visitors sort of thing on the side which is perfectly consistent with both the Open-Closed Principle as well as the Single Responsibility Principle.

Visitor Design Pattern Examples in C++

This is a reasonably complex design pattern & I do not want to confuse you by directly jumping on example. So we will come to the Visitor Design Pattern by exploring other available option. And then you will understand the importance of visitor despite the complexity.

Intrusive Visitor

Let’s suppose that you have a hierarchy of documents as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
struct Document {
    virtual void add_to_list(const string &line) = 0;
};

struct Markdown : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }

    string          m_start = "* ";
    list<string>    m_content;
};

struct HTML : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }

    string          m_start = "<li>";
    string          m_end = "</li>";
    list<string>    m_content;
};

And you need to define some new operation on existing infrastructure. For example, we have a Document class as above and now you want that different documents(i.e. HTML & Markdown) to be printable.
So you have this brand new concern of printing and you want to somehow propagate this through the entire hierarchy by making essentially every single class of your document to be independently printable somehow.
Now what you don’t want to do is you don’t want to go back into the existing code and modify each class(with new virtual function) in the hierarchy every time you have a new concern, because, unfortunately, this breaks an Open-Closed Principle, rather we should use inheritance.
There’s also the Single Responsibility Principle that you have to adhere to because if you are introducing a brand new concern such as printing then that should be a separate class. But still, let say we will do it:

 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
struct Document {
    virtual void add_to_list(const string &line) = 0;
    virtual void print() = 0;
};

struct Markdown : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }
    void print() {
        for (auto &&item : m_content) 
            cout << m_start << item << endl;
    }

    string          m_start = "* ";
    list<string>    m_content;
};

struct HTML : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }
    void print() {
        cout << "<ul>" << endl;
        for (auto &&item : m_content) {
            cout << "\t" << m_start << item << m_end << endl;
        }
        cout << "</ul>" << endl;
    }

    string          m_start = "<li>";
    string          m_end = "</li>";
    list<string>    m_content;
};

int main() {
    Document *d = new HTML;
    d->add_to_list("This is line");
    d->print();
    return EXIT_SUCCESS;
}

As you can see for only 2-3 class it’s good even if it is violating some SOLID principles. But imagine if you have 20 classes as part of this hierarchy. It would be really difficult to go into 20 different files & add a print method for every one of them.
Moreover, if there is more than one concern like save, process, etc., this approach becomes cumbersome. It would be much nicer to have each concern in a separate class that also goes towards the Single Responsibility Principle.

Reflective Visitor

 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
struct Document {
    virtual void add_to_list(const string &line) = 0;
};

struct Markdown : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }

    string          m_start = "* ";
    list<string>    m_content;
};

struct HTML : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }

    string          m_start = "<li>";
    string          m_end = "</li>";
    list<string>    m_content;
};

struct DocumentPrinter {
    static void print(Document *e) {        
        if (auto md = dynamic_cast<Markdown *>(e)) {
            for (auto &&item : md->m_content)
                cout << md->m_start << item << endl;
        }
        else if (auto hd = dynamic_cast<HTML *>(e)) {
            cout << "<ul>" << endl;
            for (auto &&item : hd->m_content) {
                cout << "\t" << hd->m_start << item << hd->m_end << endl;
            }
            cout << "</ul>" << endl;
        }
    }
};

int main() {
    Document *d = new HTML;
    d->add_to_list("This is line");
    DocumentPrinter::print(d);
    return EXIT_SUCCESS;
}

As mentioned above, we created a separate class having printing functionality for the entire hierarchy just to adhere Single Responsibility Principle. But in this approach, we have to identify types for a particular class(using dynamic_cast<>()) as we have to work on individual object of hierarchy independently.
This is not an approach which scales efficiently, especially as you expand the set of classes that you’re processing, you will end up having a long list of if/else-if along with paying performance cost on RTTI.

Classic Visitor

So far the approaches that have been sort of half measures what we really want is we really want a mechanism that will allow us to extend the entire hierarchies functionality in various different ways without being intrusive and certainly without having massive if/else-if statements full of dynamic_cast<>() in them.

 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
/* --------------------------- Added Visitor Classes ----------------------------- */
struct DocumentVisitor {
    virtual void visit(class Markdown*) = 0;
    virtual void visit(class HTML*) = 0;
};

struct DocumentPrinter : DocumentVisitor {
    void visit(class Markdown* md);
    void visit(class HTML* hd);
};
/* -------------------------------------------------------------------------------- */

struct Document {
    virtual void add_to_list(const string &line) = 0;
    virtual void visit(DocumentVisitor*) = 0; // <<<<<<<<<<--------------------------
};

struct Markdown : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }
    void visit(DocumentVisitor* dv) { dv->visit(this); } // <<<<<<<<<<---------------

    string          m_start = "* ";
    list<string>    m_content;
};

struct HTML : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }
    void visit(DocumentVisitor* dv) { dv->visit(this); } // <<<<<<<<<<---------------

    string          m_start = "<li>";
    string          m_end = "</li>";
    list<string>    m_content;
};


/* -------------------------- Added Visitor Methods ------------------------------- */
void DocumentPrinter::visit(Markdown* md) {
    for (auto &&item : md->m_content)
        cout << md->m_start << item << endl;
}
void DocumentPrinter::visit(HTML* hd) {
    cout << "<ul>" << endl;
    for (auto &&item : hd->m_content) 
        cout << "\t" << hd->m_start << item << hd->m_end << endl;
    cout << "</ul>" << endl;
}
/* -------------------------------------------------------------------------------- */

int main() {
    Document *d = new HTML;
    d->add_to_list("This is line");
    d->visit(new DocumentPrinter);
    return EXIT_SUCCESS;
}

So as you can see we have added two-layer of indirection to achieve what we wanted without violating the Single Responsibility Principle & Open-Closed Principle. Thanks to Double Dispatch in C++[TODO].
If you see all the classes involved in the process, it may seem a bit complicated. But call stack may help you to understand it easily.

From d->visit(new DocumentPrinter), we call visit()method, which will dispatch to the appropriate overridden visit i.e. `HTML::visit(DocumentVisitor* dv).
From the overridden HTML::visit(DocumentVisitor*), we call dv->visit(this), which will again dispatch to the appropriate overridden method(considering the type of this pointer) i.e. DocumentPrinter::visit(HTML*).

Visitor Design Pattern in Modern C++

 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
struct Document {
    virtual void add_to_list(const string &line) = 0;
};

struct Markdown : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }

    string          m_start = "* ";
    list<string>    m_content;
};

struct HTML : Document {
    void add_to_list(const string &line) { m_content.push_back(line); }

    string          m_start = "<li>";
    string          m_end = "</li>";
    list<string>    m_content;
};

/* ------------------------------------ Visitor ------------------------------------- */
struct DocumentPrinter {
    void operator()(Markdown &md) {
        for (auto &&item : md.m_content)
            cout << md.m_start << item << endl;
    }
    void operator()(HTML &hd){
        cout << "<ul>" << endl;
        for (auto &&item : hd.m_content)
            cout << "\t" << hd.m_start << item << hd.m_end << endl;
        cout << "</ul>" << endl;
    }
};
/* ---------------------------------------------------------------------------------- */
using document = std::variant<Markdown, HTML>;

int main() {
    HTML hd;
    hd.add_to_list("This is line");
    document d = hd;
    DocumentPrinter dp;
    std::visit(dp, d);
    return EXIT_SUCCESS;
}

So for those of you who are not familiar with the std::variant, you can consider it as a union(a type-safe union). And line std::variant<Markdown, HTML>, suggest that you can use/assign/access either Markdown or HTML at a time.
And Modern C++ provides us std::visit which accept callable i.e. DocumentPrinter in our case having overloaded function operator and std::variant as the second argument. You also make use of lambda functions rather using functor i.e. DocumentPrinter.

Benefits of Visitor Design Pattern

Adhering Single Responsibility Principle meaning separating type-specific logic in the separate entity/class. In our case, DocumentPrinter only handles the printing for different document types.
Adhering Open-Closed Principle meaning new functionality can be added without touching any class headers once we inserted visit() method for hierarchy, For example, if you want to add scan()method for each different Document, you can create DocumentScanner & rest of the edit goes as same DocumentPrinter.
This will be much useful when you already have done the unit-testing for your entire hierarchy. Now you do not want to touch that & wants to add new functionality.
Performance over dynamic_cast, typeid()and check for enum/string comparison.

Summary by FAQs

When should I use the Visitor Design Pattern?

Visitor Design Pattern is quite useful when your requirement keeps changing which also affects multiple classes in the inheritance hierarchy.

What is the typical use case of the Visitor Design Pattern?

In replacement of dynamic_cast<>, `typeid(), etc.
To process the collection of different types of objects.
Filtering different type of objects from collections.

Difference between Visitor vs Decorator Design Pattern?

Decorator(Structural Design Pattern) works on an object by enhances existing functionality. While
Visitor(Behavioral Design Pattern) works on a hierarchy of classes where you want to run different method based on concrete type but avoiding dynamic_cast<>() or typeof() operators.

Intent#

Visitor Design Pattern Examples in C++#

Intrusive Visitor#

Reflective Visitor#

Classic Visitor#

Visitor Design Pattern in Modern C++#

Benefits of Visitor Design Pattern#

Summary by FAQs#