WvStreams
Classes | Public Member Functions | Public Attributes | Protected Member Functions | List of all members
WvHashTableBase Class Referenceabstract

A small, efficient, type-safe hash table (also known as dictionary) container class. More...

#include <wvhashtable.h>

Inheritance diagram for WvHashTableBase:
Inheritance graph
[legend]

Classes

class  IterBase
 

Public Member Functions

size_t count () const
 Returns the number of elements in the hash table. More...
 
bool isempty () const
 Returns true if the hash table is empty. More...
 

Public Attributes

unsigned numslots
 
WvListBasewvslots
 

Protected Member Functions

 WvHashTableBase (unsigned _numslots)
 
WvHashTableBaseoperator= (const WvHashTableBase &t)
 
void setup ()
 
void shutdown ()
 
WvLinkprevlink (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
 

Detailed Description

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.

See also
WvList<T> The untyped base class of WvHashTable<T>.

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.

Member Function Documentation

◆ count()

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.

◆ isempty()

bool WvHashTableBase::isempty ( ) const

Returns true if the hash table is empty.

Returns: true if empty

Definition at line 61 of file wvhashtable.cc.


The documentation for this class was generated from the following files: