WvStreams
|
A small, efficient, type-safe hash table (also known as dictionary) container class. More...
#include <wvhashtable.h>
Classes | |
class | IterBase |
Public Member Functions | |
size_t | count () const |
Returns the number of elements in the hash table. | |
bool | isempty () const |
Returns true if the hash table is empty. | |
Public Attributes | |
unsigned | numslots |
WvListBase * | wvslots |
Protected Member Functions | |
WvHashTableBase (unsigned _numslots) | |
WvHashTableBase & | operator= (const WvHashTableBase &t) |
void | setup () |
void | shutdown () |
WvLink * | prevlink (WvListBase *slots, const void *data, unsigned hash) const |
void * | genfind (WvListBase *slots, const void *data, unsigned hash) const |
virtual bool | compare (const void *key, const void *elem) const =0 |
A small, efficient, type-safe hash table (also known as dictionary) container class.
These are typically used to store a reasonably large number of objects in no particular order and find them quickly when needed.
Two semi-distinct types of hash tables are supported: tables and dictionaries.
TABLE EXAMPLE:
DeclareWvTable(WvString); int main() { WvString s("foo"), s2("blue"), s3("foo"); WvStringTable t(10); // suggested size: 10 elements t.add(&s); t.add(&s2); printf("%s %s\n", t[s]->str, t[s3]->str); // prints "foo" "foo" }
Here, the WvStrings "foo" and "blue" are stored in the table, and then "foo" is looked up twice. Both table searches return &s. The suggested table size of 10 elements places no upper bound on the maximum number of elements, but optimizes the hash table for holding roughly 10 elements.
To match an element, the WvString operator== function is used. That means this particular example is rather contrived since if you already have the search string, you do not need to find it in the table. Objects with more specific operator== might have more luck.
DICTIONARY EXAMPLE:
class IntStr { int *key; WvString data; } DeclareWvDict(IntStr, int, key[0]); IntStrDict d(100);
Here, we are creating a dictionary that stores strings indexed by integers. d[5] might return the address of IntStr number 5, which in turn contains WvString number 5. When matching elements in this case, a comparison is only done on key[0] of the two elements; thus, it is not the operator== of IntStr that is important, but rather the operator== for int. (In this case, the operator== of int is predefined.)
The only reason *key is declared as a pointer in this example is to demonstrate how to use pointer-based keys with our syntax. In this case it would certainly make more sense to use int key; and DeclareWvDict(IntStr, key). Note though, that int *key; and DeclareWvDict(IntStr, key) is almost certainly not what you want, since it would compare the POINTERS, not their values.
The interface of this class resembles that of WvList by design. In particular, we support iterators in a similar way.
Putting common code in here allows us to prevent it from being replicated by each template instantiation of WvHashTable<T>.
Definition at line 88 of file wvhashtable.h.
size_t WvHashTableBase::count | ( | ) | const |
Returns the number of elements in the hash table.
Returns: the number of elements
Definition at line 51 of file wvhashtable.cc.
bool WvHashTableBase::isempty | ( | ) | const |
Returns true if the hash table is empty.
Returns: true if empty
Definition at line 61 of file wvhashtable.cc.