"The
(B)Leading Edge"
Yet Another Visitor Pattern (part 2)
by
Jack Reeves
©The C++ Report
In my previous column[1] I presented the first installment of my alternate visitor pattern, called the Indirect Visitor. As I noted then, it seemed like a good solution to the problem of the cyclic dependencies that exist with the standard visitor. Nevertheless, it did not go over as well as I had expected with my colleques. They were concerned about the overhead involved in looking up a visit function in a standard map<> class. In this column I am going to present the current version of Indirect Visitor, which has much better performance than the one presented last time. First, I want to wrap up a loose end.
The previous column described the map<> template used to provide a table of visit functions. The typedef used is:
typedef map<const type_info*, VisitFunction, type_comp> FunctionTable;
The map<> key is a pointer to the type_info object which identifies the class that the visit function is suppose to "visit". The comparison object type_comp uses the "before" member function of class type_info. In the column, I made some remark to the effect that I could have just used the default comparison object (less<>) with the type_info pointer, but decided to use the before function because it seemed like that is what is was there for. After the fact, I recalled the real reason I decided to use "before". The problem is that the standard utility template less<> usually just applies the '<' operator to its two parameters. When those parameters are pointers, then operator '<' is the built-in version. As Andy Koenig describes in his Traps and Pitfalls column [2], this operation is undefined on two pointers unless they are both pointing into the same array. On most architectures these days, the default version of less<> works fine, but this is not guaranteed. Andy mentions that on those platforms where less<> can not depend upon operator'<' that vendors will be expected to provide a partial specialization of less<> that does work for pointers.
This is what I meant when I said I could have just used the default comparison object on the const type_info pointers. What I probably should have added was something along the lines of "at least on a Standard C++ implementation that correctly guarantees the behavior of less<> with pointers." For the sake of near term portability, I decided not to depend upon partial specialization, and a library that correctly uses it, but rather to trust the type_info::before function to provide the same capability.
Indirect Visitor -- take 2
After having gotten a less than enthusiastic reception for my new and improved visitor pattern, I went off to sulk -- I mean "think" about the objections that had been raised. The bottom line was that we were building something that was expected to be pretty high performance. Therefore, the general attitude was "why pay the runtime price if you did not have to?"
This is the age old question of computer science (or at least of programming). More often than not, the answer turns out to be that the cost is not that much compared to the benefit. This is the idea behind the Visitor pattern in the first place, and for that matter it pervades the entire realm of patterns and even of object oriented programming in general -- trade a little runtime overhead for a lot of flexibility. Still, I had to admit that things can add up and the sum of all those little costs might get big enough to notice. What I needed was some way to look up a visitor function that had the same overhead as a virtual function call. Typically, virtual functions are called by just indexing into an array of function pointers. I had such an array, it just was an associative array. What I needed was a fixed index instead of a type_info object pointer. There is no such thing provided by the language, but that's Ok, I could make my own.
Listing 1 shows what I added to the top level Node class (GameObject in our example (from Meyer's[3]). First, I added a static const member UID. Every derived class also has to have a UID member. This is the Unique Identifier for the class. Since UID is a const member, it has to be initialized, but cannot then be changed. The protected member function set_uid, is used by all classes to initialize their UID. The public member function total_node_count is used by the Visitor classes to find out how many classes of the GameObject hierarchy are present in the program. The private static member _node_count is used by set_uid and returned by total_node_count. Listing 2 shows how these are implemented in GameObject.C. We don't care what order the different GameObject class UID's get initialized in, we only care that they are initialized before we try to use them. We have to take a little bit of care in that regard, but it is not a major problem.
Now in the Visitors, FunctionTable can just be a vector, instead of the map:
typedef vector<VisitFunction> FunctionTable.
To initialize the FunctionTable, first we fill it with enough null pointers to cover all the possible Node classes:
VisitFunction(0));
Then we treat it just like an array:
_table[Asteroid::UID] = &visit_asteroid;
The look_up function in the GameObject classes becomes equally simple:
Visitor::VisitFunction
game_object::look_up(const Visitor::FunctionTable& table)
{
Visitor::VisitFunction vf = table[UID];
return (vf) ? vf : inherited::look_up(table);
}
With this modification, Indirect Visitor has arrived at the point where its overhead is not significantly greater than the standard Visitor pattern.
Pro's and Con's
I have already mentioned the two biggest advantages of the Indirect Visitor, but it doesn't hurt to mention them again since they are really BIG advantages.
The first is that the Visitor base class is completely uncoupled from the various classes in the Node (i.e. GameObject) hierarchy. New GameObject classes can be added at any time without having to recompile everything. Furthermore, these classes do not have to be added to the base GameObject library, they can be added to other libraries, or to an application itself. All that is necessary to visit these new classes is to add a visit function to the FunctionTable of the visitor that needs to do the visiting.
The second big advantage of Indirect Visitor is provided by the look_up function in each GameObject derived class. It provides support for inheritance, at least within the GameObject hierarchy itself. Since look_up will not fail until it has walked all the way to the top of the tree, this means you can add derived classes all you want and existing visitors will continue to work. It also means that when developing a visitor, you only have to provide functionality at the level where it makes sense.
On top of these advantages, the Indirect Visitor based upon UID's provides O(1) performance. Allow me to illustrate these advantages with a little example. Let us suppose that we have a GameObject hierarchy such as presented in MEC++ and that is uses the Indirect Visitor. Further, assume that the base library provides a concrete visitor called PrintVisitor (which everybody uses for debugging). Listing 3 shows the header for PrintVisitor, while listing 4 shows part of its implementation. Note how the init() function sets up the FunctionTable.
Now, suppose that over time a group of developers (Ann, Bob, and I) all work on different applications that use the GameObject hierarchy. Further suppose that both Ann and Bob find they need to extend the hierarchy. Ann wants to add MilitaryStation, ComercialStation, and ScientificStation (all derived from SpaceStation), while Bob is deriving LargeMilitaryShip and SmallMilitaryShip from the MilitaryShip class. Naturally, they each decide to create a derived version of PrintVisitor that handles their new classes. Listings 5, shows part of Bob's PrintVisitor.
In this case, note that instead of initializing his FunctionTable with null pointers, Bob just copies the base PrintVisitor's table. Then he adds his own functions. This is just faking the inheritance that the compiler ordinarily provides when it builds a virtual function table. Naturally Bob's (and Ann's) visitor has to provide its own version of the virtual visit function. While it looks just like the original version, it makes sure to pass the correct FunctionTable to the GameObject::look_up function.
Finally, let's say I come along and want to use both Ann's and Bob's extensions in my own game application. Just for grins, let's also say I create a new GameObject called SpaceDock which is derived from SpaceStation but which can hold some number of SpaceShip objects. I want to create a PrintVisitor that can handle this entire hierarchy. Just to make it realistic, Ann and Bob's extensions are in libraries that I can not change. Before I go any further, I would like to challenge those of you who like such things to try and provide a solution to this scenario using the original Visitor pattern, but without using virtual inheritance. Don't forget that Ann and Bob created their versions of PrintVisitor for debugging their libraries, not with the intent that somebody would someday want to derive another visitor from them. Please let me know what you come up with, since I couldn't figure out any good solution.
Listings 6 and 7 shows one approach to using multiple inheritance with Indirect Visitor. First, let me acknowledge that if Bob and Ann had the foresight to declare PrintVisitor a virtual base class of their individual print visitor classes, things would be easier. In particular, I would have avoided the need for forwarding functions to be able to get at the individual print visitors. Still, certain things would have been necessary even with virtual inheritance.
In this case, I initialize my FunctionTable from one or the other of the PrintVisitor's. Then I go through both Ann's and Bob's tables and compare them to what is now in my table. If they are the same, I do nothing. If one or the other is different, that indicates that there is an overriding function for that entry. In that slot, I add the appropriate forwarding function. The forwarding functions handle the disambiguation by invoking the correct subvisitor.
Since I have already run over my listing limit, I will put off the discussions of the negatives of the Indirect Visitor until next time. Until then, let me leave you with the famous bleading edge comment: "It works on my machine."
References
2. Andy Koenig, Traps and Pitfalls: Containers and Pointer Comparisons, The C++ Report, Vol. 8, No. 10, Nov/Dec 1996.
3. Scott Meyers, More Effective C++: 35 New Ways to Improve Your Programs and Designs, Addison-Wesley, 1996.
Listing 1
GameObject.h
class GameObject {
public:
. . .
// part of the public interface
static const unsigned int UID;
static const unsigned int total_node_count();
. . .
protected:
// special functions for derived classes
static const unsigned int set_uid();
private:
// static data -- used to set the Uid's
static unsigned int _node_count;
};
Listing 2
GameObject.C
// _node_count;
unsigned int GameObject::_node_count = 1;
// UID
// Every derived class must provide a static const data
// member named UID and initialize it just like this.
const unsigned int GameObject::UID = GameObject::set_uid();
// set_uid
const unsigned int
GameObject::set_uid()
{
return _node_count++;
}
// total_node_count
const unsigned int
GameObject::total_node_count()
{
return _node_count;
}
Listing 3
PrintVisitor.h
#include <ostream>
using std::ostream;
#include "Visitor.h"
class PrintVisitor : public Visitor {
class Impl;
friend class Impl;
// data
ostream& _os;
public:
PrintVisitor(ostream&);
virtual ~PrintVisitor();
protected:
virtual void visit(GameObject& obj;
static const FunctionTable& function_table();
};
Listing 4
PrintVisitor.C
#include "PrintVisitor.h"
struct PrintVisitor::Impl {
// data
static Visitor::FunctionTable _tbl;
// initialization
static void init();
// visit functions
static void visit_asteroid(Visitor&, GameObject&);
static void visit_space_ship(Visitor&, GameObject&);
static void visit_space_station(Visitor&, GameObject&);
};
// Impl static data
Visitor::FunctionTable PrintVisitor::Impl::_tbl;
// Impl::init
void
PrintVisitor::Impl::init()
{
_tbl.assign(GameObject::total_field_count(), VisitFunction(0));
// now add the visit functions
_tbl[Asteroid::UID] = &visit_asteroid;
_tbl[SpaceShip::UID] = &visit_space_ship;
_tbl[SpaceStation::UID] = &visit_space_station;
}
// Impl::visit functions
void
PrintVisitor::Impl::visit_asteroid(Visitor& v, GameObject& o)
{
// print the details of an Asteroid
}
. . . // other visitor functions
Listing 5
BobsPrintVisitor.C
#include "BobsPrintVisitor.h"
struct BobsPrintVisitor::Impl {
// data
static Visitor::FunctionTable _tbl;
// initialization
static void init();
// visit functions
static void visit_large_military_ship(Visitor&, GameObject&);
static void visit_small_military_ship(Visitor&, GameObject&);
};
// Impl static data
Visitor::FunctionTable BobsPrintVisitor::Impl::_tbl;
// Impl::init
void
BobsPrintVisitor::Impl::init()
{
_tbl = PrintVisitor::function_table();
// now add the new visit functions
_tbl[LargeMilitaryShip::UID] = &visit_large_military_ship;
_tbl[SmallMilitaryShip::UID] = &visit_small_military_ship;
}
// Impl::visit functions
. . .
Listing 6
MyPrintVisitor.h
#include <ostream>
using std::ostream;
#include "PrintVisitor.h"
#include "AnnsPrintVisitor.h"
#include "BobsPrintVisitor.h"
class MyPrintVisitor : public AnnsPrintVisitor,
public BobsPrintVisitor {
// data
ostream& _os;
class Impl;
friend class Impl;
public:
MyPrintVisitor(ostream&);
virtual ~MyPrintVisitor();
void operator()(const GameObject*);
protected:
virtual void visit(GameObject& obj;
static const FunctionTable& function_table();
};
inline void
MyPrintVisitor::operator()(const GameObject* obj)
{
if (obj) visit(*const_cast<GameObject*>(obj));
}
Listing 7
MyPrintVisitor.C
#include "MyPrintVisitor.h"
struct MyPrintVisitor::Impl {
// data
static Visitor::FunctionTable _tbl;
// initialization
static void init();
// visit functions
static void visit_space_dock(Visitor&, GameObject&);
static void visit_anns_object(Visitor&, GameObject&);
static void visit_bobs_object(Visitor&, GameObject&);
};
// Impl static data
Visitor::FunctionTable MyPrintVisitor::Impl::_tbl;
// Impl::init
void
MyPrintVisitor::Impl::init()
{
_tbl = BobsPrintVisitor::PrintVisitor::function_table();
// check for overrides
Visitor::FunctionTable& atbl = AnnsPrintVisitor::function_table();
Visitor::FunctionTable& btlb = BobsPrintVisitor::function_table();
for (int i = 0; i < _tbl.size(); ++i) {
if (_tbl[i] == atbl[i] && _tbl[i] == btbl[i]) {
; // do nothing
} else if (_tbl[i] == atbl[i]) {
_tbl[i] = &visit_bobs_object;
} else if (_tbl[i] == btbl[i]) {
_tbl[i] = &visit_anns_object;
} else {
throw logic_error("ambiguous override");
}
}
// add my visit function
_tbl[SpaceDock::UID] = &visit_space_dock;
}
// Impl::visit functions
void
MyPrintVisitor::Impl::visit_space_dock(Visitor& v, GameObject& o)
{
MyPrintVisitor& pv = dynamic_cast<MyPrintVisitor&>(v);
SpaceDock& sdo = dynamic_cast<SpaceDock&>(o);
SpaceDock::iterator it = sdo.begin();
for (it; it != sdo.end(); ++it) {
pv(*it); // visit the object in space dock
}
}
void
MyPrintVisitor::Impl::visit_anns_object(Visitor& v, GameObject& o)
{
MyPrintVisitor& pv = dynamic_cast<MyPrintVisitor&>(v);
pv.AnnsPrintVisitor::visit(o); // try Ann's visitor
}
void
MyPrintVisitor::Impl::visit_bobs_object(Visitor& v, GameObject& o)
{
MyPrintVisitor& pv = dynamic_cast<MyPrintVisitor&>(v);
pv.BobsPrintVisitor::visit(o);
}
// MyPrintVisitor functions -- same as all the others