[comp.lang.c++] List Classes

sdm@cs.brown.edu (Scott Meyers) (06/14/91)

In article <1991Jun13.163831.20232@lynx.CS.ORST.EDU> budd@fog.CS.ORST.EDU (Tim Budd) writes:
| 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!).

Sorry, Tim, but David is dead right and you are dead wrong.  If you truly
have objects with protocols you can't change, then you have to define a
class specifically to hold such objects and you have to define an
operator== to compare objects of that class, but the semantics of equality
do *not* belong in the container class (except of course for equality of
container objects).  Try this:

    // DustyDeckHolder objects are just placeholders for DustyDeckObject
    // objects, but I can't change the class declaration for DustyDeckObject
    class DustyDeckHolder {
      private:
        DustyDeckObject *ddop;      // or a reference or an object,
                                    // whatever you like

      public:
        DustyDeckHolder(DustyDeckObject* p): ddop(p) {}

      friend int operator==(const DustyDeckHolder& h1,
                            const DustyDeckHolder& h2);
    };

    int operator==(const DustyDeckHolder& h1, const DustyDeckHolder& h2)
    {
      // code to determine whether *(h1.ddop) == *(h2.ddop)
    }

Now in your generic code you need to determine if two arbitrary objects x
and y are "==", but x and y are both declared as void*.  In your generic
class you declare

    virtual int match(void *a, void *b) = 0;

and in your code you write

    if (match(x, y)) ...

Note that there is no default implementation for match() in the generic
class;  there is *no way* to make sense of void* pointers, you *must* have
some type information before you can do anything with them.

Now in each template class you have:

    template<class T> 
    class List: public GenericList {
      private:
        int match(void *a, void* b) { return *((T*) a) == *((T*) b); }

      friend int operator==(const T& a, const T& b);
    };

The casts are safe because the template class only builds homogeneous
lists.  The only requirement is that anything to be listed *must* provide
an operator==, but in order to use your generic list class there must be
some way to deterime whether two objects are equal anyway, it's just a
question of where you require that logic to be.  In this case, it has to be
inside an operator==, but no subclassing is required of the template
classes.

| 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.

| 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).

You can *always* write the class being put on the list as I showed above,
and hence you can always ensure that an operator== exists.  For objects
where operator== is already defined, just pop them on a (homogeneous,
template-based) list.  For objects where it's not, but where you know how
to determine if they're "==" anyway, write an object-holding class as
above.  For other objects, you're outta luck.

Scott

-------------------------------------------------------------------------------
What do you say to a convicted felon in Providence?  "Hello, Mr. Mayor."