home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / cplus / 16367 < prev    next >
Encoding:
Text File  |  1992-11-16  |  2.8 KB  |  56 lines
  1. Newsgroups: comp.lang.c++
  2. Path: sparky!uunet!pmafire!mica.inel.gov!ux1!news.byu.edu!eff!sol.ctr.columbia.edu!usc!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!cbnews!cbnewsm!cbnewsl!cbnewsk!pegasus!hansen
  3. From: hansen@pegasus.att.com (Tony L. Hansen)
  4. Subject: Re: Making qsort type-safe
  5. Organization: AT&T
  6. Date: Mon, 16 Nov 1992 15:45:33 GMT
  7. Message-ID: <1992Nov16.154533.17360@cbnewsk.cb.att.com>
  8. Summary: examples of unsafeness
  9. Keywords: sorting, templates, qsort
  10. References: <1992Nov4.162131.10289@cs.brown.edu> <1992Nov12.194207.19040@cbnewsk.cb.att.com> <1992Nov13.215612.7145@netcom.com>
  11. Sender: hansen@cbnewsk.cb.att.com (tony.l.hansen)
  12. Lines: 42
  13.  
  14. < From: mdr@netcom.com (Marc D. Rossner)
  15. < In article <1992Nov12.194207.19040@cbnewsk.cb.att.com>, hansen@pegasus.att.com (Tony L. Hansen) writes:
  16. << [ .. describes a safe qsort]
  17. << Is that the end of the story, though? No, of course not, because just
  18. << swapping the bits around may not be sufficient to swap a[0] and a[1]. They
  19. << may truly have to be swapped using assignments, and qsort provides no way to
  20. << do that.
  21.  
  22. < Can you think of a good example of this?  I realize that COPYING an
  23. < objects bits may be insufficient for making a conceptually independent
  24. < copy, but I can't think why swapping the bits of two objects would not
  25. < leave the two objects physically and conceptually swapped.
  26.  
  27. Two examples come to mind, both related:
  28.  
  29.     o    An object consists of an outer object with a pointer to an inner
  30.     object. The inner object also contains a pointer back to the outer
  31.     object. Swapping the bits of the outer object won't get the inner
  32.     objects updated properly.
  33.  
  34.     o    An external registry of a pointer and some information about the
  35.     object is maintained about for each object, and doing an assignment
  36.     will update that external registery. 
  37.  
  38. Defining a safe and efficient sort function is hard, as there are tradeoffs
  39. which must be made. Some tradeoffs are appropriate in some cases and not in
  40. others. The example of swapping bits is one tradeoff. There may be times
  41. that swapping bits is just fine; other times it's disastrous. Some times a
  42. third algorithm is more appropriate. The example in the first bullet item
  43. above could probably be handled by swapping the bits and then updating the
  44. inner object's pointer, but only a swap<T>() function could know that.
  45. qsort<T>() cannot know apriori how to handle any given type. On a related
  46. note, the comparison function doesn't necessarily have to provide a total
  47. ordering of two elements, and using operator<() would be sufficient.
  48. Similarly, just using the less-than relationship, provided by some other
  49. function, would often be sufficient. This probably argues for a set of
  50. related functions which provide various options for the different tradeoffs.
  51.  
  52.                     Tony Hansen
  53.                 hansen@pegasus.att.com, tony@attmail.com
  54.                 att!pegasus!hansen, attmail!tony
  55.  
  56.