Re: HashTable

From: Anthony Borla (ajborla_at_bigpond.com)
Date: 12/07/04 

Date: Tue, 07 Dec 2004 20:33:06 GMT

"Billy Patton" <bpatton@ti.com> wrote in message
news:Pine.LNX.4.61.0412070909030.26950@holster07.dal.design.ti.com...
> I've changed to this and got better results in compiling:
> template <typename K,typename V> class HashTable: public std::map<K,V>
> {
> private:
> public:
> HashTable<K,V>(void) { };
> ~HashTable<K,V>(void) { } ;
> bool Put(K&,V&,bool replace=false)
> {
> if (replace)
> this->erase(K); <<<<<<< Line # 83
> return (insert(make_pair(K,V))) ? true : false;
> }
> V& Value(K&);
> bool Keys(K&,bool firstp = false);
> bool Exists(K&);
> void DumpKeys(void);
> unsigned int EntryCount(void);
> };
>

Things to consider:

* If you need an actual hash table, several implementations
   already exist. Google search, or look at the Boost site

* As pointed out by another respondent, you are mistaking
   type designators for objects [i.e. arguments / variables]

* Public inheritance, that is:

      ... class HashTable: public std::map<K,V> ...

   is normally used for creating subtypes. I suspect this is not
   the intention here, instead, the intention appears to be one
   of implementation reuse. Therefore, a more appropriate
   approach is either:

   - Private / Protected Inheritance

          ... class HashTable: private std::map<K,V> ...
     or:
          ... class HashTable: protected std::map<K,V> ...

   - Composition, that is, including a std::map instance within
      your class, and forwarding all storage management requests
      to it

* C++ code makes heavy use of the 'const' keyword in several
   contexts, including:

   - Designating member functions as *not* altering data members
   - Allowing 'read-only' references to be passed as arguments
      [thus avoiding pass-by-value copying overhead]

    Note these are very loose descriptions of 'const' usage; you may
    care to read further for more details

See example code below. It is incomplete but should provide a reasonable
sourse of ideas.

I hope this helps.

Anthony Borla

// ======================
#include <map>
#include <iostream>

template <typename K,typename V>
class HashTable : private std::map<K, V>
{
private:

public:
  // Incomplete ...
  HashTable() {}
  ~HashTable() {}

  bool Put(const K& key, const V& value)
  {
    // Could optimise i.e. not insert if exists etc ???
    erase(key);
    return insert(std::make_pair(key, value)).second;
  }

  bool Remove(const K& key)
  {
    return erase(key);
  }

  const V& Value(const K& key) const
  {
    // V() is temporary value. Consider instead using:
    // * Specialised Null Object type
    // * Exception handling
    typename const_iterator pos = find(key);
    return pos != end()
      ? pos->second
      : std::make_pair(key, V()).second;
  }

  bool Keys(const K& key, bool firstp = false) const
  {
    // ???
    return true;
  }

  bool Exists(const K& key) const
  {
    return find(key) != end();
  }

  void DumpKeys() const
  {
    // Incomplete
  }

  size_t EntryCount() const
  {
    return size();
  }
};

// Test Harness
int main()
{
  HashTable<int, std::string> ht;

  std::cout << "EntryCount() == 0 : "
            << (ht.EntryCount() == 0 ? "Yes" : "No")
            << std::endl;

  std::cout << "Exists(1) Fails : "
            << (ht.EntryCount() == 0 ? "Yes" : "No")
            << std::endl;

  std::cout << "Put(1, \"One\") : "
            << (ht.Put(1, "One") ? "Ok" : "Fail")
            << std::endl;
  std::cout << "Put(2, \"Two\") : "
            << (ht.Put(2, "Two") ? "Ok" : "Fail")
            << std::endl;

  std::cout << "EntryCount() == 2 : "
            << (ht.EntryCount() == 2 ? "Yes" : "No")
            << std::endl;

  std::cout << "Exists(1) Succeeds : "
            << (ht.Exists(1) ? "Yes" : "No")
            << std::endl;

  std::cout << "Exists(7) Fails : "
            << (!ht.Exists(7) ? "Yes" : "No")
            << std::endl;

  std::cout << "Value(1) == \"One\" : "
            << (ht.Value(1) == "One" ? "Yes" : "No")
            << std::endl;

  std::cout << "Value(7) == \"\" : "
            << (ht.Value(7) == "" ? "Yes" : "No")
            << std::endl;

  std::cout << "Remove(1) Succeeds : "
            << (ht.Remove(1) ? "Yes" : "No")
            << std::endl;

  std::cout << "Remove(2) Succeeds : "
            << (ht.Remove(2) ? "Yes" : "No")
            << std::endl;

  std::cout << "Remove(7) Fails : "
            << (ht.Remove(7) ? "Yes" : "No")
            << std::endl;

  std::cout << "EntryCount() == 0 : "
            << (ht.EntryCount() == 0 ? "Yes" : "No")
            << std::endl;

  return 0;
}

// ======================

Relevant Pages