Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!radar!cadillac!dsouza From: dsouza@optima.cad.mcc.com (Desmond Dsouza) Newsgroups: comp.lang.c++ Subject: Re: asking an object for its type Message-ID: Date: 26 Feb 91 23:29:02 GMT References: <23984@netcom.COM> <1190@sheol.UUCP> <1991Feb19.000449.22255@gpu.utcs.utoronto.ca> <607@taumet.com> <65451@brunix.UUCP> <11284@pasteur.Berkeley.EDU> <70870@microsoft.UUCP> <8608@exodus.Eng.Sun.COM> Sender: news@cadillac.CAD.MCC.COM Distribution: na Organization: MCC CAD Program, Austin, Texas Lines: 41 In-reply-to: chased@rbbb.Eng.Sun.COM's message of 26 Feb 91 02:03:57 GMT In article <8608@exodus.Eng.Sun.COM> chased@rbbb.Eng.Sun.COM (David Chase) writes: > In article <70870@microsoft.UUCP> jimad@microsoft.UUCP (Jim ADCOCK) writes: > >A "trivial" solution to the run-time type problem ought to be closer > >to O(1) than O(N), where N is the number of classes that need to have > >some notion of run-time type. ... > > >I'd like to see consideration of some standard features in support of > >run-time type. > > Do note that (using algorithms known to me) run-time type-checks and > subtype queries can be implemented much more efficiently in the > single-inheritance case. This doesn't directly help C++, unless you > choose to limit the problem that you are trying to solve. > > IF you use the single-inheritance model, > > "S subtype of T?" > > can be answered in O(1) time, given O(N) off-line preprocessing which > yields an O(N) sized data structure. If you compute the transitive closure of the inheritance relationship and storing that, you have O(N^2) storage for O(1) response with N classes. For single inheritance, you can get an O(1) response with a O(logN) data structure per class i.e. O(NlogN) in all. Is there something better than that? Could you post a reference? Multiple inheritance, as well as dynamically extending the inheritance relationship (e.g. loading new derived classes) complicate matters. -- Desmond. -- ------------------------------------------------------------------------------- Desmond D'Souza, MCC CAD Program | ARPA: dsouza@mcc.com | Phone: [512] 338-3324 Box 200195, Austin, TX 78720 | UUCP: {uunet,harvard,gatech,pyramid}!cs.utexas.edu!milano!cadillac!dsouza