From: haydens@bullwinkle.juliet.ll.mit.edu (Hayden Schultz x3685 g42)
Subject: Re: zero-length datatype
Reply-To: haydens@juliet.ll.mit.edu
Organization: M.I.T. Lincoln Lab - Group 42
	<HAYDENS.92Sep9215705@bullwinkle.juliet.ll.mit.edu>
	<TMB.92Sep10120206@arolla.idiap.ch>
Distribution: comp
Date: 10 Sep 92 10:32:08


In article <TMB.92Sep10120206@arolla.idiap.ch> tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

   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!


      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.

I'm still not convinced that you can't use existing language features
to solve (or maybe just avoid) this problem. If a legitimate subset of
the hash table problem is hash tables with just keys, then this sounds
like a basis for a class heirarchy. Again please forgive and stupid
template errors I make, since I can't test this code myself.

Something like:

template <class Key>
class KeyHash {
  protected:
    Array<Key>	keys;
    BitArray	used;
  public:
    void	Add(Key &);
    int		InTable(Key &);
};

template <class Key, class Value>
class HashTable : public KeyHash<Key> {
  protected:
    Array<Value>	values;
  public:
    Value		Lookup(Key &);
};

I think that this meets your intuitive criterion. Whenever you don't
care what the values are, you use the KeyHash class. You don't have to
make a special class to make a simple HashTable<int,int>. The Key and
Value types are as explicit as your original example. You don't even
have to modify any existing code which uses the HashTable class, since
the public interface hasn't changed.

And best of all, you don't have to modify the language to get your
memory efficiency. You also know exactly what will happen if you
inadvertently try to use the value returned by HashTable::Lookup() for
a KeyHash object-- you'll get a compiler error.

	Hayden Schultz
	MIT Lincoln Lab
	haydens@juliet.ll.mit.edu