Nat is a product architect at CogniToy LLC. He can be contacted at nat@cognitoy.com.
Item 31 of Scott Meyers's book More Effective C++ (Addison-Wesley, 1996) discusses the problem of making a C++ function virtual on more than one of its arguments. To paraphrase Meyers's example: Say you're writing a simple game program set in space, using a collection of polymorphic GameObjects: SpaceShip, SpaceStation, and Asteroid, that move around and sometimes collide. Clearly, it matters a great deal which two objects are colliding. An Asteroid colliding with a SpaceShip might do major damage, whereas a low-speed collision between a SpaceShip and a SpaceStation could be regarded as a successful attempt to dock. So when you discover that two GameObjects are colliding, how should you invoke the appropriate code to process the collision?
Meyers presents—and dismisses—a couple of obvious, but unfortunate, approaches: using the C++ virtual-function machinery on each argument and writing a series of if statements that test runtime type information (RTTI) from typeid(). From a maintenance perspective, each of these is far too similar to the dreaded "Big Switch Statement."
Instead, he suggests the clever technique of initially using typeid(type).name() on each argument type to obtain a distinct string, and building a map<pair<string, string>, function_ptr> to register each processing function. Then, given a pair of actual arguments, Meyers uses typeid(reference).name() on each argument to get the strings with which to perform a map lookup.
He points out that there is a drawback to this technique—it doesn't deal with inheritance. In his example, there's a registered processing function, shipAsteroid(), that expects actual parameters (SpaceShip, Asteroid). If you derive CommercialShip and MilitaryShip from SpaceShip, you might expect that when a MilitaryShip collides with an Asteroid, you'd call shipAsteroid() as before. Alas, it doesn't work that way. "Even though a MilitaryShip can be treated like a SpaceShip," notes Meyers, "lookup() has no way of knowing that. Furthermore, there is no easy way of telling it."
In Modern C++ Design: Generic Programming and Design Patterns Applied (Addison-Wesley, 2001), Andrei Alexandrescu also discusses multiple dispatch. "I am convinced," he writes, "there is a solution to the inheritance problem. But, alas, writers of books have deadlines, too."
I am indebted to both writers for most of what follows. I have found that with a somewhat different container, you can get reasonably good results.
Consider a small class (Listing One) to represent an arbitrary pair of GameObject subclass types. You can define a subclass to represent the types (SpaceShip, Asteroid) as in Listing Two, where you take advantage of dynamic_cast to do the type matching. It's important to work with pointers because dynamic_cast produces a zero pointer if the actual object in question cannot be downcast to the specified pointer type.
When you generalize that subclass (as in Listing Three), you just construct a container of such objects and search that. The important point is that, even for a subclass object myMilitaryShip, dynamic_cast<const SpaceShip*> produces a nonzero pointer. The catch is that this test is ambiguous. You still have the general-purpose processing function shipAsteroid(SpaceShip&, Asteroid&)—but suppose that MilitaryShips get special treatment (maybe they're more heavily armored) and need a special routine such as militaryShipAsteroid(MilitaryShip&, Asteroid&). Every MilitaryShip object actually matches both routines, so this registry can't rely on unique lookup.
The problem resembles catching an exception of a particular type. Suppose you have an Error base class with a subclass ErrorRuntime, which in turn has a subclass ErrorBounds. You could write incorrect code like that in Listing Four where, if dubiousRoutine() throws an ErrorBounds exception, it will not be caught by the ErrorBounds clause. Every ErrorBounds object is an ErrorRuntime as well, so that exception will be caught by the ErrorRuntime clause instead. To distinguish between ErrorBounds and all other ErrorRuntime exceptions, the classes in question must be written like Listing Five.
In the same spirit, you can construct a sequence container (a list) of EntryBase objects and perform a linear search. Invoke the first Entry for which matches() returns true—thus, the burden is on you to populate the list in a reasonable order.
Naturally, you can't just construct a list<EntryBase>: That would slice every Entry subclass object, which is hardly what you want. To be properly polymorphic, your list must store pointers to EntryBase. But that raises uncomfortable questions about the life span of the EntryBase objects: When the list is destroyed, what happens to all of those objects?
This is what smart pointers are all about. std::auto_ptr can't be used in STL containers. But the Boost Library (http://www .boost.org/) provides a couple of varieties of smart pointers, and boost::shared_ptr seems ideal for the job. For convenience, I'll typedef boost::shared_ptr<EntryBase> as EntryPtr.
The container, then, is a list<EntryPtr>; see Listing Six. How will you actually search it? Well, you'll be called with two specific GameObject (subclass) references, as in Listing Seven.
boost::bind() is so cool that it deserves more discussion than I can give it here. For our purposes, the boost::bind() syntax in Listing Seven essentially says: For each item in mDispatch, call matches(param1, param2), and stop when it returns true. boost::bind() automatically handles the fact that the items in mDispatch are smart pointers, as well as the fact that matches() is actually a member function of the referenced class.
Once we've found the right EntryPtr, calling it isn't hard. You must bind some sort of function or function object (called a "functor"); see Listing Eight. Any class with an operator() method accepting two GameObject& parameters works.
Since each Entry subclass already knows its Functor's parameter types, you can also equip it with a virtual method to perform the appropriate downcasting, as in Listing Nine. Therefore, you can provide a function like Listing Ten. This lets you code each Functor using the specific GameObject subclasses that it expects to process. For example, you can write shipAsteroid(SpaceShip&, Asteroid&) rather than shipAsteroid(GameObject&, GameObject&) with internal downcasts.
All that remains is to populate the DispatchTable. You want to provide a function to append new Entry objects to the existing container. Naturally, since this function must instantiate a template class, it must be a template function.
The template function must accept two "types" as well as a Functor. While it should be possible to provide those types as explicit template parameters (for example, add<SpaceShip, Asteroid>(shipAsteroid)), the Microsoft Visual C++ 6 compiler (to name one example) doesn't support that construct.
But you can borrow again from Alexandrescu and wrap these types as lightweight objects:
template<typename T>
struct Type {};
This lets you pass these types to the template function as extra parameters; see Listing Eleven. Then, as both Meyers and Alexandrescu suggest, you can add support for symmetry. Your collision-detection algorithm might turn up a given pair of colliding GameObjects in either order, (SpaceShip, Asteroid) or (Asteroid, SpaceShip). You don't want your collision-processing code to have to be sensitive to that.
Listing Twelve shows an add() function that supports inserting symmetrical Entry objects. This usage of boost::bind() simply reverses the Functor's actual arguments. Having symmetrical entries in the registry lets you write Listing Thirteen without worrying about whether the collision pair was actually detected as (Asteroid, SpaceShip). Both cases are handled by the same code.
I generalized the resulting DoubleDispatch class (available electronically; see "Resource Center," page 7) as a template so that you need not constrain the client to use a specific parameter base class—or a specific return type for the registered functions.
To illustrate how you can use this class, I've included a test program (also available electronically).
The excerpt in Listing Fourteen shows the calls that instantiate and populate the dispatcher, along with some hardcoded test collisions. That program produces the output in Listing Fifteen.
A number of refinements are possible:
- It would be useful to be able to erase() a specific Entry from the DoubleDispatch table. This is relatively straightforward: The Entry template class can capture its parameter types' typeid() values and implement an operator==() method that compares them directly. I wanted to avoid cluttering this discussion with that mechanism, though; the lookup and dispatch code does not depend on typeid() comparisons.
- Not every C++ compiler accepts void as the ReturnType template parameter because of the constructs shown in Listing Sixteen. There's template magic you can use to address that, but for present purposes, it only obscures the code.
- A more serious limitation is the need to register processing functions in a specific order. That implies that all registration calls are made by a central piece of code, which means that adding new GameObject subclasses requires maintaining that code.
I've also built a Java variation on DoubleDispatch (available electronically) where you need not break out EntryBase and Entry: Each Entry simply references the Class objects representing its two parameter types. And given the Class.isAssignableFrom(Class) method, I built an Entry.shouldPrecede(Entry) method that permits DoubleDispatch.add() to search the existing list for a good place to insert the new Entry. So in Java, you can call DoubleDispatch.add() to register new processing routines from many places in your program.
I would like to do the same in C++, but it's hard to compare two Entry template objects constructed at different times. I want to be able to examine the class types embedded in each Entry object to discover inheritance relationships—but I know of no way to do that without actually attempting to instantiate an object of one of the parameter types, which seems like a bad idea.
It's worth noting that Alexandrescu describes template magic that you can use to discover the inheritance relationship between two classes. To do that, however, both class types must be available at the same point in the code. And if you're willing to stipulate that the relevant types must all be available at the same place, then you don't need to extend DoubleDispatch because you can simply write the add() calls in an appropriate order.
DDJ
Listing One
class EntryBase
{
public:
virtual bool matches(const GameObject& param1,
const GameObject& param2) const = 0;
};
Back to Article
Listing Two
class Entry: public EntryBase
{
public:
virtual bool matches(const GameObject& param1,
const GameObject& param2) const
{
return (dynamic_cast<const SpaceShip*>(¶m1) != 0 &&
dynamic_cast<const Asteroid*>(¶m2) != 0);
}
};
Back to Article
Listing Three
template<typename Type1, typename Type2>
class Entry: public EntryBase
{
public:
virtual bool matches(const GameObject& param1,
const GameObject& param2) const
{
return (dynamic_cast<const Type1*>(¶m1) != 0 &&
dynamic_cast<const Type2*>(¶m2) != 0);
}
};
Back to Article
Listing Four
try
{
dubiousRoutine();
}
catch (const ErrorRuntime& e)
{
...
}
catch (const ErrorBounds& e) // whoops, never reached!
{
...
}
catch (const Error& e)
{
...
}
Back to Article
Listing Five
try
{
dubiousRoutine();
}
catch (const ErrorBounds& e) // better
{
...
}
catch (const ErrorRuntime& e)
{
...
}
catch (const Error& e)
{
...
}
Back to Article
Listing Six
typedef boost::shared_ptr<EntryBase> as EntryPtr; typedef std::list<EntryPtr> DispatchTable; DispatchTable mDispatch;Back to Article
Listing Seven
// Look up the first matching entry.
EntryPtr lookup(const GameObject& param1, const GameObject& param2) const
{
DispatchTable::const_iterator found =
std::find_if(mDispatch.begin(), mDispatch.end(),
boost::bind(&EntryBase::matches, _1,
boost::ref(param1), boost::ref(param2)));
if (found != mDispatch.end())
return *found;
return 0;
}
Back to Article
Listing Eight
template<typename Type1, typename Type2, class Functor>
class Entry: public EntryBase
{
// Bind whatever function or function object the instantiator passed.
Functor mFunc;
public:
Entry(Functor func): mFunc(func) {}
virtual bool matches(const GameObject& param1,
const GameObject& param2) const { ... }
};
Back to Article
Listing Nine
class EntryBase
{
public:
...
virtual void operator()(GameObject& param1,
GameObject& param2) const = 0;
};
template<typename Type1, typename Type2, class Functor>
class Entry: public EntryBase
{
Functor mFunc;
public:
Entry(Functor func): mFunc(func) {}
...
virtual void operator()(GameObject& param1,
GameObject& param2) const
{
mFunc(dynamic_cast<Type1&>(param1),
dynamic_cast<Type2&>(param2));
}
};
Back to Article
Listing Ten
void call(GameObject& param1, GameObject& param2) const
{
EntryPtr found = lookup(param1, param2);
if (found.get() == 0)
return;
(*found)(param1, param2); // call the Functor we found
}
Back to Article
Listing Eleven
template<typename Type1, typename Type2, class Functor>
void insert(const Type<Type1>&, const Type<Type2>&, Functor func)
{
mDispatch.insert(mDispatch.end(),
EntryPtr(new Entry<Type1, Type2, Functor>(func)));
}
Back to Article
Listing Twelve
template<typename Type1, typename Type2, class Functor>
void add(const Type<Type1>& t1, const Type<Type2>& t2, Functor func,
bool symmetrical = false)
{
insert(t1, t2, func);
if (symmetrical)
insert(t2, t1, boost::bind(func, _2, _1));
}
Back to Article
Listing Thirteen
void shipAsteroid(SpaceShip& ship, Asteroid& rock)
{
cout << rock.stringize() << " has pulverized " << ship.stringize() << endl;
}
Back to Article
Listing Fourteen
typedef DoubleDispatch<int, GameObject> DD;
DD dispatcher;
dispatcher.add(DD::Type<SpaceShip>(), DD::Type<Asteroid>(),
shipAsteroid, true);
dispatcher.add(DD::Type<SpaceShip>(), DD::Type<SpaceStation>(),
shipStation, true);
dispatcher.add(DD::Type<Asteroid>(), DD::Type<SpaceStation>(),
asteroidStation, true);
// Instantiate a few GameObjects. Make sure we refer to them
// polymorphically, and don't let them leak.
std::auto_ptr<GameObject> home(new SpaceStation("Terra Station"));
std::auto_ptr<GameObject> obstacle(new Asteroid("Ganymede"));
std::auto_ptr<GameObject> tug(new CommercialShip("Pilotfish"));
std::auto_ptr<GameObject> patrol(new MilitaryShip("Enterprise"));
// Try colliding them.
dispatcher(*home, *tug); // reverse params, SpaceShip subclass
dispatcher(*patrol, *home); // forward params, SpaceShip subclass
dispatcher(*obstacle, *home); // forward params
dispatcher(*home, *obstacle); // reverse params
dispatcher(*tug, *obstacle); // forward params, SpaceShip subclass
dispatcher(*obstacle, *patrol); // reverse params, SpaceShip subclass
Back to Article
Listing Fifteen
class CommercialShip Pilotfish has docked at class SpaceStation Terra Station class MilitaryShip Enterprise has docked at class SpaceStation Terra Station class Asteroid Ganymede has damaged class SpaceStation Terra Station class Asteroid Ganymede has damaged class SpaceStation Terra Station class Asteroid Ganymede has pulverized class CommercialShip Pilotfish class Asteroid Ganymede has pulverized class MilitaryShip EnterpriseBack to Article
Listing Sixteen
ReturnType operator()(ParamBaseType& param1, ParamBaseType& param2) const
{
EntryPtr found = lookup(param1, param2);
if (found.get() == 0)
return ReturnType(); // return void() ?!?
return (*found)(param1, param2); //return (value returned by void function)
}
