jr@hpgnd.grenoble.hp.com (Jean-Ren BOUVIER) (06/03/91)
I'm looking for ideas in the classical area of "list" packages. I want
to define a "List" class which could be the base class of other objects
so that these could then be put on linked lists.
In a more C++-ish way, I'd like to have the following:
class List {
// details
List *next; // I also accept solutions with "next" defined
// as a (virtual) function.
};
class SomeListableObject: public List /* may have other parents */ {
// details
};
// a few lines later ...
SomeListableObject *list;
// ...
// assignment to list
// ...
while(list) {
// do something
list = list->next;
}
I DON'T want to consider solutions based on templates (List<Object>
types) or generic classes - as I don't want to replicate code.
My problem is that "next" holds (or returns) a pointer to a List, not to
a SomeListableObject, i.e. the above code won't compile, unless I
introduce a cast like:
list = (SomeListableObject*)list->next;
Is there a solution that avoids that cast and which doesn't use the
preprocessor ?mittle@blinn.watson.ibm.com (Josh Mittleman) (06/07/91)
> My problem is that "next" holds (or returns) a pointer to a List, not to > a SomeListableObject, i.e. the above code won't compile, unless I > introduce a cast like: > > list = (SomeListableObject*)list->next; > > Is there a solution that avoids that cast and which doesn't use the > preprocessor ? No. That's why everyone is so pleased at the advent of templates. A question for the general audience: Will templates as implemented in v3 duplicate code? =========================================================================== Josh Mittleman (mittle@watson.ibm.com or joshua@paul.rutgers.edu) J2-C28 T.J. Watson Research Center, PO Box 704, Yorktown Heights, NY 10598
chip@tct.com (Chip Salzenberg) (06/10/91)
According to jr@hpgnd.grenoble.hp.com (Jean-Ren BOUVIER): >I'm looking for ideas in the classical area of "list" packages. ... > >I DON'T want to consider solutions based on templates (List<Object> >types) or generic classes - as I don't want to replicate code. Well, then, you've got very few alternatives. In C++, you cannot have all three of minimal-code polymorphism, type safety and involiate base classes. That is because the three approaches to the downcasting problem fall short in one way or another: 1. Templates (sometimes implemented with the preprocessor) almost always result in some duplicate code. 2. Brute-force downcasting completely trashes type safety. 3. Virtual downcast functions require modifying the base class for each new derivation. There is no magic bullet. Choose your poison and make it work. -- Chip Salzenberg at Teltronics/TCT <chip@tct.com>, <uunet!pdn!tct!chip> perl -e 'sub do { print "extinct!\n"; } do do()'
John.Montbriand@weyr.FIDONET.ORG (John Montbriand) (06/11/91)
well, I've tried several solutions to the problem myself. basically it always comes down to the problem of the base class providing all the functions you want without returning the correct types for subclasses. However, I have seen some interesting solutions done with #define macros. I think there's an example in Stroustrup's book... good luck.... -- John Montbriand - via FidoNet node 1:140/22 UUCP: ...!herald!weyr!John.Montbriand Domain: John.Montbriand@weyr.FIDONET.ORG Standard Disclaimers Apply...
jr@hpgnd.grenoble.hp.com (Jean-Ren BOUVIER) (06/11/91)
A while ago, I posted a note about how to define a list class without using the preprocessor, generic classes and casts. I want to thank all of you who've sent me suggestions and summarize your inputs. As Kevin Coombes states it, there seems to be no solution: |From: kevin@math.lsa.umich.edu | |You ask (essentially): can I create a list class to hold |arbitrary kinds of objects, without templates, without |using the preprocessor, and without explicit casts? |The answer is no. Personally, I've decided on the explicit |cast approach, since my compiler doesn't support templates |and I figure I'd rather reuse the same code without doubling |the size of the executable file. I may change my mind, though.... |Best, | Kevin Coombes <krc@mayme.umd.edu> I received a number of solutions, but I should have explained more precisely what my goals were: 1- I don't want to replicate code which has no reason to be duplicated, and I don't want derived classes writers to have to provide code specific to list handling. 2- I want to have a natural interface, i.e. being able to access my next element in a list by using something like "list->next" or "list->next()", the latter being easily made similar to the former by #defining "next" to be "next()" (I know, I explicitely forbade the use of the preprocessor :-)). Still, quite a few proposed solutions are interesting (I'll steal a few ideas from them) but they don't meat my goals, most of them because they define (member) functions to scan the list. One proposal is quite close to meeting my requirements, it is the one submitted by Amit Jayant Patel (Paul Connors had a similar suggestion): |From: Amit Jayant Patel <amitp@marsh.rice.edu> | class List; | typedef List *ListPtr; | | class List { | // no List *next; | virtual ListPtr& Next() = 0; | }; | | class SomeListableObject: public List { | SomeListableObject *next; | ListPtr& Next() { return next; } | }; //.... | SomeListableObject *list; | while( list ) { | list = list -> next; | } However, it fails to fully reach goal #1, as the derived class must provide the virtual "next()" function along with a "next" pointer. On the other hand, the code required from the derived class writer is very small. David Jones also sent me a full list package which doesn't require its user to write list handling code, but which doesn't meet my interface requirements. thanks for your help and time, Jean-Rene.
budd@fog.CS.ORST.EDU (Tim Budd) (06/11/91)
In article <28539115.4D91@tct.com> chip@tct.com (Chip Salzenberg) writes: > 1. Templates (sometimes implemented with the preprocessor) almost > always result in some duplicate code. > > 2. Brute-force downcasting completely trashes type safety. > > 3. Virtual downcast functions require modifying the base class > for each new derivation. > >There is no magic bullet. Choose your poison and make it work. I think these opinions are common, but misplaced. I used to hold some of them myself. Actually I do agree with (1), and I usually avoid templates when I can for just this reason. And if I accept ``Brute-force'' then I guess I agree with 2. What these do NOT imply, however, it that it is impossible to generate data structure classes that have the property that: a) data structures holding different types of objects can share the same methods (that is, new code is not created for every new type of object you hold in your container) b) this is achived with complete type-safety. As evidence (and I don't want to sound like I'm tooting my own horn here, I certain others have made the same observations, only I don't have the information to point to them) I would point to the generic data structure classes I have written. These, and a Latex description, can be obtained by sending mail to ``oopintro@cs.orst.edu'' with subject line ``Generic''. --tim budd, budd@cs.orst.edu
wicklund@intellistor.com (Tom Wicklund) (06/12/91)
In <28539115.4D91@tct.com> chip@tct.com (Chip Salzenberg) writes: >According to jr@hpgnd.grenoble.hp.com (Jean-Ren BOUVIER): >>I'm looking for ideas in the classical area of "list" packages. ... >> >>I DON'T want to consider solutions based on templates (List<Object> >>types) or generic classes - as I don't want to replicate code. >Well, then, you've got very few alternatives. In C++, you cannot have >all three of minimal-code polymorphism, type safety and involiate base >classes. That is because the three approaches to the downcasting >problem fall short in one way or another: I think what's desired (and should be implementable) is a way to define a list class using templates and have the compiler be smart enough to create a single implementation for the list methods. This should be possible by having additional information (such as a pointer to the copy constructor for the item being placed in the list) passed into member functions -- doable but not common in today's compiler technology.
jac@gandalf.llnl.gov (James A. Crotinger) (06/13/91)
jr@hpgnd.grenoble.hp.com (Jean-Ren BOUVIER) writes: > 2- I want to have a natural interface, i.e. being able to access my > next element in a list by using something like "list->next" or > "list->next()", the latter being easily made similar to the former by > #defining "next" to be "next()" (I know, I explicitely forbade the > use of the preprocessor :-)). I've found it much more useful to have a basic list which has no next() capability, and supplement it with a corresponding ListIterator class. This allows you to have multiple ListIterators instantiated simultaneously for the same List, which is sometimes useful. The list class which I've been using keeps a list of Object *'s. The class library implements type-safe cast operators for all classes inhereting from Object. Furthermore, if you want a specific class (say, a StringList) which doesn't require calling the cast operator explicitly all the time, you just build one from inheriting from List and ListIterator. I don't always like the indirection which is necessary when using a List of pointers. However, sans exception handling, I don't really know how to implement a robust ListIterator class which returns objects. Jim -- ----------------------------------------------------------------------------- James A. Crotinger Lawrence Livermore Natl Lab // The above views jac@moonshine.llnl.gov P.O. Box 808; L-630 \\ // are mine and are not (415) 422-0259 Livermore CA 94550 \\/ necessarily those of LLNL
chip@tct.com (Chip Salzenberg) (06/19/91)
According to wicklund@intellistor.com (Tom Wicklund): >I think what's desired (and should be implementable) is a way to >define a list class using templates and have the compiler be smart >enough to create a single implementation for the list methods. That can already be done with templates. Create a ListBase class with all the interesting code. Then create List<class T> template in which all member functions are inline. Presto. -- Chip Salzenberg at Teltronics/TCT <chip@tct.com>, <uunet!pdn!tct!chip> "You can call Usenet a democracy if you want to. You can call it a totalitarian dictatorship run by space aliens and the ghost of Elvis. It doesn't matter either way." -- Dave Mack
wicklund@intellistor.com (Tom Wicklund) (06/19/91)
In <285E7568.4E93@tct.com> chip@tct.com (Chip Salzenberg) writes: >According to wicklund@intellistor.com (Tom Wicklund): >>I think what's desired (and should be implementable) is a way to >>define a list class using templates and have the compiler be smart >>enough to create a single implementation for the list methods. >That can already be done with templates. Create a ListBase class with >all the interesting code. Then create List<class T> template in which >all member functions are inline. Presto. But the challenge is to do this without requiring inline functions. A list class shouldn't need to know anything about the objects which are being placed in the list except for size (depending on implementation) and the compiler can easily pass the size to a method if required. Unfortunately it requires better compiler technology than most current compilers. It should be possible to break template implementations down into various groups depending on the amount of code duplication required: 1. No duplication -- e.g. a list class using pointers to the object. 2. Needs object characteristics such as size (e.g. array of object), otherwise no duplication. 3. Needs specific methods (e.g. sorted array of object requires comparison), otherwise no duplication. At some point a function becomes complex enough that duplicate code is simpler than tracking all of the involved member functions. Unfortunately, avoiding duplicate code requires that the compiler have the template class implementation available when compiling any code using that class, which means either the compiler handles all source to the program at once or a very smart linker.
jgro@lia (Jeremy Grodberg) (06/21/91)
In article <1991Jun19.151546.15605@intellistor.com> wicklund@intellistor.com (Tom Wicklund) writes: >In <285E7568.4E93@tct.com> chip@tct.com (Chip Salzenberg) writes: > >>According to wicklund@intellistor.com (Tom Wicklund): >>>I think what's desired (and should be implementable) is a way to >>>define a list class using templates and have the compiler be smart >>>enough to create a single implementation for the list methods. > >>That can already be done with templates. Create a ListBase class with >>all the interesting code. Then create List<class T> template in which >>all member functions are inline. Presto. > >But the challenge is to do this without requiring inline functions. A >list class shouldn't need to know anything about the objects which are >being placed in the list except for size (depending on implementation) >and the compiler can easily pass the size to a method if required. >Unfortunately it requires better compiler technology than most current >compilers. This is not entirely true. The list class needs to know the type of object that is being added and extracted. Templates allow for compile-time checking, whereas other methods require run-time checking. Yes, it is a little inelegant to duplicate the code, but it is not much code to duplicate. We aren't using computers with 4 K of core and which execute a few thousand instructions per second anymore. I'm getting tired of people complaining about implementations which waste a few hundred bytes of code without ackowledging the benefit of increased reliability and decreased programming time. In many cases, templates even produce more time-efficient code. Don't get me wrong; I'd love to have a solution which provides all the benefits of templates without the extra code, but in the mean time, I think the cost is well worth it. -- Jeremy Grodberg "Show me a new widget that's bug-free, and I'll show jgro@lia.com you something that's been through several releases."
dmg@ssc-vax (David M Geary) (06/22/91)
In article <1991Jun20.220432.955@lia> jgro@lia.com (Jeremy Grodberg) writes: ]In article <1991Jun19.151546.15605@intellistor.com> wicklund@intellistor.com (Tom Wicklund) writes: ]>In <285E7568.4E93@tct.com> chip@tct.com (Chip Salzenberg) writes: ]> ]>>According to wicklund@intellistor.com (Tom Wicklund): ]>>>I think what's desired (and should be implementable) is a way to ]>>>define a list class using templates and have the compiler be smart ]>>>enough to create a single implementation for the list methods. ]> ]>>That can already be done with templates. Create a ListBase class with ]>>all the interesting code. Then create List<class T> template in which ]>>all member functions are inline. Presto. ]> ]>But the challenge is to do this without requiring inline functions. A ]>list class shouldn't need to know anything about the objects which are ]>being placed in the list except for size (depending on implementation) ]>and the compiler can easily pass the size to a method if required. ]>Unfortunately it requires better compiler technology than most current ]>compilers. ] ]This is not entirely true. The list class needs to know the type of ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ]object that is being added and extracted. Templates allow for ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Why? ]compile-time checking, whereas other methods require run-time checking. ]Yes, it is a little inelegant to duplicate the code, but it is not ]much code to duplicate. ] ]We aren't using computers with 4 K of core and which execute a few ]thousand instructions per second anymore. I'm getting tired of people ]complaining about implementations which waste a few hundred bytes of ]code without ackowledging the benefit of increased reliability and ]decreased programming time. In many cases, templates even produce more ]time-efficient code. Don't get me wrong; I'd love to have a solution ]which provides all the benefits of templates without the extra code, ]but in the mean time, I think the cost is well worth it. ] Oh, how true. This is deja vu - reminds me of those refusing to use functions years back, because the overhead of a function call was more than a goto... -- |~~~~~~~~~~ David Geary, Boeing Aerospace, Seattle, WA. ~~~~~~~~~~| |-----------------------------------------------------------------------------| |~~~~~~ Seattle: America's most attractive city... to the *jetstream* ~~~~~~| |-----------------------------------------------------------------------------|