home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / cplus / 11393 < prev    next >
Encoding:
Internet Message Format  |  1992-07-22  |  2.2 KB
  1. From: weeks@hpscit.sc.hp.com (Greg Weeks)
  2. Date: Wed, 22 Jul 1992 21:03:30 GMT
  3. Subject: iteration without iterators (and a question)
  4. Message-ID: <46960006@hpscit.sc.hp.com>
  5. Organization: Hewlett-Packard, Santa Clara, CA
  6. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!hpscdc!hplextra!hpcc05!hpscit!weeks
  7. Newsgroups: comp.lang.c++
  8. Lines: 53
  9.  
  10. This note is divided into two (brief) independent parts.  The first part
  11. describes a simple iteration protocol.  The second part asks for help in
  12. implementing it.  (Readers who just want to be helpful can skip to the
  13. second part.)
  14.  
  15. THE ITERATION PROTOCOL
  16.  
  17. Let `col' be a collection that holds items of type `Item'.  Here is a
  18. very simple iteration protocol:
  19.  
  20.     for (Item *pi = col.first(); pi; pi = col.next(pi)) {
  21.     ...
  22.     //  `pi' is the address of an item in the collection.
  23.     }
  24.  
  25. Only two member functions are used by the iteration.  No separate iterator
  26. class is needed.  The iteration code fits nicely into a `for' statement.
  27. And users can set the item at the current location by assigning to `*pi'.
  28.  
  29. However, to implement `next', you have to:
  30.  
  31.     1.  Get the "node" that holds the item at address `pi'.
  32.     2.  Get the next node.
  33.     3.    Get the address of the item in the next node.
  34.  
  35. Steps 2 and 3 are easy.  But step 1 is hard.
  36.  
  37. HOW TO IMPLEMENT?
  38.  
  39. The problem is:
  40.  
  41.     Given the address of a class object member variable, find the address
  42.     of the class object.
  43.  
  44. In C, this would be easy.  Just make the member variable the first member
  45. of the structure.  Then a pointer to the first member may simply be cast to
  46. a pointer to the structure.  But I don't think this works in C++ for a
  47. couple of reasons.
  48.  
  49. First, I don't think the first member of a class is guaranteed to be at the
  50. same physical address as the class object.
  51.  
  52. But suppose that it is.  Now suppose that the collection class is a
  53. template parameterized by the node class.  What happens if someone derives
  54. a new node class and uses that to build the collection class?  It now seems
  55. likely the the item member will no longer be at the same physical address
  56. as the new node object.  That's the second reason.
  57.  
  58. This discussion is leaning in the direction of messy
  59. implementation-dependent considerations.  Is there some nice way to avoid
  60. this?
  61.  
  62. Greg Weeks
  63.