| Member Functions | |
| apply() clear() clearAndDestroy() contains() entries() find() insert() isEmpty() occurrencesOf() operator=() |
remove() removeAll() resize() |
#include <rw/tphasht.h> unsigned hashFun(const T&); RWTPtrHashTable<T> table(hashFun);
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.
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:
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:
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.
None
#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
RWTPtrHashTable<T>(unsigned (*hashFun)(const T&),
size_t buckets = RWDEFAULT_CAPACITY);
Constructs an empty 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().
RWTPtrHashTable<T>(const RWTPtrHashTable<T>& c);
Constructs a new hash table as a shallow copy of c. After construction, pointers will be shared between the two collections. The new object will have the same number of buckets as c. Hence, the keys will not be rehashed.
RWTPtrHashTable& operator=(const RWTPtrHashTable<T>& c);
Sets self to a shallow copy of c. Afterwards, pointers will be shared between the two collections and self will have the same number of buckets as c. Hence, the keys will not be rehashed.
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. The items should not be changed in any way that could change their hash value.
void clear();
Removes all items from the collection.
void clearAndDestroy();
Removes all items from the collection and deletes them. Do not use this method if multiple pointers to the same object are stored.
RWBoolean contains(const T* p) const;
Returns TRUE if the collection contains an item which is equal to the item pointed to by p. Returns FALSE otherwise. Equality is measured by the class-defined equality operator for type T.
size_t entries() const;
Returns the number of items currently in the collection.
T* find(const T* target) const;
Returns a pointer to the object which is equal to the object pointed to by target, or nil if no such object can be found. Equality is measured by the class-defined equality operator for type T.
void insert(T* a);
Adds the object pointed to by a to the collection.
RWBoolean isEmpty() const;
Returns TRUE if the collection has no items in it, FALSE otherwise.
size_t occurrencesOf(const T* a) const;
Returns the number of objects in the collection which are equal to the object pointed to by a. Equality is measured by the class-defined equality operator for type T.
T* remove(const T* a);
Removes the object which is equal to the object pointed to by a and returns a pointer to it, or nil if no such object could be found. Equality is measured by the class-defined equality operator for type T.
size_t removeAll(const T* a);
Removes all objects which are equal to the object pointed to by a. Returns the number of objects removed. Equality is measured by the class-defined equality operator for type T.
void resize(size_t N);
Changes the number of buckets to N. This will result in all of the objects in the collection being rehashed.