Item 41:  Differentiate between inheritance and templates.

Consider the following two design problems:

• Being a devoted student of Computer Science, you want to create classes representing stacks of objects. You'll need several different classes, because each stack must be homogeneous, i.e., it must have only a single type of object in it. For example, you might have a class for stacks of ints, a second class for stacks of strings, a third for stacks of stacks of strings, etc. You're interested only in supporting a minimal interface to the class (see Item 18), so you'll limit your operations to stack creation, stack destruction, pushing objects onto the stack, popping objects off the stack, and determining whether the stack is empty. For this exercise, you'll ignore the classes in the standard library (including stack — see Item 49), because you crave the experience of writing the code yourself. Reuse is a wonderful thing, but when your goal is a deep understanding of how something works, there's nothing quite like diving in and getting your hands dirty.
• Being a devoted feline aficionado, you want to design classes representing cats. You'll need several different classes, because each breed of cat is a little different. Like all objects, cats can be created and destroyed, but, as any cat-lover knows, the only other things cats do are eat and sleep. However, each breed of cat eats and sleeps in its own endearing way.

These two problem specifications sound similar, yet they result in utterly different software designs. Why?

The answer has to do with the relationship between each class's behavior and the type of object being manipulated. With both stacks and cats, you're dealing with a variety of different types (stacks containing objects of type T, cats of breed T), but the question you must ask yourself is this: does the type T affect the behavior of the class? If T does not affect the behavior, you can use a template. If T does affect the behavior, you'll need virtual functions, and you'll therefore use inheritance.

Here's how you might define a linked-list implementation of a Stack class, assuming that the objects to be stacked are of type T:

class Stack {
public:
  Stack();
  ~Stack();

  void push(const T& object);
  T pop();

bool empty() const;             // is stack empty?

private:
  struct StackNode {              // linked list node
    T data;                       // data at this node
    StackNode *next;              // next node in list

    // StackNode constructor initializes both fields
    StackNode(const T& newData, StackNode *nextNode)
    : data(newData), next(nextNode) {}
  };

StackNode *top;                 // top of stack

Stack(const Stack& rhs);               // prevent copying and
  Stack& operator=(const Stack& rhs);    // assignment (see Item 27)
};

Stack objects would thus build data structures that look like this:

The linked list itself is made up of StackNode objects, but that's an implementation detail of the Stack class, so StackNode has been declared a private type of Stack. Notice that StackNode has a constructor to make sure all its fields are initialized properly. Just because you can write linked lists in your sleep is no reason to omit technological advances such as constructors.

Here's a reasonable first cut at how you might implement the Stack member functions. As with many prototype implementations (and far too much production software), there's no checking for errors, because in a prototypical world, nothing ever goes wrong.

Stack::Stack(): top(0) {}      // initialize top to null

void Stack::push(const T& object)
{
  top = new StackNode(object, top);    // put new node at
}                                      // front of list

T Stack::pop()
{
  StackNode *topOfStack = top;    // remember top node
  top = top->next;

T data = topOfStack->data;      // remember node data
  delete topOfStack;

  return data;
}

Stack::~Stack()                   // delete all in stack
{
  while (top) {
    StackNode *toDie = top;       // get ptr to top node
    top = top->next;              // move to next node
    delete toDie;                 // delete former top node
  }
}

bool Stack::empty() const
{ return top == 0; }

There's nothing riveting about these implementations. In fact, the only interesting thing about them is this: you are able to write each member function knowing essentially nothing about T. (You assume you can call T's copy constructor, but, as Item 45 explains, that's a pretty reasonable assumption.) The code you write for construction, destruction, pushing, popping, and determining whether the stack is empty is the same, no matter what T is. Except for the assumption that you can call T's copy constructor, the behavior of a stack does not depend on T in any way. That's the hallmark of a template class: the behavior doesn't depend on the type.

Turning your Stack class into a template, by the way, is so simple, even °Dilbert's pointy-haired boss could do it:

template<class T> class Stack {

...                          // exactly the same as above

};

But on to cats. Why won't templates work with cats?

Reread the specification and note the requirement that "each breed of cat eats and sleeps in its own endearing way." That means you're going to have to implement different behavior for each type of cat. You can't just write a single function to handle all cats, all you can do is specify an interface for a function that each type of cat must implement. Aha! The way to propagate a function interface only is to declare a pure virtual function (see Item 36):

class Cat {
public:
  virtual ~Cat();                     // see Item 14

virtual void eat() = 0;             // all cats eat
  virtual void sleep() = 0;           // all cats sleep
};

Subclasses of Cat — say, Siamese and BritishShortHairedTabby — must of course redefine the eat and sleep function interfaces they inherit:

class Siamese: public Cat {
public:
  void eat();
  void sleep();

  ...

};

class BritishShortHairedTabby: public Cat {
public:
  void eat();
  void sleep();

  ...

};

Okay, you now know why templates work for the Stack class and why they won't work for the Cat class. You also know why inheritance works for the Cat class. The only remaining question is why inheritance won't work for the Stack class. To see why, try to declare the root class of a Stack hierarchy, the single class from which all other stack classes would inherit:

class Stack {      // a stack of anything
public:
  virtual void push(const ??? object) = 0;
  virtual ??? pop() = 0;

  ...

};

Now the difficulty becomes clear. What types are you going to declare for the pure virtual functions push and pop? Remember that each subclass must redeclare the virtual functions it inherits with exactly the same parameter types and with return types consistent with the base class declarations. Unfortunately, a stack of ints will want to push and pop int objects, whereas a stack of, say, Cats, will want to push and pop Cat objects. How can the Stack class declare its pure virtual functions in such a way that clients can create both stacks of ints and stacks of Cats? The cold, hard truth is that it can't, and that's why inheritance is unsuitable for creating stacks.

But maybe you're the sneaky type. Maybe you think you can outsmart your compilers by using generic (void*) pointers. As it turns out, generic pointers don't help you here. You simply can't get around the requirement that a virtual function's declarations in derived classes must never contradict its declaration in the base class. However, generic pointers can help with a different problem, one related to the efficiency of classes generated from templates. For details, see Item 42.

Now that we've dispensed with stacks and cats, we can summarize the lessons of this Item as follows:

• A template should be used to generate a collection of classes when the type of the objects does not affect the behavior of the class's functions.
• Inheritance should be used for a collection of classes when the type of the objects does affect the behavior of the class's functions.

Internalize these two little bullet points, and you'll be well on your way to mastering the choice between inheritance and templates.