budd@fog.cs.orst.edu (Tim Budd) (06/13/91)
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.cok@islsun.Kodak.COM (David Cok) (06/13/91)
In article <1991Jun12.193426.8289@lynx.CS.ORST.EDU> budd@fog.cs.orst.edu (Tim Budd) writes: .. details of version of List class with a generic class doing the work and a template which derives from that class to provide type safety. > >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? Not necessarily, the property of two things matching is part of the definition of the things, not of the list of things. To be specific -- and use the example below -- the property of equality of Cards should be a method of Cards, not on CardLists. Thus there would be a method int Card::operator==(Card* b) { return (suit()==b->suit() && rank() == b->rank());} Then the method in CardList would be int CardList::match(void *a, void*b) { return ((Card*)a) == ((Card*)b); } which can easily be put in template form. template<class T> list<T>: public genericList { ... virtual int list<T>::match(void* a, void* b) { return ((T*)a) == ((T*) b); } Now the only problem is that one can only make list's (with the template) of classes which have implemented operator== as the equality to use as a match. One could go a step further and supply a parameter which is a pointer to a member function which could be used as the test for equality (that was *could*, not *should*...) So by defining Card with the equality, CardList can be implemented simply as list<Card> without needing additional subclassing. > >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. David R. Cok Eastman Kodak Company -- Imaging Science Lab cok@Kodak.COM
budd@fog.CS.ORST.EDU (Tim Budd) (06/13/91)
In article <1991Jun13.143127.19044@kodak.kodak.com> cok@islsun.Kodak.COM (David Cok) writes: > >Not necessarily, the property of two things matching is part of the definition >of the things, not of the list of things. To be specific -- and use the >example below -- the property of equality of Cards should be a method of >Cards, not on CardLists. Thus there would be a method > > int Card::operator==(Card* b) { return (suit()==b->suit() && rank() == b->rank());} > This misses the point of point (c). The container classes must be able to hold ARBITRARY objects. In particular, you can't be assured that the things being held will respond to ==. This is because the containers must be able to hold objects that have been developed elsewhere, are perhaps available only in binary, but in any case can't be touched (and you thought dusty decks happened only in FORTRAN!). I agree with David in as much as *IF* you are designing the containers AND he objects they will hold, then overriding == is the correct solution. But it's not the general solution. (I thought about making it the default in a virtual method in the template class, but even that won't work. If the objects being held don't recognize ==, then even if the method is overridden the compiler will still try to compile the original method, and will complain). --tim budd
mullens@jamsun.ic.ornl.gov (James A. Mullens) (06/14/91)
In article <1991Jun13.143127.19044@kodak.kodak.com>, cok@islsun.Kodak.COM (David Cok) writes: |> In article <1991Jun12.193426.8289@lynx.CS.ORST.EDU> budd@fog.cs.orst.edu (Tim Budd) writes: |> .. details of version of List class with a generic class doing the |> work and a template which derives from that class to provide |> type safety. |> > |> >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. [much deleted] |> |> Not necessarily, the property of two things matching is part of the definition |> of the things, not of the list of things. To be specific -- and use the |> example below -- the property of equality of Cards should be a method of |> Cards, not on CardLists. [example code deleted] |> |> Now the only problem is that one |> can only make list's (with the template) of classes which have implemented |> operator== as the equality to use as a match. One could go a step further |> and supply a parameter which is a pointer to a member function which could |> be used as the test for equality (that was *could*, not *should*...) |> |> So by defining Card with the equality, CardList can be implemented simply as |> list<Card> without needing additional subclassing. |> There are 2 types of equality: (1) is this the same object and (2) does this object have the same value (as another object on the list)? My application needs only the first type of equality so I simply use the object's address (instead of a '=='). I also use strings to give many of my objects (which appear on lists) unique names, so I can use string equivalence. The strings aren't there just so I can perform this equality test in the list, it's just that the objects are created from text descriptions of the objects (at run time) and the names are required by the descriptions. My whole approach to implementing lists is different. I have defined some m4 (Unix macro processor) macros which will create the appropriate .c and .h files for a list of a particular type of object. The make utility is used to update the .c and .h files whenever the macro definition changes. This is easy to implement and maintain. I intend to use templates later, but not because there is anything wrong with the way I'm doing it now. jim mullens oak ridge national laboratory mullens@jamsun.ic.ornl.gov