Creating an object-based hierarchy

An issue that has been recurring throughout this book during the demonstration of the container classes Stack and Stash is the “ownership problem.” The “owner” refers to who or what is responsible for calling delete for objects that have been created dynamically (using new). The problem when using containers is that they need to be flexible enough to hold different types of objects. To do this, the containers have held void pointers and so they haven’t known the type of object they’ve held. Deleting a void pointer doesn’t call the destructor, so the container couldn’t be responsible for cleaning up its objects.

One solution was presented in the example C14:InheritStack.cpp, in which the Stack was inherited into a new class that accepted and produced only string pointers. Since it knew that it could hold only pointers to string objects, it could properly delete them. This was a nice solution, but it requires you to inherit a new container class for each type that you want to hold in the container. (Although this seems tedious now, it will actually work quite well in Chapter 16, when templates are introduced.)

The problem is that you want the container to hold more than one type, but you don’t want to use void pointers. Another solution is to use polymorphism by forcing all the objects held in the container to be inherited from the same base class. That is, the container holds the objects of the base class, and then you can call virtual functions – in particular, you can call virtual destructors to solve the ownership problem.

This solution uses what is referred to as a singly-rooted hierarchy or an object-based hierarchy (because the root class of the hierarchy is usually named “Object”). It turns out that there are many other benefits to using a singly-rooted hierarchy; in fact, every other object-oriented language but C++ enforces the use of such a hierarchy – when you create a class, you are automatically inheriting it directly or indirectly from a common base class, a base class that was established by the creators of the language. In C++, it was thought that the enforced use of this common base class would cause too much overhead, so it was left out. However, you can choose to use a common base class in your own projects, and this subject will be examined further in Volume 2 of this book.

To solve the ownership problem, we can create an extremely simple Object for the base class, which contains only a virtual destructor. The Stack can then hold classes inherited from Object:

//: C15:OStack.h

// Using a singly-rooted hierarchy

#ifndef OSTACK_H

#define OSTACK_H

class Object {

public:

  virtual ~Object() = 0;

};

// Required definition:

inline Object::~Object() {}

class Stack {

  struct Link {

    Object* data;

    Link* next;

    Link(Object* dat, Link* nxt) : 

      data(dat), next(nxt) {}

  }* head;

public:

  Stack() : head(0) {}

  ~Stack(){ 

    while(head)

      delete pop();

  }

  void push(Object* dat) {

    head = new Link(dat, head);

  }

  Object* peek() const { 

    return head ? head->data : 0;

  }

  Object* pop() {

    if(head == 0) return 0;

    Object* result = head->data;

    Link* oldHead = head;

    head = head->next;

    delete oldHead;

    return result;

  }

};

#endif // OSTACK_H ///:~

To simplify things by keeping everything in the header file, the (required) definition for the pure virtual destructor is inlined into the header file, and pop( ) (which might be considered too large for inlining) is also inlined.

Link objects now hold pointers to Object rather than void pointers, and the Stack will only accept and return Object pointers. Now Stack is much more flexible, since it will hold lots of different types but will also destroy any objects that are left on the Stack. The new limitation (which will be finally removed when templates are applied to the problem in Chapter 16) is that anything that is placed on the Stack must be inherited from Object. That’s fine if you are starting your class from scratch, but what if you already have a class such as string that you want to be able to put onto the Stack? In this case, the new class must be both a string and an Object, which means it must be inherited from both classes. This is called multiple inheritance and it is the subject of an entire chapter in Volume 2 of this book (downloadable from www.BruceEckel.com). When you read that chapter, you’ll see that multiple inheritance can be fraught with complexity, and is a feature you should use sparingly. In this situation, however, everything is simple enough that we don’t trip across any multiple inheritance pitfalls:

//: C15:OStackTest.cpp

//{T} OStackTest.cpp

#include "OStack.h"

#include "../require.h"

#include <fstream>

#include <iostream>

#include <string>

using namespace std;

// Use multiple inheritance. We want 

// both a string and an Object:

class MyString: public string, public Object {

public:

  ~MyString() {

    cout << "deleting string: " << *this << endl;

  }

  MyString(string s) : string(s) {}

};

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

  requireArgs(argc, 1); // File name is argument

  ifstream in(argv[1]);

  assure(in, argv[1]);

  Stack textlines;

  string line;

  // Read file and store lines in the stack:

  while(getline(in, line))

    textlines.push(new MyString(line));

  // Pop some lines from the stack:

  MyString* s;

  for(int i = 0; i < 10; i++) {

    if((s=(MyString*)textlines.pop())==0) break;

    cout << *s << endl;

    delete s; 

  }

  cout << "Letting the destructor do the rest:"

    << endl;

} ///:~

Although this is similar to the previous version of the test program for Stack, you’ll notice that only 10 elements are popped from the stack, which means there are probably some objects remaining. Because the Stack knows that it holds Objects, the destructor can properly clean things up, and you’ll see this in the output of the program, since the MyString objects print messages as they are destroyed.

Creating containers that hold Objects is not an unreasonable approach – if you have a singly-rooted hierarchy (enforced either by the language or by the requirement that every class inherit from Object). In that case, everything is guaranteed to be an Object and so it’s not very complicated to use the containers. In C++, however, you cannot expect this from every class, so you’re bound to trip over multiple inheritance if you take this approach. You’ll see in Chapter 16 that templates solve the problem in a much simpler and more elegant fashion.