From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Newsgroups: comp.lang.c++
Subject: Re: zero-length datatype
Date: 10 Sep 92 16:02:06 GMT
	<HAYDENS.92Sep9215705@bullwinkle.juliet.ll.mit.edu>
Reply-To: tmb@idiap.ch
Distribution: comp
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
	Perceptive)
In-reply-to: haydens@bullwinkle.juliet.ll.mit.edu's message of 10 Sep 92 01:57:05 GMT

In article <HAYDENS.92Sep9215705@bullwinkle.juliet.ll.mit.edu> haydens@bullwinkle.juliet.ll.mit.edu (Hayden Schultz x3685 g42) writes:

      : Under the current rules,
      : 
      :       struct nothing {};
      :       HashTable<int,nothing> table(1000000);
      : 
      : table takes up 8Mbytes (on most machines). If you could write
      : 
      :       HashTable<int,void> table(1000000);
      : 
      : table takes up 4Mbytes.

      On common implementations, 1 million such objects take up
      24 MB (since a-e take up 4 bytes each), whereas Thomas's
      proposed 'void' type means only 4 MB would be needed.
      Quite a difference!

   It's implied in this discussion that code better not either assign to
   or rely upon the value of a zero-size data member.

It would be perfectly OK to assign a value to a variable of type
"void"--namely the value "void()". And you can always rely on its
value--the value of a variable of type "void" would be, by definition,
"void()". There is nothing complicated or unsafe about having a
datatype which can take on only one value; the only exceptional
property is that it doesn't require any storage to represent a type
which can take on only a single value.

If you have a template function/structure that is type-correct,
everything will work out perfectly if you make one of the template
arguments "void" (this is a statement of experience from other
languages, not belief).

   Maybe I'm missing
   something, but why can't you use unions for this?

The use of "void" as a zero-length type would be primarily as one of
the arguments in the instantiation of a template. A union could not be
used in this way.

   You really shouldn't have to resort to zero-length data types anyway.
   I remember some code posted for a template HashTable class. It went
   something like this: [...]

   Please forgive any stupid template errors, my compilers don't have
   them yet.

(If you are not using templates yet, then I agree that you have no use
for a "void" type...)

   You should be able use abstraction to avoid this problem:

   template<class KeyNode>
   class HashTable {
     public:
       KeyNode	lookup(const KeyNode &) const;
       void	add(const KeyNode &);
       int		in_table(KeyNode &);
   };

   This class assumes that KeyNode::Value() and KeyNode::Key() functions
   are used to access the key and value.  When you want to only use the
   Value(), then you can write your KeyNode class: [...]

You can do this. However, there are two problems with it:

 (1) It's counterintuitive. HashTable depends on two types, the
     Key type and the Value type, and this should be made explicit
     in the definition. Also, I don't want to have to name
     and define a structure just to make a simple "HashTable<int,int>".

 (2) It may waste lots of memory because KeyNodes can not be packed
     as tightly as Keys and Values. Consider the following two
     implementation fragments:

	template <class Key,class Value>
	struct HashTable1 {
		Array<Key> keys;
		Array<Value> values;
		BitArray used;
		...
	};

	template <class KeyNode>
	struct HashTable2 {
		Array<KeyNode> kvpairs;
		BitArray used;
		...
	};

	struct MyKeyNode { int key; char value; };

     Now, HashTable1<int,char> requires 5 bytes plus 1 bit per
     slot, whereas HashTable2<MyKeyNode> requires 8 bytes plus
     1 bit per slot.

				Thomas.