NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/comp/lang/cplus/13515

Text File | 1992-09-10 | 4.0 KB | 128 lines

Newsgroups: comp.lang.c++
Path: sparky!uunet!sun-barr!ames!xn.ll.mit.edu!xn!haydens
From: [e-mail] (Hayden Schultz x3685 g42)
Subject: Re: zero-length datatype
In-Reply-To: [e-mail]'s message of 10 Sep 92 16:02:06 GMT
Message-ID: <[e-mail]>
Lines: 111
Sender: [e-mail]
Reply-To: [e-mail]
Organization: M.I.T. Lincoln Lab - Group 42
References: <[e-mail]> <[e-mail]>
    <[e-mail]>
    <[e-mail]>
Distribution: comp
Date: 10 Sep 92 10:32:08


In article <[e-mail]> [e-mail] (Thomas M. Breuel) writes:

   In article <[e-mail]> [e-mail] (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
    [e-mail]