Back to Item 30: Proxy classes
Continue to Miscellany

Item 31: Making functions virtual with respect to more than one object.

Sometimes, to borrow a phrase from Jacqueline Susann, once is not enough. Suppose, for example, you're bucking for one of those high-profile, high-prestige, high-paying programming jobs at that famous software company in Redmond, Washington — by which of course I mean Nintendo. To bring yourself to the attention of Nintendo's management, you might decide to write a video game. Such a game might take place in outer space and involve space ships, space stations, and asteroids.

As the ships, stations, and asteroids whiz around in your artificial world, they naturally run the risk of colliding with one another. Let's assume the rules for such collisions are as follows:

- If a ship and a station collide at low velocity, the ship docks at the station. Otherwise the ship and the station sustain damage that's proportional to the speed at which they collide.
- If a ship and a ship or a station and a station collide, both participants in the collision sustain damage that's proportional to the speed at which they hit.
- If a small asteroid collides with a ship or a station, the asteroid is destroyed. If it's a big asteroid, the ship or the station is destroyed.
- If an asteroid collides with another asteroid, both break into pieces and scatter little baby asteroids in all directions.

This may sound like a dull game, but it suffices for our purpose here, which is to consider how to structure the C++ code that handles collisions between objects.

We begin by noting that ships, stations, and asteroids share some common features. If nothing else, they're all in motion, so they all have a velocity that describes that motion. Given this commonality, it is natural to define a base class from which they all inherit. In practice, such a class is almost invariably an abstract base class, and, if you heed the warning I give in Item 33, base classes are always abstract. The hierarchy might therefore look like this:

    class GameObject { ... };

    class SpaceShip: public GameObject { ... };

    class SpaceStation: public GameObject { ... };

    class Asteroid: public GameObject { ... };

Now, suppose you're deep in the bowels of your program, writing the code to check for and handle object collisions. You might come up with a function that looks something like this:

    void checkForCollision(GameObject& object1,
                           GameObject& object2)
    {
      if (theyJustCollided(object1, object2)) {
        processCollision(object1, object2);
      }
      else {
        ...
      }
    }

This is where the programming challenge becomes apparent. When you call `processCollision`, you know that `object1` and `object2` just collided, and you know that what happens in that collision depends on what `object1` really is and what `object2` really is, but you don't know what kinds of objects they really are; all you know is that they're both `GameObject`s. If the collision processing depended only on the dynamic type of `object1`, you could make `processCollision` virtual in `GameObject` and call `object1.processCollision(object2)`. You could do the same thing with `object2` if the details of the collision depended only on its dynamic type. What happens in the collision, however, depends on both their dynamic types. A function call that's virtual on only one object, you see, is not enough.

What you need is a kind of function whose behavior is somehow virtual on the types of more than one object. C++ offers no such function. Nevertheless, you still have to implement the behavior required above. The question, then, is how you are going to do it.

One possibility is to scrap the use of C++ and choose another programming language. You could turn to CLOS, for example, the Common Lisp Object System. CLOS supports what is possibly the most general object-oriented function-invocation mechanism one can imagine: multi-methods. A multi-method is a function that's virtual on as many parameters as you'd like, and CLOS goes even further by giving you substantial control over how calls to overloaded multi-methods are resolved.

Let us assume, however, that you must implement your game in C++ — that you must come up with your own way of implementing what is commonly referred to as double-dispatching. (The name comes from the object-oriented programming community, where what C++ programmers know as a virtual function call is termed a "message dispatch." A call that's virtual on two parameters is implemented through a "double dispatch." The generalization of this — a function acting virtual on several parameters — is called multiple dispatch.) There are several approaches you might consider. None is without its disadvantages, but that shouldn't surprise you. C++ offers no direct support for double-dispatching, so you must yourself do the work compilers do when they implement virtual functions (see Item 24). If that were easy to do, we'd probably all be doing it ourselves and simply programming in C. We aren't and we don't, so fasten your seat belts, it's going to be a bumpy ride.

Using Virtual Functions and RTTI

Virtual functions implement a single dispatch; that's half of what we need; and compilers do virtual functions for us, so we begin by declaring a virtual function `collide` in `GameObject`. This function is overridden in the derived classes in the usual manner:

    class GameObject {
    public:
      virtual void collide(GameObject& otherObject) = 0;
      ...
    };

    class SpaceShip: public GameObject {
    public:
      virtual void collide(GameObject& otherObject);
      ...
    };

Here I'm showing only the derived class `SpaceShip`, but `SpaceStation` and `Asteroid` are handled in exactly the same manner.

The most common approach to double-dispatching returns us to the unforgiving world of virtual function emulation via chains of `if`-`then`-`else`s. In this harsh world, we first discover the real type of `otherObject`, then we test it against all the possibilities:

    // if we collide with an object of unknown type, we
    // throw an exception of this type:
    class CollisionWithUnknownObject {
    public:
      CollisionWithUnknownObject(GameObject& whatWeHit);
      ...
    };

    void SpaceShip::collide(GameObject& otherObject)
    {
      const type_info& objectType = typeid(otherObject);

      if (objectType == typeid(SpaceShip)) {
        SpaceShip& ss = static_cast<SpaceShip&>(otherObject);

        process a SpaceShip-SpaceShip collision;

      }

      else if (objectType == typeid(SpaceStation)) {
        SpaceStation& ss =
          static_cast<SpaceStation&>(otherObject);

        process a SpaceShip-SpaceStation collision;

      }

      else if (objectType == typeid(Asteroid)) {
        Asteroid& a = static_cast<Asteroid&>(otherObject);

        process a SpaceShip-Asteroid collision;

      }

      else {
        throw CollisionWithUnknownObject(otherObject);
      }
    }

Notice how we need to determine the type of only one of the objects involved in the collision. The other object is `*this`, and its type is determined by the virtual function mechanism. We're inside a `SpaceShip` member function, so `*this` must be a `SpaceShip` object. Thus we only have to figure out the real type of `otherObject`.

There's nothing complicated about this code. It's easy to write. It's even easy to make work. That's one of the reasons RTTI is worrisome: it looks harmless. The true danger in this code is hinted at only by the final `else` clause and the exception that's thrown there.

We've pretty much bidden adios to encapsulation, because each `collide` function must be aware of each of its sibling classes, i.e., those classes that inherit from `GameObject`. In particular, if a new type of object — a new class — is added to the game, we must update each RTTI-based `if`-`then`-`else` chain in the program that might encounter the new object type. If we forget even a single one, the program will have a bug, and the bug will not be obvious. Furthermore, compilers are in no position to help us detect such an oversight, because they have no idea what we're doing (see also Item E39).

This kind of type-based programming has a long history in C, and one of the things we know about it is that it yields programs that are essentially unmaintainable. Enhancement of such programs eventually becomes unthinkable. This is the primary reason why virtual functions were invented in the first place: to shift the burden of generating and maintaining type-based function calls from programmers to compilers. When we employ RTTI to implement double-dispatching, we are harking back to the bad old days.

The techniques of the bad old days led to errors in C, and they'll lead to errors in C++, too. In recognition of our human frailty, we've included a final `else` clause in the `collide` function, a clause where control winds up if we hit an object we don't know about. Such a situation is, in principle, impossible, but where were our principles when we decided to use RTTI? There are various ways to handle such unanticipated interactions, but none is very satisfying. In this case, we've chosen to throw an exception, but it's not clear how our callers can hope to handle the error any better than we can, since we've just run into something we didn't know existed.

Using Virtual Functions Only

There is a way to minimize the risks inherent in an RTTI approach to implementing double-dispatching, but before we look at that, it's convenient to see how to attack the problem using nothing but virtual functions. That strategy begins with the same basic structure as the RTTI approach. The `collide` function is declared virtual in `GameObject` and is redefined in each derived class. In addition, `collide` is overloaded in each class, one overloading for each derived class in the hierarchy:

    class SpaceShip;                        // forward declarations
    class SpaceStation;
    class Asteroid;

    class GameObject {
    public:
      virtual void collide(GameObject&      otherObject) = 0;
      virtual void collide(SpaceShip&       otherObject) = 0;
      virtual void collide(SpaceStation&    otherObject) = 0;
      virtual void collide(Asteroid&        otherobject) = 0;
      ...

    };

    class SpaceShip: public GameObject {
    public:
      virtual void collide(GameObject&       otherObject);
      virtual void collide(SpaceShip&        otherObject);
      virtual void collide(SpaceStation&     otherObject);
      virtual void collide(Asteroid&         otherobject);
      ...

    };

The basic idea is to implement double-dispatching as two single dispatches, i.e., as two separate virtual function calls: the first determines the dynamic type of the first object, the second determines that of the second object. As before, the first virtual call is to the `collide` function taking a `GameObject&` parameter. That function's implementation now becomes startlingly simple:

    void SpaceShip::collide(GameObject& otherObject)
    {
      otherObject.collide(*this);
    }

At first glance, this appears to be nothing more than a recursive call to `collide` with the order of the parameters reversed, i.e., with `otherObject` becoming the object calling the member function and `*this` becoming the function's parameter. Glance again, however, because this is not a recursive call. As you know, compilers figure out which of a set of functions to call on the basis of the static types of the arguments passed to the function. In this case, four different `collide` functions could be called, but the one chosen is based on the static type of `*this`. What is that static type? Being inside a member function of the class `SpaceShip`, `*this` must be of type `SpaceShip`. The call is therefore to the `collide` function taking a `SpaceShip&`, not the `collide` function taking a `GameObject&`.

All the `collide` functions are virtual, so the call inside `SpaceShip`::`collide` resolves to the implementation of `collide` corresponding to the real type of `otherObject`. Inside that implementation of `collide`, the real types of both objects are known, because the left-hand object is `*this` (and therefore has as its type the class implementing the member function) and the right-hand object's real type is `SpaceShip`, the same as the declared type of the parameter.

All this may be clearer when you see the implementations of the other `collide` functions in `SpaceShip`:

    void SpaceShip::collide(SpaceShip& otherObject)
    {
      process a SpaceShip-SpaceShip collision;
    }

    void SpaceShip::collide(SpaceStation& otherObject)
    {
      process a SpaceShip-SpaceStation collision;
    }

    void SpaceShip::collide(Asteroid& otherObject)
    {
      process a SpaceShip-Asteroid collision;
    }

As you can see, there's no muss, no fuss, no RTTI, no need to throw exceptions for unexpected object types. There can be no unexpected object types — that's the whole point of using virtual functions. In fact, were it not for its fatal flaw, this would be the perfect solution to the double-dispatching problem.

The flaw is one it shares with the RTTI approach we saw earlier: each class must know about its siblings. As new classes are added, the code must be updated. However, the way in which the code must be updated is different in this case. True, there are no `if`-`then`-`else`s to modify, but there is something that is often worse: each class definition must be amended to include a new virtual function. If, for example, you decide to add a new class `Satellite` (inheriting from `GameObject`) to your game, you'd have to add a new `collide` function to each of the existing classes in the program.

Modifying existing classes is something you are frequently in no position to do. If, instead of writing the entire video game yourself, you started with an off-the-shelf class library comprising a video game application framework, you might not have write access to the `GameObject` class or the framework classes derived from it. In that case, adding new member functions, virtual or otherwise, is not an option. Alternatively, you may have physical access to the classes requiring modification, but you may not have practical access. For example, suppose you were hired by Nintendo and were put to work on programs using a library containing `GameObject` and other useful classes. Surely you wouldn't be the only one using that library, and Nintendo would probably be less than thrilled about recompiling every application using that library each time you decided to add a new type of object to your program. In practice, libraries in wide use are modified only rarely, because the cost of recompiling everything using those libraries is too great. (See Item E34 for information on how to design libraries that minimize compilation dependencies.)

The long and short of it is if you need to implement double-dispatching in your program, your best recourse is to modify your design to eliminate the need. Failing that, the virtual function approach is safer than the RTTI strategy, but it constrains the extensibility of your system to match that of your ability to edit header files. The RTTI approach, on the other hand, makes no recompilation demands, but, if implemented as shown above, it generally leads to software that is unmaintainable. You pays your money and you takes your chances.

Emulating Virtual Function Tables

There is a way to improve those chances. You may recall from Item 24 that compilers typically implement virtual functions by creating an array of function pointers (the vtbl) and then indexing into that array when a virtual function is called. Using a vtbl eliminates the need for compilers to perform chains of `if`-`then`-`else`-like computations, and it allows compilers to generate the same code at all virtual function call sites: determine the correct vtbl index, then call the function pointed to at that position in the vtbl.

There is no reason you can't do this yourself. If you do, you not only make your RTTI-based code more efficient (indexing into an array and following a function pointer is almost always more efficient than running through a series of `if`-`then`-`else` tests, and it generates less code, too), you also isolate the use of RTTI to a single location: the place where your array of function pointers is initialized. I should mention that the meek may inherit the earth, but the meek of heart may wish to take a few deep breaths before reading what follows.

We begin by making some modifications to the functions in the `GameObject` hierarchy:

    class GameObject {
    public:
      virtual void collide(GameObject& otherObject) = 0;
      ...
    };

    class SpaceShip: public GameObject {
    public:
      virtual void collide(GameObject& otherObject);
      virtual void hitSpaceShip(SpaceShip& otherObject);
      virtual void hitSpaceStation(SpaceStation& otherObject);
      virtual void hitAsteroid(Asteroid& otherobject);
      ...
    };

    void SpaceShip::hitSpaceShip(SpaceShip& otherObject)
    {
      process a SpaceShip-SpaceShip collision;
    }

    void SpaceShip::hitSpaceStation(SpaceStation& otherObject)
    {
      process a SpaceShip-SpaceStation collision;
    }

    void SpaceShip::hitAsteroid(Asteroid& otherObject)
    {
      process a SpaceShip-Asteroid collision;
    }

Like the RTTI-based hierarchy we started out with, the `GameObject` class contains only one function for processing collisions, the one that performs the first of the two necessary dispatches. Like the virtual-function-based hierarchy we saw later, each kind of interaction is encapsulated in a separate function, though in this case the functions have different names instead of sharing the name `collide`. There is a reason for this abandonment of overloading, and we shall see it soon. For the time being, note that the design above contains everything we need except an implementation for `SpaceShip`::`collide`; that's where the various `hit` functions will be invoked. As before, once we successfully implement the `SpaceShip` class, the `SpaceStation` and `Asteroid` classes will follow suit.

Inside `SpaceShip`::`collide`, we need a way to map the dynamic type of the parameter `otherObject` to a member function pointer that points to the appropriate collision-handling function. An easy way to do this is to create an associative array that, given a class name, yields the appropriate member function pointer. It's possible to implement `collide` using such an associative array directly, but it's a bit easier to understand what's going on if we add an intervening function, `lookup`, that takes a `GameObject` and returns the appropriate member function pointer. That is, you pass `lookup` a `GameObject`, and it returns a pointer to the member function to call when you collide with something of that `GameObject`'s type.

Here's the declaration of `lookup`:

    class SpaceShip: public GameObject {
    private:
      typedef void (SpaceShip::*HitFunctionPtr)(GameObject&);

      static HitFunctionPtr lookup(const GameObject& whatWeHit);

      ...
    };

The syntax of function pointers is never very pretty, and for member function pointers it's worse than usual, so we've `typedef`ed `HitFunctionPtr` to be shorthand for a pointer to a member function of `SpaceShip` that takes a `GameObject&` and returns nothing.

Once we've got `lookup`, implementation of `collide` becomes the proverbial piece of cake:

    void SpaceShip::collide(GameObject& otherObject)
    {
      HitFunctionPtr hfp =
        lookup(otherObject);                // find the function to call

      if (hfp) {                            // if a function was found
        (this->*hfp)(otherObject);          // call it
      }
      else {
        throw CollisionWithUnknownObject(otherObject);
      }
    }

Provided we've kept the contents of our associative array in sync with the class hierarchy under `GameObject`, `lookup` must always find a valid function pointer for the object we pass it. People are people, however, and mistakes have been known to creep into even the most carefully crafted software systems. That's why we still check to make sure a valid pointer was returned from `lookup`, and that's why we still throw an exception if the impossible occurs and the lookup fails.

All that remains now is the implementation of `lookup`. Given an associative array that maps from object types to member function pointers, the lookup itself is easy, but creating, initializing, and destroying the associative array is an interesting problem of its own.

Such an array should be created and initialized before it's used, and it should be destroyed when it's no longer needed. We could use `new` and `delete` to create and destroy the array manually, but that would be error-prone: how could we guarantee the array wasn't used before we got around to initializing it? A better solution is to have compilers automate the process, and we can do that by making the associative array static in `lookup`. That way it will be created and initialized the first time `lookup` is called, and it will be automatically destroyed sometime after `main` is exited (see Item E47).

Furthermore, we can use the `map` template from the Standard Template Library (see Item 35) as the associative array, because that's what a `map` is:

    class SpaceShip: public GameObject {
    private:
      typedef void (SpaceShip::*HitFunctionPtr)(GameObject&);
      typedef map<string, HitFunctionPtr> HitMap;
      ...
    };

    SpaceShip::HitFunctionPtr
    SpaceShip::lookup(const GameObject& whatWeHit)
    {
      static HitMap collisionMap;
      ...
    }

Here, `collisionMap` is our associative array. It maps the name of a class (as a `string` object) to a `SpaceShip` member function pointer. Because `map<string,` `HitFunctionPtr>` is quite a mouthful, we use a typedef to make it easier to swallow. (For fun, try writing the declaration of `collisionMap` without using the `HitMap` and `HitFunctionPtr` typedefs. Most people will want to do this only once.)

Given `collisionMap`, the implementation of `lookup` is rather anticlimactic. That's because searching for something is an operation directly supported by the `map` class, and the one member function we can always (portably) call on the result of a `typeid` invocation is `name` (which, predictably11, yields the name of the object's dynamic type). To implement `lookup`, then, we just find the entry in `collisionMap` corresponding to the dynamic type of `lookup`'s argument.

The code for `lookup` is straightforward, but if you're not familiar with the Standard Template Library (again, see Item 35), it may not seem that way. Don't worry. The comments in the function explain what's going on.

    SpaceShip::HitFunctionPtr
    SpaceShip::lookup(const GameObject& whatWeHit)
    {
      static HitMap collisionMap;        // we'll see how to
                                         // initialize this below

      // look up the collision-processing function for the type
      // of whatWeHit. The value returned is a pointer-like
      // object called an "iterator" (see Item 35).
      HitMap::iterator mapEntry=
        collisionMap.find(typeid(whatWeHit).name());

      // mapEntry == collisionMap.end() if the lookup failed;
      // this is standard map behavior. Again, see Item 35.
      if (mapEntry == collisionMap.end()) return 0;

      // If we get here, the search succeeded. mapEntry
      // points to a complete map entry, which is a
      // (string, HitFunctionPtr) pair. We want only the
      // second part of the pair, so that's what we return.
      return (*mapEntry).second;
    }

The final statement in the function returns `(*mapEntry).second` instead of the more conventional `mapEntry->second` in order to satisfy the vagaries of the STL. For details, see page 96.

Initializing Emulated Virtual Function Tables

Which brings us to the initialization of `collisionMap`. We'd like to say something like this,

    // An incorrect implementation
    SpaceShip::HitFunctionPtr
    SpaceShip::lookup(const GameObject& whatWeHit)
    {
      static HitMap collisionMap;

      collisionMap["SpaceShip"] = &hitSpaceShip;
      collisionMap["SpaceStation"] = &hitSpaceStation;
      collisionMap["Asteroid"] = &hitAsteroid;

      ...

    }

but this inserts the member function pointers into collisionMap each time `lookup` is called, and that's needlessly inefficient. In addition, this won't compile, but that's a secondary problem we'll address shortly.

What we need now is a way to put the member function pointers into `collisionMap` only once — when `collisionMap` is created. That's easy enough to accomplish; we just write a private static member function called `initializeCollisionMap` to create and initialize our `map`, then we initialize `collisionMap` with `initializeCollisionMap`'s return value:

    class SpaceShip: public GameObject {
    private:
      static HitMap initializeCollisionMap();
      ...

    };

    SpaceShip::HitFunctionPtr
    SpaceShip::lookup(const GameObject& whatWeHit)
    {
      static HitMap collisionMap = initializeCollisionMap();
      ...
    }

But this means we may have to pay the cost of copying the `map` object returned from `initializeCollisionMap` into `collisionMap` (see Items 19 and 20). We'd prefer not to do that. We wouldn't have to pay if `initializeCollisionMap` returned a pointer, but then we'd have to worry about making sure the `map` object the pointer pointed to was destroyed at an appropriate time.

Fortunately, there's a way for us to have it all. We can turn `collisionMap` into a smart pointer (see Item 28) that automatically deletes what it points to when the pointer itself is destroyed. In fact, the standard C++ library contains a template, `auto_ptr`, for just such a smart pointer (see Item 9). By making `collisionMap` a static `auto_ptr` in `lookup`, we can have `initializeCollisionMap` return a pointer to an initialized `map` object, yet never have to worry about a resource leak; the `map` to which `collisionMap` points will be automatically destroyed when `collisionMap` is. Thus:

    class SpaceShip: public GameObject {
    private:
      static HitMap * initializeCollisionMap();

      ...

    };

    SpaceShip::HitFunctionPtr
    SpaceShip::lookup(const GameObject& whatWeHit)
    {
      static auto_ptr<HitMap>
        collisionMap(initializeCollisionMap());
      ...

    }

The clearest way to implement `initializeCollisionMap` would seem to be this,

    SpaceShip::HitMap * SpaceShip::initializeCollisionMap()
    {
      HitMap *phm = new HitMap;

      (*phm)["SpaceShip"] = &hitSpaceShip;
      (*phm)["SpaceStation"] = &hitSpaceStation;
      (*phm)["Asteroid"] = &hitAsteroid;

      return phm;
    }

but as I noted earlier, this won't compile. That's because a `HitMap` is declared to hold pointers to member functions that all take the same type of argument, namely `GameObject`. But `hitSpaceShip` takes a `SpaceShip`, `hitSpaceStation` takes a `SpaceStation`, and, `hitAsteroid` takes an `Asteroid`. Even though `SpaceShip`, `SpaceStation`, and `Asteroid` can all be implicitly converted to `GameObject`, there is no such conversion for pointers to functions taking these argument types.

To placate your compilers, you might be tempted to employ `reinterpret_cast`s (see Item 2), which are generally the casts of choice when converting between function pointer types:

    // A bad idea...
    SpaceShip::HitMap * SpaceShip::initializeCollisionMap()
    {
      HitMap *phm = new HitMap;

      (*phm)["SpaceShip"] =
        reinterpret_cast<HitFunctionPtr>(&hitSpaceShip);

      (*phm)["SpaceStation"] =
        reinterpret_cast<HitFunctionPtr>(&hitSpaceStation);

      (*phm)["Asteroid"] =
        reinterpret_cast<HitFunctionPtr>(&hitAsteroid);

      return phm;
    }

This will compile, but it's a bad idea. It entails doing something you should never do: lying to your compilers. Telling them that `hitSpaceShip`, `hitSpaceStation`, and `hitAsteroid` are functions expecting a `GameObject` argument is simply not true. `hitSpaceShip` expects a `SpaceShip`, `hitSpaceStation` expects a `SpaceStation`, and `hitAsteroid` expects an `Asteroid`. The casts say otherwise. The casts lie.

More than morality is on the line here. Compilers don't like to be lied to, and they often find a way to exact revenge when they discover they've been deceived. In this case, they're likely to get back at you by generating bad code for functions you call through `*phm` in cases where `GameObject`'s derived classes employ multiple inheritance or have virtual base classes. In other words, if `SpaceStation`, `SpaceShip`, or `Asteroid` had other base classes (in addition to `GameObject`), you'd probably find that your calls to collision-processing functions in `collide` would behave quite rudely.

Consider again the A-B-C-D inheritance hierarchy and the possible object layout for a `D` object that is described in Item 24:

Each of the four class parts in a `D` object has a different address. This is important, because even though pointers and references behave differently (see Item 1), compilers typically implement references by using pointers in the generated code. Thus, pass-by-reference is typically implemented by passing a pointer to an object. When an object with multiple base classes (such as a `D` object) is passed by reference, it is crucial that compilers pass the correct address — the one corresponding to the declared type of the parameter in the function being called.

But what if you've lied to your compilers and told them your function expects a `GameObject` when it really expects a `SpaceShip` or a `SpaceStation`? Then they'll pass the wrong address when you call the function, and the resulting runtime carnage will probably be gruesome. It will also be very difficult to determine the cause of the problem. There are good reasons why casting is discouraged. This is one of them.

Okay, so casting is out. Fine. But the type mismatch between the function pointers a `HitMap` is willing to contain and the pointers to the `hitSpaceShip`, `hitSpaceStation`, and `hitAsteroid` functions remains. There is only one way to resolve the conflict: change the types of the functions so they all take `GameObject` arguments:

    class GameObject {                    // this is unchanged
    public:
      virtual void collide(GameObject& otherObject) = 0;
      ...
    };

    class SpaceShip: public GameObject {
    public:
      virtual void collide(GameObject& otherObject);

      // these functions now all take a GameObject parameter
      virtual void hitSpaceShip(GameObject& spaceShip);
      virtual void hitSpaceStation(GameObject& spaceStation);
      virtual void hitAsteroid(GameObject& asteroid);
      ...
    };

Our solution to the double-dispatching problem that was based on virtual functions overloaded the function name `collide`. Now we are in a position to understand why we didn't follow suit here — why we decided to use an associative array of member function pointers instead. All the `hit` functions take the same parameter type, so we must give them different names.

Now we can write `initializeCollisionMap` the way we always wanted to:

    SpaceShip::HitMap * SpaceShip::initializeCollisionMap()
    {
      HitMap *phm = new HitMap;

      (*phm)["SpaceShip"] = &hitSpaceShip;
      (*phm)["SpaceStation"] = &hitSpaceStation;
      (*phm)["Asteroid"] = &hitAsteroid;

      return phm;
    }

Regrettably, our `hit` functions now get a general `GameObject` parameter instead of the derived class parameters they expect. To bring reality into accord with expectation, we must resort to a `dynamic_cast` (see Item 2) at the top of each function:

    void SpaceShip::hitSpaceShip(GameObject& spaceShip)
    {
      SpaceShip& otherShip=
        dynamic_cast<SpaceShip&>(spaceShip);

      process a SpaceShip-SpaceShip collision;

    }

    void SpaceShip::hitSpaceStation(GameObject& spaceStation)
    {
      SpaceStation& station=
        dynamic_cast<SpaceStation&>(spaceStation);

      process a SpaceShip-SpaceStation collision;

    }

    void SpaceShip::hitAsteroid(GameObject& asteroid)
    {
      Asteroid& theAsteroid =
        dynamic_cast<Asteroid&>(asteroid);

      process a SpaceShip-Asteroid collision;

    }

Each of the `dynamic_cast`s will throw a `bad_cast` exception if the cast fails. They should never fail, of course, because the `hit` functions should never be called with incorrect parameter types. Still, we're better off safe than sorry.

Using Non-Member Collision-Processing Functions

We now know how to build a vtbl-like associative array that lets us implement the second half of a double-dispatch, and we know how to encapsulate the details of the associative array inside a lookup function. Because this array contains pointers to member functions, however, we still have to modify class definitions if a new type of `GameObject` is added to the game, and that means everybody has to recompile, even people who don't care about the new type of object. For example, if `Satellite` were added to our game, we'd have to augment the `SpaceShip` class with a declaration of a function to handle collisions between satellites and spaceships. All `SpaceShip` clients would then have to recompile, even if they couldn't care less about the existence of satellites. This is the problem that led us to reject the implementation of double-dispatching based purely on virtual functions, and that solution was a lot less work than the one we've just seen.

The recompilation problem would go away if our associative array contained pointers to non-member functions. Furthermore, switching to non-member collision-processing functions would let us address a design question we have so far ignored, namely, in which class should collisions between objects of different types be handled? With the implementation we just developed, if object 1 and object 2 collide and object 1 happens to be the left-hand argument to `processCollision`, the collision will be handled inside the class for object 1. If object 2 happens to be the left-hand argument to `processCollision`, however, the collision will be handled inside the class for object 2. Does this make sense? Wouldn't it be better to design things so that collisions between objects of types A and B are handled by neither A nor B but instead in some neutral location outside both classes?

If we move the collision-processing functions out of our classes, we can give clients header files that contain class definitions without any `hit` or `collide` functions. We can then structure our implementation file for `processCollision` as follows:

    #include "SpaceShip.h"
    #include "SpaceStation.h"
    #include "Asteroid.h"

    namespace {                     // unnamed namespace — see below

      // primary collision-processing functions
      void shipAsteroid(GameObject& spaceShip,
                        GameObject& asteroid);

      void shipStation(GameObject& spaceShip,
                       GameObject& spaceStation);

      void asteroidStation(GameObject& asteroid,
                           GameObject& spaceStation);
      ...

      // secondary collision-processing functions that just
      // implement symmetry: swap the parameters and call a
      // primary function
      void asteroidShip(GameObject& asteroid,
                        GameObject& spaceShip)
      { shipAsteroid(spaceShip, asteroid); }

      void stationShip(GameObject& spaceStation,
                       GameObject& spaceShip)
      { shipStation(spaceShip, spaceStation); }

      void stationAsteroid(GameObject& spaceStation,
                           GameObject& asteroid)
      { asteroidStation(asteroid, spaceStation); }

      ...

      // see below for a description of these types/functions
      typedef void (*HitFunctionPtr)(GameObject&, GameObject&);
      typedef map< pair<string,string>, HitFunctionPtr > HitMap;

      pair<string,string> makeStringPair(const char *s1,
                                         const char *s2);

      HitMap * initializeCollisionMap();

      HitFunctionPtr lookup(const string& class1,
                            const string& class2);

    } // end namespace

    void processCollision(GameObject& object1,
                            GameObject& object2)
    {
      HitFunctionPtr phf = lookup(typeid(object1).name(),
                                  typeid(object2).name());

      if (phf) phf(object1, object2);
      else throw UnknownCollision(object1, object2);
    }

Note the use of the unnamed namespace to contain the functions used to implement `processCollision`. Everything in such an unnamed namespace is private to the current translation unit (essentially the current file) — it's just like the functions were declared `static` at file scope. With the advent of namespaces, however, statics at file scope have been deprecated, so you should accustom yourself to using unnamed namespaces as soon as your compilers support them.

Conceptually, this implementation is the same as the one that used member functions, but there are some minor differences. First, `HitFunctionPtr` is now a typedef for a pointer to a non-member function. Second, the exception class `CollisionWithUnknownObject` has been renamed `UnknownCollision` and modified to take two objects instead of one. Finally, `lookup` must now take two type names and perform both parts of the double-dispatch. This means our collision map must now hold three pieces of information: two types names and a `HitFunctionPtr`.

As fate would have it, the standard `map` class is defined to hold only two pieces of information. We can finesse that problem by using the standard `pair` template, which lets us bundle the two type names together as a single object. `initializeCollisionMap`, along with its `makeStringPair` helper function, then looks like this:

    // we use this function to create pair<string,string>
    // objects from two char* literals. It's used in
    // initializeCollisionMap below. Note how this function
    // enables the return value optimization (see Item 20).

    namespace {          // unnamed namespace again — see below

      pair<string,string> makeStringPair(const char *s1,
                                         const char *s2)
      { return pair<string,string>(s1, s2);   }

    } // end namespace

    namespace {          // still the unnamed namespace — see below

      HitMap * initializeCollisionMap()
      {
        HitMap *phm = new HitMap;

        (*phm)[makeStringPair("SpaceShip","Asteroid")] =
          &shipAsteroid;

        (*phm)[makeStringPair("SpaceShip", "SpaceStation")] =
          &shipStation;

      ...

      return phm;
    }

    } // end namespace

`lookup` must also be modified to work with the `pair<string, string>` objects that now comprise the first component of the collision map:

    namespace {          // I explain this below — trust me

      HitFunctionPtr lookup(const string& class1,
                            const string& class2)
      {
        static auto_ptr<HitMap>
          collisionMap(initializeCollisionMap());

        // see below for a description of make_pair
        HitMap::iterator mapEntry=
          collisionMap->find(make_pair(class1, class2));

        if (mapEntry == collisionMap->end()) return 0;

        return (*mapEntry).second;
      }

    } // end namespace

This is almost exactly what we had before. The only real difference is the use of the `make_pair` function in this statement:

    HitMap::iterator mapEntry=
      collisionMap->find(make_pair(class1, class2));

`make_pair` is just a convenience function (template) in the standard library (see Item E49 and Item 35) that saves us the trouble of specifying the types when constructing a `pair` object. We could just as well have written the statement like this:

    HitMap::iterator mapEntry=
      collisionMap->find(pair<string,string>(class1, class2));

This calls for more typing, however, and specifying the types for the `pair` is redundant (they're the same as the types of `class1` and `class2`), so the `make_pair` form is more commonly used.

Because `makeStringPair`, `initializeCollisionMap`, and `lookup` were declared inside an unnamed namespace, each must be implemented within the same namespace. That's why the implementations of the functions above are in the unnamed namespace (for the same translation unit as their declarations): so the linker will correctly associate their definitions (i.e., their implementations) with their earlier declarations.

We have finally achieved our goals. If new subclasses of `GameObject` are added to our hierarchy, existing classes need not recompile (unless they wish to use the new classes). We have no tangle of RTTI-based `switch` or `if`-`then`-`else` conditionals to maintain. The addition of new classes to the hierarchy requires only well-defined and localized changes to our system: the addition of one or more map insertions in `initializeCollisionMap` and the declarations of the new collision-processing functions in the unnamed namespace associated with the implementation of `processCollision`. It may have been a lot of work to get here, but at least the trip was worthwhile. Yes? Yes?

Maybe.

Inheritance and Emulated Virtual Function Tables

There is one final problem we must confront. (If, at this point, you are wondering if there will always be one final problem to confront, you have truly come to appreciate the difficulty of designing an implementation mechanism for virtual functions.) Everything we've done will work fine as long as we never need to allow inheritance-based type conversions when calling collision-processing functions. But suppose we develop a game in which we must sometimes distinguish between commercial space ships and military space ships. We could modify our hierarchy as follows, where we've heeded the guidance of Item 33 and made the concrete classes `CommercialShip` and `MilitaryShip` inherit from the newly abstract class `SpaceShip`:

Suppose commercial and military ships behave identically when they collide with something. Then we'd expect to be able to use the same collision-processing functions we had before `CommercialShip` and `MilitaryShip` were added. In particular, if a `MilitaryShip` object and an `Asteroid` collided, we'd expect

    void shipAsteroid(GameObject& spaceShip,
                      GameObject& asteroid);

to be called. It would not be. Instead, an `UnknownCollision` exception would be thrown. That's because `lookup` would be asked to find a function corresponding to the type names "MilitaryShip" and "Asteroid," and no such function would be found in `collisionMap`. Even though a `MilitaryShip` can be treated like a `SpaceShip`, `lookup` has no way of knowing that.

Furthermore, there is no easy way of telling it. If you need to implement double-dispatching and you need to support inheritance-based parameter conversions such as these, your only practical recourse is to fall back on the double-virtual-function-call mechanism we examined earlier. That implies you'll also have to put up with everybody recompiling when you add to your inheritance hierarchy, but that's just the way life is sometimes.

Initializing Emulated Virtual Function Tables (Reprise)

That's really all there is to say about double-dispatching, but it would be unpleasant to end the discussion on such a downbeat note, and unpleasantness is, well, unpleasant. Instead, let's conclude by outlining an alternative approach to initializing `collisionMap`.

As things stand now, our design is entirely static. Once we've registered a function for processing collisions between two types of objects, that's it; we're stuck with that function forever. What if we'd like to add, remove, or change collision-processing functions as the game proceeds? There's no way to do it.

But there can be. We can turn the concept of a map for storing collision-processing functions into a class that offers member functions allowing us to modify the contents of the map dynamically. For example:

    class CollisionMap {
    public:
      typedef void (*HitFunctionPtr)(GameObject&, GameObject&);

      void addEntry(const string& type1,
                    const string& type2,
                    HitFunctionPtr collisionFunction,
                    bool symmetric = true);               // see below

      void removeEntry(const string& type1,
                       const string& type2);

      HitFunctionPtr lookup(const string& type1,
                            const string& type2);

      // this function returns a reference to the one and only
      // map — see Item 26
      static CollisionMap& theCollisionMap();

    private:
      // these functions are private to prevent the creation
      // of multiple maps — see Item 26
      CollisionMap();
      CollisionMap(const CollisionMap&);
    };

This class lets us add entries to the map, remove them from it, and look up the collision-processing function associated with a particular pair of type names. It also uses the techniques of Item 26 to limit the number of `CollisionMap` objects to one, because there is only one map in our system. (More complex games with multiple maps are easy to imagine.) Finally, it allows us to simplify the addition of symmetric collisions to the map (i.e., collisions in which the effect of an object of type T1 hitting an object of type T2 are the same as that of an object of type T2 hitting an object of type T1) by automatically adding the implied map entry when `addEntry` is called with the optional parameter `symmetric` set to `true`.

With the `CollisionMap` class, each client wishing to add an entry to the map does so directly:

    void shipAsteroid(GameObject& spaceShip,
                      GameObject& asteroid);
    CollisionMap::theCollisionMap().addEntry("SpaceShip",
                                             "Asteroid",
                                             &shipAsteroid);

    void shipStation(GameObject& spaceShip,
                     GameObject& spaceStation);
    CollisionMap::theCollisionMap().addEntry("SpaceShip",
                                             "SpaceStation",
                                             &shipStation);

    void asteroidStation(GameObject& asteroid,
                         GameObject& spaceStation);
    CollisionMap::theCollisionMap().addEntry("Asteroid",
                                             "SpaceStation",
                                             &asteroidStation);
    ...

Care must be taken to ensure that these map entries are added to the map before any collisions occur that would call the associated functions. One way to do this would be to have constructors in `GameObject` subclasses check to make sure the appropriate mappings had been added each time an object was created. Such an approach would exact a small performance penalty at runtime. An alternative would be to create a `RegisterCollisionFunction` class:

    class RegisterCollisionFunction {
    public:
      RegisterCollisionFunction(
              const string& type1,
              const string& type2,
              CollisionMap::HitFunctionPtr collisionFunction,
              bool symmetric = true)
      {
        CollisionMap::theCollisionMap().addEntry(type1, type2,
                                                 collisionFunction,
                                                 symmetric);
      }
    };

Clients could then use global objects of this type to automatically register the functions they need:

    RegisterCollisionFunction cf1("SpaceShip", "Asteroid",
                                  &shipAsteroid);

    RegisterCollisionFunction cf2("SpaceShip", "SpaceStation",
                                  &shipStation);

    RegisterCollisionFunction cf3("Asteroid", "SpaceStation",
                                  &asteroidStation);

    ...

    int main(int argc, char * argv[])
    {
      ...
    }

Because these objects are created before `main` is invoked, the functions their constructors register are also added to the map before `main` is called. If, later, a new derived class is added

    class Satellite: public GameObject { ... };

and one or more new collision-processing functions are written,

    void satelliteShip(GameObject& satellite,
                       GameObject& spaceShip);

    void satelliteAsteroid(GameObject& satellite,
                           GameObject& asteroid);

these new functions can be similarly added to the map without disturbing existing code:

    RegisterCollisionFunction cf4("Satellite", "SpaceShip",
                                  &satelliteShip);

    RegisterCollisionFunction cf5("Satellite", "Asteroid",
                                  &satelliteAsteroid);

This doesn't change the fact that there's no perfect way to implement multiple dispatch, but it does make it easy to provide data for a map-based implementation if we decide such an approach is the best match for our needs.

Back to Item 30: Proxy classes
Continue to Miscellany

11 It turns out that it's not so predictable after all. °The C++ standard doesn't specify the return value of `type_info::name`, and different implementations behave differently. (Given a class `SpaceShip`, for example, one implementation's `type_info::name` returns "`class` `SpaceShip`".) A better design would identify a class by the address of its associated `type_info` object, because that is guaranteed to be unique. `HitMap` would then be declared to be of type `map<const type_info*, HitFunctionPtr>`.
Return