C++ double dispatch "extensible" without RTTI

Question

Does anyone know a way to have double dispatch handled correctly in C++ without using RTTI and dynamic_cast<> and also a solution, in which the class hierarchy is extensible, that is the base class can be derived from further and its definition/implementation does not need to know about that?
I suspect there is no way, but I'd be glad to be proven wrong :)

Answer 1

The first thing to realize is that double (or higher order) dispatch doesn't scale. With single dispatch, and n types, you need n functions; for double dispatch n^2, and so on. How you handle this problem partially determines how you handle double dispatch. One obvious solution is to limit the number of derived types, by creating a closed hierarchy; in that case, double dispatch can be implemented easily using a variant of the visitor pattern. If you don't close the hierarchy, then you have several possible approaches.

If you insist that every pair corresponds to a function, then you basically need a:

std::map<std::pair<std::type_index, std::type_index>, void (*)(Base const& lhs, Base const& rhs)>
                dispatchMap;

(Adjust the function signature as necessary.) You also have to implement the n^2 functions, and insert them into the dispatchMap. (I'm assuming here that you use free functions; there's no logical reason to put them in one of the classes rather than the other.) After that, you call:

(*dispatchMap[std::make_pair( std::type_index( typeid( obj1 ) ), std::type_index( typeid( obj2 ) )])( obj1, obj2 );

(You'll obviously want to wrap that into a function; it's not the sort of thing you want scattered all over the code.)

A minor variant would be to say that only certain combinations are legal. In this case, you can use find on the dispatchMap, and generate an error if you don't find what you're looking for. (Expect a lot of errors.) The same solution could e used if you can define some sort of default behavior.

If you want to do it 100% correctly, with some of the functions able to handle an intermediate class and all of its derivatives, you then need some sort of more dynamic searching, and ordering to control overload resolution. Consider for example:

            Base
         /       \
        /         \
       I1          I2
      /  \        /  \
     /    \      /    \
    D1a   D1b   D2a   D2b

If you have an f(I1, D2a) and an f(D1a, I2), which one should be chosen. The simplest solution is just a linear search, selecting the first which can be called (as determined by dynamic_cast on pointers to the objects), and manually managing the order of insertion to define the overload resolution you wish. With n^2 functions, this could become slow fairly quickly, however. Since there is an ordering, it should be possible to use std::map, but the ordering function is going to be decidedly non-trivial to implement (and will still have to use dynamic_cast all over the place).

All things considered, my suggestion would be to limit double dispatch to small, closed hierarchies, and stick to some variant of the visitor pattern.

Answer 2

The "visitor pattern" in C++ is often equated with double dispatch. It uses no RTTI or dynamic_casts.

See also the answers to this question.