Click on the banner to return to the Class Reference home page.
Return to the Appendix home page.

©Copyright 1996 Rogue Wave Software

RWTPtrHashTable<T>

Alternate template: Standard C++ Library not required

Synopsis

#include <rw/tphasht.h>
unsigned hashFun(const T&);
RWTPtrHashTable<T> table(hashFun);

Please Note!


If you do not have the Standard C++ Library, use the interface described here. Otherwise, use the interface to RWTPtrHashMultiSet described in the Class Reference.



Description

This class implements a parameterized hash table of types T. It uses chaining to resolve hash collisions. Duplicates are allowed.

It is a pointer based collection: pointers to objects are copied in and out of the hash buckets.

Parameter T represents the type of object to be inserted into the table, either a class or fundamental type. The class T must have:

A user-supplied hashing function for type T must be supplied to the constructor when creating a new table. If T is a Rogue Wave class, then this requirement is usually trivial because most Rogue Wave objects know how to return a hashing value. In fact, classes RWCString, RWDate, RWTime, and RWWString contain static member functions called hash that can be supplied to the constructor as is. The function must have prototype:

unsigned hFun(const T& a);

and should return a suitable hash value for the object a.

To find an object, it is first hashed to determine in which bucket it occurs. The bucket is then searched for an object that is equal (as determined by the equality operator) to the candidate.

The initial number of buckets in the table is set by the constructor. There is a default value. If the number of items in the collection greatly exceeds the number of buckets then efficiency will sag because each bucket must be searched linearly. The number of buckets can be changed by calling member function resize(). This is relatively expensive because all of the keys must be rehashed.

If you wish for this to be done automatically, then you can subclass from this class and implement your own special insert() and remove() functions which perform a resize() as necessary.

Persistence

None

Example

#include <rw/tphasht.h>
#include <rw/cstring.h>
#include <rw/rstream.h>

main()  { 
  RWTPtrHashTable<RWCString> table(RWCString::hash);
  RWCString *states[4] = { new RWCString("Alabama"),
                           new RWCString("Pennsylvania"), 
                           new RWCString("Oregon"),
                           new RWCString("Montana") };

  table.insert(states[0]);
  table.insert(states[1]);
  table.insert(states[2]);
  table.insert(states[3]);

  RWCString key("Oregon");
  cout << "The table " <<
    (table.contains(&key) ? "does " : "does not ") <<
    "contain Oregon\n";

  table.removeAll(&key);

  cout << "Now the table " <<
    (table.contains(&key) ? "does " : "does not ") <<
    "contain Oregon";

  delete states[0];
  delete states[1];
  delete states[2];
  delete states[3];
  return 0;
}

Program output

The table does contain Oregon
Now the table does not contain Oregon

Public Constructors

RWTPtrHashTable<T>(unsigned (*hashFun)(const T&),
                       size_t buckets = RWDEFAULT_CAPACITY);
RWTPtrHashTable<T>(const RWTPtrHashTable<T>& c);

Public Operators

RWTPtrHashTable&
operator=(const RWTPtrHashTable<T>& c);
void

Public Member Functions

apply(void (*applyFun)(T*, void*), void* d);
void
clear();
void
clearAndDestroy();
RWBoolean
contains(const T* p) const;
size_t
entries() const;
T*
find(const T* target) const;
void
insert(T* a);
RWBoolean
isEmpty() const;
size_t
occurrencesOf(const T* a) const;
T*
remove(const T* a);
size_t
removeAll(const T* a);
void
resize(size_t N);