SourcePro C++ 12.0 |
SourcePro® C++ API Reference Guide |
SourcePro C++ Documentation Home |
A simple hash table for objects inheriting from RWCollectable. Uses chaining (as implemented by class RWSlistCollectables) to resolve hash collisions. More...
#include <rw/hashtab.h>
Public Member Functions | |
virtual RWCollectable * | newSpecies () const |
virtual RWClassID | isA () const |
RWHashTable (size_t N=RWCollection::DEFAULT_CAPACITY) | |
RWHashTable (const RWHashTable &t) | |
RWHashTable (RWHashTable &&t) | |
RWHashTable & | operator= (const RWHashTable &t) |
RWHashTable & | operator= (RWHashTable &&t) |
bool | operator<= (const RWHashTable &t) const |
bool | operator== (const RWHashTable &t) const |
bool | operator!= (const RWHashTable &) const |
virtual void | apply (RWapplyCollectable ap, void *) |
virtual void | clear () |
virtual size_t | entries () const |
virtual RWCollectable * | find (const RWCollectable *) const |
virtual RWCollectable * | insert (RWCollectable *a) |
virtual bool | isEmpty () const |
virtual bool | isEqual (const RWCollectable *) const |
virtual size_t | occurrencesOf (const RWCollectable *) const |
virtual RWCollectable * | remove (const RWCollectable *) |
virtual RWIterator * | newIterator () |
virtual RWConstIterator * | newConstIterator () const |
virtual void | resize (size_t n=0) |
void | swap (RWHashTable &t) |
Static Public Member Functions | |
static RWClassID | classIsA () |
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().
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 sags because each bucket must be searched linearly. The number of buckets can be changed by calling member function resize(). This requires that all objects be rehashed.
The iterator for this class is RWHashTableIterator.
#include <rw/hashtab.h> RWHashTable h ;
Polymorphic
#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:
RWHashTable::RWHashTable | ( | size_t | N = RWCollection::DEFAULT_CAPACITY |
) |
Constructs an empty hash table with N buckets.
RWHashTable::RWHashTable | ( | const RWHashTable & | t | ) |
Copy constructor. Creates a new hash table as a shallow copy of the table t. The new table has the same number of buckets as the old table. Hence, the members need not be and will not be rehashed.
RWHashTable::RWHashTable | ( | RWHashTable && | t | ) |
Move constructor. The constructed RWHashTable takes ownership of the data owned by t.
virtual void RWHashTable::apply | ( | RWapplyCollectable | ap, | |
void * | ||||
) | [virtual] |
The function pointed to by ap is called for each member in the collection. Because of the nature of hashing collections, this is not done in any particular order. The function should not do anything that could change the hash value or equality properties of the objects.
Implements RWCollection.
static RWClassID RWHashTable::classIsA | ( | ) | [static] |
Returns the RWClassID of this class.
Reimplemented from RWCollectable.
Reimplemented in RWHashDictionary, RWIdentityDictionary, RWIdentitySet, and RWSet.
virtual void RWHashTable::clear | ( | ) | [virtual] |
Removes all objects from the collection. Does not delete the objects themselves.
Implements RWCollection.
Reimplemented in RWHashDictionary.
virtual size_t RWHashTable::entries | ( | ) | const [inline, virtual] |
Returns the total number of items in the collection.
Implements RWCollection.
virtual RWCollectable* RWHashTable::find | ( | const RWCollectable * | target | ) | const [virtual] |
Returns a pointer to the first item in the collection which "matches" the object pointed to by target or rwnil if no item was found. For most collections, an item "matches" the target if either isEqual() or compareTo() find equivalence, whichever is appropriate for the actual collection type. However, the "identity collections" (i.e., RWIdentitySet and RWIdentityDictionary) look for an item with the same address (i.e., "is identical to").
Implements RWCollection.
Reimplemented in RWHashDictionary, and RWIdentitySet.
virtual RWCollectable* RWHashTable::insert | ( | RWCollectable * | a | ) | [virtual] |
Returns a if successful, otherwise rwnil.
Implements RWCollection.
Reimplemented in RWHashDictionary, RWIdentitySet, and RWSet.
virtual RWClassID RWHashTable::isA | ( | ) | const [virtual] |
Returns __RWHASHTABLE
.
Reimplemented from RWCollection.
Reimplemented in RWHashDictionary, RWIdentityDictionary, RWIdentitySet, and RWSet.
virtual bool RWHashTable::isEmpty | ( | ) | const [inline, virtual] |
Returns true
if the collection is empty, otherwise returns false
.
Implements RWCollection.
virtual bool RWHashTable::isEqual | ( | const RWCollectable * | t | ) | const [virtual] |
Returns true
if the collectable object "matches" the object at address t. The default definition is:
return this == t;
i.e., both objects have the same address (a test for identity). The definition may be redefined in any consistent way.
Reimplemented from RWCollectable.
Reimplemented in RWHashDictionary, RWIdentityDictionary, RWIdentitySet, and RWSet.
virtual RWConstIterator* RWHashTable::newConstIterator | ( | ) | const [virtual] |
Returns a const pointer to a dynamically allocated iterator for the collection.
Implements RWCollection.
Reimplemented in RWHashDictionary, and RWSet.
virtual RWIterator* RWHashTable::newIterator | ( | ) | [virtual] |
Returns a dynamically allocated iterator for the collection.
Implements RWCollection.
Reimplemented in RWHashDictionary, and RWSet.
virtual RWCollectable* RWHashTable::newSpecies | ( | ) | const [virtual] |
Allocates a new object off the heap of the same type as self and returns a pointer to it. You are responsible for deleting the object when done with it.
Reimplemented from RWCollectable.
Reimplemented in RWHashDictionary, RWIdentityDictionary, RWIdentitySet, and RWSet.
virtual size_t RWHashTable::occurrencesOf | ( | const RWCollectable * | t | ) | const [virtual] |
Returns the number of items in the collection which are "matches" for t. See function find() for a definition of matches.
Implements RWCollection.
Reimplemented in RWSet.
bool RWHashTable::operator!= | ( | const RWHashTable & | ) | const |
Returns the negation of operator==().
bool RWHashTable::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().
Reimplemented in RWFactory, RWHashDictionary, RWIdentityDictionary, and RWSet.
RWHashTable& RWHashTable::operator= | ( | RWHashTable && | t | ) |
Move assignment. Self takes ownership of the data owned by t.
RWHashTable& RWHashTable::operator= | ( | const RWHashTable & | t | ) |
Assignment operator. Sets self as a shallow copy of t. Afterwards, the two tables have the same number of buckets. Hence, the members need not be and will not be rehashed.
bool RWHashTable::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().
Reimplemented in RWHashDictionary.
virtual RWCollectable* RWHashTable::remove | ( | const RWCollectable * | target | ) | [virtual] |
Removes and returns a pointer to the first item in the collection which "matches" the object pointed to by target. Returns nil
if no object was found. Does not delete the object. See function find() for a definition of matches.
Implements RWCollection.
Reimplemented in RWHashDictionary, and RWIdentitySet.
virtual void RWHashTable::resize | ( | size_t | n = 0 |
) | [virtual] |
Resizes the internal hash table to have n buckets. This causes rehashing all the members of the collection. If n is zero, resizes to 3*
entries()/2
.
void RWHashTable::swap | ( | RWHashTable & | t | ) |
Swaps the data owned by self with the data owned by t.
© 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.