RWHashTable
Module: Essential Tools Module Group: RWCollectable Classes
RWHashTableRWCollection
- Local Index
- Synopsis
- Description
- Persistence
- Example
- Public Constructors
- Public Operators
- Member Functions
Local Index
Members
Synopsis
#include <rw/hashtab.h> RWHashTable h ;
Description
This class is a simple hash table for objects inheriting from RWCollectable. It uses chaining (as implemented by class RWSlistCollectables) to resolve hash collisions. Duplicate objects are allowed. An object stored by RWHashTable must inherit from the abstract base class RWCollectable, with suitable definition for virtual functions hash() and isEqual() (see class RWCollectable).
To find an object that matches a key, the key's virtual function hash() is first called to determine in which bucket the object occurs. The bucket is then searched linearly by calling the virtual function isEqual() for each candidate, with the key as the argument. The first object to return true is the returned object.
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 will require that all objects be rehashed.
The iterator for this class is RWHashTableIterator.
Persistence
Polymorphic
Example
#include <rw/hashtab.h>
#include <rw/tools/ctdatetime.h>
int main ()
{
RWHashTable table;
RWCollectableDateTime *july = new RWCollectableDateTime ("July 7, 1990", RWDateTime::setDate);
RWCollectableDateTime *may = new RWCollectableDateTime ("May 1, 1977", RWDateTime::setDate);
RWCollectableDateTime *feb = new RWCollectableDateTime ("Feb 22, 1983", RWDateTime::setDate);
RWCollectableDateTime *aug = new RWCollectableDateTime ("Aug 2, 1966", RWDateTime::setDate);
table.insert(july);
table.insert(may);
table.insert(feb);
table.insert(aug);
std::cout << "Table contains " << table.entries() << " entries ";
RWCollectableDateTime key("Feb 22, 1983", RWDateTime::setDate);
std::cout << "and it does"
<< (table.contains(&key) ? " " : " not ")
<< "contain the key " << key << std::endl;
delete july;
delete may;
delete feb;
delete aug;
return 0;
}
Program output:
Table contains 4 entries and it does contain the key Tue Feb 22 00:00:00 1983
Public Constructors
RWHashTable(size_t N = RWCollection::DEFAULT_CAPACITY);
Construct an empty hash table with N buckets.
RWHashTable(const RWHashTable& t);
Copy constructor. Create a new hash table as a shallow copy of the table t. The new table will have the same number of buckets as the old table. Hence, the members need not be and will not be rehashed.
Public Operators
void operator=(const RWHashTable& t);
Assignment operator. Sets self as a shallow copy of t. Afterwards, the two tables will have the same number of buckets. Hence, the members need not be and will not be rehashed.
bool operator==(const RWHashTable& t) const;
Returns true if self and t have the same number of elements and if for every key in self there is a corresponding key in t which isEqual.
bool operator<=(const RWHashTable& t) const;
Returns true if self is a subset of t, that is, every element of self has a counterpart in t which isEqual. Note: If you inherit from RWHashTable in the presence of the C++ Standard Library, we recommend that you override this operator and explicitly forward the call. Overload resolution in C++ will choose the standard library-provided global operators over inherited class members. These global definitions are not appropriate for set-like partial orderings.
bool operator!=(const RWHashTable&) const;
Returns the negation of operator==(), above.
Member Functions
virtual void apply(RWapplyCollectable ap, void*);
Redefined from RWCollection. The function pointed to by ap will be called for each member in the collection. Because of the nature of hashing collections, this will not be done in any particular order. The function should not do anything that could change the hash value or equality properties of the objects.
virtual RWspace binaryStoreSize() const;
Inherited from RWCollection.
virtual void clear();
Redefined from RWCollection.
virtual void clearAndDestroy();
Inherited from RWCollection.
virtual int compareTo(const RWCollectable*) const;
Inherited from RWCollection.
virtual bool contains(const RWCollectable*) const;
Inherited from RWCollection.
virtual size_t entries() const;
Redefined from RWCollection.
virtual RWCollectable* find(const RWCollectable*) const;
Redefined from RWCollection.
virtual unsigned hash() const;
Inherited from RWCollection.
virtual RWCollectable* insert(RWCollectable* a);
Redefined from RWCollection. Returns a if successful, nil otherwise.
virtual RWClassID isA() const;
Redefined from RWCollection to return __RWHASHTABLE.
virtual bool isEmpty() const;
Redefined from RWCollection.
virtual bool isEqual(const RWCollectable*) const;
Redefined from RWCollection.
virtual RWConstIterator* newConstIterator();
Returns a const pointer to a dynamically allocated iterator for the collection.
virtual RWIterator* newIterator();
Returns a dynamically allocated iterator for the collection.
virtual RWCollectable* newSpecies() const;
Redefined from RWCollection.
virtual size_t occurrencesOf(const RWCollectable*) const;
Redefined from RWCollection.
virtual RWCollectable* remove(const RWCollectable*);
Redefined from RWCollection.
virtual void removeAndDestroy(const RWCollectable*);
Inherited from RWCollection.
virtual void resize(size_t n = 0);
Resizes the internal hash table to have n buckets. This causes rehashing all the members of the collection. If n is zero, then an appropriate size will be picked automatically.
virtual void restoreGuts(RWvistream&); virtual void restoreGuts(RWFile&); virtual void saveGuts(RWvostream&) const; virtual void saveGuts(RWFile&) const;
Inherited from class RWCollection.
RWStringID stringID();
(acts virtual) Inherited from class RWCollectable.
© Copyright Rogue Wave Software, Inc. All Rights Reserved.
Rogue Wave and SourcePro are registered trademarks of Rogue Wave Software, Inc. in the United States and other countries. All other trademarks are the property of their respective owners.
Contact Rogue Wave about documentation or support issues.