maverick@fir.Berkeley.EDU (Vance Maverick) (03/06/91)
I have a problem for which I have not yet found a clean solution in C++. In my application, there are various classes of which I wish to keep lists. So I define a single class List, which handles objects of class Listable, and I make all the things I want lists of (musical notes, names, and other incompatible types) subclasses of Listable. So far so good; but I want the List code to be able to compare two objects, so it can insert items in sorted order, where this matters. I define a virtual member function (actually it's an overloaded operator, but same difference) on Listable, taking an argument of type Listable. On Name, I define such a function taking an argument of type Name; similarly, a Note member function comparing two Notes. So in my insertion code, I have something like this: Listable *member, *newvalue; if (*newvalue < *member) .... Unfortunately, this can't invoke my Note-to-Note or Name-to-Name comparator, since the signature of these functions contains the derived type, and C++ uses the declared type of the right-hand argument in selecting the function to call. To get this to work, I need to define alternate comparators, comparing Note to Listable and Name to Listable. This is unpleasant, because it involves a distasteful cast in the alternate comparator, and because it now allows me to explicitly compare a Note to a Name. Does anybody have a suggestion for how to do this "correctly", lacking parameterized types and runtime method selection on multiple arguments? Thanks, Vance
pal@xanadu.wpd.sgi.com (Anil Pal) (03/06/91)
In article <11687@pasteur.Berkeley.EDU>, maverick@fir.Berkeley.EDU (Vance Maverick) writes: |> |> I have a problem for which I have not yet found a clean solution in C++. |> In my application, there are various classes of which I wish to keep |> lists. So I define a single class List, which handles objects of class |> Listable, and I make all the things I want lists of (musical notes, |> names, and other incompatible types) subclasses of Listable. |> |> So far so good; but I want the List code to be able to compare two |> objects [...]. |> |> Does anybody have a suggestion for how to do this "correctly", lacking |> parameterized types and runtime method selection on multiple arguments? Depends on what you mean by "correctly". I see two cases here, and will describe the "correct" solution (or my interpretation thereof) for each of them. Case 1: Homogeneous lists This one is easy. Use parameterized types (templates, generics). Yes, I know C++ doesn't have them yet, but it will soon (in the standard). And in the meantime, you can fake it with the pre-processor. Case 2: Heterogeneous lists I am assuming here that you want a sorted heterogeneous list, which implies that you have some well-defined ordering function that *can* meaningfully compare a Name to a Note (to use your example). This is not easy to do, but then the requirements aren't trivial. You will, in general, need n-squared comparison functions (where n is the number of Listable classes). And you have to do some manual double-dispatching. For the sake of an example, let me assume just two classes, Name and Note. I also use Comparable instead of Listable as the base class. class Comparable { public: virtual int operator<(Comparable&) = 0; virtual int operator<(Name&) = 0; virtual int operator<(Note&) = 0; // Note - you need to add one more virtual operator // for each class derived from Comparable }; class Note : public Comparable { public: virtual int operator<(Comparable& other); virtual int operator<(Name& other); virtual int operator<(Note& other); }; int Note::operator<(Comparable& other) { return ! (other.operator<(*this)); // Invokes other.operator<(Note&) } int Note::operator<(Note& other) { // Actually compare the two Notes, and return appropriate result } int Note::operator<(Name& other) { // Now both types are known - Note and Name; do appropriate comparison } // Similarly for class Name The key step here is in the Note::operator<(Comparable& other). At this point, the type of one operand (the left one) is determined through the virtual function mechanism. By reversing the operands at this point you determine the type of the other operand, also through the virtual function mechanism. Once both types are determined, the two types determine the appropriate one of the n-squared comparison functions. This method of dispatching first on one argument type, then another is referred to as double-dispatching. -- Anil A. Pal, Silicon Graphics, Inc. pal@sgi.com (415)-335-7279
maverick@fir.Berkeley.EDU (Vance Maverick) (03/08/91)
To all those who have responded via mail or news --
I was obviously unclear about what I wanted to accomplish. I want to use a
single List class to maintain sorted homogeneous lists of various
essentially unrelated classes. The best solution I've seen is
double-dispatch, which is type-safe and accomplishes what I want to, though
it makes for obscure code. For example, if we have
class Base {
public:
virtual int operator < (const Base &) = 0;
virtual int operator >= (const Base &) = 0;
};
class IntVal : public Base {
public:
int val;
int operator < (const IntVal &i)
{ return (val < i.val); }
int operator >= (const IntVal &i)
{ return (val >= i.val); }
/* Comparing an IntVal to a Base? Flip the arguments to
see if the Base isn't really an IntVal after all */
int operator < (const Base &b)
{ return (b >= *this); }
};
class FloatVal : public Base {
public:
float val;
int operator < (const FloatVal &f)
{ return (val < f.val); }
int operator >= (const FloatVal &f)
{ return (val >= f.val); }
/* Comparing a FloatVal to a Base? Flip the arguments to
see if the Base isn't really a FloatVal after all */
int operator < (const Base &b)
{ return (b >= *this); }
};
then comparisons of Base objects will invoke a comparison of values only if
the derived types match at runtime. Thanks for the response,
Vancepal@xanadu.wpd.sgi.com (Anil Pal) (03/08/91)
In article <11764@pasteur.Berkeley.EDU>, maverick@fir.Berkeley.EDU (Vance Maverick) writes: |> |> class Base { |> public: |> virtual int operator < (const Base &) = 0; |> virtual int operator >= (const Base &) = 0; |> }; |> |> class IntVal : public Base { |> public: |> int val; |> |> int operator < (const IntVal &i) |> { return (val < i.val); } |> int operator >= (const IntVal &i) |> { return (val >= i.val); } |> |> /* Comparing an IntVal to a Base? Flip the arguments to |> see if the Base isn't really an IntVal after all */ |> |> int operator < (const Base &b) |> { return (b >= *this); } |> }; Not so fast. Consider Base& x = IntVal(2); Base& y = IntVal(3); if (x < y) ... This will invoke x.operator<(y), which is virtual to IntVal::operator<(Base&) Since there is no Base.operator<(IntVal&), this will call operator<(Base&), which will (through the magic of virtual functions) bring you back to IntVal::operator<(Base&), where, mirabile dictu, you will switch back and call... you guessed it. Infinite loop. To break the cycle, you have to make use of the knowledge that one operand is an IntVal, which means that there has to be a Base::operator<(IntVal&) (and, liekwise, a Base::operator<(FloatVal)). Also, if you want the arguments to be const, you need to declare the operators consts as well, or else you won't be able to do the flip. And finally, you will need to define FloatVal::operator<(IntVal&) and vice versa, as well; they should raise an error condition, given your requirements. -- Anil A. Pal, Silicon Graphics, Inc. pal@wpd.sgi.com (415)-335-7279
davis@barbes.ilog.fr (Harley Davis) (03/12/91)
In article <1991Mar5.215208.21511@dragon.wpd.sgi.com> pal@xanadu.wpd.sgi.com (Anil Pal) writes:
This method of dispatching first on one argument type, then
another is referred to as double-dispatching.
Another way to solve the problem is to define a virtual function on
Listable which returns a numeric equivalent for the object, and then
compare the numbers. This avoids having to write n-squared methods;
you only have to write n. Of course, it assumes that you can sensibly
generate a number for every object, but I don't think that's more
outrageous than comparing Names and Notes.
-- Harley Davis
--
------------------------------------------------------------------------------
nom: Harley Davis ILOG S.A.
net: davis@ilog.fr 2 Avenue Gallie'ni, BP 85
tel: (33 1) 46 63 66 66 94253 Gentilly Cedex, France