Public API Reference

csHash< T, K, ArrayMemoryAlloc > Class Template Reference
[Containers]

A generic hash table class, which grows dynamically and whose buckets are unsorted arrays. More...

#include <csutil/hash.h>

Inheritance diagram for csHash< T, K, ArrayMemoryAlloc >:

[legend]List of all members.

Public Member Functions
bool	Contains (const K &key) const
	Returns whether at least one element matches the given key.
	csHash (const csHash< T > &o)
	Copy constructor.
	csHash (size_t size=23, size_t grow_rate=5, size_t max_size=20000)
	Construct a hash table with an array of the given size, which for optimisation reasons should be a prime number.
bool	Delete (const K &key, const T &value)
	Delete all the elements matching the given key and value.
bool	DeleteAll (const K &key)
	Delete all the elements matching the given key.
void	DeleteAll ()
	Delete all the elements.
void	DeleteElement (ConstGlobalIterator &iterator)
	Delete the element pointed by the iterator.
void	DeleteElement (GlobalIterator &iterator)
	Delete the element pointed by the iterator.
void	Empty ()
	Delete all the elements. (Idiomatic alias for DeleteAll().).
T &	Get (const K &key, T &fallback)
	Get the first element matching the given key, or fallback if there is none.
const T &	Get (const K &key, const T &fallback) const
	Get the first element matching the given key, or fallback if there is none.
template<typename H, typename M>
csArray< T, H, M >	GetAll (const K &key) const
	Get all the elements with the given key, or empty if there are none.
csArray< T >	GetAll (const K &key) const
	Get all the elements with the given key, or empty if there are none.
T *	GetElementPointer (const K &key)
	Get a pointer to the first element matching the given key, or 0 if there is none.
const T *	GetElementPointer (const K &key) const
	Get a pointer to the first element matching the given key, or 0 if there is none.
ConstGlobalIterator	GetIterator () const
	Return a const iterator for the hash, to iterate over all elements.
ConstIterator	GetIterator (const K &key) const
	Return a const iterator for the hash, to iterate only over the elements with the given key.
GlobalIterator	GetIterator ()
	Return an iterator for the hash, to iterate over all elements.
Iterator	GetIterator (const K &key)
	Return an iterator for the hash, to iterate only over the elements with the given key.
size_t	GetSize () const
	Get the number of elements in the hash.
bool	In (const K &key) const
	Returns whether at least one element matches the given key.
bool	IsEmpty () const
	Return true if the hash is empty.
void	Put (const K &key, const T &value)
	Add an element to the hash table.
void	PutFirst (const K &key, const T &value)
	Add an element to the hash table, overwriting if the key already exists.
void	PutUnique (const K &key, const T &value)
	Add an element to the hash table, overwriting if the key already exists.
Protected Types
typedef csArray< Element, csArrayElementHandler< Element >, ArrayMemoryAlloc >	ElementArray
Protected Attributes
csArray< ElementArray, csArrayElementHandler< ElementArray >, ArrayMemoryAlloc >	Elements
size_t	Modulo
Friends
class	ConstGlobalIterator
class	ConstIterator
class	GlobalIterator
class	Iterator
Classes
class	ConstGlobalIterator
	An const iterator class for the hash. More...
class	ConstIterator
	An const iterator class for the hash. More...
struct	Element
class	GlobalIterator
	An iterator class for the hash. More...
class	Iterator
	An iterator class for the hash. More...

---

Detailed Description

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>
class csHash< T, K, ArrayMemoryAlloc >

A generic hash table class, which grows dynamically and whose buckets are unsorted arrays.

The hash value of a key is computed using csHashComputer<>, two keys are compared using csComparator<>. You need to provide appropriate specializations of those templates if you want use non-integral types (other than const char*, csStrKey and csString for which appropriate specializations are already provided) or special hash algorithms.

Definition at line 256 of file hash.h.

---

Constructor & Destructor Documentation

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

csHash< T, K, ArrayMemoryAlloc >::csHash	(	size_t	size = 23,
		size_t	grow_rate = 5,
		size_t	max_size = 20000
	)			[inline]

Construct a hash table with an array of the given size, which for optimisation reasons should be a prime number.

grow_rate is the rate at which the hash table grows: size doubles once there are size/grow_rate collisions. It will not grow after it reaches max_size.

Here are a few primes: 7, 11, 19, 29, 59, 79, 101, 127, 151, 199, 251, 307, 401, 503, 809, 1009, 1499, 2003, 3001, 5003, 12263, 25247, 36923, 50119, 70951, 90313, 104707.

For a bigger list go to http://www.utm.edu/research/primes/

Definition at line 333 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

csHash< T, K, ArrayMemoryAlloc >::csHash

(

const csHash< T > &

o

)

[inline]

Copy constructor.

Definition at line 340 of file hash.h.

---

Member Function Documentation

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

bool csHash< T, K, ArrayMemoryAlloc >::Contains

(

const K &

key

)

const [inline]

Returns whether at least one element matches the given key.

Definition at line 421 of file hash.h.

Referenced by csSet< csPtrKey< iMeshWrapper > >::Contains().

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

bool csHash< T, K, ArrayMemoryAlloc >::Delete	(	const K &	key,
		const T &	value
	)			[inline]

Delete all the elements matching the given key and value.

Definition at line 553 of file hash.h.

Referenced by csSet< csPtrKey< iMeshWrapper > >::Delete().

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

bool csHash< T, K, ArrayMemoryAlloc >::DeleteAll

(

const K &

key

)

[inline]

Delete all the elements matching the given key.

Definition at line 533 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

void csHash< T, K, ArrayMemoryAlloc >::DeleteAll

(

)

[inline]

Delete all the elements.

Definition at line 522 of file hash.h.

Referenced by csSet< csPtrKey< iMeshWrapper > >::DeleteAll().

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

void csHash< T, K, ArrayMemoryAlloc >::DeleteElement

(

ConstGlobalIterator &

iterator

)

[inline]

Delete the element pointed by the iterator.

This is safe for this iterator, not for the others.

Definition at line 939 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

void csHash< T, K, ArrayMemoryAlloc >::DeleteElement

(

GlobalIterator &

iterator

)

[inline]

Delete the element pointed by the iterator.

This is safe for this iterator, not for the others.

Definition at line 929 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

void csHash< T, K, ArrayMemoryAlloc >::Empty

(

)

[inline]

Delete all the elements. (Idiomatic alias for DeleteAll().).

Definition at line 530 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

T& csHash< T, K, ArrayMemoryAlloc >::Get	(	const K &	key,
		T &	fallback
	)			[inline]

Get the first element matching the given key, or fallback if there is none.

Definition at line 505 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

const T& csHash< T, K, ArrayMemoryAlloc >::Get	(	const K &	key,
		const T &	fallback
	)			const [inline]

Get the first element matching the given key, or fallback if there is none.

Definition at line 485 of file hash.h.

Referenced by csHashReversible< T, K >::GetKey().

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

template<typename H, typename M>

csArray<T, H, M> csHash< T, K, ArrayMemoryAlloc >::GetAll

(

const K &

key

)

const [inline]

Get all the elements with the given key, or empty if there are none.

Definition at line 371 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

csArray<T> csHash< T, K, ArrayMemoryAlloc >::GetAll

(

const K &

key

)

const [inline]

Get all the elements with the given key, or empty if there are none.

Definition at line 363 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

T* csHash< T, K, ArrayMemoryAlloc >::GetElementPointer

(

const K &

key

)

[inline]

Get a pointer to the first element matching the given key, or 0 if there is none.

Definition at line 465 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

const T* csHash< T, K, ArrayMemoryAlloc >::GetElementPointer

(

const K &

key

)

const [inline]

Get a pointer to the first element matching the given key, or 0 if there is none.

Definition at line 445 of file hash.h.

Referenced by csHashReversible< T, K >::GetKeyPointer().

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

ConstGlobalIterator csHash< T, K, ArrayMemoryAlloc >::GetIterator

(

)

const [inline]

Return a const iterator for the hash, to iterate over all elements.

Warning:

Modifying the hash (except with DeleteElement()) while you have open iterators will result in undefined behaviour.

Definition at line 984 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

ConstIterator csHash< T, K, ArrayMemoryAlloc >::GetIterator

(

const K &

key

)

const [inline]

Return a const iterator for the hash, to iterate only over the elements with the given key.

Warning:

Modifying the hash (except with DeleteElement()) while you have open iterators will result in undefined behaviour.

Definition at line 974 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

GlobalIterator csHash< T, K, ArrayMemoryAlloc >::GetIterator

(

)

[inline]

Return an iterator for the hash, to iterate over all elements.

Warning:

Modifying the hash (except with DeleteElement()) while you have open iterators will result in undefined behaviour.

Definition at line 963 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

Iterator csHash< T, K, ArrayMemoryAlloc >::GetIterator

(

const K &

key

)

[inline]

Return an iterator for the hash, to iterate only over the elements with the given key.

Warning:

Modifying the hash (except with DeleteElement()) while you have open iterators will result in undefined behaviour.

Definition at line 953 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

size_t csHash< T, K, ArrayMemoryAlloc >::GetSize

(

)

const [inline]

Get the number of elements in the hash.

Definition at line 574 of file hash.h.

Referenced by csSet< csPtrKey< iMeshWrapper > >::GetSize().

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

bool csHash< T, K, ArrayMemoryAlloc >::In

(

const K &

key

)

const [inline]

Returns whether at least one element matches the given key.

Remarks:

This is rigidly equivalent to Contains(key), but may be considered more idiomatic by some.

Definition at line 438 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

bool csHash< T, K, ArrayMemoryAlloc >::IsEmpty

(

)

const [inline]

Return true if the hash is empty.

Remarks:

Rigidly equivalent to return GetSize() == 0, but more idiomatic.

Definition at line 584 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

void csHash< T, K, ArrayMemoryAlloc >::Put	(	const K &	key,
		const T &	value
	)			[inline]

Add an element to the hash table.

Remarks:

If `key' is already present, does NOT replace the existing value, but merely adds `value' as an additional value of `key'. To retrieve all values for a given key, use GetAll(). If you instead want to replace an existing value for 'key', use PutUnique().

Reimplemented in csHashReversible< T, K >.

Definition at line 351 of file hash.h.

Referenced by csSet< csPtrKey< iMeshWrapper > >::AddNoTest(), and csHashReversible< T, K >::Put().

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

void csHash< T, K, ArrayMemoryAlloc >::PutFirst	(	const K &	key,
		const T &	value
	)			[inline]

Add an element to the hash table, overwriting if the key already exists.

Deprecated:

Use PutUnique() instead.

Definition at line 415 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc>

void csHash< T, K, ArrayMemoryAlloc >::PutUnique	(	const K &	key,
		const T &	value
	)			[inline]

Add an element to the hash table, overwriting if the key already exists.

Reimplemented in csHashReversible< T, K >.

Definition at line 388 of file hash.h.

Referenced by csHashReversible< T, K >::PutUnique().

---

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

• csutil/hash.h

---