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<NLComponent*> 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<NLComponent*> 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<NLComponent*>::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<FSA> pfsa1(FSA::makeFSA());

    // indirectly call FSA copy constructor
    auto_ptr<FSA> 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., `int`s, `char`s, 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 BeingCounted>
    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<class BeingCounted>
    Counted<BeingCounted>::Counted()
    { init(); }

    template<class BeingCounted>
    Counted<BeingCounted>::Counted(const Counted<BeingCounted>&)
    { init(); }

    template<class BeingCounted>
    void Counted<BeingCounted>::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<Printer> {
    public:
      // pseudo-constructors
      static Printer * makePrinter();
      static Printer * makePrinter(const Printer& rhs);

      ~Printer();

      void submitJob(const PrintJob& job);
      void reset();
      void performSelfTest();
      ...

      using Counted<Printer>::objectCount;     // see below
      using Counted<Printer>::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<Printer>`, 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<Printer>*` 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<Printer> {
    public:
      ...
      using Counted<Printer>::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<Printer> {
    public:
      ...
      Counted<Printer>::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<Printer>`, 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<Printer>`) 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<Printer>` constructors, and because `Counted<Printer>` is a base class of `Printer`, we know that a `Counted<Printer>` constructor will always be called before a `Printer` constructor. If too many objects are created, a `Counted<Printer>` 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<class BeingCounted>                 // defines numObjects
    int Counted<BeingCounted>::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<Printer>`::`maxObjects` to 10. If, on the other hand, we want to allow up to 16 file descriptor objects, we should initialize `Counted<FileDescriptor>`::`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<Printer>::maxObjects = 10;

Similarly, the author of `FileDescriptor` must add this:

    const size_t Counted<FileDescriptor>::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 `UPNumber`s 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,

1. Call `operator` `new` for first object
2. Call constructor for first object
3. Call `operator` `new` for second object
4. 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:

1. Call `operator` `new` for first object
2. Call `operator` `new` for second object
3. Call constructor for first object
4. 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 `delete`d. 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<RawAddress> 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<RawAddress> 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<RawAddress>::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<const void*>(this);

      // look up the pointer in the list of addresses
      // returned by operator new
      list<RawAddress>::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<const void*>(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_cast`ing 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_cast`ing `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<class T>                    // 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<class T>                    // 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 T>
    class LogEntry {
    public:
      LogEntry(const T& objectToBeModified);
      ~LogEntry();
    };

    void editTuple(DBPtr<Tuple>& pt)
    {
      LogEntry<Tuple> 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 T>
    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<TreeNode> ptn1(new TreeNode);

    auto_ptr<TreeNode> ptn2 = ptn1;      // call to copy ctor;
                                         // what should happen?

    auto_ptr<TreeNode> ptn3;

    ptn3 = ptn2;                         // call to operator=;
                                         // what should happen?

If we just copied the internal dumb pointer, we'd end up with two `auto_ptr`s 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_ptr`s 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<T>` 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 T>
    class auto_ptr {
    public:
      ...

      auto_ptr(auto_ptr<T>& rhs);        // copy constructor

      auto_ptr<T>&                       // assignment
      operator=(auto_ptr<T>& rhs);       // operator

      ...
    };

    template<class T>
    auto_ptr<T>::auto_ptr(auto_ptr<T>& rhs)
    {
      pointee = rhs.pointee;             // transfer ownership of
                                         // *pointee to *this

      rhs.pointee = 0;                   // rhs no longer owns
    }                                    // anything

    template<class T>
    auto_ptr<T>& auto_ptr<T>::operator=(auto_ptr<T>& 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_ptr`s by value is often a very bad idea. Here's why:

    // this function will often lead to disaster
    void printTreeNode(ostream& s, auto_ptr<TreeNode> p)
    { s << *p; }

    int main()
    {
      auto_ptr<TreeNode> 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_ptr`s 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_ptr`s 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<TreeNode>& 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_ptr`s 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' `const`ness (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<class T>
    SmartPtr<T>::~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<class T>
    T& SmartPtr<T>::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<Tuple>& pt)
    {
      LogEntry<Tuple> 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<class T>
    T* SmartPtr<T>::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<TreeNode> 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 T>
    class SmartPtr {
    public:
      ...
      operator void*();                  // returns 0 if the smart
      ...                                // ptr is null, nonzero
    };                                   // otherwise

    SmartPtr<TreeNode> 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<Apple> pa;
    SmartPtr<Orange> po;

    ...

    if (pa == po) ...                    // this compiles!

Even if there is no `operator==` taking a `SmartPtr<Apple>` and a `SmartPtr<Orange>`, 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 T>
    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<TreeNode> 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<Apple> pa;
    SmartPtr<Orange> 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<Tuple> pt;

    ...

    normalize(pt);                       // error!

The call will fail to compile, because there is no way to convert a `DBPtr<Tuple>` 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<class T>                   // as before
    class DBPtr {
    public:
      ...
      operator T*() { return pointee; }
      ...
    };

    DBPtr<Tuple> 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<Tuple>& pt)
    {
      Tuple *rawTuplePtr = pt;           // converts DBPtr<Tuple> 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<Tuple>` pointers, however, fails to compile:

    DBPtr<Tuple> pt1, pt2;

    ...

    merge(pt1, pt2);                     // error! No way to convert pt1 and
                                         // pt2 to TupleAccessors objects

That's because a conversion from `DBPtr<Tuple>` to `TupleAccessors` calls for two user-defined conversions (one from `DBPtr<Tuple>` 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<Tuple> 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<MusicProduct>& pmp,
                        int numTimes);

    SmartPtr<Cassette> funMusic(new Cassette("Alapalooza"));
    SmartPtr<CD> 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<CD>` or a `SmartPtr<Cassette>` to a `SmartPtr<MusicProduct>`. 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<CD>` or `SmartPtr<Cassette>` inherits from`SmartPtr<MusicProduct>`. 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<MusicProduct>` to the smart pointer classes for `Cassette` and `CD`:

    class SmartPtr<Cassette> {
    public:
      operator SmartPtr<MusicProduct>()
      { return SmartPtr<MusicProduct>(pointee); }

      ...

    private:
      Cassette *pointee;
    };

    class SmartPtr<CD> {
    public:
      operator SmartPtr<MusicProduct>()
      { return SmartPtr<MusicProduct>(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<class T>                    // template class for smart
    class SmartPtr {                     // pointers-to-T objects
    public:
      SmartPtr(T* realPtr = 0);

      T* operator->() const;
      T& operator*() const;

      template<class newType>             // template function for
      operator SmartPtr<newType>()        // implicit conversion ops.
      {
        return SmartPtr<newType>(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<T>` 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<MusicProduct>& pmp,
                        int howMany);

    SmartPtr<Cassette> funMusic(new Cassette("Alapalooza"));
    SmartPtr<CD> 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<Cassette>`. The function `displayAndPlay` expects a `SmartPtr<MusicProduct>` object. Compilers detect the type mismatch and seek a way to convert `funMusic` into a `SmartPtr<MusicProduct>` object. They look for a single-argument constructor (see Item 5) in the `SmartPtr<MusicProduct>` class that takes a `SmartPtr<Cassette>`, but they find none. They look for an implicit type conversion operator in the `SmartPtr<Cassette>` class that yields a `SmartPtr<MusicProduct>` 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<Cassette>`, when instantiated with `newType` bound to `MusicProduct`, generates the necessary function. They instantiate the function, yielding the following code:

    SmartPtr<Cassette>::  operator SmartPtr<MusicProduct>()
    {
      return SmartPtr<MusicProduct>(pointee);
    }

Will this compile? For all intents and purposes, nothing is happening here except the calling of the `SmartPtr<MusicProduct>` constructor with `pointee` as its argument, so the real question is whether one can construct a `SmartPtr<MusicProduct>` object with a `Cassette*` pointer. The `SmartPtr<MusicProduct>` 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<MusicProduct>` is therefore successful, and the conversion of the `SmartPtr<Cassette>` to `SmartPtr<MusicProduct>` 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<class T>                    // as above, including member tem-
    class SmartPtr { ... };              // plate for conversion operators

    void displayAndPlay(const SmartPtr<MusicProduct>& pmp,
                        int howMany);

    void displayAndPlay(const SmartPtr<Cassette>& pc,
                        int howMany);

    SmartPtr<CasSingle> dumbMusic(new CasSingle("Achy Breaky Heart"));

    displayAndPlay(dumbMusic, 1);        // error!

In this example, `displayAndPlay` is overloaded, with one function taking a `SmartPtr<MusicProduct>` object and the other taking a `SmartPtr<Cassette>` object. When we invoke `displayAndPlay` with a `SmartPtr<CasSingle>`, we expect the `SmartPtr<Cassette>` 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<CasSingle>` to `SmartPtr<Cassette>` is no better than the conversion to `SmartPtr<MusicProduct>`.

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<CD> 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<const CD> 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<CD> p;                          // non-const object,
                                             // non-const pointer

    SmartPtr<const CD> p;                    // const object,
                                             // non-const pointer

    const SmartPtr<CD> p = &goodCD;          // non-const object,
                                             // const pointer

    const SmartPtr<const CD> 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-`const`s; 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<CD> pCD = new CD("Famous Movie Themes");

    SmartPtr<const CD> pConstCD = pCD;       // fine?

`SmartPtr<CD>` and `SmartPtr<const` `CD>` 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<CD>` to objects of type `SmartPtr<const` `CD>`. 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-`const`s that you can't do with pointers-to-`const`s.

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<class T>                    // 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<class T>                    // smart pointers to
    class SmartPtr:                      // non-const objects
      public SmartPtrToConst<T> {
      ...                                // 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<T>` objects use the `constPointee` pointer, `SmartPtr<T>` 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<CD> pCD = new CD("Famous Movie Themes");

    SmartPtrToConst<CD> 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-`const`s 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;
    };

`RCObject`s 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 `RCObject`s 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 `delete`ing `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 `RCObject`s 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 T>
    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<class T>
    RCPtr<T>::RCPtr(T* realPtr): pointee(realPtr)
    {
      init();
    }

    template<class T>
    RCPtr<T>::RCPtr(const RCPtr& rhs): pointee(rhs.pointee)
    {
      init();
    }

    template<class T>
    void RCPtr<T>::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<T>` 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<T>` 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<T>` 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<StringValue>` 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<class T>
    RCPtr<T>& RCPtr<T>::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<class T>
    RCPtr<T>::~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<class T>
    T* RCPtr<T>::operator->() const { return pointee; }

    template<class T>
    T& RCPtr<T>::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<class T>                       // 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<StringValue> 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<class T>
    void RCPtr<T>::init()
    {
      if (pointee == 0) return;

      if (pointee->isShareable() == false) {
        pointee = new T(*pointee);
      }

      pointee->addReference();
    }

    template<class T>
    RCPtr<T>::RCPtr(T* realPtr)
    : pointee(realPtr)
    { init(); }

    template<class T>
    RCPtr<T>::RCPtr(const RCPtr& rhs)
    : pointee(rhs.pointee)
    { init(); }

    template<class T>
    RCPtr<T>::~RCPtr()
    { if (pointee)pointee->removeReference(); }

    template<class T>
    RCPtr<T>& RCPtr<T>::operator=(const RCPtr& rhs)
    {
      if (pointee != rhs.pointee) {
        if (pointee) pointee->removeReference();

        pointee = rhs.pointee;
        init();
      }

    return *this;
    }

    template<class T>
    T* RCPtr<T>::operator->() const { return pointee; }

    template<class T>
    T& RCPtr<T>::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 `RCPtr`s 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 T>
    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<class T>
    void RCIPtr<T>::init()
    {
      if (counter->isShareable() == false) {
        T *oldValue = counter->pointee;
        counter = new CountHolder;
        counter->pointee = new T(*oldValue);
      }

      counter->addReference();
    }

    template<class T>
    RCIPtr<T>::RCIPtr(T* realPtr)
    : counter(new CountHolder)
    {
      counter->pointee = realPtr;
      init();
    }

    template<class T>
    RCIPtr<T>::RCIPtr(const RCIPtr& rhs)
    : counter(rhs.counter)
    { init(); }

    template<class T>
    RCIPtr<T>::~RCIPtr()
    { counter->removeReference(); }

    template<class T>
    RCIPtr<T>& RCIPtr<T>::operator=(const RCIPtr& rhs)
    {
      if (counter != rhs.counter) {
        counter->removeReference();
        counter = rhs.counter;
        init();
      }
      return *this;
    }

    template<class T>                          // implement the copy
    void RCIPtr<T>::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<class T>                           // const access;
    const T* RCIPtr<T>::operator->() const      // no COW needed
    { return counter->pointee; }

    template<class T>                           // non-const
    T* RCIPtr<T>::operator->()                  // access; COW
    { makeCopy(); return counter->pointee; }    // needed

    template<class T>                           // const access;
    const T& RCIPtr<T>::operator*() const       // no COW needed
    { return *(counter->pointee); }

    template<class T>                           // non-const
    T& RCIPtr<T>::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<Widget> 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 `delete`ing `this`. This is a safe operation only if the object was allocated by calling `new`, so we need some way of ensuring that `RCObject`s 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 `RCObject`s 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 `RCObject`s. There is no possibility that random clients can accidently (or maliciously) create `RCObject`s 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 T>
    class Array2D {
    public:
      Array2D(int dim1, int dim2);
      ...

    };

Now we can define the arrays we want:

    Array2D<int> data(10, 20);             // fine

    Array2D<float> *data =
      new Array2D<float>(10, 20);          // fine

    void processInput(int dim1, int dim2)
    {
      Array2D<int> 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 T>
    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 T>
    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 T>
    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<float> 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 `const`ness, 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<StringValue> 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<String&>(*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 `char`s and the `CharProxy`s 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<class T>                        // reference-counted array
    class Array {                            // using proxies
    public:
      class Proxy {
      public:
        Proxy(Array<T>& 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<int> 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<T>`::`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<Rational> 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 `Rational`s, 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<int> intArray;

    intArray[4] = 10;

    watchTV(intArray[4], 2.5);              // error! no conversion
                                            // from Proxy<int> 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 `GameObject`s. If the collision processing depended only on the dynamic type of `object1`, you could make `processCollision` virtual in `GameObject` and call `object1.processCollision(object2)`. You could do the same thing with `object2` if the details of the collision depended only on its dynamic type. What happens in the collision, however, depends on both their dynamic types. A function call that's virtual on only one object, you see, is not enough.

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

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

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

Using Virtual Functions and RTTI

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

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

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

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

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

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

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

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

        process a SpaceShip-SpaceShip collision;

      }

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

        process a SpaceShip-SpaceStation collision;

      }

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

        process a SpaceShip-Asteroid collision;

      }

      else {
        throw CollisionWithUnknownObject(otherObject);
      }
    }

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

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

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

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

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

Using Virtual Functions Only

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

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

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

    };

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

    };

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

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

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

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

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

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

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

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

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

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

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

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

Emulating Virtual Function Tables

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

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

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

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

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

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

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

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

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

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

Here's the declaration of `lookup`:

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

      static HitFunctionPtr lookup(const GameObject& whatWeHit);

      ...
    };

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Initializing Emulated Virtual Function Tables

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

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

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

      ...

    }

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

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

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

    };

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

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

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

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

      ...

    };

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

    }

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

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

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

      return phm;
    }

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

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

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

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

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

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

      return phm;
    }

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

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

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

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

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

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

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

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

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

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

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

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

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

      return phm;
    }

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

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

      process a SpaceShip-SpaceShip collision;

    }

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

      process a SpaceShip-SpaceStation collision;

    }

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

      process a SpaceShip-Asteroid collision;

    }

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

Using Non-Member Collision-Processing Functions

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

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

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

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

    namespace {                     // unnamed namespace — see below

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

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

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

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

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

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

      ...

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

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

      HitMap * initializeCollisionMap();

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

    } // end namespace

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

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

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

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

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

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

    namespace {          // unnamed namespace again — see below

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

    } // end namespace

    namespace {          // still the unnamed namespace — see below

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

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

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

      ...

      return phm;
    }

    } // end namespace

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

    namespace {          // I explain this below — trust me

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

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

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

        return (*mapEntry).second;
      }

    } // end namespace

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

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

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

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

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

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

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

Maybe.

Inheritance and Emulated Virtual Function Tables

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

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

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

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

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

Initializing Emulated Virtual Function Tables (Reprise)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    ...

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

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

    class Satellite: public GameObject { ... };

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

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

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

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

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

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

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

Back to Item 31: Making functions virtual with respect to more than one object
Continue to Chapter 6: Miscellany

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

10 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

11 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