Chrono::Engine C++ API
Public Types | Public Member Functions | Friends
chrono::ChHashTable< K, T, H, E > Class Template Reference

#include <ChHashTable.h>

List of all members.

Public Types

typedef unsigned size_type
typedef K key_type
typedef T data_type
typedef T mapped_type
typedef std::pair< const K, T > value_type
typedef ch_hash_iterator< K, T,
H, E, value_type > 
iterator
typedef ch_hash_iterator< K, T,
H, E, const value_type > 
const_iterator

Public Member Functions

 ChHashTable (unsigned bins=0)
 ChHashTable (const ChHashTable &)
ChHashTableoperator= (const ChHashTable &)
bool empty (void) const
unsigned size (void) const
bool operator== (const ChHashTable &) const
bool operator!= (const ChHashTable &) const
void auto_rehash (void)
void manual_rehash (void)
void rehash (unsigned bins=0)
float loading (void) const
bool present (const K &key) const
size_type count (const K &key) const
iterator insert (const K &key, const T &data)
std::pair< iterator, bool > insert (const value_type &value)
iterator insert (const K &key)
bool erase (const K &key)
void erase (void)
void clear (void)
const_iterator find (const K &key) const
iterator find (const K &key)
const T & operator[] (const K &key) const
T & operator[] (const K &key)
const_iterator begin (void) const
iterator begin (void)
const_iterator end (void) const
iterator end (void)

Friends

class hash_element< K, T >
class ch_hash_iterator< K, T, H, E, std::pair< const K, T > >
class ch_hash_iterator< K, T, H, E, const std::pair< const K, T > >

Detailed Description

template<typename K, typename T, class H = HashFunction_Generic<K>, class E = std::equal_to<K>>
class chrono::ChHashTable< K, T, H, E >

The ChHashTable class. This container is most useful when you need a quasi-constant-time retrieval of a value, given its key. In fact, this container stores 'pairs' of values-keys, where keys should be unique (an example: a key could be the credit card number, and the value could be a structure with name, age and address of the credit card owner). When the hash table is filled too much, the performance get worse. Also, when you fill it beyond the initial suggested number of bins, an automatic table resizing (with rehashing) is performed. This may be a time-consuming cpu operation! So, choose initial size as close as possible to the maximum number of elements that you foresee to insert, plus some more space (es: +50%) to avoid performance degradation.

K = key type T = value type H = hash function object with the profile 'unsigned H(const K&)' E = equal function object with the profile 'bool E(const K&, const K&)' defaults to equal_to which in turn calls '=='


Constructor & Destructor Documentation

template<typename K , typename T , class H , class E >
chrono::ChHashTable< K, T, H, E >::ChHashTable ( unsigned  bins = 0)

Construct a ChHashTable table with specified number of bins. The default 0 bins means leave it to the table to decide. Specifying 0 bins also enables auto-rehashing, otherwise auto-rehashing defaults off


Member Function Documentation

template<typename K , typename T , class H , class E >
ChHashTable< K, T, H, E >::const_iterator chrono::ChHashTable< K, T, H, E >::begin ( void  ) const

Iterators allow the hash table to be traversed Iterators remain valid unless an item is removed or unless a rehash happens

template<typename K , typename T , class H , class E >
bool chrono::ChHashTable< K, T, H, E >::empty ( void  ) const

Test for an empty table and for the size of a table Efficient because the size is stored separately from the table contents

template<typename K, typename T , class H , class E >
ChHashTable< K, T, H, E >::const_iterator chrono::ChHashTable< K, T, H, E >::find ( const K &  key) const

Find a key and return an iterator to it The iterator is like a pointer to a pair<const K,T> end() is returned if the find fails

template<typename K , typename T , class H , class E >
float chrono::ChHashTable< K, T, H, E >::loading ( void  ) const

Test the loading ratio, which is the size divided by the number of bins. Use this if you are doing your own rehashing.

template<typename K, typename T , class H , class E >
const T & chrono::ChHashTable< K, T, H, E >::operator[] ( const K &  key) const

Returns the data corresponding to the key the const version is used by the compiler on const hashes and cannot change the hash, so find failure causes an exception the non-const version is used by the compiler on non-const hashes and is like map - it creates a new key/data pair if find fails

template<typename K , typename T , class H , class E >
void chrono::ChHashTable< K, T, H, E >::rehash ( unsigned  bins = 0)

Force a rehash now Default of 0 means implement built-in size calculation for rehashing (recommended - it doubles the number of bins)