MAUtil::HashMap< Key, Value > Class Template Reference

#include <MAUtil/HashMap.h>

List of all members.

---

Detailed Description

template<class Key, class Value>
class MAUtil::HashMap< Key, Value >

Thin template HashMap.

The HashMap is a data storage mechanism that stores unique keys, and a value associated with each key.

It has very fast insert, erase and lookup operations, assuming a good hash function is being used. For a perfect hash function (which generally doesn't exist), lookups and erases take constant time, while inserts run in constant time amortized over O(n).

It has an Iterator, which allows you to access all elements. The HashMap is not sorted. For each iteration, you will get an undefined, semi-random order of elements.

This particular implementation is built on top of kazlib's hash table system, which makes it quite small, even when used with multiple data types.

Public Types
typedef Pair< Key, Value >	PairKV
typedef hash_val_t(*	HashFunction )(const Key &)
typedef int(*	CompareFunction )(const Key &, const Key &)
Public Member Functions
	HashMap (HashFunction hf=&THashFunction< Key >, CompareFunction cf=&Compare< Key >, int init_bits=6)
	HashMap (const HashMap &)
	Constructs a copy of another HashMap. All elements are also copied.
HashMap &	operator= (const HashMap &)
	Clears this HashMap, then copies the other HashMap to this one.
	~HashMap ()
	The destructor deletes all elements.
Pair< Iterator, bool >	insert (const Key &, const Value &)
Iterator	find (const Key &)
ConstIterator	find (const Key &) const
bool	erase (const Key &)
void	erase (Iterator)
size_t	size () const
void	clear ()
Iterator	begin ()
ConstIterator	begin () const
Iterator	end ()
ConstIterator	end () const
Value &	operator[] (const Key &)
Protected Member Functions
void	init ()
Static Protected Member Functions
static hnode_t *	alloc (void *)
static void	free (hnode_t *node, void *)
Protected Attributes
hash_t	mHash
HashFunction	mHashFunction
Classes
class	ConstIterator
class	Iterator
struct	HashNode

---

Member Typedef Documentation

template<class Key, class Value> typedef Pair<Key, Value> MAUtil::HashMap< Key, Value >::PairKV

template<class Key, class Value> typedef hash_val_t(* MAUtil::HashMap< Key, Value >::HashFunction)(const Key &)

template<class Key, class Value> typedef int(* MAUtil::HashMap< Key, Value >::CompareFunction)(const Key &, const Key &)

---

Constructor & Destructor Documentation

template<class Key, class Value> MAUtil::HashMap< Key, Value >::HashMap (  HashFunction  hf = &THashFunction< Key >, CompareFunction  cf = &Compare< Key >, int  init_bits = 6 )

Constructs an empty HashMap. Parameters: hf  The hash function. cf  The compare function. See Compare. init_bits  The intial size of the hash table is 2 to the power of this number. While the table grows and shrinks dynamically, it is possible to optimize if you're doing a known number of insertions directly after constructing the HashMap.

template<class Key, class Value> MAUtil::HashMap< Key, Value >::HashMap (  const HashMap< Key, Value > &   )

Constructs a copy of another HashMap. All elements are also copied.

template<class Key, class Value> MAUtil::HashMap< Key, Value >::~HashMap (   )

The destructor deletes all elements.

---

Member Function Documentation

template<class Key, class Value> MAUtil::HashMap< Key, Value > & MAUtil::HashMap< Key, Value >::operator= (  const HashMap< Key, Value > &   )

Clears this HashMap, then copies the other HashMap to this one.

template<class Key, class Value> MAUtil::Pair< typename MAUtil::HashMap< Key, Value >::Iterator, bool > MAUtil::HashMap< Key, Value >::insert (  const Key &  , const Value &  )

Inserts a new key into the HashMap. Returns a Pair. The Pair's second element is true if the value was indeed inserted. The Pair's first element is an Iterator that points to the element in the HashMap. An element which compares equal to the new one may already be present in the HashMap; in that case, this operation does nothing, and the Iterator returned will point to the old element.

template<class Key, class Value> MAUtil::HashMap< Key, Value >::Iterator MAUtil::HashMap< Key, Value >::find (  const Key &   )

Searches the HashMap for a specified Key. The returned Iterator points to the element matching the Key if one was found, or to HashMap::end() if not.

template<class Key, class Value> MAUtil::HashMap< Key, Value >::ConstIterator MAUtil::HashMap< Key, Value >::find (  const Key &   )  const

template<class Key, class Value> bool MAUtil::HashMap< Key, Value >::erase (  const Key &   )

Deletes an element, matching the specified Key, from the HashMap. Returns true if an element was erased, or false if there was no element matching the Key.

template<class Key, class Value> void MAUtil::HashMap< Key, Value >::erase (  Iterator   )

Deletes an element, pointed to by the specified Iterator. The Iterator is invalidated, so if you want to continue iterating through the HashMap, you must use a different Iterator instance. Warning: If the Iterator is bound to a different HashMap, or if it points to end(), the system will crash.

template<class Key, class Value> size_t MAUtil::HashMap< Key, Value >::size (   )  const

Returns the number of elements in the HashMap.

template<class Key, class Value> void MAUtil::HashMap< Key, Value >::clear (   )

Deletes all elements.

template<class Key, class Value> MAUtil::HashMap< Key, Value >::Iterator MAUtil::HashMap< Key, Value >::begin (   )

Returns an Iterator pointing to the first element in the HashMap.

template<class Key, class Value> MAUtil::HashMap< Key, Value >::ConstIterator MAUtil::HashMap< Key, Value >::begin (   )  const

template<class Key, class Value> MAUtil::HashMap< Key, Value >::Iterator MAUtil::HashMap< Key, Value >::end (   )

Returns an Iterator pointing to a place beyond the last element of the HashMap. This Iterator is often used to determine when another Iterator has reached its end.

template<class Key, class Value> MAUtil::HashMap< Key, Value >::ConstIterator MAUtil::HashMap< Key, Value >::end (   )  const

template<class Key, class Value> Value & MAUtil::HashMap< Key, Value >::operator[] (  const Key &   )

The square bracket operator returns a reference to the Value corresponding to the specified Key. If the Key doesn't yet exist in the HashMap, it will be inserted with a default Value. There is no const variant of this function, because each call might potentially modify the HashMap by inserting a new key. Use find() if you have a const HashMap.

template<class Key, class Value> static hnode_t* MAUtil::HashMap< Key, Value >::alloc (  void *   )  [inline, static, protected]

template<class Key, class Value> static void MAUtil::HashMap< Key, Value >::free (  hnode_t *  node, void *  )  [inline, static, protected]

template<class Key, class Value> void MAUtil::HashMap< Key, Value >::init (   )  [protected]

---

Member Data Documentation

template<class Key, class Value> hash_t MAUtil::HashMap< Key, Value >::mHash [protected]

template<class Key, class Value> HashFunction MAUtil::HashMap< Key, Value >::mHashFunction [protected]

---