Templates

C++ has a very powerful abstraction mechanism that is exercised during compilation of your program instead of at run-time. It is called templates, but is more generally known outside of C++ as generics or generic programming. You had a peek at a template class named list in the lab introducing you to our C++ development environment. We will eventually cover this more in class, but you can find information about templates in volume 2 of our text (on line).

We can follow the same abstraction approach by using templates. Your problem solver is now a template class that must be "instantiated" with a specific class that conforms to an interface for a configuration. But now, there is no parent class from which it must inherit; the compiler just makes sure it has the right operations. This eliminates the need for pointers, which eliminates the problems mentioned in pointer-based approaches.

To give you a better feel for this, let's compare the two approaches on a simpler problem. The goal is to order a pair of objects. All we know about these objects is that they can be compared.

Using Inheritance

If we were using a pointer/inheritance approach, we would need an abstraction for the comparable objects that would look something like this:

class Comparable {
public:
	virtual bool operator<( const Comparable &other ) = 0; // abstract
};

The holder for the pair of them that also puts them in order (the code is shown inline to save space) is shown next. Note that, to keep the polymorphism, we must use pointers throughout.

class Pair {
public:
	void order() {
		if ( *b < *a ) {
			Comparable *temp( a );
			a = b;
			b = temp;
		}
	}
private:
	Comparable *a, *b;
};

Then we would need to create a subclass for a specific type of thing, say an integer. (This class declaration is clearly incomplete.)

class Integer: public Comparable {
public:
	virtual bool operator<( const Comparable &other ); // concrete
private:
	int value;
};

An additional little gotcha here is the type of the argument to operator<() above. But we won't even get into that! The smart pointer solution attempts to fix this with a run-time assertion check.

Using Templates

The tempate approach is different. We no longer need the abstract base class. Integer could be done this way:

class Integer {
public:
	bool operator<( const Integer &other ); // concrete
private:
	int value;
};

The Pair class would be written as a template:

template < class Comp >
class Pair {
public:
	void order() {
		if ( b < a ) {
			Comp temp( a );
			a = b;
			b = temp;
		}
	}
private:
	Comp a, b;
};

How does this work? Well, when an instance of Pair is declared this way,

Pair< Integer > p;

The compiler will at some point attempt to regenerate the code for order() with Integer substituted for Comp. Since Integer defines operator<() the code compiles successfully. In fact, we could just use plain old int's, too!:

Pair< int > p;

Applying templates to this problem means that your configuration is now the template parameter, just like Comp, and the problem solver becomes the template class, like Pair.

If you are curious, UML represents template classes as parameterized classes.

By the way, Java is expected to have generics in their 1.5 release in early 2004.