Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!ogicse!orstcs!fog.CS.ORST.EDU!budd
From: budd@fog.cs.orst.edu (Tim Budd)
Newsgroups: comp.lang.c++
Subject: To template or not
Message-ID: <1991Jun12.193426.8289@lynx.CS.ORST.EDU>
Date: 12 Jun 91 19:34:26 GMT
Sender: @lynx.CS.ORST.EDU
Organization: Computer Science Department, Oregon State Univ.
Lines: 96
Originator: budd@fog.CS.ORST.EDU
Nntp-Posting-Host: fog.cs.orst.edu

To template or not?  (or why templates are not the WHOLE answer).

Recently I made available to the usenet commnity a number of data structure 
classes, along with a short report on their design.   
Some of the objectives in this design were
a) achieve as much type safety as possible.
b) achieve as much code reuse as possible (including at the object code level)
c) the containers should be able to hold (a pointer to) any type of object.
	(i.e. no assumptions about the nature of the objects being held).

Because of (b) I avoided using templates - at least in the systems I have
seen to date templates duplicate source code, and thus duplicate object
code as well.  On the other hand, my design therefore required users to
create new classes (admittedly ones with almost exclusively simple in-line 
functions) to achive (a).  A few objected (that is the nature of this
paradigm, isn't it?) that this was unnecessarily difficult, and that with
templates the subclassing was not necessary, and therefore less error-prone.
The purpose of this note is to admit that they are right, but only 80% right.

It was pointed out that templates should not be so easily dismissed.  In
particular, a template'd class that inherits from another class that does
all the work could give the best of all possible worlds.  
(I'll put an example at the end of this note - I don't want to distract you
right now).  The template class could provide (a), and although the
template class is duplicated for each type of instantiation, since the 
majority of methods are in-line this is no large problem.

Well, this works fine with ONE small exception.  In order to test whether
something is already in the container, or remove it from the container, you
need some notion of what it means for two things to match.  This is
inheritantly application-specific (assumption c - we can't assume the items
in the container will respond to ANY message, not even an equality test).
In my original design, I achieved this by defining a virtual method
``match(void *, void *)'' which was required to be overridden by
subclasses.   With templates I can move this forward epsilon (making the
arguments pointers to the right type), but it is STILL the case that the
operation is inheritantly application specific.  It seems to me that the
best way to handle this is STILL to make a new subclass.  So even with
templates, you end up subclassing.  Right?

To illustrate, the example.  ``genericList'' is my name for the
void-holding list class.  Here is the template'd class.

template<class T> class list<T> : public genericList {
public:
	void add(T * ele)
		{ genericList::addToEnd(ele); }

	T * current()
		{ return (T *) genericList::current(); }

	int includes(T * ele)
		{ return genericList::includes(ele); }

	T * remove(T * ele)
		{ return (T *) genericList::remove(ele); }

	virtual int equal(T *, T *);

protected:
	//	match invokes equal - users should now override equal
	virtual int match(void *, void *);
};

template<class T> int list<T>::equal(T * a, T * b)
{	return a == b; }

template<class T> int list<T>::match(void * a, void * b)
{	return equal((T *) a, (T *) b); }

Now, suppose we want to make a list of cards.  Here is what I need to do
if two cards are equal if they have the same rank and suit (even if they
aren't pointer-equivalent).

class CardList : public list<Card> {
public:
	virtual int equal(Card *, Card *);
};

int CardList::equal(Card * a, Card * b)
{
	return (a->rank() == b->rank()) && (a->suit() == b->suit());
}

So the whole point is that yes templates can make SOME things easier and
less error prone, and are therefore probably a GOOD THING (and I will
include them in the next release of my generic classes), but like any tool
they aren't the only solution to all problems.

--tim budd

p.s. I've also received a large number of messages of the sort ``it doesn't
compile on xxx'', for which I am grateful, and a few which also said ``and
here is why and how you can fix it'' for which I am even more grateful.
It was also pointed out that ``generic'' might be a bad choice of prefix,
since it means something else on a few C++ systems.