RWTValHashTable(3C++) RWTValHashTable(3C++)
Name
RWTValHashTable<T> - Rogue Wave library class
Synopsis
#include <rw/tvhasht.h>
unsigned hashFun(const T&);
RWTValHashTable<T> table(hashFun);
Please Note!
If you do not have the Standard C++ Library, use the interface described
here. Otherwise, use the interface to RWTValHashMultiSet 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
value based collection: 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:
well-defined copy semantics (T::T(const T&) or equivalent);
well-defined assignment semantics (T::operator=(const T&) or
equivalent);
well-defined equality semantics (T::operator==(const T&)).
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:.Ex
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 an expensive proposition because not only must all items be
Page 1
RWTValHashTable(3C++) RWTValHashTable(3C++)
copied into the new buckets, but they must also be rehashed. If you wish
this to be automatically done, 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/tvhasht.h>
#include <rw/cstring.h>
#include <rw/rstream.h>
main() {
RWTValHashTable<RWCString> table(RWCString::hash);
table.insert("Alabama"); // NB: Type conversion occurs
table.insert("Pennsylvania");
table.insert("Oregon");
table.insert("Montana");
cout << "The table " <<
(table.contains("Oregon") ? "does " : "does not ") <<
"contain Oregon0;
table.removeAll("Oregon");
cout << "Now the table "
<< (table.contains("Oregon") ? "does " : "does not ")
<< "contain Oregon";
return 0;
}
Program output
The table does contain Oregon
Now the table does not contain Oregon
Public Constructors
RWTValHashTable<T>(unsigned (*hashFun)(const T&),
size_t buckets = RWDEFAULT_CAPACITY);
Constructs a new hash table. The first argument is a pointer to a user-
defined hashing function for items of type T. The table will initally
have buckets buckets although this can be changed with member function
resize().
RWTValHashTable<T>(const RWTValHashTable<T>& table);
Constructs a new hash table as a copy of table. The new table will have
the same number of buckets as the old table. Hence, although objects
Page 2
RWTValHashTable(3C++) RWTValHashTable(3C++)
must be copied into the new table, they will not be hashed.
Public Operators
RWTValHashTable&
operator=(const RWTValHashTable<T>&);
Sets self to a copy of table. Afterwards, the new table will have the
same number of buckets as the old table. Hence, although objects must be
copied into the new table, they will not be hashed.
Public Member Functions
void
apply(void (*applyFun)(T&, void*), void* d);
Applies the user-defined function pointed to by applyFun to every item in
the table. This function must have prototype:
void yourFun(T& a, void* d);
Client data may be passed through as parameter d.
void
clear();
Removes all items from the collection.
RWBoolean
contains(const T& val) const;
Returns TRUE if the collection contains an item which is equal to val.
Returns FALSE otherwise. Equality is measured by the class-defined
equality operator.
size_t
entries() const;
Returns the number of items currently in the collection.
RWBoolean
find(const T& target, T& k) const;
Returns TRUE if the collection contains an item which is equal to target
Page 3
RWTValHashTable(3C++) RWTValHashTable(3C++)
and puts the matching object into k. Returns FALSE otherwise and leaves
k untouched. Equality is measured by the class-defined equality
operator.
void
insert(const T& val);
Inserts the value val into the collection.
RWBoolean
isEmpty() const;
Returns TRUE if the collection has no items in it, FALSE otherwise.
size_t
occurrencesOf(const T& val) const;
Returns the number of items in the collection which are equal to val.
Equality is measured by the class-defined equality operator.
RWBoolean
remove(const T& val);
Removes the first object which is equal to the object a and returns TRUE.
Returns FALSE if there is no such object. Equality is measured by the
class-defined equality operator.
size_t
removeAll(const T& val);
Removes all objects which are equal to the object a. Returns the number
of objects removed. Equality is measured by the class-defined equality
operator.
void
resize(size_t N);
Changes the number of buckets to N, a relatively expensive operation if
there are many items in the collection.
Page 4