MFC Programmer's SourceBook : Thinking in C++
Bruce Eckel's Thinking in C++, 2nd Ed Contents | Prev | Next

Applying double dispatching

The above design is certainly satisfactory. Adding new types to the system consists of adding or modifying distinct classes without causing code changes to be propagated throughout the system. In addition, RTTI is not as “misused” as it was in Recycle1.cpp. However, it’s possible to go one step further and eliminate RTTI altogether from the operation of sorting the trash into bins.

To accomplish this, you must first take the perspective that all type-dependent activities – such as detecting the type of a piece of trash and putting it into the appropriate bin – should be controlled through polymorphism and dynamic binding.

The previous examples first sorted by type, then acted on sequences of elements that were all of a particular type. But whenever you find yourself picking out particular types, stop and think. The whole idea of polymorphism (dynamically-bound member function calls) is to handle type-specific information for you. So why are you hunting for types?

The multiple-dispatch pattern demonstrated at the beginning of this chapter uses virtual functions to determine all type information, thus eliminating RTTI.

Implementing the double dispatch

In the Trash hierarchy we will now make use of the “stub” virtual function addToBin( ) that was added to the base class Trash but unused up until now. This takes an argument of a container of TypedBin. A Trash object uses addToBin( ) with this container to step through and try to add itself to the appropriate bin, and this is where you’ll see the double dispatch.

The new hierarchy is TypedBin, and it contains its own member function called add( ) that is also used polymorphically. But here’s an additional twist: add( ) is overloaded to take arguments of the different types of Trash. So an essential part of the double dispatching scheme also involves overloading (or at least having a group of virtual functions to call; overloading happens to be particularly convenient here).

//: C25:TypedBin.h
#ifndef TYPEDBIN_H
#define TYPEDBIN_H
#include <vector>
#include "Trash.h"
#include "Aluminum.h"
#include "Paper.h"
#include "Glass.h"
#include "Cardboard.h"

// Template to generate double-dispatching
// trash types by inheriting from originals:
template<class TrashType> 
class DD : public TrashType {
protected:
  DD() : TrashType(0) {}
  friend class TrashPrototypeInit;
public:
  DD(double wt) : TrashType(wt) {}
  bool addToBin(std::vector<TypedBin*>& tb) {
    for(int i = 0; i < tb.size(); i++)
      if(tb[i]->add(this))
        return true;
    return false;
  }
  // Override clone() to create this new type:
  Trash* clone(const Trash::Info& info) {
    return new DD(info.data());
  }
};

// vector<Trash*> that knows how to 
// grab the right type
class TypedBin : public std::vector<Trash*> {
protected:
  bool addIt(Trash* t) {
    push_back(t);
    return true;
  }
public:
  virtual bool add(DD<Aluminum>*) {
    return false;
  }
  virtual bool add(DD<Paper>*) {
    return false;
  }
  virtual bool add(DD<Glass>*) {
    return false;
  }
  virtual bool add(DD<Cardboard>*) {
    return false;
  }
};

// Template to generate specific TypedBins:
template<class TrashType>
class BinOf : public TypedBin {
public:
  // Only overrides add() for this specific type:
  bool add(TrashType* t) { return addIt(t); }
};
#endif // TYPEDBIN_H ///:~ 

In each particular subtype of Aluminum, Paper, Glass, and Cardboard, the addToBin( ) member function is implemented, but it looks like the code is exactly the same in each case. The code in each addToBin( ) calls add( ) for each TypedBin object in the array. But notice the argument: this. The type of this is different for each subclass of Trash, so the code is different. So this is the first part of the double dispatch, because once you’re inside this member function you know you’re Aluminum, or Paper, etc. During the call to add( ), this information is passed via the type of this. The compiler resolves the call to the proper overloaded version of add( ). But since tb[i] produces a pointer to the base type TypedBin, this call will end up calling a different member function depending on the type of TypedBin that’s currently selected. That is the second dispatch.

You can see that the overloaded add( ) methods all return false. If the member function is not overloaded in a derived class, it will continue to return false, and the caller ( addToBin( ), in this case) will assume that the current Trash object has not been added successfully to a container, and continue searching for the right container.

In each of the subclasses of TypedBin, only one overloaded member function is overridden, according to the type of bin that’s being created. For example, CardboardBin overrides add(DD<Cardboard>). The overridden member function adds the Trash pointer to its container and returns true, while all the rest of the add( ) methods in CardboardBin continue to return false, since they haven’t been overridden. With C++ templates, you don’t have to explicitly write the subclasses or place the addToBin( ) member function in Trash.

To set up for prototyping the new types of trash, there must be a different initializer file:

//: C25:DDTrashPrototypeInit.cpp {O}
#include "TypedBin.h"
#include "Aluminum.h"
#include "Paper.h"
#include "Glass.h"
#include "Cardboard.h"

std::vector<Trash*> Trash::prototypes;

class TrashPrototypeInit {
  DD<Aluminum> a;
  DD<Paper> p;
  DD<Glass> g;
  DD<Cardboard> c;
  TrashPrototypeInit() {
    Trash::prototypes.push_back(&a);
    Trash::prototypes.push_back(&p);
    Trash::prototypes.push_back(&g);
    Trash::prototypes.push_back(&c);
  }
  static TrashPrototypeInit singleton;
};

TrashPrototypeInit 
  TrashPrototypeInit::singleton; ///:~ 

Here’s the rest of the program:

//: C25:DoubleDispatch.cpp
//{L} DDTrashPrototypeInit
//{L} FillBin Trash TrashStatics
// Using multiple dispatching to handle more than
// one unknown type during a member function call
#include <iostream>
#include <fstream>
#include "TypedBin.h"
#include "fillBin.h"
#include "sumValue.h"
#include "../purge.h"
using namespace std;
ofstream out("DoubleDispatch.out");

class TrashBinSet : public vector<TypedBin*> {
public:
  TrashBinSet() {
    push_back(new BinOf<DD<Aluminum> >());
    push_back(new BinOf<DD<Paper> >());
    push_back(new BinOf<DD<Glass> >());
    push_back(new BinOf<DD<Cardboard> >());
  };
  void sortIntoBins(vector<Trash*>& bin) {
    vector<Trash*>::iterator it;
    for(it = bin.begin(); it != bin.end(); it++)
      // Perform the double dispatch:
      if(!(*it)->addToBin(*this))
        cerr << "Couldn't add " << *it << endl;
  }
  ~TrashBinSet() { purge(*this); }
};

int main() {
  vector<Trash*> bin;
  TrashBinSet bins;
  // fillBin() still works, without changes, but
  // different objects are cloned:
  fillBin("Trash.dat", bin);
  // Sort from the master bin into the
  // individually-typed bins:
  bins.sortIntoBins(bin);
  TrashBinSet::iterator it;
  for(it = bins.begin(); it != bins.end(); it++)
    sumValue(**it);
  // ... and for the master bin
  sumValue(bin);
  purge(bin);
} ///:~ 

TrashBinSet encapsulates all of the different types of TypedBins, along with the sortIntoBins( ) member function, which is where all the double dispatching takes place. You can see that once the structure is set up, sorting into the various TypedBins is remarkably easy. In addition, the efficiency of two virtual calls and the double dispatch is probably better than any other way you could sort.

Notice the ease of use of this system in main( ), as well as the complete independence of any specific type information within main( ). All other methods that talk only to the Trash base-class interface will be equally invulnerable to changes in Trash types.

The changes necessary to add a new type are relatively isolated: you inherit the new type of Trash with its addToBin( ) member function, then make a small modification to TypedBin, and finally you add a new type into the vector in TrashBinSet and modify DDTrashPrototypeInit.cpp.

Contents | Prev | Next


Go to CodeGuru.com
Contact: webmaster@codeguru.com
© Copyright 1997-1999 CodeGuru