LDK::Hash< Key, Data, Alloc > Class Template Reference
[Containers, Containers, Containers]

A Hash specialised for c strings (const char *). More...

#include <LDK/CStringHash.h>

Inheritance diagram for LDK::Hash< Key, Data, Alloc >:

[legend]Collaboration diagram for LDK::Hash< Key, Data, Alloc >:

[legend]

Public Types
typedef Iterator	iterator
typedef ConstIterator	const_iterator
Public Member Functions
	Hash (size_t initialSize=100)
	Hash (const Hash &rhs)
	~Hash () throw ()
	Destructor.
Hash &	operator= (const Hash &rhs)
ConstIterator	find (const Key &key) const
Iterator	find (const Key &key)
Pair *	element (size_t idx)
const Pair *	element (size_t idx) const
void	set (const Key &k, const Data &d)
bool	insert (const Key &key, const Data &data)
bool	insert (const Pair &p)
Iterator	erase (const Key &key)
Iterator	erase (Iterator it)
size_t	size () const
size_t	allocated () const
Iterator	begin ()
ConstIterator	begin () const
Iterator	end ()
ConstIterator	end () const
void	clear ()
	Clears all elements. Does not resize the table.
DataProxy	operator[] (const Key &k)
const Data &	operator[] (const Key &k) const
Protected Types
typedef Alloc< Pair >	PairAlloc
typedef Alloc< Pair * >	PairPtrAlloc
Protected Member Functions
size_t	hash (const Key &k, size_t allocated) const
void	rehash (size_t newAlloc)
void	assign (const Hash &rhs)
Static Protected Member Functions
static size_t	primeGreaterThan (size_t size)
static size_t	newSize (size_t currentSize, size_t freeSlots)
Protected Attributes
PairAlloc	mPairAlloc
PairPtrAlloc	mPairPtrAlloc
Pair **	mArray
size_t	mAllocated
size_t	mFreeSlots
size_t	mSize
Static Protected Attributes
static const int	cIncBy = 7
Data Structures
class	ConstIterator
	Allows iteration over a const Hash. More...
class	DataProxy
	Returned by an "[]" operator to allow transparent getting and setting of keys/value pairs. More...
class	Iterator
	Allows iteration over a non-const Hash. More...
class	Pair
	A sensible, less generic substitute for std::pair<>. More...

---

Detailed Description

template<class Key, class Data, template< class > class Alloc = Allocator>
class LDK::Hash< Key, Data, Alloc >

Uses a array of Hash::Pairs to store its data, so it is a simple associative array. NOT STL compliant, so cannot be used with the std::algorithms. That should not be much of a problem for a hash table though.

A partial specialisation Hash<const char*, Data> is provided for using c-style strings as keys - it copies and holds the strings internally. This is probably the fastest string key Hash.

Note that many methods can pass through Runtime and BadAlloc exceptions from methods and functions they call. Influenced by hash table code by Per Nilson available at http://www.codeguru.com/Cpp/Cpp/algorithms/hash/

Warning: Uses LDK::Allocator by default, so DON'T use this class across threads without changing it to an LDK::MallocAllocator.

Definition at line 173 of file Hash.h.

---

Constructor & Destructor Documentation

template<class Key, class Data, template< class > class Alloc = Allocator>

LDK::Hash< Key, Data, Alloc >::Hash

(

size_t

initialSize = 100

)

[inline]

Constructor

Parameters:

initialSize

Initial possible entries in the table (will get rounded up to the nearest prime number.

Exceptions:

BadAlloc

if the table cannot be allocated.

Definition at line 555 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

LDK::Hash< Key, Data, Alloc >::Hash

(

const Hash< Key, Data, Alloc > &

rhs

)

[inline]

Copy constructor

Parameters:

rhs

The hash to copy

Exceptions:

BadAlloc

if the table cannot be allocated.

Definition at line 571 of file Hash.h.

---

Member Function Documentation

template<class Key, class Data, template< class > class Alloc = Allocator>

Hash& LDK::Hash< Key, Data, Alloc >::operator=

(

const Hash< Key, Data, Alloc > &

rhs

)

[inline]

Assignment operator

Parameters:

rhs

The hash to copy

Exceptions:

BadAlloc

if the table cannot be allocated.

Definition at line 590 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

ConstIterator LDK::Hash< Key, Data, Alloc >::find

(

const Key &

key

)

const [inline]

Find an ConstIterator assocated with a key.

Parameters:

key

The key to search for in the table

Returns:

A ConstIterator referencing the Pair containing the desired key and data, or Hash::end() const if the key is not present in the table.

Definition at line 610 of file Hash.h.

References LDK::Hash< Key, Data, Alloc >::Pair::mData, LDK::Hash< Key, Data, Alloc >::Pair::mKey, and NULL.

template<class Key, class Data, template< class > class Alloc = Allocator>

Iterator LDK::Hash< Key, Data, Alloc >::find

(

const Key &

key

)

[inline]

Find an Iterator assocated with a key.

Parameters:

key

The key to search for in the table

Returns:

A Iterator referencing the Pair containing the desired key and data, or Hash::end() if the key is not present in the table.

Definition at line 643 of file Hash.h.

References LDK::Hash< Key, Data, Alloc >::Pair::mData, and LDK::Hash< Key, Data, Alloc >::Pair::mKey.

template<class Key, class Data, template< class > class Alloc = Allocator>

Pair* LDK::Hash< Key, Data, Alloc >::element

(

size_t

idx

)

[inline]

Get a pointer to the Pair at an index in the table

Parameters:

idx

The index to look at

Returns:

A pointer to the table element at idx

Definition at line 674 of file Hash.h.

References LDK_INDEX_ERROR.

Referenced by LDK::Hash< Key, Data, Alloc >::rehash().

template<class Key, class Data, template< class > class Alloc = Allocator>

const Pair* LDK::Hash< Key, Data, Alloc >::element

(

size_t

idx

)

const [inline]

Get a const pointer to the Pair at an index in the table

Parameters:

idx

The index to look at

Returns:

A const pointer to the table element at idx

Definition at line 684 of file Hash.h.

References LDK_INDEX_ERROR.

template<class Key, class Data, template< class > class Alloc = Allocator>

void LDK::Hash< Key, Data, Alloc >::set	(	const Key &	k,
		const Data &	d
	)			[inline]

Associate some data with a key. Can associate a new piece of data with a key already in the table.

Parameters:

	k	The key to associate the data with
	d	The data to associate with key

Exceptions:

IndexError

if there is a problem inserting a new key/data pair

Definition at line 696 of file Hash.h.

References LDK_INDEX_ERROR.

template<class Key, class Data, template< class > class Alloc = Allocator>

bool LDK::Hash< Key, Data, Alloc >::insert	(	const Key &	key,
		const Data &	data
	)			[inline]

Associate some data with a key. Assumes the key is NOT already in the table.

Parameters:

	key	The key to associate the data with
	data	The data to associate with key

Returns:

True if successful, false otherwise.

Definition at line 712 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

bool LDK::Hash< Key, Data, Alloc >::insert

(

const Pair &

p

)

[inline]

Insert a Pair into the table.

Parameters:

p

The key/data pair to insert.

Returns:

True if successful, false otherwise.

Definition at line 749 of file Hash.h.

References LDK::Hash< Key, Data, Alloc >::Pair::mData, and LDK::Hash< Key, Data, Alloc >::Pair::mKey.

template<class Key, class Data, template< class > class Alloc = Allocator>

Iterator LDK::Hash< Key, Data, Alloc >::erase

(

const Key &

key

)

[inline]

Erase an element associated with a key.

Parameters:

key

The key associated with the element to erase.

Returns:

end() if key is not in the table, otherwise an Iterator referencing the element after the erased element.

Definition at line 755 of file Hash.h.

References LDK::Hash< Key, Data, Alloc >::Iterator::index(), and NULL.

Here is the call graph for this function:

template<class Key, class Data, template< class > class Alloc = Allocator>

Iterator LDK::Hash< Key, Data, Alloc >::erase

(

Iterator

it

)

[inline]

Erase an element referenced by an Iterator.

Parameters:

it

The Iterator referencing the element to erase.

Returns:

end() if key is not in the table, otherwise an Iterator referencing the element after the erased element.

Exceptions:

LogicError

if the Iterator references a different Hash instance.

Definition at line 776 of file Hash.h.

References LDK::Hash< Key, Data, Alloc >::Iterator::index(), LDK::Hash< Key, Data, Alloc >::Iterator::mHash, and NULL.

Here is the call graph for this function:

template<class Key, class Data, template< class > class Alloc = Allocator>

size_t LDK::Hash< Key, Data, Alloc >::size

(

)

const [inline]

Get the number of used elements in the table.

Returns:

The number of used elements.

Definition at line 793 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

size_t LDK::Hash< Key, Data, Alloc >::allocated

(

)

const [inline]

Get the size of the allocated internal table.

Returns:

The size of the internal table.

Definition at line 797 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

Iterator LDK::Hash< Key, Data, Alloc >::begin

(

)

[inline]

Get an iterator that references the first element in the table.

Returns:

An Iterator that references the first element in the table.

Definition at line 801 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

ConstIterator LDK::Hash< Key, Data, Alloc >::begin

(

)

const [inline]

Get an iterator that references the first element in the table.

Returns:

A ConstIterator that references the first element in the table.

Definition at line 805 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

Iterator LDK::Hash< Key, Data, Alloc >::end

(

)

[inline]

Get an iterator that is one past the end of the table.

Returns:

An Iterator that is one past the end of the table.

Definition at line 809 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

ConstIterator LDK::Hash< Key, Data, Alloc >::end

(

)

const [inline]

Get an iterator that is one past the end of the table.

Returns:

A ConstIterator that is one past the end of the table.

Definition at line 813 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

DataProxy LDK::Hash< Key, Data, Alloc >::operator[]

(

const Key &

k

)

[inline]

Makes the Hash resemble a simple array.

Returns:

A DataProxy to allow automatic getting and setting of the data associated with key.

Exceptions:

IndexError

if the key is not present in the table.

Definition at line 837 of file Hash.h.

template<class Key, class Data, template< class > class Alloc = Allocator>

const Data& LDK::Hash< Key, Data, Alloc >::operator[]

(

const Key &

k

)

const [inline]

Makes the Hash resemble a simple array. Does not require a DataProxy because this method does not allow setting of the data associated with key.

Returns:

A const reference to the data associated with key.

Exceptions:

IndexError

if the key is not present in the table.

Definition at line 843 of file Hash.h.

References LDK_INDEX_ERROR.

---

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

• Hash.h

---