Simple Application Framework: Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType > Class Template Reference

Simple Application Framework 1

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Unordered associative container. More...

#include <HashMap.h>

Inheritance diagram for Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >:

List of all members.

Public Types
typedef BaseType::ConstIterator	ConstIterator
	Bidirectional non-mutable HashTable iterator.
typedef BaseType::Iterator	Iterator
	Bidirectional mutable HashTable iterator.
Public Member Functions
	HashMap (Size bucketHint=0)
	Default constructor.
	HashMap (const MyType &d)
	Copy constructor.
ValType &	At (const KeyType &key)
	Get a reference to the value corresponding to a given key.
const ValType &	At (const KeyType &key) const
	Get a reference to the value corresponding to a given key.
MyType &	operator= (const MyType &d)
	Assignment operator.
ValType &	operator[] (const KeyType &key)
	Operator returning the reference to the value corresponding to a given key.
MyType &	Swap (MyType &d)
	Swap the content of two hash maps.
Iterator	Update (const KeyType &key, const ValType &val)
	Update the value corresponding to a given key.
Protected Types
typedef Algo::Struct::HashTable < KeyType, RecType, Algo::Selector::FirstMember < RecType >, HashFuncType, HashPolicyType, CompType >	BaseType
typedef HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >	MyType
typedef Pair< const KeyType, ValType >	RecType

Detailed Description

template<class KeyType, class ValType, class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>
class Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >

Unordered associative container.

This class implements an associative container where keys map to values. Internally, the data are stored in an unordered list and a hash table is used to enable fast insert, erase and look-up of values mapped to particular keys. If a hash function is chosen appropriately, all these operations can be performed in amortized constant time.

Iterator category: Bidirectional.

Template Parameters:

KeyType	Key data type. Each key can appear only once in the map.
ValType	Data type of the mapped values.
HashFuncType	Unary hash functor that takes values of `KeyType` and returns a value of type Saf::Size.
HashPolicyType	Hash policy object that controls which hashes map to which buckets and when and how to enlarge the bucket count. The policy should never allow zero bucket count.
CompType	A binary equality predicate on `KeyType`. Keys that have the same hash must be equal according to this predicate.

See also:: Algo::Struct::HashTable, Algo::Struct::HashTablePolicy, Algo::Hash, Collection::TreeMap.

Member Typedef Documentation

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

typedef Algo::Struct::HashTable<KeyType,RecType,Algo::Selector::FirstMember<RecType>,HashFuncType,HashPolicyType,CompType> Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::BaseType [protected]

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

typedef BaseType::ConstIterator Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::ConstIterator

Bidirectional non-mutable HashTable iterator.

Reimplemented from Saf::Algo::Struct::HashTable< KeyType, Pair< const KeyType, ValType >, Algo::Selector::FirstMember< Pair< const KeyType, ValType > >, HashFuncType, HashPolicyType, CompType >.

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

typedef BaseType::Iterator Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::Iterator

Bidirectional mutable HashTable iterator.

Reimplemented from Saf::Algo::Struct::HashTable< KeyType, Pair< const KeyType, ValType >, Algo::Selector::FirstMember< Pair< const KeyType, ValType > >, HashFuncType, HashPolicyType, CompType >.

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

typedef HashMap<KeyType,ValType,HashFuncType,HashPolicyType,CompType> Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::MyType [protected]

Reimplemented from Saf::Algo::Struct::HashTable< KeyType, Pair< const KeyType, ValType >, Algo::Selector::FirstMember< Pair< const KeyType, ValType > >, HashFuncType, HashPolicyType, CompType >.

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

typedef Pair<const KeyType,ValType> Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::RecType [protected]

Constructor & Destructor Documentation

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::HashMap ( Size bucketHint = 0 ) [inline, explicit]

Default constructor.

Parameters:

[in] bucketHint Minimum initial number of buckets. The actual number of buckets may be higher depending on the hash policy.

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::HashMap ( const MyType & d ) [inline]

Copy constructor.

Member Function Documentation

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

ValType& Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::At ( const KeyType & key ) [inline]

Get a reference to the value corresponding to a given key.

If the key does not exist in the HashMap then an IndexOutOfRangeException is thrown.

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

const ValType& Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::At ( const KeyType & key ) const [inline]

Get a reference to the value corresponding to a given key.

If the key does not exist in the HashMap then an IndexOutOfRangeException is thrown.

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

MyType& Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::operator= ( const MyType & d ) [inline]

Assignment operator.

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

ValType& Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::operator[] ( const KeyType & key ) [inline]

Operator returning the reference to the value corresponding to a given key.

If the key does not exist in the HashMap then it is created and the corresponding value is initialized using a default constructor.

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

MyType& Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::Swap ( MyType & d ) [inline]

Swap the content of two hash maps.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

template<class KeyType , class ValType , class HashFuncType = Algo::Hash<KeyType>, class HashPolicyType = Algo::Struct::HashPolicy::PrimePolicy, class CompType = Algo::Predicate::Equal<KeyType>>

Iterator Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >::Update	(	const KeyType &	key,
		const ValType &	val
	)		`[inline]`

Update the value corresponding to a given key.

If the key exists in the HashMap then its corresponding value is updated. Otherwise a new pair is inserted into the HashMap.

Remarks:: In general, should be a little bit faster than using map[key] = val.

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

Saf/Collection/HashMap.h