home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / cplus / 16025 < prev    next >
Encoding:
Text File  |  1992-11-10  |  2.5 KB  |  49 lines
  1. Newsgroups: comp.lang.c++
  2. Path: sparky!uunet!sun-barr!cs.utexas.edu!torn!nott!bnrgate!bcrka451!bcrki65!sjm
  3. From: sjm@bcrki65.bnr.ca (Stuart MacMartin)
  4. Subject: Re: Making qsort type-safe
  5. Message-ID: <1992Nov10.134651.19803@bcrka451.bnr.ca>
  6. Sender: 5E00 Corkstown News Server
  7. Organization: Bell-Northern Research Ltd., Ottawa, Canada
  8. References: <1992Nov6.202732.27007@mprgate.mpr.ca> <dak.721261218@messua> <1992Nov09.155723.112061@Cookie.secapl.com>
  9. Date: Tue, 10 Nov 1992 13:46:51 GMT
  10. Lines: 37
  11.  
  12. In article <1992Nov09.155723.112061@Cookie.secapl.com> frank@Cookie.secapl.com (Frank Adams) writes:
  13. >In article <dak.721261218@messua> dak@messua.informatik.rwth-aachen.de (David Kastrup) writes:
  14. >
  15. >>If you are sorting linked lists, however, use a mergesort
  16. >
  17. >Absolutely.
  18.  
  19. I have sometimes sorted linked lists by creating an array of pointers to data,
  20. sorting this array using my modified qsort, and then adjusting the linked list
  21. pointers.  I have not noticed this to be grossly inefficient.  That way I just
  22. had a few lines of coding to do to be able to use existing code.  Is there a
  23. problem with my approach?
  24.  
  25. Also, if the comparison function is at all complicated (like comparing field a,
  26. and if that is equal, compare field b) I do a first pass through the data to
  27. construct a temporary array of the fields I want to compare in the correct order.
  28. The purpose of this is to simplify the comparison function as much as possible.
  29. It also reduces paging problems with qsort on huge collections.  If I want to
  30. do a pass like this anyway, I see no reason to have the temporary collection
  31. in a linked list.  So what exactly do you mean by "Absolutely"?  Under all
  32. circumstances it is the best thing to do?
  33.  
  34. On a slight variation of this topic:  the Lipmann code for qsort compares 
  35. two objects using operator<().  That is,  "a < b".  But there can be more than
  36. one sort order on a collection.  I could sort people by name or by birth date.
  37. The actual ordering of the objects in the collection is a property of the
  38. collection, not of the objects themselves.  How is this best resolved?
  39. Should the objects in the collection be able to compare themselves according
  40. to different orderings?  Is operator<() enough?  Surely it is not a good idea
  41. to have the collection class know details of how to sort the objects in the 
  42. collection.
  43.  
  44. Stuart
  45. --
  46. : Stuart MacMartin                                    email: sjm@bnr.ca      :
  47. : Bell-Northern Research                              phone: (613) 763-5625  :
  48. : PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :
  49.