The Vee The Vee - 2 months ago 7
C++ Question

Is there any better way to define a visitor pattern without a priori knowledge of derived classes?

This is my first encounter with the visitor design pattern for double dispatch. In my scenario objects derived from a common base class can interact somehow with each other, so the visitor and the visitee are from the same set. However, for practical reasons, my goal is to completely separate the logic from the application. In particular, I want to avoid at all costs the base class to be aware of what derived classes can be using it. There will be different independent application layers approaching the same base within one application.

The problem is that a

virtual
method needs to be defined in the base for each of the possible derived classes. This can be easily solved using templates. A bigger problem turned out to be that I don't want to be limited to a particular number (or upper bound) of derived classes. This is as close as I got:

/*** Generic ***/

template<class...>
struct Visit { };

template<class... Derived>
struct Base : Visit<Derived...> {
virtual int accept(Base*) = 0;
};

// specializations for different numbers...

template<class X>
struct Visit<X> {
virtual int visit(X*) = 0;
};

template<class X, class Y>
struct Visit<X, Y> {
virtual int visit(X*) = 0;
virtual int visit(Y*) = 0;
};

// and more for 3, 4, ...


/*** Application ***/

struct D1;
struct D2;

using A = Base<D1, D2>; // <--- the goal is to keep this simple

struct D1 : A {
int accept(A* a) { return a->visit(this); }
int visit(D1*) { return 1; }
int visit(D2*) { return 2; }
};

struct D2 : A {
int accept(A* a) { return a->visit(this); }
int visit(D1*) { return 3; }
int visit(D2*) { return 4; }
};

int main() {
A* d1 = new D1();
A* d2 = new D2();
return d2->accept(d1); // expected: 2
}


This works and satisfies most of the criteria except the last one. The maximum number of possible derived classes needs to be known in advance and hard-coded in the
Visit
template. And it's not very elegant to repeat the same boilerplate so many times just with different numbers of lines.

I was wondering whether something cleaner along the lines of

template<class X>
struct InjectVisit {
virtual int visit(X*) = 0;
};

template<class... Derived>
struct Base : InjectVisit<Derived>... {
virtual int accept(Base*) = 0;
};


(replacing the
Visit
template entirely) could be possible at all, in any variation, in C++. This, namely, does not work, for much the same reason as why partial specialization of function templates won't:


Overload resolution only selects a base template (or a nontemplate function, if one is available). Only after it's been decided which base template is going to be selected, and that choice is locked in, will the compiler look around to see if there happens to be a suitable specialization of that template available, and if so that specialization will get used.


Since each of the injected
visit(X*)
comes from a different template instantiation of
InjectVisit
, they won't compete against each other, leading to ambiguity errors (even though only exactly one of them could be used at any point).

I tried to adapt the second half of this answer but it won't work if
D1
and
D2
need to be derived from the same base (unless, again, all the deriveds are hard-coded into that). Of course, a
dynamic_cast
would be possible. But this code is meant to be called several 100,000's a second and I don't want RTTI to become my main bottleneck.

Currently I am stuck on a middle way in which the base class of
Base
is replaced by a single template class which needs to be provided, along the lines of
Visit
, by each application pattern separately, which seems to be the least evil, but I am still curious. Is just listing the names of a few classes and making C++ generate the few lines for me on demand really impossible?

Answer

Since each of the injected visit(X*) comes from a different template instantiation of InjectVisit, they won't compete against each other, leading to ambiguity errors (even though only exactly one of them could be used at any point).

You could use following using trick:

LIVE DEMO

#include <iostream>

void println(const char *s)
{
    using namespace std;
    cout << s << endl;
}

template<typename X>
struct InjectVisit
{
    virtual void visit(X*) = 0;
};

template<typename Head, typename ...Tail>
struct VirtualChain : InjectVisit<Head>, VirtualChain<Tail...>
{
    using InjectVisit<Head>::visit;
    using VirtualChain<Tail...>::visit;
};

template<typename Head>
struct VirtualChain<Head> : InjectVisit<Head>
{
    using InjectVisit<Head>::visit;
};

template<typename ...List>
struct Base : VirtualChain<List...>
{
    virtual void accept(Base*) = 0;
};

/****************************************************************/

struct D1;
struct D2;

using ConcreteBase = Base<D1, D2>;

struct D1 : ConcreteBase
{
    virtual void accept(ConcreteBase* visitor) { visitor->visit(this); }
    virtual void visit(D1*) { println("D1 visited by D1"); }
    virtual void visit(D2*) { println("D2 visited by D1"); }
};

struct D2 : ConcreteBase
{
    virtual void accept(ConcreteBase* visitor) { visitor->visit(this); }
    virtual void visit(D1*) { println("D1 visited by D2"); }
    virtual void visit(D2*) { println("D2 visited by D2"); }
};

int main()
{
    ConcreteBase* d1 = new D1();
    ConcreteBase* d2 = new D2();
    d1->accept(d2);
    d2->accept(d2);
}

Output is:

D1 visited by D2
D2 visited by D2