More Effective C++ | Chapter 5: Techniques Back to Item 24: Understand the costs of virtual functions, multiple inheritance, virtual base classes, and RTTI Continue to Item 25: Virtualizing constructors and non-member functions. Techniques Most of this book is concerned with programming guidelines. Such guidelines are important, but no programmer lives by guidelines alone. According to the old TV show Felix the Cat, "Whenever he gets in a fix, he reaches into his bag of tricks." Well, if a cartoon character can have a bag of tricks, so too can C++ programmers. Think of this chapter as a starter set for your bag of tricks. Some problems crop up repeatedly when designing C++ software. How can you make constructors and non-member functions act like virtual functions? How can you limit the number of instances of a class? How can you prevent objects from being created on the heap? How can you guarantee that they will be created there? How can you create objects that automatically perform some actions anytime some other class's member functions are called? How can you have different objects share data structures while giving clients the illusion that each has its own copy? How can you distinguish between read and write usage of operator[]? How can you create a virtual function whose behavior depends on the dynamic types of more than one object? All these questions (and more) are answered in this chapter, in which I describe proven solutions to problems commonly encountered by C++ programmers. I call such solutions techniques, but they're also known as idioms and, when documented in a stylized fashion, patterns. Regardless of what you call them, the information that follows will serve you well as you engage in the day-to-day skirmishes of practical software development. It should also convince you that no matter what you want to do, there is almost certainly a way to do it in C++. Back to Techniques Continue to Item 26: Limiting the number of objects of a class Item 25: Virtualizing constructors and non-member functions. On the face of it, it doesn't make much sense to talk about "virtual constructors." You call a virtual function to achieve type-specific behavior when you have a pointer or reference to an object but you don't know what the real type of the object is. You call a constructor only when you don't yet have an object but you know exactly what type you'd like to have. How, then, can one talk of virtual constructors? It's easy. Though virtual constructors may seem nonsensical, they are remarkably useful. (If you think nonsensical ideas are never useful, how do you explain the success of modern physics?) For example, suppose you write applications for working with newsletters, where a newsletter consists of components that are either textual or graphical. You might organize things this way: class NLComponent { // abstract base class for public: // newsletter components ... // contains at least one }; // pure virtual function class TextBlock: public NLComponent { public: ... // contains no pure virtual }; // functions class Graphic: public NLComponent { public: ... // contains no pure virtual }; // functions class NewsLetter { // a newsletter object public: // consists of a list of ... // NLComponent objects private: list components; }; The classes relate in this way: The list class used inside NewsLetter is part of the Standard Template Library, which is part of the standard C++ library (see Item E49 and Item 35). Objects of type list behave like doubly linked lists, though they need not be implemented in that way. NewsLetter objects, when not being worked on, would likely be stored on disk. To support the creation of a Newsletter from its on-disk representation, it would be convenient to give NewsLetter a constructor that takes an istream. The constructor would read information from the stream as it created the necessary in-core data structures: class NewsLetter { public: NewsLetter(istream& str); ... Pseudocode for this constructor might look like this, NewsLetter::NewsLetter(istream& str) { while (str) { read the next component object from str; add the object to the list of this newsletter's components; } } or, after moving the tricky stuff into a separate function called readComponent, like this: class NewsLetter { public: ... private: // read the data for the next NLComponent from str, // create the component and return a pointer to it static NLComponent * readComponent(istream& str); ... }; NewsLetter::NewsLetter(istream& str) { while (str) { // add the pointer returned by readComponent to the // end of the components list; "push_back" is a list // member function that inserts at the end of the list components.push_back(readComponent(str)); } } Consider what readComponent does. It creates a new object, either a TextBlock or a Graphic, depending on the data it reads. Because it creates new objects, it acts much like a constructor, but because it can create different types of objects, we call it a virtual constructor. A virtual constructor is a function that creates different types of objects depending on the input it is given. Virtual constructors are useful in many contexts, only one of which is reading object information from disk (or off a network connection or from a tape, etc.). A particular kind of virtual constructor the virtual copy constructor is also widely useful. A virtual copy constructor returns a pointer to a new copy of the object invoking the function. Because of this behavior, virtual copy constructors are typically given names like copySelf, cloneSelf, or, as shown below, just plain clone. Few functions are implemented in a more straightforward manner: class NLComponent { public: // declaration of virtual copy constructor virtual NLComponent * clone() const = 0; ... }; class TextBlock: public NLComponent { public: virtual TextBlock * clone() const // virtual copy { return new TextBlock(*this); } // constructor ... }; class Graphic: public NLComponent { public: virtual Graphic * clone() const // virtual copy { return new Graphic(*this); } // constructor ... }; As you can see, a class's virtual copy constructor just calls its real copy constructor. The meaning of "copy" is hence the same for both functions. If the real copy constructor performs a shallow copy, so does the virtual copy constructor. If the real copy constructor performs a deep copy, so does the virtual copy constructor. If the real copy constructor does something fancy like reference counting or copy-on-write (see Item 29), so does the virtual copy constructor. Consistency what a wonderful thing. Notice that the above implementation takes advantage of a relaxation in the rules for virtual function return types that was adopted relatively recently. No longer must a derived class's redefinition of a base class's virtual function declare the same return type. Instead, if the function's return type is a pointer (or a reference) to a base class, the derived class's function may return a pointer (or reference) to a class derived from that base class. This opens no holes in C++'s type system, and it makes it possible to accurately declare functions such as virtual copy constructors. That's why TextBlock's clone can return a TextBlock* and Graphic's clone can return a Graphic*, even though the return type of NLComponent's clone is NLComponent*. The existence of a virtual copy constructor in NLComponent makes it easy to implement a (normal) copy constructor for NewsLetter: class NewsLetter { public: NewsLetter(const NewsLetter& rhs); ... private: list components; }; NewsLetter::NewsLetter(const NewsLetter& rhs) { // iterate over rhs's list, using each element's // virtual copy constructor to copy the element into // the components list for this object. For details on // how the following code works, see Item 35. for (list::const_iterator it = rhs.components.begin(); it != rhs.components.end(); ++it) { // "it" points to the current element of rhs.components, // so call that element's clone function to get a copy // of the element, and add that copy to the end of // this object's list of components components.push_back((*it)->clone()); } } Unless you are familiar with the Standard Template Library, this code looks bizarre, I know, but the idea is simple: just iterate over the list of components for the NewsLetter object being copied, and for each component in the list, call its virtual copy constructor. We need a virtual copy constructor here, because the list contains pointers to NLComponent objects, but we know each pointer really points to a TextBlock or a Graphic. We want to copy whatever the pointer really points to, and the virtual copy constructor does that for us. Making Non-Member Functions Act Virtual Just as constructors can't really be virtual, neither can non-member functions (see Item E19). However, just as it makes sense to conceive of functions that construct new objects of different types, it makes sense to conceive of non-member functions whose behavior depends on the dynamic types of their parameters. For example, suppose you'd like to implement output operators for the TextBlock and Graphic classes. The obvious approach to this problem is to make the output operator virtual. However, the output operator is operator<<, and that function takes an ostream& as its left-hand argument; that effectively rules out the possibility of making it a member function of the TextBlock or Graphic classes. (It can be done, but then look what happens: class NLComponent { public: // unconventional declaration of output operator virtual ostream& operator<<(ostream& str) const = 0; ... }; class TextBlock: public NLComponent { public: // virtual output operator (also unconventional) virtual ostream& operator<<(ostream& str) const; }; class Graphic: public NLComponent { public: // virtual output operator (still unconventional) virtual ostream& operator<<(ostream& str) const; }; TextBlock t; Graphic g; ... t << cout; // print t on cout via // virtual operator<<; note // unconventional syntax g << cout; // print g on cout via // virtual operator<<; note // unconventional syntax Clients must place the stream object on the right-hand side of the "<<" symbol, and that's contrary to the convention for output operators. To get back to the normal syntax, we must move operator<< out of the TextBlock and Graphic classes, but if we do that, we can no longer declare it virtual.) An alternate approach is to declare a virtual function for printing (e.g., print) and define it for the TextBlock and Graphic classes. But if we do that, the syntax for printing TextBlock and Graphic objects is inconsistent with that for the other types in the language, all of which rely on operator<< as their output operator. Neither of these solutions is very satisfying. What we want is a non-member function called operator<< that exhibits the behavior of a virtual function like print. This description of what we want is in fact very close to a description of how to get it. We define both operator<< and print and have the former call the latter! class NLComponent { public: virtual ostream& print(ostream& s) const = 0; ... }; class TextBlock: public NLComponent { public: virtual ostream& print(ostream& s) const; ... }; class Graphic: public NLComponent { public: virtual ostream& print(ostream& s) const; ... }; inline ostream& operator<<(ostream& s, const NLComponent& c) { return c.print(s); } Virtual-acting non-member functions, then, are easy. You write virtual functions to do the work, then write a non-virtual function that does nothing but call the virtual function. To avoid incurring the cost of a function call for this syntactic sleight-of-hand, of course, you inline the non-virtual function (see Item E33). Now that you know how to make non-member functions act virtually on one of their arguments, you may wonder if it's possible to make them act virtually on more than one of their arguments. It is, but it's not easy. How hard is it? Turn to Item 31; it's devoted to that question. Back to Item 25: Virtualizing constructors and non-member functions Continue to Item 27: Requiring or prohibiting heap-based objects Item 26: Limiting the number of objects of a class. Okay, you're crazy about objects, but sometimes you'd like to bound your insanity. For example, you've got only one printer in your system, so you'd like to somehow limit the number of printer objects to one. Or you've got only 16 file descriptors you can hand out, so you've got to make sure there are never more than that many file descriptor objects in existence. How can you do such things? How can you limit the number of objects? If this were a proof by mathematical induction, we might start with n = 1, then build from there. Fortunately, this is neither a proof nor an induction. Moreover, it turns out to be instructive to begin with n = 0, so we'll start there instead. How do you prevent objects from being instantiated at all? Allowing Zero or One Objects Each time an object is instantiated, we know one thing for sure: a constructor will be called. That being the case, the easiest way to prevent objects of a particular class from being created is to declare the constructors of that class private: class CantBeInstantiated { private: CantBeInstantiated(); CantBeInstantiated(const CantBeInstantiated&); ... }; Having thus removed everybody's right to create objects, we can selectively loosen the restriction. If, for example, we want to create a class for printers, but we also want to abide by the constraint that there is only one printer available to us, we can encapsulate the printer object inside a function so that everybody has access to the printer, but only a single printer object is created: class PrintJob; // forward declaration // see Item E34 class Printer { public: void submitJob(const PrintJob& job); void reset(); void performSelfTest(); ... friend Printer& thePrinter(); private: Printer(); Printer(const Printer& rhs); ... }; Printer& thePrinter() { static Printer p; // the single printer object return p; } There are three separate components to this design. First, the constructors of the Printer class are private. That suppresses object creation. Second, the global function thePrinter is declared a friend of the class. That lets thePrinter escape the restriction imposed by the private constructors. Finally, thePrinter contains a static Printer object. That means only a single object will be created. Client code refers to thePrinter whenever it wishes to interact with the system's lone printer. By returning a reference to a Printer object, thePrinter can be used in any context where a Printer object itself could be: class PrintJob { public: PrintJob(const string& whatToPrint); ... }; string buffer; ... // put stuff in buffer thePrinter().reset(); thePrinter().submitJob(buffer); It's possible, of course, that thePrinter strikes you as a needless addition to the global namespace. "Yes," you may say, "as a global function it looks more like a global variable, but global variables are gauche, and I'd prefer to localize all printer-related functionality inside the Printer class." Well, far be it from me to argue with someone who uses words like gauche. thePrinter can just as easily be made a static member function of Printer, and that puts it right where you want it. It also eliminates the need for a friend declaration, which many regard as tacky in its own right. Using a static member function, Printer looks like this: class Printer { public: static Printer& thePrinter(); ... private: Printer(); Printer(const Printer& rhs); ... }; Printer& Printer::thePrinter() { static Printer p; return p; } Clients must now be a bit wordier when they refer to the printer: Printer::thePrinter().reset(); Printer::thePrinter().submitJob(buffer); Another approach is to move Printer and thePrinter out of the global scope and into a namespace (see Item E28). Namespaces are a recent addition to C++. Anything that can be declared at global scope can also be declared in a namespace. This includes classes, structs, functions, variables, objects, typedefs, etc. The fact that something is in a namespace doesn't affect its behavior, but it does prevent name conflicts between entities in different namespaces. By putting the Printer class and the thePrinter function into a namespace, we don't have to worry about whether anybody else happened to choose the names Printer or thePrinter for themselves; our namespace prevents name conflicts. Syntactically, namespaces look much like classes, but there are no public, protected, or private sections; everything is public. This is how we'd put Printer and thePrinter into a namespace called PrintingStuff: namespace PrintingStuff { class Printer { // this class is in the public: // PrintingStuff namespace void submitJob(const PrintJob& job); void reset(); void performSelfTest(); ... friend Printer& thePrinter(); private: Printer(); Printer(const Printer& rhs); ... }; Printer& thePrinter() // so is this function { static Printer p; return p; } } // this is the end of the // namespace Given this namespace, clients can refer to thePrinter using a fully-qualified name (i.e., one that includes the name of the namespace), PrintingStuff::thePrinter().reset(); PrintingStuff::thePrinter().submitJob(buffer); but they can also employ a using declaration to save themselves keystrokes: using PrintingStuff::thePrinter; // import the name // "thePrinter" from the // namespace "PrintingStuff" // into the current scope thePrinter().reset(); // now thePrinter can be thePrinter().submitJob(buffer); // used as if it were a // local name There are two subtleties in the implementation of thePrinter that are worth exploring. First, it's important that the single Printer object be static in a function and not in a class. An object that's static in a class is, for all intents and purposes, always constructed (and destructed), even if it's never used. In contrast, an object that's static in a function is created the first time through the function, so if the function is never called, the object is never created. (You do, however, pay for a check each time the function is called to see whether the object needs to be created.) One of the philosophical pillars on which C++ was built is the idea that you shouldn't pay for things you don't use, and defining an object like our printer as a static object in a function is one way of adhering to this philosophy. It's a philosophy you should adhere to whenever you can. There is another drawback to making the printer a class static versus a function static, and that has to do with its time of initialization. We know exactly when a function static is initialized: the first time through the function at the point where the static is defined. The situation with a class static (or, for that matter, a global static, should you be so gauche as to use one) is less well defined. C++ offers certain guarantees regarding the order of initialization of statics within a particular translation unit (i.e., a body of source code that yields a single object file), but it says nothing about the initialization order of static objects in different translation units (see Item E47). In practice, this turns out to be a source of countless headaches. Function statics, when they can be made to suffice, allow us to avoid these headaches. In our example here, they can, so why suffer? The second subtlety has to do with the interaction of inlining and static objects inside functions. Look again at the code for the non-member version of thePrinter: Printer& thePrinter() { static Printer p; return p; } Except for the first time through this function (when p must be constructed), this is a one-line function it consists entirely of the statement "return p;". If ever there were a good candidate for inlining, this function would certainly seem to be the one. Yet it's not declared inline. Why not? Consider for a moment why you'd declare an object to be static. It's usually because you want only a single copy of that object, right? Now consider what inline means. Conceptually, it means compilers should replace each call to the function with a copy of the function body, but for non-member functions, it also means something else. It means the functions in question have internal linkage. You don't ordinarily need to worry about such linguistic mumbo jumbo, but there is one thing you must remember: functions with internal linkage may be duplicated within a program (i.e., the object code for the program may contain more than one copy of each function with internal linkage), and this duplication includes static objects contained within the functions. The result? If you create an inline non-member function containing a local static object, you may end up with more than one copy of the static object in your program! So don't create inline non-member functions that contain local static data.9 But maybe you think this business of creating a function to return a reference to a hidden object is the wrong way to go about limiting the number of objects in the first place. Perhaps you think it's better to simply count the number of objects in existence and throw an exception in a constructor if too many objects are requested. In other words, maybe you think we should handle printer creation like this: class Printer { public: class TooManyObjects{}; // exception class for use // when too many objects // are requested Printer(); ~Printer(); ... private: static size_t numObjects; Printer(const Printer& rhs); // there is a limit of 1 // printer, so never allow }; // copying (see Item E27) The idea is to use numObjects to keep track of how many Printer objects are in existence. This value will be incremented in the class constructor and decremented in its destructor. If an attempt is made to construct too many Printer objects, we throw an exception of type TooManyObjects: // Obligatory definition of the class static size_t Printer::numObjects = 0; Printer::Printer() { if (numObjects >= 1) { throw TooManyObjects(); } proceed with normal construction here; ++numObjects; } Printer::~Printer() { perform normal destruction here; --numObjects; } This approach to limiting object creation is attractive for a couple of reasons. For one thing, it's straightforward everybody should be able to understand what's going on. For another, it's easy to generalize so that the maximum number of objects is some number other than one. Contexts for Object Construction There is also a problem with this strategy. Suppose we have a special kind of printer, say, a color printer. The class for such printers would have much in common with our generic printer class, so of course we'd inherit from it: class ColorPrinter: public Printer { ... }; Now suppose we have one generic printer and one color printer in our system: Printer p; ColorPrinter cp; How many Printer objects result from these object definitions? The answer is two: one for p and one for the Printer part of cp. At runtime, a TooManyObjects exception will be thrown during the construction of the base class part of cp. For many programmers, this is neither what they want nor what they expect. (Designs that avoid having concrete classes inherit from other concrete classes do not suffer from this problem. For details on this design philosophy, see Item 33.) A similar problem occurs when Printer objects are contained inside other objects: class CPFMachine { // for machines that can private: // copy, print, and fax Printer p; // for printing capabilities FaxMachine f; // for faxing capabilities CopyMachine c; // for copying capabilities ... }; CPFMachine m1; // fine CPFMachine m2; // throws TooManyObjects exception The problem is that Printer objects can exist in three different contexts: on their own, as base class parts of more derived objects, and embedded inside larger objects. The presence of these different contexts significantly muddies the waters regarding what it means to keep track of the "number of objects in existence," because what you consider to be the existence of an object may not jibe with your compilers'. Often you will be interested only in allowing objects to exist on their own, and you will wish to limit the number of those kinds of instantiations. That restriction is easy to satisfy if you adopt the strategy exemplified by our original Printer class, because the Printer constructors are private, and (in the absence of friend declarations) classes with private constructors can't be used as base classes, nor can they be embedded inside other objects. The fact that you can't derive from classes with private constructors leads to a general scheme for preventing derivation, one that doesn't necessarily have to be coupled with limiting object instantiations. Suppose, for example, you have a class, FSA, for representing finite state automata. (Such state machines are useful in many contexts, among them user interface design.) Further suppose you'd like to allow any number of FSA objects to be created, but you'd also like to ensure that no class ever inherits from FSA. (One reason for doing this might be to justify the presence of a nonvirtual destructor in FSA. Item E14 explains why base classes generally need virtual destructors, and Item 24 explains why classes without virtual functions yield smaller objects than do equivalent classes with virtual functions.) Here's how you can design FSA to satisfy both criteria: class FSA { public: // pseudo-constructors static FSA * makeFSA(); static FSA * makeFSA(const FSA& rhs); ... private: FSA(); FSA(const FSA& rhs); ... }; FSA * FSA::makeFSA() { return new FSA(); } FSA * FSA::makeFSA(const FSA& rhs) { return new FSA(rhs); } Unlike the thePrinter function that always returned a reference to a single object, each makeFSA pseudo-constructor returns a pointer to a unique object. That's what allows an unlimited number of FSA objects to be created. This is nice, but the fact that each pseudo-constructor calls new implies that callers will have to remember to call delete. Otherwise a resource leak will be introduced. Callers who wish to have delete called automatically when the current scope is exited can store the pointer returned from makeFSA in an auto_ptr object (see Item 9); such objects automatically delete what they point to when they themselves go out of scope: // indirectly call default FSA constructor auto_ptr pfsa1(FSA::makeFSA()); // indirectly call FSA copy constructor auto_ptr pfsa2(FSA::makeFSA(*pfsa1)); ... // use pfsa1 and pfsa2 as normal pointers, // but don't worry about deleting them Allowing Objects to Come and Go We now know how to design a class that allows only a single instantiation, we know that keeping track of the number of objects of a particular class is complicated by the fact that object constructors are called in three different contexts, and we know that we can eliminate the confusion surrounding object counts by making constructors private. It is worthwhile to make one final observation. Our use of the thePrinter function to encapsulate access to a single object limits the number of Printer objects to one, but it also limits us to a single Printer object for each run of the program. As a result, it's not possible to write code like this: create Printer object p1; use p1; destroy p1; create Printer object p2; use p2; destroy p2; ... This design never instantiates more than a single Printer object at a time, but it does use different Printer objects in different parts of the program. It somehow seems unreasonable that this isn't allowed. After all, at no point do we violate the constraint that only one printer may exist. Isn't there a way to make this legal? There is. All we have to do is combine the object-counting code we used earlier with the pseudo-constructors we just saw: class Printer { public: class TooManyObjects{}; // pseudo-constructor static Printer * makePrinter(); ~Printer(); void submitJob(const PrintJob& job); void reset(); void performSelfTest(); ... private: static size_t numObjects; Printer(); Printer(const Printer& rhs); // we don't define this }; // function, because we'll // never allow copying // (see Item E27) // Obligatory definition of class static size_t Printer::numObjects = 0; Printer::Printer() { if (numObjects >= 1) { throw TooManyObjects(); } proceed with normal object construction here; ++numObjects; } Printer * Printer::makePrinter() { return new Printer; } If the notion of throwing an exception when too many objects are requested strikes you as unreasonably harsh, you could have the pseudo-constructor return a null pointer instead. Clients would then have to check for this before doing anything with it, of course. Clients use this Printer class just as they would any other class, except they must call the pseudo-constructor function instead of the real constructor: Printer p1; // error! default ctor is // private Printer *p2 = Printer::makePrinter(); // fine, indirectly calls // default ctor Printer p3 = *p2; // error! copy ctor is // private p2->performSelfTest(); // all other functions are p2->reset(); // called as usual ... delete p2; // avoid resource leak; this // would be unnecessary if // p2 were an auto_ptr This technique is easily generalized to any number of objects. All we have to do is replace the hard-wired constant 1 with a class-specific value, then lift the restriction against copying objects. For example, the following revised implementation of our Printer class allows up to 10 Printer objects to exist: class Printer { public: class TooManyObjects{}; // pseudo-constructors static Printer * makePrinter(); static Printer * makePrinter(const Printer& rhs); ... private: static size_t numObjects; static const size_t maxObjects = 10; // see below Printer(); Printer(const Printer& rhs); }; // Obligatory definitions of class statics size_t Printer::numObjects = 0; const size_t Printer::maxObjects; Printer::Printer() { if (numObjects >= maxObjects) { throw TooManyObjects(); } ... } Printer::Printer(const Printer& rhs) { if (numObjects >= maxObjects) { throw TooManyObjects(); } ... } Printer * Printer::makePrinter() { return new Printer; } Printer * Printer::makePrinter(const Printer& rhs) { return new Printer(rhs); } Don't be surprised if your compilers get all upset about the declaration of Printer::maxObjects in the class definition above. In particular, be prepared for them to complain about the specification of 10 as an initial value for that variable. The ability to specify initial values for static const members (of integral type, e.g., ints, chars, enums, etc.) inside a class definition was added to C++ only relatively recently, so some compilers don't yet allow it. If your compilers are as-yet-unupdated, pacify them by declaring maxObjects to be an enumerator inside a private anonymous enum, class Printer { private: enum { maxObjects = 10 }; // within this class, ... // maxObjects is the }; // constant 10 or by initializing the constant static like a non-const static member: class Printer { private: static const size_t maxObjects; // no initial value given ... }; // this goes in a single implementation file const size_t Printer::maxObjects = 10; This latter approach has the same effect as the original code above, but explicitly specifying the initial value is easier for other programmers to understand. When your compilers support the specification of initial values for const static members in class definitions, you should take advantage of that capability. An Object-Counting Base Class Initialization of statics aside, the approach above works like the proverbial charm, but there is one aspect of it that continues to nag. If we had a lot of classes like Printer whose instantiations needed to be limited, we'd have to write this same code over and over, once per class. That would be mind-numbingly dull. Given a fancy-pants language like C++, it somehow seems we should be able to automate the process. Isn't there a way to encapsulate the notion of counting instances and bundle it into a class? We can easily come up with a base class for counting object instances and have classes like Printer inherit from that, but it turns out we can do even better. We can actually come up with a way to encapsulate the whole counting kit and kaboodle, by which I mean not only the functions to manipulate the instance count, but also the instance count itself. (We'll see the need for a similar trick when we examine reference counting in Item 29. For a detailed examination of this design, see my article on counting objects.) The counter in the Printer class is the static variable numObjects, so we need to move that variable into an instance-counting class. However, we also need to make sure that each class for which we're counting instances has a separate counter. Use of a counting class template lets us automatically generate the appropriate number of counters, because we can make the counter a static member of the classes generated from the template: template class Counted { public: class TooManyObjects{}; // for throwing exceptions static int objectCount() { return numObjects; } protected: Counted(); Counted(const Counted& rhs); ~Counted() { --numObjects; } private: static int numObjects; static const size_t maxObjects; void init(); // to avoid ctor code }; // duplication template Counted::Counted() { init(); } template Counted::Counted(const Counted&) { init(); } template void Counted::init() { if (numObjects >= maxObjects) throw TooManyObjects(); ++numObjects; } The classes generated from this template are designed to be used only as base classes, hence the protected constructors and destructor. Note the use of the private member function init to avoid duplicating the statements in the two Counted constructors. We can now modify the Printer class to use the Counted template: class Printer: private Counted { public: // pseudo-constructors static Printer * makePrinter(); static Printer * makePrinter(const Printer& rhs); ~Printer(); void submitJob(const PrintJob& job); void reset(); void performSelfTest(); ... using Counted::objectCount; // see below using Counted::TooManyObjects; // see below private: Printer(); Printer(const Printer& rhs); }; The fact that Printer uses the Counted template to keep track of how many Printer objects exist is, frankly, nobody's business but the author of Printer's. Such implementation details are best kept private, and that's why private inheritance is used here (see Item E42). The alternative would be to use public inheritance between Printer and Counted, but then we'd be obliged to give the Counted classes a virtual destructor. (Otherwise we'd risk incorrect behavior if somebody deleted a Printer object through a Counted* pointer see Item E14.) As Item 24 makes clear, the presence of a virtual function in Counted would almost certainly affect the size and layout of objects of classes inheriting from Counted. We don't want to absorb that overhead, and the use of private inheritance lets us avoid it. Quite properly, most of what Counted does is hidden from Printer's clients, but those clients might reasonably want to find out how many Printer objects exist. The Counted template offers the objectCount function to provide this information, but that function becomes private in Printer due to our use of private inheritance. To restore the public accessibility of that function, we employ a using declaration: class Printer: private Counted { public: ... using Counted::objectCount; // make this function // public for clients ... // of Printer }; This is perfectly legitimate, but if your compilers don't yet support namespaces, they won't allow it. If they don't, you can use the older access declaration syntax: class Printer: private Counted { public: ... Counted::objectCount; // make objectCount // public in Printer ... }; This more traditional syntax has the same meaning as the using declaration, but it's deprecated. The class TooManyObjects is handled in the same fashion as objectCount, because clients of Printer must have access to TooManyObjects if they are to be able to catch exceptions of that type. When Printer inherits from Counted, it can forget about counting objects. The class can be written as if somebody else were doing the counting for it, because somebody else (Counted) is. A Printer constructor now looks like this: Printer::Printer() { proceed with normal object construction; } What's interesting here is not what you see, it's what you don't. No checking of the number of objects to see if the limit is about to be exceeded, no incrementing the number of objects in existence once the constructor is done. All that is now handled by the Counted constructors, and because Counted is a base class of Printer, we know that a Counted constructor will always be called before a Printer constructor. If too many objects are created, a Counted constructor throws an exception, and the Printer constructor won't even be invoked. Nifty, huh? Nifty or not, there's one loose end that demands to be tied, and that's the mandatory definitions of the statics inside Counted. It's easy enough to take care of numObjects we just put this in Counted's implementation file: template // defines numObjects int Counted::numObjects; // and automatically // initializes it to 0 The situation with maxObjects is a bit trickier. To what value should we initialize this variable? If we want to allow up to 10 printers, we should initialize Counted::maxObjects to 10. If, on the other hand, we want to allow up to 16 file descriptor objects, we should initialize Counted::maxObjects to 16. What to do? We take the easy way out: we do nothing. We provide no initialization at all for maxObjects. Instead, we require that clients of the class provide the appropriate initialization. The author of Printer must add this to an implementation file: const size_t Counted::maxObjects = 10; Similarly, the author of FileDescriptor must add this: const size_t Counted::maxObjects = 16; What will happen if these authors forget to provide a suitable definition for maxObjects? Simple: they'll get an error during linking, because maxObjects will be undefined. Provided we've adequately documented this requirement for clients of Counted, they can then say "Duh" to themselves and go back and add the requisite initialization. Back to Item 26: Limiting the number of objects of a class Continue to Item 28: Smart pointers Item 27: Requiring or prohibiting heap-based objects. Sometimes you want to arrange things so that objects of a particular type can commit suicide, i.e., can "delete this." Such an arrangement clearly requires that objects of that type be allocated on the heap. Other times you'll want to bask in the certainty that there can be no memory leaks for a particular class, because none of the objects could have been allocated on the heap. This might be the case if you are working on an embedded system, where memory leaks are especially troublesome and heap space is at a premium. Is it possible to produce code that requires or prohibits heap-based objects? Often it is, but it also turns out that the notion of being "on the heap" is more nebulous than you might think. Requiring Heap-Based Objects Let us begin with the prospect of limiting object creation to the heap. To enforce such a restriction, you've got to find a way to prevent clients from creating objects other than by calling new. This is easy to do. Non-heap objects are automatically constructed at their point of definition and automatically destructed at the end of their lifetime, so it suffices to simply make these implicit constructions and destructions illegal. The straightforward way to make these calls illegal is to declare the constructors and the destructor private. This is overkill. There's no reason why they both need to be private. Better to make the destructor private and the constructors public. Then, in a process that should be familiar from Item 26, you can introduce a privileged pseudo-destructor function that has access to the real destructor. Clients then call the pseudo-destructor to destroy the objects they've created. If, for example, we want to ensure that objects representing unlimited precision numbers are created only on the heap, we can do it like this: class UPNumber { public: UPNumber(); UPNumber(int initValue); UPNumber(double initValue); UPNumber(const UPNumber& rhs); // pseudo-destructor (a const member function, because // even const objects may be destroyed) void destroy() const { delete this; } ... private: ~UPNumber(); }; Clients would then program like this: UPNumber n; // error! (legal here, but // illegal when n's dtor is // later implicitly invoked) UPNumber *p = new UPNumber; // fine ... delete p; // error! attempt to call // private destructor p->destroy(); // fine An alternative is to declare all the constructors private. The drawback to that idea is that a class often has many constructors, and the class's author must remember to declare each of them private. This includes the copy constructor, and it may include a default constructor, too, if these functions would otherwise be generated by compilers; compiler-generated functions are always public (see Item E45). As a result, it's easier to declare only the destructor private, because a class can have only one of those. Restricting access to a class's destructor or its constructors prevents the creation of non-heap objects, but, in a story that is told in Item 26, it also prevents both inheritance and containment: class UPNumber { ... }; // declares dtor or ctors // private class NonNegativeUPNumber: public UPNumber { ... }; // error! dtor or ctors // won't compile class Asset { private: UPNumber value; ... // error! dtor or ctors // won't compile }; Neither of these difficulties is insurmountable. The inheritance problem can be solved by making UPNumber's destructor protected (while keeping its constructors public), and classes that need to contain objects of type UPNumber can be modified to contain pointers to UPNumber objects instead: class UPNumber { ... }; // declares dtor protected class NonNegativeUPNumber: public UPNumber { ... }; // now okay; derived // classes have access to // protected members class Asset { public: Asset(int initValue); ~Asset(); ... private: UPNumber *value; }; Asset::Asset(int initValue) : value(new UPNumber(initValue)) // fine { ... } Asset::~Asset() { value->destroy(); } // also fine Determining Whether an Object is On The Heap If we adopt this strategy, we must reexamine what it means to be "on the heap." Given the class definition sketched above, it's legal to define a non-heap NonNegativeUPNumber object: NonNegativeUPNumber n; // fine Now, the UPNumber part of the NonNegativeUPNumber object n is not on the heap. Is that okay? The answer depends on the details of the class's design and implementation, but let us suppose it is not okay, that all UPNumber objects even base class parts of more derived objects must be on the heap. How can we enforce this restriction? There is no easy way. It is not possible for a UPNumber constructor to determine whether it's being invoked as the base class part of a heap-based object. That is, there is no way for the UPNumber constructor to detect that the following contexts are different: NonNegativeUPNumber *n1 = new NonNegativeUPNumber; // on heap NonNegativeUPNumber n2; // not on heap But perhaps you don't believe me. Perhaps you think you can play games with the interaction among the new operator, operator new and the constructor that the new operator calls (see Item 8). Perhaps you think you can outsmart them all by modifying UPNumber as follows: class UPNumber { public: // exception to throw if a non-heap object is created class HeapConstraintViolation {}; static void * operator new(size_t size); UPNumber(); ... private: static bool onTheHeap; // inside ctors, whether // the object being ... // constructed is on heap }; // obligatory definition of class static bool UPNumber::onTheHeap = false; void *UPNumber::operator new(size_t size) { onTheHeap = true; return ::operator new(size); } UPNumber::UPNumber() { if (!onTheHeap) { throw HeapConstraintViolation(); } proceed with normal construction here; onTheHeap = false; // clear flag for next obj. } There's nothing deep going on here. The idea is to take advantage of the fact that when an object is allocated on the heap, operator new is called to allocate the raw memory, then a constructor is called to initialize an object in that memory. In particular, operator new sets onTheHeap to true, and each constructor checks onTheHeap to see if the raw memory of the object being constructed was allocated by operator new. If not, an exception of type HeapConstraintViolation is thrown. Otherwise, construction proceeds as usual, and when construction is finished, onTheHeap is set to false, thus resetting the default value for the next object to be constructed. This is a nice enough idea, but it won't work. Consider this potential client code: UPNumber *numberArray = new UPNumber[100]; The first problem is that the memory for the array is allocated by operator new[], not operator new, but (provided your compilers support it) you can write the former function as easily as the latter. What is more troublesome is the fact that numberArray has 100 elements, so there will be 100 constructor calls. But there is only one call to allocate memory, so onTheHeap will be set to true for only the first of those 100 constructors. When the second constructor is called, an exception is thrown, and woe is you. Even without arrays, this bit-setting business may fail. Consider this statement: UPNumber *pn = new UPNumber(*new UPNumber); Here we create two UPNumbers on the heap and make pn point to one of them; it's initialized with the value of the second one. This code has a resource leak, but let us ignore that in favor of an examination of what happens during execution of this expression: new UPNumber(*new UPNumber) This contains two calls to the new operator, hence two calls to operator new and two calls to UPNumber constructors (see Item 8). Programmers typically expect these function calls to be executed in this order, Call operator new for first object Call constructor for first object Call operator new for second object Call constructor for second object but the language makes no guarantee that this is how it will be done. Some compilers generate the function calls in this order instead: Call operator new for first object Call operator new for second object Call constructor for first object Call constructor for second object There is nothing wrong with compilers that generate this kind of code, but the set-a-bit-in-operator-new trick fails with such compilers. That's because the bit set in steps 1 and 2 is cleared in step 3, thus making the object constructed in step 4 think it's not on the heap, even though it is. These difficulties don't invalidate the basic idea of having each constructor check to see if *this is on the heap. Rather, they indicate that checking a bit set inside operator new (or operator new[]) is not a reliable way to determine this information. What we need is a better way to figure it out. If you're desperate enough, you might be tempted to descend into the realm of the unportable. For example, you might decide to take advantage of the fact that on many systems, a program's address space is organized as a linear sequence of addresses, with the program's stack growing down from the top of the address space and the heap rising up from the bottom: On systems that organize a program's memory in this way (many do, but many do not), you might think you could use the following function to determine whether a particular address is on the heap: // incorrect attempt to determine whether an address // is on the heap bool onHeap(const void *address) { char onTheStack; // local stack variable return address < &onTheStack; } The thinking behind this function is interesting. Inside onHeap, onTheStack is a local variable. As such, it is, well, it's on the stack. When onHeap is called, its stack frame (i.e., its activation record) will be placed at the top of the program's stack, and because the stack grows down (toward lower addresses) in this architecture, the address of onTheStack must be less than the address of any other stack-based variable or object. If the parameter address is less than the location of onTheStack, it can't be on the stack, so it must be on the heap. Such logic is fine, as far as it goes, but it doesn't go far enough. The fundamental problem is that there are three places where objects may be allocated, not two. Yes, the stack and the heap hold objects, but let us not forget about static objects. Static objects are those that are initialized only once during a program run. Static objects comprise not only those objects explicitly declared static, but also objects at global and namespace scope (see Item E47). Such objects have to go somewhere, and that somewhere is neither the stack nor the heap. Where they go is system-dependent, but on many of the systems that have the stack and heap grow toward one another, they go below the heap. The earlier picture of memory organization, while telling the truth and nothing but the truth for many systems, failed to tell the whole truth for those systems. With static objects added to the picture, it looks like this: Suddenly it becomes clear why onHeap won't work, not even on systems where it's purported to: it fails to distinguish between heap objects and static objects: void allocateSomeObjects() { char *pc = new char; // heap object: onHeap(pc) // will return true char c; // stack object: onHeap(&c) // will return false static char sc; // static object: onHeap(&sc) // will return true ... } Now, you may be desperate for a way to tell heap objects from stack objects, and in your desperation you may be willing to strike a deal with the portability Devil, but are you so desperate that you'll strike a deal that fails to guarantee you the right answers? Surely not, so I know you'll reject this seductive but unreliable compare-the-addresses trick. The sad fact is there's not only no portable way to determine whether an object is on the heap, there isn't even a semi-portable way that works most of the time. If you absolutely, positively have to tell whether an address is on the heap, you're going to have to turn to unportable, implementation-dependent system calls, and that's that. As such, you're better off trying to redesign your software so you don't need to determine whether an object is on the heap in the first place. If you find yourself obsessing over whether an object is on the heap, the likely cause is that you want to know if it's safe to invoke delete on it. Often such deletion will take the form of the infamous "delete this." Knowing whether it's safe to delete a pointer, however, is not the same as simply knowing whether that pointer points to something on the heap, because not all pointers to things on the heap can be safely deleted. Consider again an Asset object that contains a UPNumber object: class Asset { private: UPNumber value; ... }; Asset *pa = new Asset; Clearly *pa (including its member value) is on the heap. Equally clearly, it's not safe to invoke delete on a pointer to pa->value, because no such pointer was ever returned from new. As luck would have it, it's easier to determine whether it's safe to delete a pointer than to determine whether a pointer points to something on the heap, because all we need to answer the former question is a collection of addresses that have been returned by operator new. Since we can write operator new ourselves (see Items E8-E10), it's easy to construct such a collection. Here's how we might approach the problem: void *operator new(size_t size) { void *p = getMemory(size); // call some function to // allocate memory and // handle out-of-memory // conditions add p to the collection of allocated addresses; return p; } void operator delete(void *ptr) { releaseMemory(ptr); // return memory to // free store remove ptr from the collection of allocated addresses; } bool isSafeToDelete(const void *address) { return whether address is in collection of allocated addresses; } This is about as simple as it gets. operator new adds entries to a collection of allocated addresses, operator delete removes entries, and isSafeToDelete does a lookup in the collection to see if a particular address is there. If the operator new and operator delete functions are at global scope, this should work for all types, even the built-ins. In practice, three things are likely to dampen our enthusiasm for this design. The first is our extreme reluctance to define anything at global scope, especially functions with predefined meanings like operator new and operator delete. Knowing as we do that there is but one global scope and but a single version of operator new and operator delete with the "normal" signatures (i.e., sets of parameter types) within that scope (see Item E9), the last thing we want to do is seize those function signatures for ourselves. Doing so would render our software incompatible with any other software that also implements global versions of operator new and operator delete (such as many object-oriented database systems). Our second consideration is one of efficiency: why burden all heap allocations with the bookkeeping overhead necessary to keep track of returned addresses if we don't need to? Our final concern is pedestrian, but important. It turns out to be essentially impossible to implement isSafeToDelete so that it always works. The difficulty has to do with the fact that objects with multiple or virtual base classes have multiple addresses, so there's no guarantee that the address passed to isSafeToDelete is the same as the one returned from operator new, even if the object in question was allocated on the heap. For details, see Items 24 and 31. What we'd like is the functionality provided by these functions without the concomitant pollution of the global namespace, the mandatory overhead, and the correctness problems. Fortunately, C++ gives us exactly what we need in the form of an abstract mixin base class. An abstract base class is a base class that can't be instantiated, i.e., one with at least one pure virtual function. A mixin ("mix in") class is one that provides a single well-defined capability and is designed to be compatible with any other capabilities an inheriting class might provide (see Item E7). Such classes are nearly always abstract. We can therefore come up with an abstract mixin base class that offers derived classes the ability to determine whether a pointer was allocated from operator new. Here's such a class: class HeapTracked { // mixin class; keeps track of public: // ptrs returned from op. new class MissingAddress{}; // exception class; see below virtual ~HeapTracked() = 0; static void *operator new(size_t size); static void operator delete(void *ptr); bool isOnHeap() const; private: typedef const void* RawAddress; static list addresses; }; This class uses the list data structure that's part of the standard C++ library (see Item E49 and Item 35) to keep track of all pointers returned from operator new. That function allocates memory and adds entries to the list; operator delete deallocates memory and removes entries from the list; and isOnHeap returns whether an object's address is in the list. Implementation of the HeapTracked class is simple, because the global operator new and operator delete functions are called to perform the real memory allocation and deallocation, and the list class has functions to make insertion, removal, and lookup single-statement operations. Here's the full implementation of HeapTracked: // mandatory definition of static class member list HeapTracked::addresses; // HeapTracked's destructor is pure virtual to make the // class abstract (see Item E14). The destructor must still // be defined, however, so we provide this empty definition. HeapTracked::~HeapTracked() {} void * HeapTracked::operator new(size_t size) { void *memPtr = ::operator new(size); // get the memory addresses.push_front(memPtr); // put its address at // the front of the list return memPtr; } void HeapTracked::operator delete(void *ptr) { // get an "iterator" that identifies the list // entry containing ptr; see Item 35 for details list::iterator it = find(addresses.begin(), addresses.end(), ptr); if (it != addresses.end()) { // if an entry was found addresses.erase(it); // remove the entry ::operator delete(ptr); // deallocate the memory } else { // otherwise throw MissingAddress(); // ptr wasn't allocated by } // op. new, so throw an } // exception bool HeapTracked::isOnHeap() const { // get a pointer to the beginning of the memory // occupied by *this; see below for details const void *rawAddress = dynamic_cast(this); // look up the pointer in the list of addresses // returned by operator new list::iterator it = find(addresses.begin(), addresses.end(), rawAddress); return it != addresses.end(); // return whether it was } // found This code is straightforward, though it may not look that way if you are unfamiliar with the list class and the other components of the Standard Template Library. Item 35 explains everything, but the comments in the code above should be sufficient to explain what's happening in this example. The only other thing that may confound you is this statement (in isOnHeap): const void *rawAddress = dynamic_cast(this); I mentioned earlier that writing the global function isSafeToDelete is complicated by the fact that objects with multiple or virtual base classes have several addresses. That problem plagues us in isOnHeap, too, but because isOnHeap applies only to HeapTracked objects, we can exploit a special feature of the dynamic_cast operator (see Item 2) to eliminate the problem. Simply put, dynamic_casting a pointer to void* (or const void* or volatile void* or, for those who can't get enough modifiers in their usual diet, const volatile void*) yields a pointer to the beginning of the memory for the object pointed to by the pointer. But dynamic_cast is applicable only to pointers to objects that have at least one virtual function. Our ill-fated isSafeToDelete function had to work with any type of pointer, so dynamic_cast wouldn't help it. isOnHeap is more selective (it tests only pointers to HeapTracked objects), so dynamic_casting this to const void* gives us a pointer to the beginning of the memory for the current object. That's the pointer that HeapTracked::operator new must have returned if the memory for the current object was allocated by HeapTracked::operator new in the first place. Provided your compilers support the dynamic_cast operator, this technique is completely portable. Given this class, even BASIC programmers could add to a class the ability to track pointers to heap allocations. All they'd need to do is have the class inherit from HeapTracked. If, for example, we want to be able to determine whether a pointer to an Asset object points to a heap-based object, we'd modify Asset's class definition to specify HeapTracked as a base class: class Asset: public HeapTracked { private: UPNumber value; ... }; We could then query Asset* pointers as follows: void inventoryAsset(const Asset *ap) { if (ap->isOnHeap()) { ap is a heap-based asset inventory it as such; } else { ap is a non-heap-based asset record it that way; } } A disadvantage of a mixin class like HeapTracked is that it can't be used with the built-in types, because types like int and char can't inherit from anything. Still, the most common reason for wanting to use a class like HeapTracked is to determine whether it's okay to "delete this," and you'll never want to do that with a built-in type because such types have no this pointer. Prohibiting Heap-Based Objects Thus ends our examination of determining whether an object is on the heap. At the opposite end of the spectrum is preventing objects from being allocated on the heap. Here the outlook is a bit brighter. There are, as usual, three cases: objects that are directly instantiated, objects instantiated as base class parts of derived class objects, and objects embedded inside other objects. We'll consider each in turn. Preventing clients from directly instantiating objects on the heap is easy, because such objects are always created by calls to new and you can make it impossible for clients to call new. Now, you can't affect the availability of the new operator (that's built into the language), but you can take advantage of the fact that the new operator always calls operator new (see Item 8), and that function is one you can declare yourself. In particular, it is one you can declare private. If, for example, you want to keep clients from creating UPNumber objects on the heap, you could do it this way: class UPNumber { private: static void *operator new(size_t size); static void operator delete(void *ptr); ... }; Clients can now do only what they're supposed to be able to do: UPNumber n1; // okay static UPNumber n2; // also okay UPNumber *p = new UPNumber; // error! attempt to call // private operator new It suffices to declare operator new private, but it looks strange to have operator new be private and operator delete be public, so unless there's a compelling reason to split up the pair, it's best to declare them in the same part of a class. If you'd like to prohibit heap-based arrays of UPNumber objects, too, you could declare operator new[] and operator delete[] (see Item 8) private as well. (The bond between operator new and operator delete is stronger than many people think. For information on a rarely-understood aspect of their relationship, turn to the sidebar in my article on counting objects.) Interestingly, declaring operator new private often also prevents UPNumber objects from being instantiated as base class parts of heap-based derived class objects. That's because operator new and operator delete are inherited, so if these functions aren't declared public in a derived class, that class inherits the private versions declared in its base(s): class UPNumber { ... }; // as above class NonNegativeUPNumber: // assume this class public UPNumber { // declares no operator new ... }; NonNegativeUPNumber n1; // okay static NonNegativeUPNumber n2; // also okay NonNegativeUPNumber *p = // error! attempt to call new NonNegativeUPNumber; // private operator new If the derived class declares an operator new of its own, that function will be called when allocating derived class objects on the heap, and a different way will have to be found to prevent UPNumber base class parts from winding up there. Similarly, the fact that UPNumber's operator new is private has no effect on attempts to allocate objects containing UPNumber objects as members: class Asset { public: Asset(int initValue); ... private: UPNumber value; }; Asset *pa = new Asset(100); // fine, calls // Asset::operator new or // ::operator new, not // UPNumber::operator new For all practical purposes, this brings us back to where we were when we wanted to throw an exception in the UPNumber constructors if a UPNumber object was being constructed in memory that wasn't on the heap. This time, of course, we want to throw an exception if the object in question is on the heap. Just as there is no portable way to determine if an address is on the heap, however, there is no portable way to determine that it is not on the heap, so we're out of luck. This should be no surprise. After all, if we could tell when an address is on the heap, we could surely tell when an address is not on the heap. But we can't, so we can't. Oh well. Back to Item 27: Requiring or prohibiting heap-based objects Continue to Item 29: Reference counting Item 28: Smart pointers. Smart pointers are objects that are designed to look, act, and feel like built-in pointers, but to offer greater functionality. They have a variety of applications, including resource management (see Items 9, 10, 25, and 31) and the automation of repetitive coding tasks (see Items 17 and 29). When you use smart pointers in place of C++'s built-in pointers (i.e., dumb pointers), you gain control over the following aspects of pointer behavior: Construction and destruction. You determine what happens when a smart pointer is created and destroyed. It is common to give smart pointers a default value of 0 to avoid the headaches associated with uninitialized pointers. Some smart pointers are made responsible for deleting the object they point to when the last smart pointer pointing to the object is destroyed. This can go a long way toward eliminating resource leaks. Copying and assignment. You control what happens when a smart pointer is copied or is involved in an assignment. For some smart pointer types, the desired behavior is to automatically copy or make an assignment to what is pointed to, i.e., to perform a deep copy. For others, only the pointer itself should be copied or assigned. For still others, these operations should not be allowed at all. Regardless of what behavior you consider "right," the use of smart pointers lets you call the shots. Dereferencing. What should happen when a client refers to the object pointed to by a smart pointer? You get to decide. You could, for example, use smart pointers to help implement the lazy fetching strategy outlined in Item 17. Smart pointers are generated from templates because, like built-in pointers, they must be strongly typed; the template parameter specifies the type of object pointed to. Most smart pointer templates look something like this: template // template for smart class SmartPtr { // pointer objects public: SmartPtr(T* realPtr = 0); // create a smart ptr to an // obj given a dumb ptr to // it; uninitialized ptrs // default to 0 (null) SmartPtr(const SmartPtr& rhs); // copy a smart ptr ~SmartPtr(); // destroy a smart ptr // make an assignment to a smart ptr SmartPtr& operator=(const SmartPtr& rhs); T* operator->() const; // dereference a smart ptr // to get at a member of // what it points to T& operator*() const; // dereference a smart ptr private: T *pointee; // what the smart ptr }; // points to The copy constructor and assignment operator are both shown public here. For smart pointer classes where copying and assignment are not allowed, they would typically be declared private (see Item E27). The two dereferencing operators are declared const, because dereferencing a pointer doesn't modify it (though it may lead to modification of what the pointer points to). Finally, each smart pointer-to-T object is implemented by containing a dumb pointer-to-T within it. It is this dumb pointer that does the actual pointing. Before going into the details of smart pointer implementation, it's worth seeing how clients might use smart pointers. Consider a distributed system in which some objects are local and some are remote. Access to local objects is generally simpler and faster than access to remote objects, because remote access may require remote procedure calls or some other way of communicating with a distant machine. For clients writing application code, the need to handle local and remote objects differently is a nuisance. It is more convenient to have all objects appear to be located in the same place. Smart pointers allow a library to offer this illusion: template // template for smart ptrs class DBPtr { // to objects in a public: // distributed DB DBPtr(T *realPtr = 0); // create a smart ptr to a // DB object given a local // dumb pointer to it DBPtr(DataBaseID id); // create a smart ptr to a // DB object given its // unique DB identifier ... // other smart ptr }; // functions as above class Tuple { // class for database public: // tuples ... void displayEditDialog(); // present a graphical // dialog box allowing a // user to edit the tuple bool isValid() const; // return whether *this }; // passes validity check // class template for making log entries whenever a T // object is modified; see below for details template class LogEntry { public: LogEntry(const T& objectToBeModified); ~LogEntry(); }; void editTuple(DBPtr& pt) { LogEntry entry(*pt); // make log entry for this // editing operation; see // below for details // repeatedly display edit dialog until valid values // are provided do { pt->displayEditDialog(); } while (pt->isValid() == false); } The tuple to be edited inside editTuple may be physically located on a remote machine, but the programmer writing editTuple need not be concerned with such matters; the smart pointer class hides that aspect of the system. As far as the programmer is concerned, all tuples are accessed through objects that, except for how they're declared, act just like run-of-the-mill built-in pointers. Notice the use of a LogEntry object in editTuple. A more conventional design would have been to surround the call to displayEditDialog with calls to begin and end the log entry. In the approach shown here, the LogEntry's constructor begins the log entry and its destructor ends the log entry. As Item 9 explains, using an object to begin and end logging is more robust in the face of exceptions than explicitly calling functions, so you should accustom yourself to using classes like LogEntry. Besides, it's easier to create a single LogEntry object than to add separate calls to start and stop an entry. As you can see, using a smart pointer isn't much different from using the dumb pointer it replaces. That's testimony to the effectiveness of encapsulation. Clients of smart pointers are supposed to be able to treat them as dumb pointers. As we shall see, sometimes the substitution is more transparent than others. Construction, Assignment, and Destruction of Smart Pointers Construction of a smart pointer is usually straightforward: locate an object to point to (typically by using the smart pointer's constructor arguments), then make the smart pointer's internal dumb pointer point there. If no object can be located, set the internal pointer to 0 or signal an error (possibly by throwing an exception). Implementing a smart pointer's copy constructor, assignment operator(s) and destructor is complicated somewhat by the issue of ownership. If a smart pointer owns the object it points to, it is responsible for deleting that object when it (the smart pointer) is destroyed. This assumes the object pointed to by the smart pointer is dynamically allocated. Such an assumption is common when working with smart pointers. (For ideas on how to make sure the assumption is true, see Item 27.) Consider the auto_ptr template from the standard C++ library. As Item 9 explains, an auto_ptr object is a smart pointer that points to a heap-based object until it (the auto_ptr) is destroyed. When that happens, the auto_ptr's destructor deletes the pointed-to object. The auto_ptr template might be implemented like this: template class auto_ptr { public: auto_ptr(T *ptr = 0): pointee(ptr) {} ~auto_ptr() { delete pointee; } ... private: T *pointee; }; This works fine provided only one auto_ptr owns an object. But what should happen when an auto_ptr is copied or assigned? auto_ptr ptn1(new TreeNode); auto_ptr ptn2 = ptn1; // call to copy ctor; // what should happen? auto_ptr ptn3; ptn3 = ptn2; // call to operator=; // what should happen? If we just copied the internal dumb pointer, we'd end up with two auto_ptrs pointing to the same object. This would lead to grief, because each auto_ptr would delete what it pointed to when the auto_ptr was destroyed. That would mean we'd delete an object more than once. The results of such double-deletes are undefined (and are frequently disastrous). An alternative would be to create a new copy of what was pointed to by calling new. That would guarantee we didn't have too many auto_ptrs pointing to a single object, but it might engender an unacceptable performance hit for the creation (and later destruction) of the new object. Furthermore, we wouldn't necessarily know what type of object to create, because an auto_ptr object need not point to an object of type T; it might point to an object of a type derived from T. Virtual constructors (see Item 25) can help solve this problem, but it seems inappropriate to require their use in a general-purpose class like auto_ptr. The problems would vanish if auto_ptr prohibited copying and assignment, but a more flexible solution was adopted for the auto_ptr classes: object ownership is transferred when an auto_ptr is copied or assigned: template class auto_ptr { public: ... auto_ptr(auto_ptr& rhs); // copy constructor auto_ptr& // assignment operator=(auto_ptr& rhs); // operator ... }; template auto_ptr::auto_ptr(auto_ptr& rhs) { pointee = rhs.pointee; // transfer ownership of // *pointee to *this rhs.pointee = 0; // rhs no longer owns } // anything template auto_ptr& auto_ptr::operator=(auto_ptr& rhs) { if (this == &rhs) // do nothing if this return *this; // object is being assigned // to itself delete pointee; // delete currently owned // object pointee = rhs.pointee; // transfer ownership of rhs.pointee = 0; // *pointee from rhs to *this return *this; } Notice that the assignment operator must delete the object it owns before assuming ownership of a new object. If it failed to do this, the object would never be deleted. Remember, nobody but the auto_ptr object owns the object the auto_ptr points to. Because object ownership is transferred when auto_ptr's copy constructor is called, passing auto_ptrs by value is often a very bad idea. Here's why: // this function will often lead to disaster void printTreeNode(ostream& s, auto_ptr p) { s << *p; } int main() { auto_ptr ptn(new TreeNode); ... printTreeNode(cout, ptn); // pass auto_ptr by value ... } When printTreeNode's parameter p is initialized (by calling auto_ptr's copy constructor), ownership of the object pointed to by ptn is transferred to p. When printTreeNode finishes executing, p goes out of scope and its destructor deletes what it points to (which is what ptn used to point to). ptn, however, no longer points to anything (its underlying dumb pointer is null), so just about any attempt to use it after the call to printTreeNode will yield undefined behavior. Passing auto_ptrs by value, then, is something to be done only if you're sure you want to transfer ownership of an object to a (transient) function parameter. Only rarely will you want to do this. This doesn't mean you can't pass auto_ptrs as parameters, it just means that pass-by-value is not the way to do it. Pass-by-reference-to-const is: // this function behaves much more intuitively void printTreeNode(ostream& s, const auto_ptr& p) { s << *p; } In this function, p is a reference, not an object, so no constructor is called to initialize p. When ptn is passed to this version of printTreeNode, it retains ownership of the object it points to, and ptn can safely be used after the call to printTreeNode. Thus, passing auto_ptrs by reference-to-const avoids the hazards arising from pass-by-value. (For other reasons to prefer pass-by-reference to pass-by-value, check out Item E22.) The notion of transferring ownership from one smart pointer to another during copying and assignment is interesting, but you may have been at least as interested in the unconventional declarations of the copy constructor and assignment operator. These functions normally take const parameters, but above they do not. In fact, the code above changes these parameters during the copy or the assignment. In other words, auto_ptr objects are modified if they are copied or are the source of an assignment! Yes, that's exactly what's happening. Isn't it nice that C++ is flexible enough to let you do this? If the language required that copy constructors and assignment operators take const parameters, you'd probably have to cast away the parameters' constness (see Item E21) or play other games to implement ownership transferral. Instead, you get to say exactly what you want to say: when an object is copied or is the source of an assignment, that object is changed. This may not seem intuitive, but it's simple, direct, and, in this case, accurate. If you find this examination of auto_ptr member functions interesting, you may wish to see a complete implementation. You'll find one on pages 291-294, where you'll also see that the auto_ptr template in the standard C++ library has copy constructors and assignment operators that are more flexible than those described here. In the standard auto_ptr template, those functions are member function templates, not just member functions. (Member function templates are described later in this Item. You can also read about them in Item E25.) A smart pointer's destructor often looks like this: template SmartPtr::~SmartPtr() { if (*this owns *pointee) { delete pointee; } } Sometimes there is no need for the test. An auto_ptr always owns what it points to, for example. At other times the test is a bit more complicated. A smart pointer that employs reference counting (see Item 29) must adjust a reference count before determining whether it has the right to delete what it points to. Of course, some smart pointers are like dumb pointers: they have no effect on the object they point to when they themselves are destroyed. Implementing the Dereferencing Operators Let us now turn our attention to the very heart of smart pointers, the operator* and operator-> functions. The former returns the object pointed to. Conceptually, this is simple: template T& SmartPtr::operator*() const { perform "smart pointer" processing; return *pointee; } First the function does whatever processing is needed to initialize or otherwise make pointee valid. For example, if lazy fetching is being used (see Item 17), the function may have to conjure up a new object for pointee to point to. Once pointee is valid, the operator* function just returns a reference to the pointed-to object. Note that the return type is a reference. It would be disastrous to return an object instead, though compilers will let you do it. Bear in mind that pointee need not point to an object of type T; it may point to an object of a class derived from T. If that is the case and your operator* function returns a T object instead of a reference to the actual derived class object, your function will return an object of the wrong type! (This is the slicing problem. See Item E22 and Item 13.) Virtual functions invoked on the object returned from your star-crossed operator* will not invoke the function corresponding to the dynamic type of the pointed-to object. In essence, your smart pointer will not properly support virtual functions, and how smart is a pointer like that? Besides, returning a reference is more efficient anyway, because there is no need to construct a temporary object (see Item 19). This is one of those happy occasions when correctness and efficiency go hand in hand. If you're the kind who likes to worry, you may wonder what you should do if somebody invokes operator* on a null smart pointer, i.e., one whose embedded dumb pointer is null. Relax. You can do anything you want. The result of dereferencing a null pointer is undefined, so there is no "wrong" behavior. Wanna throw an exception? Go ahead, throw it. Wanna call abort (possibly by having an assert call fail)? Fine, call it. Wanna walk through memory setting every byte to your birth date modulo 256? That's okay, too. It's not nice, but as far as the language is concerned, you are completely unfettered. The story with operator-> is similar to that for operator*, but before examining operator->, let us remind ourselves of the unusual meaning of a call to this function. Consider again the editTuple function that uses a smart pointer-to-Tuple object: void editTuple(DBPtr& pt) { LogEntry entry(*pt); do { pt->displayEditDialog(); } while (pt->isValid() == false); } The statement pt->displayEditDialog(); is interpreted by compilers as: (pt.operator->())->displayEditDialog(); That means that whatever operator-> returns, it must be legal to apply the member-selection operator (->) to it. There are thus only two things operator-> can return: a dumb pointer to an object or another smart pointer object. Most of the time, you'll want to return an ordinary dumb pointer. In those cases, you implement operator-> as follows: template T* SmartPtr::operator->() const { perform "smart pointer" processing; return pointee; } This will work fine. Because this function returns a pointer, virtual function calls via operator-> will behave the way they're supposed to. For many applications, this is all you need to know about smart pointers. The reference-counting code of Item 29, for example, draws on no more functionality than we've discussed here. If you want to push your smart pointers further, however, you must know more about dumb pointer behavior and how smart pointers can and cannot emulate it. If your motto is "Most people stop at the Z but not me!", the material that follows is for you. Testing Smart Pointers for Nullness With the functions we have discussed so far, we can create, destroy, copy, assign, and dereference smart pointers. One of the things we cannot do, however, is find out if a smart pointer is null: SmartPtr ptn; ... if (ptn == 0) ... // error! if (ptn) ... // error! if (!ptn) ... // error! This is a serious limitation. It would be easy to add an isNull member function to our smart pointer classes, but that wouldn't address the problem that smart pointers don't act like dumb pointers when testing for nullness. A different approach is to provide an implicit conversion operator that allows the tests above to compile. The conversion traditionally employed for this purpose is to void*: template class SmartPtr { public: ... operator void*(); // returns 0 if the smart ... // ptr is null, nonzero }; // otherwise SmartPtr ptn; ... if (ptn == 0) ... // now fine if (ptn) ... // also fine if (!ptn) ... // fine This is similar to a conversion provided by the iostream classes, and it explains why it's possible to write code like this: ifstream inputFile("datafile.dat"); if (inputFile) ... // test to see if inputFile // was successfully // opened Like all type conversion functions, this one has the drawback of letting function calls succeed that most programmers would expect to fail (see Item 5). In particular, it allows comparisons of smart pointers of completely different types: SmartPtr pa; SmartPtr po; ... if (pa == po) ... // this compiles! Even if there is no operator== taking a SmartPtr and a SmartPtr, this compiles, because both smart pointers can be implicitly converted into void* pointers, and there is a built-in comparison function for built-in pointers. This kind of behavior makes implicit conversion functions dangerous. (Again, see Item 5, and keep seeing it over and over until you can see it in the dark.) There are variations on the conversion-to-void* motif. Some designers advocate conversion to const void*, others embrace conversion to bool. Neither of these variations eliminates the problem of allowing mixed-type comparisons. There is a middle ground that allows you to offer a reasonable syntactic form for testing for nullness while minimizing the chances of accidentally comparing smart pointers of different types. It is to overload operator! for your smart pointer classes so that operator! returns true if and only if the smart pointer on which it's invoked is null: template class SmartPtr { public: ... bool operator!() const; // returns true if and only ... // if the smart ptr is null }; This lets your clients program like this, SmartPtr ptn; ... if (!ptn) { // fine ... // ptn is null } else { ... // ptn is not null } but not like this: if (ptn == 0) ... // still an error if (ptn) ... // also an error The only risk for mixed-type comparisons is statements such as these: SmartPtr pa; SmartPtr po; ... if (!pa == !po) ... // alas, this compiles Fortunately, programmers don't write code like this very often. Interestingly, iostream library implementations provide an operator! in addition to the implicit conversion to void*, but these two functions typically test for slightly different stream states. (In the C++ library standard (see Item E49 and Item 35), the implicit conversion to void* has been replaced by an implicit conversion to bool, and operator bool always returns the negation of operator!.) Converting Smart Pointers to Dumb Pointers Sometimes you'd like to add smart pointers to an application or library that already uses dumb pointers. For example, your distributed database system may not originally have been distributed, so you may have some old library functions that aren't designed to use smart pointers: class Tuple { ... }; // as before void normalize(Tuple *pt); // put *pt into canonical // form; note use of dumb // pointer Consider what will happen if you try to call normalize with a smart pointer-to-Tuple: DBPtr pt; ... normalize(pt); // error! The call will fail to compile, because there is no way to convert a DBPtr to a Tuple*. You can make it work by doing this, normalize(&*pt); // gross, but legal but I hope you'll agree this is repugnant. The call can be made to succeed by adding to the smart pointer-to-T template an implicit conversion operator to a dumb pointer-to-T: template // as before class DBPtr { public: ... operator T*() { return pointee; } ... }; DBPtr pt; ... normalize(pt); // this now works Addition of this function also eliminates the problem of testing for nullness: if (pt == 0) ... // fine, converts pt to a // Tuple* if (pt) ... // ditto if (!pt) ... // ditto (reprise) However, there is a dark side to such conversion functions. (There almost always is. Have you been seeing Item 5?) They make it easy for clients to program directly with dumb pointers, thus bypassing the smarts your pointer-like objects are designed to provide: void processTuple(DBPtr& pt) { Tuple *rawTuplePtr = pt; // converts DBPtr to // Tuple* use rawTuplePtr to modify the tuple; } Usually, the "smart" behavior provided by a smart pointer is an essential component of your design, so allowing clients to use dumb pointers typically leads to disaster. For example, if DBPtr implements the reference-counting strategy of Item 29, allowing clients to manipulate dumb pointers directly will almost certainly lead to bookkeeping errors that corrupt the reference-counting data structures. Even if you provide an implicit conversion operator to go from a smart pointer to the dumb pointer it's built on, your smart pointer will never be truly interchangeable with the dumb pointer. That's because the conversion from a smart pointer to a dumb pointer is a user-defined conversion, and compilers are forbidden from applying more than one such conversion at a time. For example, suppose you have a class representing all the clients who have accessed a particular tuple: class TupleAccessors { public: TupleAccessors(const Tuple *pt); // pt identifies the ... // tuple whose accessors }; // we care about As usual, TupleAccessors' single-argument constructor also acts as a type-conversion operator from Tuple* to TupleAccessors (see Item 5). Now consider a function for merging the information in two TupleAccessors objects: TupleAccessors merge(const TupleAccessors& ta1, const TupleAccessors& ta2); Because a Tuple* may be implicitly converted to a TupleAccessors, calling merge with two dumb Tuple* pointers is fine: Tuple *pt1, *pt2; ... merge(pt1, pt2); // fine, both pointers are converted // to TupleAccessors objects The corresponding call with smart DBPtr pointers, however, fails to compile: DBPtr pt1, pt2; ... merge(pt1, pt2); // error! No way to convert pt1 and // pt2 to TupleAccessors objects That's because a conversion from DBPtr to TupleAccessors calls for two user-defined conversions (one from DBPtr to Tuple* and one from Tuple* to TupleAccessors), and such sequences of conversions are prohibited by the language. Smart pointer classes that provide an implicit conversion to a dumb pointer open the door to a particularly nasty bug. Consider this code: DBPtr pt = new Tuple; ... delete pt; This should not compile. After all, pt is not a pointer, it's an object, and you can't delete an object. Only pointers can be deleted, right? Right. But remember from Item 5 that compilers use implicit type conversions to make function calls succeed whenever they can, and recall from Item 8 that use of the delete operator leads to calls to a destructor and to operator delete, both of which are functions. Compilers want these function calls to succeed, so in the delete statement above, they implicitly convert pt to a Tuple*, then they delete that. This will almost certainly break your program. If pt owns the object it points to, that object is now deleted twice, once at the point where delete is called, a second time when pt's destructor is invoked. If pt doesn't own the object, somebody else does. That somebody may be the person who deleted pt, in which case all is well. If, however, the owner of the object pointed to by pt is not the person who deleted pt, we can expect the rightful owner to delete that object again later. The first and last of these scenarios leads to an object being deleted twice, and deleting an object more than once yields undefined behavior. This bug is especially pernicious because the whole idea behind smart pointers is to make them look and feel as much like dumb pointers as possible. The closer you get to this ideal, the more likely your clients are to forget they are using smart pointers. If they do, who can blame them if they continue to think that in order to avoid resource leaks, they must call delete if they called new? The bottom line is simple: don't provide implicit conversion operators to dumb pointers unless there is a compelling reason to do so. Smart Pointers and Inheritance-Based Type Conversions Suppose we have a public inheritance hierarchy modeling consumer products for storing music: class MusicProduct { public: MusicProduct(const string& title); virtual void play() const = 0; virtual void displayTitle() const = 0; ... }; class Cassette: public MusicProduct { public: Cassette(const string& title); virtual void play() const; virtual void displayTitle() const; ... }; class CD: public MusicProduct { public: CD(const string& title); virtual void play() const; virtual void displayTitle() const; ... }; Further suppose we have a function that, given a MusicProduct object, displays the title of the product and then plays it: void displayAndPlay(const MusicProduct* pmp, int numTimes) { for (int i = 1; i <= numTimes; ++i) { pmp->displayTitle(); pmp->play(); } } Such a function might be used like this: Cassette *funMusic = new Cassette("Alapalooza"); CD *nightmareMusic = new CD("Disco Hits of the 70s"); displayAndPlay(funMusic, 10); displayAndPlay(nightmareMusic, 0); There are no surprises here, but look what happens if we replace the dumb pointers with their allegedly smart counterparts: void displayAndPlay(const SmartPtr& pmp, int numTimes); SmartPtr funMusic(new Cassette("Alapalooza")); SmartPtr nightmareMusic(new CD("Disco Hits of the 70s")); displayAndPlay(funMusic, 10); // error! displayAndPlay(nightmareMusic, 0); // error! If smart pointers are so brainy, why won't these compile? They won't compile because there is no conversion from a SmartPtr or a SmartPtr to a SmartPtr. As far as compilers are concerned, these are three separate classes they have no relationship to one another. Why should compilers think otherwise? After all, it's not like SmartPtr or SmartPtr inherits from SmartPtr. With no inheritance relationship between these classes, we can hardly expect compilers to run around converting objects of one type to objects of other types. Fortunately, there is a way to get around this limitation, and the idea (if not the practice) is simple: give each smart pointer class an implicit type conversion operator (see Item 5) for each smart pointer class to which it should be implicitly convertible. For example, in the music hierarchy, you'd add an operator SmartPtr to the smart pointer classes for Cassette and CD: class SmartPtr { public: operator SmartPtr() { return SmartPtr(pointee); } ... private: Cassette *pointee; }; class SmartPtr { public: operator SmartPtr() { return SmartPtr(pointee); } ... private: CD *pointee; }; The drawbacks to this approach are twofold. First, you must manually specialize the SmartPtr class instantiations so you can add the necessary implicit type conversion operators, but that pretty much defeats the purpose of templates. Second, you may have to add many such conversion operators, because your pointed-to object may be deep in an inheritance hierarchy, and you must provide a conversion operator for each base class from which that object directly or indirectly inherits. (If you think you can get around this by providing only an implicit type conversion operator for each direct base class, think again. Because compilers are prohibited from employing more than one user-defined type conversion function at a time, they can't convert a smart pointer-to-T to a smart pointer-to-indirect-base-class-of-T unless they can do it in a single step.) It would be quite the time-saver if you could somehow get compilers to write all these implicit type conversion functions for you. Thanks to a recent language extension, you can. The extension in question is the ability to declare (nonvirtual) member function templates (usually just called member templates), and you use it to generate smart pointer conversion functions like this: template // template class for smart class SmartPtr { // pointers-to-T objects public: SmartPtr(T* realPtr = 0); T* operator->() const; T& operator*() const; template // template function for operator SmartPtr() // implicit conversion ops. { return SmartPtr(pointee); } ... }; Now hold on to your headlights, this isn't magic but it's close. It works as follows. (I'll give a specific example in a moment, so don't despair if the remainder of this paragraph reads like so much gobbledygook. After you've seen the example, it'll make more sense, I promise.) Suppose a compiler has a smart pointer-to-T object, and it's faced with the need to convert that object into a smart pointer-to-base-class-of-T. The compiler checks the class definition for SmartPtr to see if the requisite conversion operator is declared, but it is not. (It can't be: no conversion operators are declared in the template above.) The compiler then checks to see if there's a member function template it can instantiate that would let it perform the conversion it's looking for. It finds such a template (the one taking the formal type parameter newType), so it instantiates the template with newType bound to the base class of T that's the target of the conversion. At that point, the only question is whether the code for the instantiated member function will compile. In order for it to compile, it must be legal to pass the (dumb) pointer pointee to the constructor for the smart pointer-to-base-of-T. pointee is of type T, so it is certainly legal to convert it into a pointer to its (public or protected) base classes. Hence, the code for the type conversion operator will compile, and the implicit conversion from smart pointer-to-T to smart pointer-to-base-of-T will succeed. An example will help. Let us return to the music hierarchy of CDs, cassettes, and music products. We saw earlier that the following code wouldn't compile, because there was no way for compilers to convert the smart pointers to CDs or cassettes into smart pointers to music products: void displayAndPlay(const SmartPtr& pmp, int howMany); SmartPtr funMusic(new Cassette("Alapalooza")); SmartPtr nightmareMusic(new CD("Disco Hits of the 70s")); displayAndPlay(funMusic, 10); // used to be an error displayAndPlay(nightmareMusic, 0); // used to be an error With the revised smart pointer class containing the member function template for implicit type conversion operators, this code will succeed. To see why, look at this call: displayAndPlay(funMusic, 10); The object funMusic is of type SmartPtr. The function displayAndPlay expects a SmartPtr object. Compilers detect the type mismatch and seek a way to convert funMusic into a SmartPtr object. They look for a single-argument constructor (see Item 5) in the SmartPtr class that takes a SmartPtr, but they find none. They look for an implicit type conversion operator in the SmartPtr class that yields a SmartPtr class, but that search also fails. They then look for a member function template they can instantiate to yield one of these functions. They discover that the template inside SmartPtr, when instantiated with newType bound to MusicProduct, generates the necessary function. They instantiate the function, yielding the following code: SmartPtr:: operator SmartPtr() { return SmartPtr(pointee); } Will this compile? For all intents and purposes, nothing is happening here except the calling of the SmartPtr constructor with pointee as its argument, so the real question is whether one can construct a SmartPtr object with a Cassette* pointer. The SmartPtr constructor expects a MusicProduct* pointer, but now we're on the familiar ground of conversions between dumb pointer types, and it's clear that Cassette* can be passed in where a MusicProduct* is expected. The construction of the SmartPtr is therefore successful, and the conversion of the SmartPtr to SmartPtr is equally successful. Voil! Implicit conversion of smart pointer types. What could be simpler? Furthermore, what could be more powerful? Don't be misled by this example into assuming that this works only for pointer conversions up an inheritance hierarchy. The method shown succeeds for any legal implicit conversion between pointer types. If you've got a dumb pointer type T1* and another dumb pointer type T2*, you can implicitly convert a smart pointer-to-T1 to a smart pointer-to-T2 if and only if you can implicitly convert a T1* to a T2*. This technique gives you exactly the behavior you want almost. Suppose we augment our MusicProduct hierarchy with a new class, CasSingle, for representing cassette singles. The revised hierarchy looks like this: Now consider this code: template // as above, including member tem- class SmartPtr { ... }; // plate for conversion operators void displayAndPlay(const SmartPtr& pmp, int howMany); void displayAndPlay(const SmartPtr& pc, int howMany); SmartPtr dumbMusic(new CasSingle("Achy Breaky Heart")); displayAndPlay(dumbMusic, 1); // error! In this example, displayAndPlay is overloaded, with one function taking a SmartPtr object and the other taking a SmartPtr object. When we invoke displayAndPlay with a SmartPtr, we expect the SmartPtr function to be chosen, because CasSingle inherits directly from Cassette and only indirectly from MusicProduct. Certainly that's how it would work with dumb pointers. Alas, our smart pointers aren't that smart. They employ member functions as conversion operators, and as far as C++ compilers are concerned, all calls to conversion functions are equally good. As a result, the call to displayAndPlay is ambiguous, because the conversion from SmartPtr to SmartPtr is no better than the conversion to SmartPtr. Implementing smart pointer conversions through member templates has two additional drawbacks. First, support for member templates is rare, so this technique is currently anything but portable. In the future, that will change, but nobody knows just how far in the future that will be. Second, the mechanics of why this works are far from transparent, relying as they do on a detailed understanding of argument-matching rules for function calls, implicit type conversion functions, implicit instantiation of template functions, and the existence of member function templates. Pity the poor programmer who has never seen this trick before and is then asked to maintain or enhance code that relies on it. The technique is clever, that's for sure, but too much cleverness can be a dangerous thing. Let's stop beating around the bush. What we really want to know is how we can make smart pointer classes behave just like dumb pointers for purposes of inheritance-based type conversions. The answer is simple: we can't. As Daniel Edelson has noted, smart pointers are smart, but they're not pointers. The best we can do is to use member templates to generate conversion functions, then use casts (see Item 2) in those cases where ambiguity results. This isn't a perfect state of affairs, but it's pretty good, and having to cast away ambiguity in a few cases is a small price to pay for the sophisticated functionality smart pointers can provide. Smart Pointers and const Recall that for dumb pointers, const can refer to the thing pointed to, to the pointer itself, or both (see Item E21): CD goodCD("Flood"); const CD *p; // p is a non-const pointer // to a const CD object CD * const p = &goodCD; // p is a const pointer to // a non-const CD object; // because p is const, it // must be initialized const CD * const p = &goodCD; // p is a const pointer to // a const CD object Naturally, we'd like to have the same flexibility with smart pointers. Unfortunately, there's only one place to put the const, and there it applies to the pointer, not to the object pointed to: const SmartPtr p = // p is a const smart ptr &goodCD; // to a non-const CD object This seems simple enough to remedy just create a smart pointer to a const CD: SmartPtr p = // p is a non-const smart ptr &goodCD; // to a const CD object Now we can create the four combinations of const and non-const objects and pointers we seek: SmartPtr p; // non-const object, // non-const pointer SmartPtr p; // const object, // non-const pointer const SmartPtr p = &goodCD; // non-const object, // const pointer const SmartPtr p = &goodCD; // const object, // const pointer Alas, this ointment has a fly in it. Using dumb pointers, we can initialize const pointers with non-const pointers and we can initialize pointers to const objects with pointers to non-consts; the rules for assignments are analogous. For example: CD *pCD = new CD("Famous Movie Themes"); const CD * pConstCD = pCD; // fine But look what happens if we try the same thing with smart pointers: SmartPtr pCD = new CD("Famous Movie Themes"); SmartPtr pConstCD = pCD; // fine? SmartPtr and SmartPtr are completely different types. As far as your compilers know, they are unrelated, so they have no reason to believe they are assignment-compatible. In what must be an old story by now, the only way these two types will be considered assignment-compatible is if you've provided a function to convert objects of type SmartPtr to objects of type SmartPtr. If you've got a compiler that supports member templates, you can use the technique shown above for automatically generating the implicit type conversion operators you need. (I remarked earlier that the technique worked anytime the corresponding conversion for dumb pointers would work, and I wasn't kidding. Conversions involving const are no exception.) If you don't have such a compiler, you have to jump through one more hoop. Conversions involving const are a one-way street: it's safe to go from non-const to const, but it's not safe to go from const to non-const. Furthermore, anything you can do with a const pointer you can do with a non-const pointer, but with non-const pointers you can do other things, too (for example, assignment). Similarly, anything you can do with a pointer-to-const is legal for a pointer-to-non-const, but you can do some things (such as assignment) with pointers-to-non-consts that you can't do with pointers-to-consts. These rules sound like the rules for public inheritance (see Item E35). You can convert from a derived class object to a base class object, but not vice versa, and you can do anything to a derived class object you can do to a base class object, but you can typically do additional things to a derived class object, as well. We can take advantage of this similarity when implementing smart pointers by having each smart pointer-to-T class publicly inherit from a corresponding smart pointer-to-const-T class: template // smart pointers to const class SmartPtrToConst { // objects ... // the usual smart pointer // member functions protected: union { const T* constPointee; // for SmartPtrToConst access T* pointee; // for SmartPtr access }; }; template // smart pointers to class SmartPtr: // non-const objects public SmartPtrToConst { ... // no data members }; With this design, the smart pointer-to-non-const-T object needs to contain a dumb pointer-to-non-const-T, and the smart pointer-to-const-T needs to contain a dumb pointer-to-const-T. The naive way to handle this would be to put a dumb pointer-to-const-T in the base class and a dumb pointer-to-non-const-T in the derived class. That would be wasteful, however, because SmartPtr objects would contain two dumb pointers: the one they inherited from SmartPtrToConst and the one in SmartPtr itself. This problem is resolved by employing that old battle axe of the C world, a union, which can be as useful in C++ as it is in C. The union is protected, so both classes have access to it, and it contains both of the necessary dumb pointer types. SmartPtrToConst objects use the constPointee pointer, SmartPtr objects use the pointee pointer. We therefore get the advantages of two different pointers without having to allocate space for more than one. (See Item E10 for another example of this.) Such is the beauty of a union. Of course, the member functions of the two classes must constrain themselves to using only the appropriate pointer, and you'll get no help from compilers in enforcing that constraint. Such is the risk of a union. With this new design, we get the behavior we want: SmartPtr pCD = new CD("Famous Movie Themes"); SmartPtrToConst pConstCD = pCD; // fine Evaluation That wraps up the subject of smart pointers, but before we leave the topic, we should ask this question: are they worth the trouble, especially if your compilers lack support for member function templates? Often they are. The reference-counting code of Item 29, for example, is greatly simplified by using smart pointers. Furthermore, as that example demonstrates, some uses of smart pointers are sufficiently limited in scope that things like testing for nullness, conversion to dumb pointers, inheritance-based conversions, and support for pointers-to-consts are irrelevant. At the same time, smart pointers can be tricky to implement, understand, and maintain. Debugging code using smart pointers is more difficult than debugging code using dumb pointers. Try as you may, you will never succeed in designing a general-purpose smart pointer that can seamlessly replace its dumb pointer counterpart. Smart pointers nevertheless make it possible to achieve effects in your code that would otherwise be difficult to implement. Smart pointers should be used judiciously, but every C++ programmer will find them useful at one time or another. Back to Item 28: Smart pointers Continue to Item 30: Proxy classes Item 29: Reference counting. Reference counting is a technique that allows multiple objects with the same value to share a single representation of that value. There are two common motivations for the technique. The first is to simplify the bookkeeping surrounding heap objects. Once an object is allocated by calling new, it's crucial to keep track of who owns that object, because the owner and only the owner is responsible for calling delete on it. But ownership can be transferred from object to object as a program runs (by passing pointers as parameters, for example), so keeping track of an object's ownership is hard work. Classes like auto_ptr (see Item 9) can help with this task, but experience has shown that most programs still fail to get it right. Reference counting eliminates the burden of tracking object ownership, because when an object employs reference counting, it owns itself. When nobody is using it any longer, it destroys itself automatically. Thus, reference counting constitutes a simple form of garbage collection. The second motivation for reference counting is simple common sense. If many objects have the same value, it's silly to store that value more than once. Instead, it's better to let all the objects with that value share its representation. Doing so not only saves memory, it also leads to faster-running programs, because there's no need to construct and destruct redundant copies of the same object value. Like most simple ideas, this one hovers above a sea of interesting details. God may or may not be in the details, but successful implementations of reference counting certainly are. Before delving into details, however, let us master basics. A good way to begin is by seeing how we might come to have many objects with the same value in the first place. Here's one way: class String { // the standard string type may public: // employ the techniques in this // Item, but that is not required String(const char *value = ""); String& operator=(const String& rhs); ... private: char *data; }; String a, b, c, d, e; a = b = c = d = e = "Hello"; It should be apparent that objects a through e all have the same value, namely "Hello". How that value is represented depends on how the String class is implemented, but a common implementation would have each String object carry its own copy of the value. For example, String's assignment operator might be implemented like this: String& String::operator=(const String& rhs) { if (this == &rhs) return *this; // see Item E17 delete [] data; data = new char[strlen(rhs.data) + 1]; strcpy(data, rhs.data); return *this; // see Item E15 } Given this implementation, we can envision the five objects and their values as follows: The redundancy in this approach is clear. In an ideal world, we'd like to change the picture to look like this: Here only one copy of the value "Hello" is stored, and all the String objects with that value share its representation. In practice, it isn't possible to achieve this ideal, because we need to keep track of how many objects are sharing a value. If object a above is assigned a different value from "Hello", we can't destroy the value "Hello", because four other objects still need it. On the other hand, if only a single object had the value "Hello" and that object went out of scope, no object would have that value and we'd have to destroy the value to avoid a resource leak. The need to store information on the number of objects currently sharing referring to a value means our ideal picture must be modified somewhat to take into account the existence of a reference count: (Some people call this number a use count, but I am not one of them. C++ has enough idiosyncrasies of its own; the last thing it needs is terminological factionalism.) Implementing Reference Counting Creating a reference-counted String class isn't difficult, but it does require attention to detail, so we'll walk through the implementation of the most common member functions of such a class. Before we do that, however, it's important to recognize that we need a place to store the reference count for each String value. That place cannot be in a String object, because we need one reference count per string value, not one reference count per string object. That implies a coupling between values and reference counts, so we'll create a class to store reference counts and the values they track. We'll call this class StringValue, and because its only raison d'tre is to help implement the String class, we'll nest it inside String's private section. Furthermore, it will be convenient to give all the member functions of String full access to the StringValue data structure, so we'll declare StringValue to be a struct. This is a trick worth knowing: nesting a struct in the private part of a class is a convenient way to give access to the struct to all the members of the class, but to deny access to everybody else (except, of course, friends of the class). Our basic design looks like this: class String { public: ... // the usual String member // functions go here private: struct StringValue { ... }; // holds a reference count // and a string value StringValue *value; // value of this String }; We could give this class a different name (RCString, perhaps) to emphasize that it's implemented using reference counting, but the implementation of a class shouldn't be of concern to clients of that class. Rather, clients should interest themselves only in a class's public interface. Our reference-counting implementation of the String interface supports exactly the same operations as a non-reference-counted version, so why muddy the conceptual waters by embedding implementation decisions in the names of classes that correspond to abstract concepts? Why indeed? So we don't. Here's StringValue: class String { private: struct StringValue { int refCount; char *data; StringValue(const char *initValue); ~StringValue(); }; ... }; String::StringValue::StringValue(const char *initValue) : refCount(1) { data = new char[strlen(initValue) + 1]; strcpy(data, initValue); } String::StringValue::~StringValue() { delete [] data; } That's all there is to it, and it should be clear that's nowhere near enough to implement the full functionality of a reference-counted string. For one thing, there's neither a copy constructor nor an assignment operator (see Item E11), and for another, there's no manipulation of the refCount field. Worry not the missing functionality will be provided by the String class. The primary purpose of StringValue is to give us a place to associate a particular value with a count of the number of String objects sharing that value. StringValue gives us that, and that's enough. We're now ready to walk our way through String's member functions. We'll begin with the constructors: class String { public: String(const char *initValue = ""); String(const String& rhs); ... }; The first constructor is implemented about as simply as possible. We use the passed-in char* string to create a new StringValue object, then we make the String object we're constructing point to the newly-minted StringValue: String::String(const char *initValue) : value(new StringValue(initValue)) {} For client code that looks like this, String s("More Effective C++"); we end up with a data structure that looks like this: String objects constructed separately, but with the same initial value do not share a data structure, so client code of this form, String s1("More Effective C++"); String s2("More Effective C++"); yields this data structure: It is possible to eliminate such duplication by having String (or StringValue) keep track of existing StringValue objects and create new ones only for truly unique strings, but such refinements on reference counting are somewhat off the beaten path. As a result, I'll leave them in the form of the feared and hated exercise for the reader. The String copy constructor is not only unfeared and unhated, it's also efficient: the newly created String object shares the same StringValue object as the String object that's being copied: String::String(const String& rhs) : value(rhs.value) { ++value->refCount; } Graphically, code like this, String s1("More Effective C++"); String s2 = s1; results in this data structure: This is substantially more efficient than a conventional (non-reference-counted) String class, because there is no need to allocate memory for the second copy of the string value, no need to deallocate that memory later, and no need to copy the value that would go in that memory. Instead, we merely copy a pointer and increment a reference count. The String destructor is also easy to implement, because most of the time it doesn't do anything. As long as the reference count for a StringValue is non-zero, at least one String object is using the value; it must therefore not be destroyed. Only when the String being destructed is the sole user of the value i.e., when the value's reference count is 1 should the String destructor destroy the StringValue object: class String { public: ~String(); ... }; String::~String() { if (--value->refCount == 0) delete value; } Compare the efficiency of this function with that of the destructor for a non-reference-counted implementation. Such a function would always call delete and would almost certainly have a nontrivial runtime cost. Provided that different String objects do in fact sometimes have the same values, the implementation above will sometimes do nothing more than decrement a counter and compare it to zero. If, at this point, the appeal of reference counting is not becoming apparent, you're just not paying attention. That's all there is to String construction and destruction, so we'll move on to consideration of the String assignment operator: class String { public: String& operator=(const String& rhs); ... }; When a client writes code like this, s1 = s2; // s1 and s2 are both String objects the result of the assignment should be that s1 and s2 both point to the same StringValue object. That object's reference count should therefore be incremented during the assignment. Furthermore, the StringValue object that s1 pointed to prior to the assignment should have its reference count decremented, because s1 will no longer have that value. If s1 was the only String with that value, the value should be destroyed. In C++, all that looks like this: String& String::operator=(const String& rhs) { if (value == rhs.value) { // do nothing if the values return *this; // are already the same; this } // subsumes the usual test of // this against &rhs (see Item E17) if (--value->refCount == 0) { // destroy *this's value if delete value; // no one else is using it } value = rhs.value; // have *this share rhs's ++value->refCount; // value return *this; } Copy-on-Write To round out our examination of reference-counted strings, consider an array-bracket operator ([]), which allows individual characters within strings to be read and written: class String { public: const char& operator[](int index) const; // for const Strings char& operator[](int index); // for non-const Strings ... }; Implementation of the const version of this function is straightforward, because it's a read-only operation; the value of the string can't be affected: const char& String::operator[](int index) const { return value->data[index]; } (This function performs sanity checking on index in the grand C++ tradition, which is to say not at all. As usual, if you'd like a greater degree of parameter validation, it's easy to add.) The non-const version of operator[] is a completely different story. This function may be called to read a character, but it might be called to write one, too: String s; ... cout << s[3]; // this is a read s[5] = 'x'; // this is a write We'd like to deal with reads and writes differently. A simple read can be dealt with in the same way as the const version of operator[] above, but a write must be implemented in quite a different fashion. When we modify a String's value, we have to be careful to avoid modifying the value of other String objects that happen to be sharing the same StringValue object. Unfortunately, there is no way for C++ compilers to tell us whether a particular use of operator[] is for a read or a write, so we must be pessimistic and assume that all calls to the non-const operator[] are for writes. (Proxy classes can help us differentiate reads from writes see Item 30.) To implement the non-const operator[] safely, we must ensure that no other String object shares the StringValue to be modified by the presumed write. In short, we must ensure that the reference count for a String's StringValue object is exactly one any time we return a reference to a character inside that StringValue object. Here's how we do it: char& String::operator[](int index) { // if we're sharing a value with other String objects, // break off a separate copy of the value for ourselves if (value->refCount > 1) { --value->refCount; // decrement current value's // refCount, because we won't // be using that value any more value = // make a copy of the new StringValue(value->data); // value for ourselves } // return a reference to a character inside our // unshared StringValue object return value->data[index]; } This idea that of sharing a value with other objects until we have to write on our own copy of the value has a long and distinguished history in Computer Science, especially in operating systems, where processes are routinely allowed to share pages until they want to modify data on their own copy of a page. The technique is common enough to have a name: copy-on-write. It's a specific example of a more general approach to efficiency, that of lazy evaluation (see Item 17). Pointers, References, and Copy-on-Write This implementation of copy-on-write allows us to preserve both efficiency and correctness almost. There is one lingering problem. Consider this code: String s1 = "Hello"; char *p = &s1[1]; Our data structure at this point looks like this: Now consider an additional statement: String s2 = s1; The String copy constructor will make s2 share s1's StringValue, so the resulting data structure will be this one: The implications of a statement such as the following, then, are not pleasant to contemplate: *p = 'x'; // modifies both s1 and s2! There is no way the String copy constructor can detect this problem, because it has no way to know that a pointer into s1's StringValue object exists. And this problem isn't limited to pointers: it would exist if someone had saved a reference to the result of a call to String's non-const operator[]. There are at least three ways of dealing with this problem. The first is to ignore it, to pretend it doesn't exist. This approach turns out to be distressingly common in class libraries that implement reference-counted strings. If you have access to a reference-counted string, try the above example and see if you're distressed, too. If you're not sure if you have access to a reference-counted string, try the example anyway. Through the wonder of encapsulation, you may be using such a type without knowing it. Not all implementations ignore such problems. A slightly more sophisticated way of dealing with such difficulties is to define them out of existence. Implementations adopting this strategy typically put something in their documentation that says, more or less, "Don't do that. If you do, results are undefined." If you then do it anyway wittingly or no and complain about the results, they respond, "Well, we told you not to do that." Such implementations are often efficient, but they leave much to be desired in the usability department. There is a third solution, and that's to eliminate the problem. It's not difficult to implement, but it can reduce the amount of value sharing between objects. Its essence is this: add a flag to each StringValue object indicating whether that object is shareable. Turn the flag on initially (the object is shareable), but turn it off whenever the non-const operator[] is invoked on the value represented by that object. Once the flag is set to false, it stays that way forever.10 Here's a modified version of StringValue that includes a shareability flag: class String { private: struct StringValue { int refCount; bool shareable; // add this char *data; StringValue(const char *initValue); ~StringValue(); }; ... }; String::StringValue::StringValue(const char *initValue) : refCount(1), shareable(true) // add this { data = new char[strlen(initValue) + 1]; strcpy(data, initValue); } String::StringValue::~StringValue() { delete [] data; } As you can see, not much needs to change; the two lines that require modification are flagged with comments. Of course, String's member functions must be updated to take the shareable field into account. Here's how the copy constructor would do that: String::String(const String& rhs) { if (rhs.value->shareable) { value = rhs.value; ++value->refCount; } else { value = new StringValue(rhs.value->data); } } All the other String member functions would have to check the shareable field in an analogous fashion. The non-const version of operator[] would be the only function to set the shareable flag to false: char& String::operator[](int index) { if (value->refCount > 1) { --value->refCount; value = new StringValue(value->data); } value->shareable = false; // add this return value->data[index]; } If you use the proxy class technique of Item 30 to distinguish read usage from write usage in operator[], you can usually reduce the number of StringValue objects that must be marked unshareable. A Reference-Counting Base Class Reference counting is useful for more than just strings. Any class in which different objects may have values in common is a legitimate candidate for reference counting. Rewriting a class to take advantage of reference counting can be a lot of work, however, and most of us already have more than enough to do. Wouldn't it be nice if we could somehow write (and test and document) the reference counting code in a context-independent manner, then just graft it onto classes when needed? Of course it would. In a curious twist of fate, there's a way to do it (or at least to do most of it). The first step is to create a base class, RCObject, for reference-counted objects. Any class wishing to take advantage of automatic reference counting must inherit from this class. RCObject encapsulates the reference count itself, as well as functions for incrementing and decrementing that count. It also contains the code for destroying a value when it is no longer in use, i.e., when its reference count becomes 0. Finally, it contains a field that keeps track of whether this value is shareable, and it provides functions to query this value and set it to false. There is no need for a function to set the shareability field to true, because all values are shareable by default. As noted above, once an object has been tagged unshareable, there is no way to make it shareable again. RCObject's class definition looks like this: class RCObject { public: RCObject(); RCObject(const RCObject& rhs); RCObject& operator=(const RCObject& rhs); virtual ~RCObject() = 0; void addReference(); void removeReference(); void markUnshareable(); bool isShareable() const; bool isShared() const; private: int refCount; bool shareable; }; RCObjects can be created (as the base class parts of more derived objects) and destroyed; they can have new references added to them and can have current references removed; their shareability status can be queried and can be disabled; and they can report whether they are currently being shared. That's all they offer. As a class encapsulating the notion of being reference-countable, that's really all we have a right to expect them to do. Note the tell-tale virtual destructor, a sure sign this class is designed for use as a base class (see Item E14). Note also how the destructor is a pure virtual function, a sure sign this class is designed to be used only as a base class. The code to implement RCObject is, if nothing else, brief: RCObject::RCObject() : refCount(0), shareable(true) {} RCObject::RCObject(const RCObject&) : refCount(0), shareable(true) {} RCObject& RCObject::operator=(const RCObject&) { return *this; } RCObject::~RCObject() {} // virtual dtors must always // be implemented, even if // they are pure virtual // and do nothing (see also // Item 33 and Item E14) void RCObject::addReference() { ++refCount; } void RCObject::removeReference() { if (--refCount == 0) delete this; } void RCObject::markUnshareable() { shareable = false; } bool RCObject::isShareable() const { return shareable; } bool RCObject::isShared() const { return refCount > 1; } Curiously, we set refCount to 0 inside both constructors. This seems counterintuitive. Surely at least the creator of the new RCObject is referring to it! As it turns out, it simplifies things for the creators of RCObjects to set refCount to 1 themselves, so we oblige them here by not getting in their way. We'll get a chance to see the resulting code simplification shortly. Another curious thing is that the copy constructor always sets refCount to 0, regardless of the value of refCount for the RCObject we're copying. That's because we're creating a new object representing a value, and new values are always unshared and referenced only by their creator. Again, the creator is responsible for setting the refCount to its proper value. The RCObject assignment operator looks downright subversive: it does nothing. Frankly, it's unlikely this operator will ever be called. RCObject is a base class for a shared value object, and in a system based on reference counting, such objects are not assigned to one another, objects pointing to them are. In our case, we don't expect StringValue objects to be assigned to one another, we expect only String objects to be involved in assignments. In such assignments, no change is made to the value of a StringValue only the StringValue reference count is modified. Nevertheless, it is conceivable that some as-yet-unwritten class might someday inherit from RCObject and might wish to allow assignment of reference-counted values (see Item 32 and Item E16). If so, RCObject's assignment operator should do the right thing, and the right thing is to do nothing. To see why, imagine that we wished to allow assignments between StringValue objects. Given StringValue objects sv1 and sv2, what should happen to sv1's and sv2's reference counts in an assignment? sv1 = sv2; // how are sv1's and sv2's reference // counts affected? Before the assignment, some number of String objects are pointing to sv1. That number is unchanged by the assignment, because only sv1's value changes. Similarly, some number of String objects are pointing to sv2 prior to the assignment, and after the assignment, exactly the same String objects point to sv2. sv2's reference count is also unchanged. When RCObjects are involved in an assignment, then, the number of objects pointing to those objects is unaffected, hence RCObject::operator= should change no reference counts. That's exactly what the implementation above does. Counterintuitive? Perhaps, but it's still correct. The code for RCObject::removeReference is responsible not only for decrementing the object's refCount, but also for destroying the object if the new value of refCount is 0. It accomplishes this latter task by deleteing this, which, as Item 27 explains, is safe only if we know that *this is a heap object. For this class to be successful, we must engineer things so that RCObjects can be created only on the heap. General approaches to achieving that end are discussed in Item 27, but the specific measures we'll employ in this case are described at the conclusion of this Item. To take advantage of our new reference-counting base class, we modify StringValue to inherit its reference counting capabilities from RCObject: class String { private: struct StringValue: public RCObject { char *data; StringValue(const char *initValue); ~StringValue(); }; ... }; String::StringValue::StringValue(const char *initValue) { data = new char[strlen(initValue) + 1]; strcpy(data, initValue); } String::StringValue::~StringValue() { delete [] data; } This version of StringValue is almost identical to the one we saw earlier. The only thing that's changed is that StringValue's member functions no longer manipulate the refCount field. RCObject now handles what they used to do. Don't feel bad if you blanched at the sight of a nested class (StringValue) inheriting from a class (RCObject) that's unrelated to the nesting class (String). It looks weird to everybody at first, but it's perfectly kosher. A nested class is just as much a class as any other, so it has the freedom to inherit from whatever other classes it likes. In time, you won't think twice about such inheritance relationships. Automating Reference Count Manipulations The RCObject class gives us a place to store a reference count, and it gives us member functions through which that reference count can be manipulated, but the calls to those functions must still be manually inserted in other classes. It is still up to the String copy constructor and the String assignment operator to call addReference and removeReference on StringValue objects. This is clumsy. We'd like to move those calls out into a reusable class, too, thus freeing authors of classes like String from worrying about any of the details of reference counting. Can it be done? Isn't C++ supposed to support reuse? It can, and it does. There's no easy way to arrange things so that all reference-counting considerations can be moved out of application classes, but there is a way to eliminate most of them for most classes. (In some application classes, you can eliminate all reference-counting code, but our String class, alas, isn't one of them. One member function spoils the party, and I suspect you won't be too surprised to hear it's our old nemesis, the non-const version of operator[]. Take heart, however; we'll tame that miscreant in the end.) Notice that each String object contains a pointer to the StringValue object representing that String's value: class String { private: struct StringValue: public RCObject { ... }; StringValue *value; // value of this String ... }; We have to manipulate the refCount field of the StringValue object anytime anything interesting happens to one of the pointers pointing to it. "Interesting happenings" include copying a pointer, reassigning one, and destroying one. If we could somehow make the pointer itself detect these happenings and automatically perform the necessary manipulations of the refCount field, we'd be home free. Unfortunately, pointers are rather dense creatures, and the chances of them detecting anything, much less automatically reacting to things they detect, are pretty slim. Fortunately, there's a way to smarten them up: replace them with objects that act like pointers, but that do more. Such objects are called smart pointers, and you can read about them in more detail than you probably care to in Item 28. For our purposes here, it's enough to know that smart pointer objects support the member selection (->) and dereferencing (*) operations, just like real pointers (which, in this context, are generally referred to as dumb pointers), and, like dumb pointers, they are strongly typed: you can't make a smart pointer-to-T point to an object that isn't of type T. Here's a template for objects that act as smart pointers to reference-counted objects: // template class for smart pointers-to-T objects. T must // support the RCObject interface, typically by inheriting // from RCObject template class RCPtr { public: RCPtr(T* realPtr = 0); RCPtr(const RCPtr& rhs); ~RCPtr(); RCPtr& operator=(const RCPtr& rhs); T* operator->() const; // see Item 28 T& operator*() const; // see Item 28 private: T *pointee; // dumb pointer this // object is emulating void init(); // common initialization }; // code This template gives smart pointer objects control over what happens during their construction, assignment, and destruction. When such events occur, these objects can automatically perform the appropriate manipulations of the refCount field in the objects to which they point. For example, when an RCPtr is created, the object it points to needs to have its reference count increased. There's no need to burden application developers with the requirement to tend to this irksome detail manually, because RCPtr constructors can handle it themselves. The code in the two constructors is all but identical only the member initialization lists differ so rather than write it twice, we put it in a private member function called init and have both constructors call that: template RCPtr::RCPtr(T* realPtr): pointee(realPtr) { init(); } template RCPtr::RCPtr(const RCPtr& rhs): pointee(rhs.pointee) { init(); } template void RCPtr::init() { if (pointee == 0) { // if the dumb pointer is return; // null, so is the smart one } if (pointee->isShareable() == false) { // if the value pointee = new T(*pointee); // isn't shareable, } // copy it pointee->addReference(); // note that there is now a } // new reference to the value Moving common code into a separate function like init is exemplary software engineering, but its luster dims when, as in this case, the function doesn't behave correctly. The problem is this. When init needs to create a new copy of a value (because the existing copy isn't shareable), it executes the following code: pointee = new T(*pointee); The type of pointee is pointer-to-T, so this statement creates a new T object and initializes it by calling T's copy constructor. In the case of an RCPtr in the String class, T will be String::StringValue, so the statement above will call String::StringValue's copy constructor. We haven't declared a copy constructor for that class, however, so our compilers will generate one for us. The copy constructor so generated will, in accordance with the rules for automatically generated copy constructors in C++, copy only StringValue's data pointer; it will not copy the char* string data points to. Such behavior is disastrous in nearly any class (not just reference-counted classes), and that's why you should get into the habit of writing a copy constructor (and an assignment operator) for all your classes that contain pointers (see Item E11). The correct behavior of the RCPtr template depends on T containing a copy constructor that makes a truly independent copy (i.e., a deep copy) of the value represented by T. We must augment StringValue with such a constructor before we can use it with the RCPtr class: class String { private: struct StringValue: public RCObject { StringValue(const StringValue& rhs); ... }; ... }; String::StringValue::StringValue(const StringValue& rhs) { data = new char[strlen(rhs.data) + 1]; strcpy(data, rhs.data); } The existence of a deep-copying copy constructor is not the only assumption RCPtr makes about T. It also requires that T inherit from RCObject, or at least that T provide all the functionality that RCObject does. In view of the fact that RCPtr objects are designed to point only to reference-counted objects, this is hardly an unreasonable assumption. Nevertheless, the assumption must be documented. A final assumption in RCPtr is that the type of the object pointed to is T. This seems obvious enough. After all, pointee is declared to be of type T*. But pointee might really point to a class derived from T. For example, if we had a class SpecialStringValue that inherited from String::StringValue, class String { private: struct StringValue: public RCObject { ... }; struct SpecialStringValue: public StringValue { ... }; ... }; we could end up with a String containing a RCPtr pointing to a SpecialStringValue object. In that case, we'd want this part of init, pointee = new T(*pointee); // T is StringValue, but // pointee really points to // a SpecialStringValue to call SpecialStringValue's copy constructor, not StringValue's. We can arrange for this to happen by using a virtual copy constructor (see Item 25). In the case of our String class, we don't expect classes to derive from StringValue, so we'll disregard this issue. With RCPtr's constructors out of the way, the rest of the class's functions can be dispatched with considerably greater alacrity. Assignment of an RCPtr is straightforward, though the need to test whether the newly assigned value is shareable complicates matters slightly. Fortunately, such complications have already been handled by the init function that was created for RCPtr's constructors. We take advantage of that fact by using it again here: template RCPtr& RCPtr::operator=(const RCPtr& rhs) { if (pointee != rhs.pointee) { // skip assignments // where the value // doesn't change if (pointee) { pointee->removeReference(); // remove reference to } // current value pointee = rhs.pointee; // point to new value init(); // if possible, share it } // else make own copy return *this; } The destructor is easier. When an RCPtr is destroyed, it simply removes its reference to the reference-counted object: template RCPtr::~RCPtr() { if (pointee)pointee->removeReference(); } If the RCPtr that just expired was the last reference to the object, that object will be destroyed inside RCObject's removeReference member function. Hence RCPtr objects never need to worry about destroying the values they point to. Finally, RCPtr's pointer-emulating operators are part of the smart pointer boilerplate you can read about in Item 28: template T* RCPtr::operator->() const { return pointee; } template T& RCPtr::operator*() const { return *pointee; } Putting it All Together Enough! Finis! At long last we are in a position to put all the pieces together and build a reference-counted String class based on the reusable RCObject and RCPtr classes. With luck, you haven't forgotten that that was our original goal. Each reference-counted string is implemented via this data structure: The classes making up this data structure are defined like this: template // template class for smart class RCPtr { // pointers-to-T objects; T public: // must inherit from RCObject RCPtr(T* realPtr = 0); RCPtr(const RCPtr& rhs); ~RCPtr(); RCPtr& operator=(const RCPtr& rhs); T* operator->() const; T& operator*() const; private: T *pointee; void init(); }; class RCObject { // base class for reference- public: // counted objects void addReference(); void removeReference(); void markUnshareable(); bool isShareable() const; bool isShared() const; protected: RCObject(); RCObject(const RCObject& rhs); RCObject& operator=(const RCObject& rhs); virtual ~RCObject() = 0; private: int refCount; bool shareable; }; class String { // class to be used by public: // application developers String(const char *value = ""); const char& operator[](int index) const; char& operator[](int index); private: // class representing string values struct StringValue: public RCObject { char *data; StringValue(const char *initValue); StringValue(const StringValue& rhs); void init(const char *initValue); ~StringValue(); }; RCPtr value; }; For the most part, this is just a recap of what we've already developed, so nothing should be much of a surprise. Close examination reveals we've added an init function to String::StringValue, but, as we'll see below, that serves the same purpose as the corresponding function in RCPtr: it prevents code duplication in the constructors. There is a significant difference between the public interface of this String class and the one we used at the beginning of this Item. Where is the copy constructor? Where is the assignment operator? Where is the destructor? Something is definitely amiss here. Actually, no. Nothing is amiss. In fact, some things are working perfectly. If you don't see what they are, prepare yourself for a C++ epiphany. We don't need those functions anymore. Sure, copying of String objects is still supported, and yes, the copying will correctly handle the underlying reference-counted StringValue objects, but the String class doesn't have to provide a single line of code to make this happen. That's because the compiler-generated copy constructor for String will automatically call the copy constructor for String's RCPtr member, and the copy constructor for that class will perform all the necessary manipulations of the StringValue object, including its reference count. An RCPtr is a smart pointer, remember? We designed it to take care of the details of reference counting, so that's what it does. It also handles assignment and destruction, and that's why String doesn't need to write those functions, either. Our original goal was to move the unreusable reference-counting code out of our hand-written String class and into context-independent classes where it would be available for use with any class. Now we've done it (in the form of the RCObject and RCPtr classes), so don't be so surprised when it suddenly starts working. It's supposed to work. Just so you have everything in one place, here's the implementation of RCObject: RCObject::RCObject() : refCount(0), shareable(true) {} RCObject::RCObject(const RCObject&) : refCount(0), shareable(true) {} RCObject& RCObject::operator=(const RCObject&) { return *this; } RCObject::~RCObject() {} void RCObject::addReference() { ++refCount; } void RCObject::removeReference() { if (--refCount == 0) delete this; } void RCObject::markUnshareable() { shareable = false; } bool RCObject::isShareable() const { return shareable; } bool RCObject::isShared() const { return refCount > 1; } And here's the implementation of RCPtr: template void RCPtr::init() { if (pointee == 0) return; if (pointee->isShareable() == false) { pointee = new T(*pointee); } pointee->addReference(); } template RCPtr::RCPtr(T* realPtr) : pointee(realPtr) { init(); } template RCPtr::RCPtr(const RCPtr& rhs) : pointee(rhs.pointee) { init(); } template RCPtr::~RCPtr() { if (pointee)pointee->removeReference(); } template RCPtr& RCPtr::operator=(const RCPtr& rhs) { if (pointee != rhs.pointee) { if (pointee) pointee->removeReference(); pointee = rhs.pointee; init(); } return *this; } template T* RCPtr::operator->() const { return pointee; } template T& RCPtr::operator*() const { return *pointee; } The implementation of String::StringValue looks like this: void String::StringValue::init(const char *initValue) { data = new char[strlen(initValue) + 1]; strcpy(data, initValue); } String::StringValue::StringValue(const char *initValue) { init(initValue); } String::StringValue::StringValue(const StringValue& rhs) { init(rhs.data); } String::StringValue::~StringValue() { delete [] data; } Ultimately, all roads lead to String, and that class is implemented this way: String::String(const char *initValue) : value(new StringValue(initValue)) {} const char& String::operator[](int index) const { return value->data[index]; } char& String::operator[](int index) { if (value->isShared()) { value = new StringValue(value->data); } value->markUnshareable(); return value->data[index]; } If you compare the code for this String class with that we developed for the String class using dumb pointers, you'll be struck by two things. First, there's a lot less of it here than there. That's because RCPtr has assumed much of the reference-counting burden that used to fall on String. Second, the code that remains in String is nearly unchanged: the smart pointer replaced the dumb pointer essentially seamlessly. In fact, the only changes are in operator[], where we call isShared instead of checking the value of refCount directly and where our use of the smart RCPtr object eliminates the need to manually manipulate the reference count during a copy-on-write. This is all very nice, of course. Who can object to less code? Who can oppose encapsulation success stories? The bottom line, however, is determined more by the impact of this newfangled String class on its clients than by any of its implementation details, and it is here that things really shine. If no news is good news, the news here is very good indeed. The String interface has not changed. We added reference counting, we added the ability to mark individual string values as unshareable, we moved the notion of reference countability into a new base class, we added smart pointers to automate the manipulation of reference counts, yet not one line of client code needs to be changed. Sure, we changed the String class definition, so clients who want to take advantage of reference-counted strings must recompile and relink, but their investment in code is completely and utterly preserved. You see? Encapsulation really is a wonderful thing. Adding Reference Counting to Existing Classes Everything we've discussed so far assumes we have access to the source code of the classes we're interested in. But what if we'd like to apply the benefits of reference counting to some class Widget that's in a library we can't modify? There's no way to make Widget inherit from RCObject, so we can't use smart RCPtrs with it. Are we out of luck? We're not. With some minor modifications to our design, we can add reference counting to any type. First, let's consider what our design would look like if we could have Widget inherit from RCObject. In that case, we'd have to add a class, RCWidget, for clients to use, but everything would then be analogous to our String/StringValue example, with RCWidget playing the role of String and Widget playing the role of StringValue. The design would look like this: We can now apply the maxim that most problems in Computer Science can be solved with an additional level of indirection. We add a new class, CountHolder, to hold the reference count, and we have CountHolder inherit from RCObject. We also have CountHolder contain a pointer to a Widget. We then replace the smart RCPtr template with an equally smart RCIPtr template that knows about the existence of the CountHolder class. (The "I" in RCIPtr stands for "indirect.") The modified design looks like this: Just as StringValue was an implementation detail hidden from clients of String, CountHolder is an implementation detail hidden from clients of RCWidget. In fact, it's an implementation detail of RCIPtr, so it's nested inside that class. RCIPtr is implemented this way: template class RCIPtr { public: RCIPtr(T* realPtr = 0); RCIPtr(const RCIPtr& rhs); ~RCIPtr(); RCIPtr& operator=(const RCIPtr& rhs); const T* operator->() const; // see below for an T* operator->(); // explanation of why const T& operator*() const; // these functions are T& operator*(); // declared this way private: struct CountHolder: public RCObject { ~CountHolder() { delete pointee; } T *pointee; }; CountHolder *counter; void init(); void makeCopy(); // see below }; template void RCIPtr::init() { if (counter->isShareable() == false) { T *oldValue = counter->pointee; counter = new CountHolder; counter->pointee = new T(*oldValue); } counter->addReference(); } template RCIPtr::RCIPtr(T* realPtr) : counter(new CountHolder) { counter->pointee = realPtr; init(); } template RCIPtr::RCIPtr(const RCIPtr& rhs) : counter(rhs.counter) { init(); } template RCIPtr::~RCIPtr() { counter->removeReference(); } template RCIPtr& RCIPtr::operator=(const RCIPtr& rhs) { if (counter != rhs.counter) { counter->removeReference(); counter = rhs.counter; init(); } return *this; } template // implement the copy void RCIPtr::makeCopy() // part of copy-on- { // write (COW) if (counter->isShared()) { T *oldValue = counter->pointee; counter->removeReference(); counter = new CountHolder; counter->pointee = new T(*oldValue); counter->addReference(); } } template // const access; const T* RCIPtr::operator->() const // no COW needed { return counter->pointee; } template // non-const T* RCIPtr::operator->() // access; COW { makeCopy(); return counter->pointee; } // needed template // const access; const T& RCIPtr::operator*() const // no COW needed { return *(counter->pointee); } template // non-const T& RCIPtr::operator*() // access; do the { makeCopy(); return *(counter->pointee); } // COW thing RCIPtr differs from RCPtr in only two ways. First, RCPtr objects point to values directly, while RCIPtr objects point to values through intervening CountHolder objects. Second, RCIPtr overloads operator-> and operator* so that a copy-on-write is automatically performed whenever a non-const access is made to a pointed-to object. Given RCIPtr, it's easy to implement RCWidget, because each function in RCWidget is implemented by forwarding the call through the underlying RCIPtr to a Widget object. For example, if Widget looks like this, class Widget { public: Widget(int size); Widget(const Widget& rhs); ~Widget(); Widget& operator=(const Widget& rhs); void doThis(); int showThat() const; }; RCWidget will be defined this way: class RCWidget { public: RCWidget(int size): value(new Widget(size)) {} void doThis() { value->doThis(); } int showThat() const { return value->showThat(); } private: RCIPtr value; }; Note how the RCWidget constructor calls the Widget constructor (via the new operator see Item 8) with the argument it was passed; how RCWidget's doThis calls doThis in the Widget class; and how RCWidget::showThat returns whatever its Widget counterpart returns. Notice also how RCWidget declares no copy constructor, no assignment operator, and no destructor. As with the String class, there is no need to write these functions. Thanks to the behavior of the RCIPtr class, the default versions do the right things. If the thought occurs to you that creation of RCWidget is so mechanical, it could be automated, you're right. It would not be difficult to write a program that takes a class like Widget as input and produces a class like RCWidget as output. If you write such a program, please let me know. Evaluation Let us disentangle ourselves from the details of widgets, strings, values, smart pointers, and reference-counting base classes. That gives us an opportunity to step back and view reference counting in a broader context. In that more general context, we must address a higher-level question, namely, when is reference counting an appropriate technique? Reference-counting implementations are not without cost. Each reference-counted value carries a reference count with it, and most operations require that this reference count be examined or manipulated in some way. Object values therefore require more memory, and we sometimes execute more code when we work with them. Furthermore, the underlying source code is considerably more complex for a reference-counted class than for a less elaborate implementation. An un-reference-counted string class typically stands on its own, while our final String class is useless unless it's augmented with three auxiliary classes (StringValue, RCObject, and RCPtr). True, our more complicated design holds out the promise of greater efficiency when values can be shared, it eliminates the need to track object ownership, and it promotes reusability of the reference counting idea and implementation. Nevertheless, that quartet of classes has to be written, tested, documented, and maintained, and that's going to be more work than writing, testing, documenting, and maintaining a single class. Even a manager can see that. Reference counting is an optimization technique predicated on the assumption that objects will commonly share values (see also Item 18). If this assumption fails to hold, reference counting will use more memory than a more conventional implementation and it will execute more code. On the other hand, if your objects do tend to have common values, reference counting should save you both time and space. The bigger your object values and the more objects that can simultaneously share values, the more memory you'll save. The more you copy and assign values between objects, the more time you'll save. The more expensive it is to create and destroy a value, the more time you'll save there, too. In short, reference counting is most useful for improving efficiency under the following conditions: Relatively few values are shared by relatively many objects. Such sharing typically arises through calls to assignment operators and copy constructors. The higher the objects/values ratio, the better the case for reference counting. Object values are expensive to create or destroy, or they use lots of memory. Even when this is the case, reference counting still buys you nothing unless these values can be shared by multiple objects. There is only one sure way to tell whether these conditions are satisfied, and that way is not to guess or rely on your programmer's intuition (see Item 16). The reliable way to find out whether your program can benefit from reference counting is to profile or instrument it. That way you can find out if creating and destroying values is a performance bottleneck, and you can measure the objects/values ratio. Only when you have such data in hand are you in a position to determine whether the benefits of reference counting (of which there are many) outweigh the disadvantages (of which there are also many). Even when the conditions above are satisfied, a design employing reference counting may still be inappropriate. Some data structures (e.g., directed graphs) lead to self-referential or circular dependency structures. Such data structures have a tendency to spawn isolated collections of objects, used by no one, whose reference counts never drop to zero. That's because each object in the unused structure is pointed to by at least one other object in the same structure. Industrial-strength garbage collectors use special techniques to find such structures and eliminate them, but the simple reference-counting approach we've examined here is not easily extended to include such techniques. Reference counting can be attractive even if efficiency is not your primary concern. If you find yourself weighed down with uncertainty over who's allowed to delete what, reference counting could be just the technique you need to ease your burden. Many programmers are devoted to reference counting for this reason alone. Let us close this discussion on a technical note by tying up one remaining loose end. When RCObject::removeReference decrements an object's reference count, it checks to see if the new count is 0. If it is, removeReference destroys the object by deleteing this. This is a safe operation only if the object was allocated by calling new, so we need some way of ensuring that RCObjects are created only in that manner. In this case we do it by convention. RCObject is designed for use as a base class of reference-counted value objects, and those value objects should be referred to only by smart RCPtr pointers. Furthermore, the value objects should be instantiated only by application objects that realize values are being shared; the classes describing the value objects should never be available for general use. In our example, the class for value objects is StringValue, and we limit its use by making it private in String. Only String can create StringValue objects, so it is up to the author of the String class to ensure that all such objects are allocated via new. Our approach to the constraint that RCObjects be created only on the heap, then, is to assign responsibility for conformance to this constraint to a well-defined set of classes and to ensure that only that set of classes can create RCObjects. There is no possibility that random clients can accidently (or maliciously) create RCObjects in an inappropriate manner. We limit the right to create reference-counted objects, and when we do hand out the right, we make it clear that it's accompanied by the concomitant responsibility to follow the rules governing object creation. Back to Item 29: Reference counting Continue to Item 31: Making functions virtual with respect to more than one object Item 30: Proxy classes. Though your in-laws may be one-dimensional, the world, in general, is not. Unfortunately, C++ hasn't yet caught on to that fact. At least, there's little evidence for it in the language's support for arrays. You can create two-dimensional, three-dimensional heck, you can create n-dimensional arrays in FORTRAN, in BASIC, even in COBOL (okay, FORTRAN only allows up to seven dimensions, but let's not quibble), but can you do it in C++? Only sometimes, and even then only sort of. This much is legal: int data[10][20]; // 2D array: 10 by 20 The corresponding construct using variables as dimension sizes, however, is not: void processInput(int dim1, int dim2) { int data[dim1][dim2]; // error! array dimensions ... // must be known during } // compilation It's not even legal for a heap-based allocation: int *data = new int[dim1][dim2]; // error! Implementing Two-Dimensional Arrays Multidimensional arrays are as useful in C++ as they are in any other language, so it's important to come up with a way to get decent support for them. The usual way is the standard one in C++: create a class to represent the objects we need but that are missing in the language proper. Hence we can define a class template for two-dimensional arrays: template class Array2D { public: Array2D(int dim1, int dim2); ... }; Now we can define the arrays we want: Array2D data(10, 20); // fine Array2D *data = new Array2D(10, 20); // fine void processInput(int dim1, int dim2) { Array2D data(dim1, dim2); // fine ... } Using these array objects, however, isn't quite as straightforward. In keeping with the grand syntactic tradition of both C and C++, we'd like to be able to use brackets to index into our arrays, cout << data[3][6]; but how do we declare the indexing operator in Array2D to let us do this? Our first impulse might be to declare operator[][] functions, like this: template class Array2D { public: // declarations that won't compile T& operator[][](int index1, int index2); const T& operator[][](int index1, int index2) const; ... }; We'd quickly learn to rein in such impulses, however, because there is no such thing as operator[][], and don't think your compilers will forget it. (For a complete list of operators, overloadable and otherwise, see Item 7.) We'll have to do something else. If you can stomach the syntax, you might follow the lead of the many programming languages that use parentheses to index into arrays. To use parentheses, you just overload operator(): template class Array2D { public: // declarations that will compile T& operator()(int index1, int index2); const T& operator()(int index1, int index2) const; ... }; Clients then use arrays this way: cout << data(3, 6); This is easy to implement and easy to generalize to as many dimensions as you like. The drawback is that your Array2D objects don't look like built-in arrays any more. In fact, the above access to element (3, 6) of data looks, on the face of it, like a function call. If you reject the thought of your arrays looking like FORTRAN refugees, you might turn again to the notion of using brackets as the indexing operator. Although there is no such thing as operator[][], it is nonetheless legal to write code that appears to use it: int data[10][20]; ... cout << data[3][6]; // fine What gives? What gives is that the variable data is not really a two-dimensional array at all, it's a 10-element one-dimensional array. Each of those 10 elements is itself a 20-element array, so the expression data[3][6] really means (data[3])[6], i.e., the seventh element of the array that is the fourth element of data. In short, the value yielded by the first application of the brackets is another array, so the second application of the brackets gets an element from that secondary array. We can play the same game with our Array2D class by overloading operator[] to return an object of a new class, Array1D. We can then overload operator[] again in Array1D to return an element in our original two-dimensional array: template class Array2D { public: class Array1D { public: T& operator[](int index); const T& operator[](int index) const; ... }; Array1D operator[](int index); const Array1D operator[](int index) const; ... }; The following then becomes legal: Array2D data(10, 20); ... cout << data[3][6]; // fine Here, data[3] yields an Array1D object and the operator[] invocation on that object yields the float in position (3, 6) of the original two-dimensional array. Clients of the Array2D class need not be aware of the presence of the Array1D class. Objects of this latter class stand for one-dimensional array objects that, conceptually, do not exist for clients of Array2D. Such clients program as if they were using real, live, honest-to-Allah two-dimensional arrays. It is of no concern to Array2D clients that those objects must, in order to satisfy the vagaries of C++, be syntactically compatible with one-dimensional arrays of other one-dimensional arrays. Each Array1D object stands for a one-dimensional array that is absent from the conceptual model used by clients of Array2D. Objects that stand for other objects are often called proxy objects, and the classes that give rise to proxy objects are often called proxy classes. In this example, Array1D is a proxy class. Its instances stand for one-dimensional arrays that, conceptually, do not exist. (The terminology for proxy objects and classes is far from universal; objects of such classes are also sometimes known as surrogates.) Distinguishing Reads from Writes via operator[] The use of proxies to implement classes whose instances act like multidimensional arrays is common, but proxy classes are more flexible than that. Item 5, for example, shows how proxy classes can be employed to prevent single-argument constructors from being used to perform unwanted type conversions. Of the varied uses of proxy classes, however, the most heralded is that of helping distinguish reads from writes through operator[]. Consider a reference-counted string type that supports operator[]. Such a type is examined in detail in Item 29. If the concepts behind reference counting have slipped your mind, it would be a good idea to familiarize yourself with the material in that Item now. A string type supporting operator[] allows clients to write code like this: String s1, s2; // a string-like class; the // use of proxies keeps this // class from conforming to // the standard string ... // interface cout << s1[5]; // read s1 s2[5] = 'x'; // write s2 s1[3] = s2[8]; // write s1, read s2 Note that operator[] can be called in two different contexts: to read a character or to write a character. Reads are known as rvalue usages; writes are known as lvalue usages. (The terms come from the field of compilers, where an lvalue goes on the left-hand side of an assignment and an rvalue goes on the right-hand side.) In general, using an object as an lvalue means using it such that it might be modified, and using it as an rvalue means using it such that it cannot be modified. We'd like to distinguish between lvalue and rvalue usage of operator[] because, especially for reference-counted data structures, reads can be much less expensive to implement than writes. As Item 29 explains, writes of reference-counted objects may involve copying an entire data structure, but reads never require more than the simple returning of a value. Unfortunately, inside operator[], there is no way to determine the context in which the function was called; it is not possible to distinguish lvalue usage from rvalue usage within operator[]. "But wait," you say, "we don't need to. We can overload operator[] on the basis of its constness, and that will allow us to distinguish reads from writes." In other words, you suggest we solve our problem this way: class String { public: const char& operator[](int index) const; // for reads char& operator[](int index); // for writes ... }; Alas, this won't work. Compilers choose between const and non-const member functions by looking only at whether the object invoking a function is const. No consideration is given to the context in which a call is made. Hence: String s1, s2; ... cout << s1[5]; // calls non-const operator[], // because s1 isn't const s2[5] = 'x'; // also calls non-const // operator[]: s2 isn't const s1[3] = s2[8]; // both calls are to non-const // operator[], because both s1 // and s2 are non-const objects Overloading operator[], then, fails to distinguish reads from writes. In Item 29, we resigned ourselves to this unsatisfactory state of affairs and made the conservative assumption that all calls to operator[] were for writes. This time we shall not give up so easily. It may be impossible to distinguish lvalue from rvalue usage inside operator[], but we still want to do it. We will therefore find a way. What fun is life if you allow yourself to be limited by the possible? Our approach is based on the fact that though it may be impossible to tell whether operator[] is being invoked in an lvalue or an rvalue context from within operator[], we can still treat reads differently from writes if we delay our lvalue-versus-rvalue actions until we see how the result of operator[] is used. All we need is a way to postpone our decision on whether our object is being read or written until after operator[] has returned. (This is an example of lazy evaluation see Item 17.) A proxy class allows us to buy the time we need, because we can modify operator[] to return a proxy for a string character instead of a string character itself. We can then wait to see how the proxy is used. If it's read, we can belatedly treat the call to operator[] as a read. If it's written, we must treat the call to operator[] as a write. We will see the code for this in a moment, but first it is important to understand the proxies we'll be using. There are only three things you can do with a proxy: Create it, i.e., specify which string character it stands for. Use it as the target of an assignment, in which case you are really making an assignment to the string character it stands for. When used in this way, a proxy represents an lvalue use of the string on which operator[] was invoked. Use it in any other way. When used like this, a proxy represents an rvalue use of the string on which operator[] was invoked. Here are the class definitions for a reference-counted String class using a proxy class to distinguish between lvalue and rvalue usages of operator[]: class String { // reference-counted strings; public: // see Item 29 for details class CharProxy { // proxies for string chars public: CharProxy(String& str, int index); // creation CharProxy& operator=(const CharProxy& rhs); // lvalue CharProxy& operator=(char c); // uses operator char() const; // rvalue // use private: String& theString; // string this proxy pertains to int charIndex; // char within that string // this proxy stands for }; // continuation of String class const CharProxy operator[](int index) const; // for const Strings CharProxy operator[](int index); // for non-const Strings ... friend class CharProxy; private: RCPtr value; }; Other than the addition of the CharProxy class (which we'll examine below), the only difference between this String class and the final String class in Item 29 is that both operator[] functions now return CharProxy objects. Clients of String can generally ignore this, however, and program as if the operator[] functions returned characters (or references to characters see Item 1) in the usual manner: String s1, s2; // reference-counted strings // using proxies ... cout << s1[5]; // still legal, still works s2[5] = 'x'; // also legal, also works s1[3] = s2[8]; // of course it's legal, // of course it works What's interesting is not that this works. What's interesting is how it works. Consider first this statement: cout << s1[5]; The expression s1[5] yields a CharProxy object. No output operator is defined for such objects, so your compilers labor to find an implicit type conversion they can apply to make the call to operator<< succeed (see Item 5). They find one: the implicit conversion from CharProxy to char declared in the CharProxy class. They automatically invoke this conversion operator, and the result is that the string character represented by the CharProxy is printed. This is representative of the CharProxy-to-char conversion that takes place for all CharProxy objects used as rvalues. Lvalue usage is handled differently. Look again at s2[5] = 'x'; As before, the expression s2[5] yields a CharProxy object, but this time that object is the target of an assignment. Which assignment operator is invoked? The target of the assignment is a CharProxy, so the assignment operator that's called is in the CharProxy class. This is crucial, because inside a CharProxy assignment operator, we know that the CharProxy object being assigned to is being used as an lvalue. We therefore know that the string character for which the proxy stands is being used as an lvalue, and we must take whatever actions are necessary to implement lvalue access for that character. Similarly, the statement s1[3] = s2[8]; calls the assignment operator for two CharProxy objects, and inside that operator we know the object on the left is being used as an lvalue and the object on the right as an rvalue. "Yeah, yeah, yeah," you grumble, "show me." Okay. Here's the code for String's operator[] functions: const String::CharProxy String::operator[](int index) const { return CharProxy(const_cast(*this), index); } String::CharProxy String::operator[](int index) { return CharProxy(*this, index); } Each function just creates and returns a proxy for the requested character. No action is taken on the character itself: we defer such action until we know whether the access is for a read or a write. Note that the const version of operator[] returns a const proxy. Because CharProxy::operator= isn't a const member function, such proxies can't be used as the target of assignments. Hence neither the proxy returned from the const version of operator[] nor the character for which it stands may be used as an lvalue. Conveniently enough, that's exactly the behavior we want for the const version of operator[]. Note also the use of a const_cast (see Item 2) on *this when creating the CharProxy object that the const operator[] returns. That's necessary to satisfy the constraints of the CharProxy constructor, which accepts only a non-const String. Casts are usually worrisome, but in this case the CharProxy object returned by operator[] is itself const, so there is no risk the String containing the character to which the proxy refers will be modified. Each proxy returned by an operator[] function remembers which string it pertains to and, within that string, the index of the character it represents: String::CharProxy::CharProxy(String& str, int index) : theString(str), charIndex(index) {} Conversion of a proxy to an rvalue is straightforward we just return a copy of the character represented by the proxy: String::CharProxy::operator char() const { return theString.value->data[charIndex]; } If you've forgotten the relationship among a String object, its value member, and the data member it points to, you can refresh your memory by turning to Item 29. Because this function returns a character by value, and because C++ limits the use of such by-value returns to rvalue contexts only, this conversion function can be used only in places where an rvalue is legal. We thus turn to implementation of CharProxy's assignment operators, which is where we must deal with the fact that a character represented by a proxy is being used as the target of an assignment, i.e., as an lvalue. We can implement CharProxy's conventional assignment operator as follows: String::CharProxy& String::CharProxy::operator=(const CharProxy& rhs) { // if the string is sharing a value with other String objects, // break off a separate copy of the value for this string only if (theString.value->isShared()) { theString.value = new StringValue(theString.value->data); } // now make the assignment: assign the value of the char // represented by rhs to the char represented by *this theString.value->data[charIndex] = rhs.theString.value->data[rhs.charIndex]; return *this; } If you compare this with the implementation of the non-const String::operator in Item 29, you'll see that they are strikingly similar. This is to be expected. In Item 29, we pessimistically assumed that all invocations of the non-const operator[] were writes, so we treated them as such. Here, we moved the code implementing a write into CharProxy's assignment operators, and that allows us to avoid paying for a write when the non-const operator[] is used only in an rvalue context. Note, by the way, that this function requires access to String's private data member value. That's why CharProxy is declared a friend in the earlier class definition for String. The second CharProxy assignment operator is almost identical: String::CharProxy& String::CharProxy::operator=(char c) { if (theString.value->isShared()) { theString.value = new StringValue(theString.value->data); } theString.value->data[charIndex] = c; return *this; } As an accomplished software engineer, you would, of course, banish the code duplication present in these two assignment operators to a private CharProxy member function that both would call. Aren't you the modular one? Limitations The use of a proxy class is a nice way to distinguish lvalue and rvalue usage of operator[], but the technique is not without its drawbacks. We'd like proxy objects to seamlessly replace the objects they stand for, but this ideal is difficult to achieve. That's because objects are used as lvalues in contexts other than just assignment, and using proxies in such contexts usually yields behavior different from using real objects. Consider again the code fragment from Item 29 that motivated our decision to add a shareability flag to each StringValue object. If String::operator[] returns a CharProxy instead of a char&, that code will no longer compile: String s1 = "Hello"; char *p = &s1[1]; // error! The expression s1[1] returns a CharProxy, so the type of the expression on the right-hand side of the "=" is CharProxy*. There is no conversion from a CharProxy* to a char*, so the initialization of p fails to compile. In general, taking the address of a proxy yields a different type of pointer than does taking the address of a real object. To eliminate this difficulty, you'll need to overload the address-of operators for the CharProxy class: class String { public: class CharProxy { public: ... char * operator&(); const char * operator&() const; ... }; ... }; These functions are easy to implement. The const function just returns a pointer to a const version of the character represented by the proxy: const char * String::CharProxy::operator&() const { return &(theString.value->data[charIndex]); } The non-const function is a bit more work, because it returns a pointer to a character that may be modified. This is analogous to the behavior of the non-const version of String::operator[] in Item 29, and the implementation is equally analogous: char * String::CharProxy::operator&() { // make sure the character to which this function returns // a pointer isn't shared by any other String objects if (theString.value->isShared()) { theString.value = new StringValue(theString.value->data); } // we don't know how long the pointer this function // returns will be kept by clients, so the StringValue // object can never be shared theString.value->markUnshareable(); return &(theString.value->data[charIndex]); } Much of this code is common to other CharProxy member functions, so I know you'd encapsulate it in a private member function that all would call. A second difference between chars and the CharProxys that stand for them becomes apparent if we have a template for reference-counted arrays that use proxy classes to distinguish lvalue and rvalue invocations of operator[]: template // reference-counted array class Array { // using proxies public: class Proxy { public: Proxy(Array& array, int index); Proxy& operator=(const T& rhs); operator T() const; ... }; const Proxy operator[](int index) const; Proxy operator[](int index); ... }; Consider how these arrays might be used: Array intArray; ... intArray[5] = 22; // fine intArray[5] += 5; // error! ++intArray[5]; // error! As expected, use of operator[] as the target of a simple assignment succeeds, but use of operator[] on the left-hand side of a call to operator+= or operator++ fails. That's because operator[] returns a proxy, and there is no operator+= or operator++ for Proxy objects. A similar situation exists for other operators that require lvalues, including operator*=, operator<<=, operator--, etc. If you want these operators to work with operator[] functions that return proxies, you must define each of these functions for the Array::Proxy class. That's a lot of work, and you probably don't want to do it. Unfortunately, you either do the work or you do without. Them's the breaks. A related problem has to do with invoking member functions on real objects through proxies. To be blunt about it, you can't. For example, suppose we'd like to work with reference-counted arrays of rational numbers. We could define a class Rational and then use the Array template we just saw: class Rational { public: Rational(int numerator = 0, int denominator = 1); int numerator() const; int denominator() const; ... }; Array array; This is how we'd expect to be able to use such arrays, but, alas, we'd be disappointed: cout << array[4].numerator(); // error! int denom = array[22].denominator(); // error! By now the difficulty is predictable; operator[] returns a proxy for a rational number, not an actual Rational object. But the numerator and denominator member functions exist only for Rationals, not their proxies. Hence the complaints by your compilers. To make proxies behave like the objects they stand for, you must overload each function applicable to the real objects so it applies to proxies, too. Yet another situation in which proxies fail to replace real objects is when being passed to functions that take references to non-const objects: void swap(char& a, char& b); // swaps the value of a and b String s = "+C+"; // oops, should be "C++" swap(s[0], s[1]); // this should fix the // problem, but it won't // compile String::operator[] returns a CharProxy, but swap demands that its arguments be of type char&. A CharProxy may be implicitly converted into a char, but there is no conversion function to a char&. Furthermore, the char to which it may be converted can't be bound to swap's char& parameters, because that char is a temporary object (it's operator char's return value) and, as Item 19 explains, there are good reasons for refusing to bind temporary objects to non-const reference parameters. A final way in which proxies fail to seamlessly replace real objects has to do with implicit type conversions. When a proxy object is implicitly converted into the real object it stands for, a user-defined conversion function is invoked. For instance, a CharProxy can be converted into the char it stands for by calling operator char. As Item 5 explains, compilers may use only one user-defined conversion function when converting a parameter at a call site into the type needed by the corresponding function parameter. As a result, it is possible for function calls that succeed when passed real objects to fail when passed proxies. For example, suppose we have a TVStation class and a function, watchTV: class TVStation { public: TVStation(int channel); ... }; void watchTV(const TVStation& station, float hoursToWatch); Thanks to implicit type conversion from int to TVStation (see Item 5), we could then do this: watchTV(10, 2.5); // watch channel 10 for // 2.5 hours Using the template for reference-counted arrays that use proxy classes to distinguish lvalue and rvalue invocations of operator[], however, we could not do this: Array intArray; intArray[4] = 10; watchTV(intArray[4], 2.5); // error! no conversion // from Proxy to // TVStation Given the problems that accompany implicit type conversions, it's hard to get too choked up about this. In fact, a better design for the TVStation class would declare its constructor explicit, in which case even the first call to watchTV would fail to compile. For all the details on implicit type conversions and how explicit affects them, see Item 5. Evaluation Proxy classes allow you to achieve some types of behavior that are otherwise difficult or impossible to implement. Multidimensional arrays are one example, lvalue/rvalue differentiation is a second, suppression of implicit conversions (see Item 5) is a third. At the same time, proxy classes have disadvantages. As function return values, proxy objects are temporaries (see Item 19), so they must be created and destroyed. That's not free, though the cost may be more than recouped through their ability to distinguish write operations from read operations. The very existence of proxy classes increases the complexity of software systems that employ them, because additional classes make things harder to design, implement, understand, and maintain, not easier. Finally, shifting from a class that works with real objects to a class that works with proxies often changes the semantics of the class, because proxy objects usually exhibit behavior that is subtly different from that of the real objects they represent. Sometimes this makes proxies a poor choice when designing a system, but in many cases there is little need for the operations that would make the presence of proxies apparent to clients. For instance, few clients will want to take the address of an Array1D object in the two-dimensional array example we saw at the beginning of this Item, and there isn't much chance that an ArrayIndex object (see Item 5) would be passed to a function expecting a different type. In many cases, proxies can stand in for real objects perfectly acceptably. When they can, it is often the case that nothing else will do. 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 GameObjects. 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-elses. 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(otherObject); process a SpaceShip-SpaceShip collision; } else if (objectType == typeid(SpaceStation)) { SpaceStation& ss = static_cast(otherObject); process a SpaceShip-SpaceStation collision; } else if (objectType == typeid(Asteroid)) { Asteroid& a = static_cast(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-elses 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 typedefed 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 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 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 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_casts (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(&hitSpaceShip); (*phm)["SpaceStation"] = reinterpret_cast(&hitSpaceStation); (*phm)["Asteroid"] = reinterpret_cast(&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); process a SpaceShip-SpaceShip collision; } void SpaceShip::hitSpaceStation(GameObject& spaceStation) { SpaceStation& station= dynamic_cast(spaceStation); process a SpaceShip-SpaceStation collision; } void SpaceShip::hitAsteroid(GameObject& asteroid) { Asteroid& theAsteroid = dynamic_cast(asteroid); process a SpaceShip-Asteroid collision; } Each of the dynamic_casts 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, HitFunctionPtr > HitMap; pair 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 // 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 makeStringPair(const char *s1, const char *s2) { return pair(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 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 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(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 31: Making functions virtual with respect to more than one object Continue to Miscellany 9 In July 1996, the ISO/ANSI standardization committee changed the default linkage of inline functions to external, so the problem I describe here has been eliminated, at least on paper. Your compilers may not yet be in accord with the standard, however, so your best bet is still to shy away from inline functions with static data. Return 10 The string type in the standard C++ library (see Item E49 and Item 35) uses a combination of solutions two and three. The reference returned from the non-const operator[] is guaranteed to be valid until the next function call that might modify the string. After that, use of the reference (or the character to which it refers) yields undefined results. This allows the string's shareability flag to be reset to true whenever a function is called that might modify the string. Return 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. Return