csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler > Class Template Reference
[Containers]
A generic hash table class, which grows dynamically and whose buckets are unsorted arrays. More...
#include <csutil/hash.h>
Classes | |
class | ConstGlobalIterator |
An const iterator class for the csHash class. More... | |
class | ConstIterator |
An const iterator class for the csHash class. More... | |
class | GlobalIterator |
An iterator class for the csHash class. More... | |
class | Iterator |
An iterator class for the csHash class. More... | |
Public Member Functions | |
bool | Contains (const K &key) const |
Returns whether at least one element matches the given key. | |
csHash (const csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler > &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. | |
csArray< T > | GetAll () const |
Get all the elements, 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. | |
T & | GetOrCreate (const K &key, const T &defaultValue=T()) |
Get the first element matching the given key, or, if there is none, insert default and return a reference to the new entry. | |
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. | |
T * | operator[] (const K &key) |
h["key"] shorthand notation for h.GetElementPointer ("key") | |
T & | Put (const K &key, const T &value) |
Add an element to the hash table. | |
T & | PutUnique (const K &key, const T &value) |
Add an element to the hash table, overwriting if the key already exists. |
Detailed Description
template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
class csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >
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* and csString for which appropriate specializations are already provided) or special hash algorithms.
Definition at line 128 of file hash.h.
Constructor & Destructor Documentation
csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::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/
csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::csHash | ( | const csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler > & | o | ) | [inline] |
Member Function Documentation
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Contains | ( | const K & | key | ) | const [inline] |
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Delete | ( | const K & | key, | |
const T & | value | |||
) | [inline] |
Delete all the elements matching the given key and value.
Reimplemented in csHashReversible< T, K >.
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::DeleteAll | ( | const K & | key | ) | [inline] |
Delete all the elements matching the given key.
Reimplemented in csHashReversible< T, K >.
void csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::DeleteAll | ( | ) | [inline] |
Delete all the elements.
Reimplemented in csHashReversible< T, K >.
void csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::DeleteElement | ( | ConstGlobalIterator & | iterator | ) | [inline] |
void csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::DeleteElement | ( | GlobalIterator & | iterator | ) | [inline] |
void csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Empty | ( | ) | [inline] |
Delete all the elements. (Idiomatic alias for DeleteAll().).
T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Get | ( | const K & | key, | |
T & | fallback | |||
) | [inline] |
const T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Get | ( | const K & | key, | |
const T & | fallback | |||
) | const [inline] |
csArray<T, H, M> csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetAll | ( | const K & | key | ) | const [inline] |
T* csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetElementPointer | ( | const K & | key | ) | [inline] |
const T* csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetElementPointer | ( | const K & | key | ) | const [inline] |
ConstGlobalIterator csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::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.
ConstIterator csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::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.
GlobalIterator csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::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.
Reimplemented in CS::Container::WeakKeyedHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >, and CS::Container::WeakKeyedHash< csRef< CachedCursor >, csWeakRef< iImage > >.
Iterator csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::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.
T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetOrCreate | ( | const K & | key, | |
const T & | defaultValue = T() | |||
) | [inline] |
size_t csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetSize | ( | ) | const [inline] |
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::In | ( | const K & | key | ) | const [inline] |
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::IsEmpty | ( | ) | const [inline] |
T* csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::operator[] | ( | const K & | key | ) | [inline] |
T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::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 >, CS::Container::WeakKeyedHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >, and CS::Container::WeakKeyedHash< csRef< CachedCursor >, csWeakRef< iImage > >.
T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::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 >.
The documentation for this class was generated from the following file:
- csutil/hash.h
Generated for Crystal Space 2.0 by doxygen 1.6.1