home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / lang / cplus / 13461 < prev    next >
Encoding:
Text File  |  1992-09-10  |  4.0 KB  |  115 lines
  1. Path: sparky!uunet!noc.near.net!news.Brown.EDU!qt.cs.utexas.edu!cs.utexas.edu!sun-barr!olivea!mintaka.lcs.mit.edu!ai-lab!life.ai.mit.edu!tmb
  2. From: tmb@arolla.idiap.ch (Thomas M. Breuel)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: zero-length datatype
  5. Message-ID: <TMB.92Sep10120206@arolla.idiap.ch>
  6. Date: 10 Sep 92 16:02:06 GMT
  7. References: <TMB.92Sep8141523@arolla.idiap.ch> <4947@holden.lulea.trab.se>
  8.     <HAYDENS.92Sep9215705@bullwinkle.juliet.ll.mit.edu>
  9. Sender: news@ai.mit.edu
  10. Reply-To: tmb@idiap.ch
  11. Distribution: comp
  12. Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
  13.     Perceptive)
  14. Lines: 98
  15. In-reply-to: haydens@bullwinkle.juliet.ll.mit.edu's message of 10 Sep 92 01:57:05 GMT
  16.  
  17. In article <HAYDENS.92Sep9215705@bullwinkle.juliet.ll.mit.edu> haydens@bullwinkle.juliet.ll.mit.edu (Hayden Schultz x3685 g42) writes:
  18.  
  19.       : Under the current rules,
  20.       : 
  21.       :       struct nothing {};
  22.       :       HashTable<int,nothing> table(1000000);
  23.       : 
  24.       : table takes up 8Mbytes (on most machines). If you could write
  25.       : 
  26.       :       HashTable<int,void> table(1000000);
  27.       : 
  28.       : table takes up 4Mbytes.
  29.  
  30.       On common implementations, 1 million such objects take up
  31.       24 MB (since a-e take up 4 bytes each), whereas Thomas's
  32.       proposed 'void' type means only 4 MB would be needed.
  33.       Quite a difference!
  34.  
  35.    It's implied in this discussion that code better not either assign to
  36.    or rely upon the value of a zero-size data member.
  37.  
  38. It would be perfectly OK to assign a value to a variable of type
  39. "void"--namely the value "void()". And you can always rely on its
  40. value--the value of a variable of type "void" would be, by definition,
  41. "void()". There is nothing complicated or unsafe about having a
  42. datatype which can take on only one value; the only exceptional
  43. property is that it doesn't require any storage to represent a type
  44. which can take on only a single value.
  45.  
  46. If you have a template function/structure that is type-correct,
  47. everything will work out perfectly if you make one of the template
  48. arguments "void" (this is a statement of experience from other
  49. languages, not belief).
  50.  
  51.    Maybe I'm missing
  52.    something, but why can't you use unions for this?
  53.  
  54. The use of "void" as a zero-length type would be primarily as one of
  55. the arguments in the instantiation of a template. A union could not be
  56. used in this way.
  57.  
  58.    You really shouldn't have to resort to zero-length data types anyway.
  59.    I remember some code posted for a template HashTable class. It went
  60.    something like this: [...]
  61.  
  62.    Please forgive any stupid template errors, my compilers don't have
  63.    them yet.
  64.  
  65. (If you are not using templates yet, then I agree that you have no use
  66. for a "void" type...)
  67.  
  68.    You should be able use abstraction to avoid this problem:
  69.  
  70.    template<class KeyNode>
  71.    class HashTable {
  72.      public:
  73.        KeyNode    lookup(const KeyNode &) const;
  74.        void    add(const KeyNode &);
  75.        int        in_table(KeyNode &);
  76.    };
  77.  
  78.    This class assumes that KeyNode::Value() and KeyNode::Key() functions
  79.    are used to access the key and value.  When you want to only use the
  80.    Value(), then you can write your KeyNode class: [...]
  81.  
  82. You can do this. However, there are two problems with it:
  83.  
  84.  (1) It's counterintuitive. HashTable depends on two types, the
  85.      Key type and the Value type, and this should be made explicit
  86.      in the definition. Also, I don't want to have to name
  87.      and define a structure just to make a simple "HashTable<int,int>".
  88.  
  89.  (2) It may waste lots of memory because KeyNodes can not be packed
  90.      as tightly as Keys and Values. Consider the following two
  91.      implementation fragments:
  92.  
  93.     template <class Key,class Value>
  94.     struct HashTable1 {
  95.         Array<Key> keys;
  96.         Array<Value> values;
  97.         BitArray used;
  98.         ...
  99.     };
  100.  
  101.     template <class KeyNode>
  102.     struct HashTable2 {
  103.         Array<KeyNode> kvpairs;
  104.         BitArray used;
  105.         ...
  106.     };
  107.  
  108.     struct MyKeyNode { int key; char value; };
  109.  
  110.      Now, HashTable1<int,char> requires 5 bytes plus 1 bit per
  111.      slot, whereas HashTable2<MyKeyNode> requires 8 bytes plus
  112.      1 bit per slot.
  113.  
  114.                 Thomas.
  115.