HashTable< Key, Value, Hasher, KeyEqual > Class Template Reference

#include <hashtable.h>

Inheritance diagram for HashTable< Key, Value, Hasher, KeyEqual >:

Collaboration diagram for HashTable< Key, Value, Hasher, KeyEqual >:

Public Types
typedef KeyValue	value_type
typedef HashTableDetail::BucketIterator < Key, Value, hash_type >	iterator
Public Member Functions
	HashTable ()
	HashTable (std::size_t bucketCount)
	~HashTable ()
iterator	begin ()
iterator	end ()
bool	empty () const
std::size_t	size () const
iterator	find (const Key &key)
	Returns an iterator pointing to the value associated with `key` if it is contained by the hash-table, else `end()`.
iterator	insert (const Key &key, const Value &value)
	Adds `value` to the hash-table associated with `key` if it does not exist.
void	erase (iterator i)
	Removes the value pointed to by `i` from the hash-table.
Value &	operator[] (const Key &key)
	Returns the value identified by `key` if it is contained by the hash-table, else inserts and returns a new default-constructed value associated with `key`.
void	erase (const Key &key)
	Removes the value associated with `key` from the hash-table.
void	swap (HashTable &other)
	Swaps the contents of the hash-table with `other`.
void	clear ()
	Removes all values from the hash-table.
Private Types
typedef Hasher::hash_type	hash_type
typedef HashTableDetail::KeyValue< Key, Value >	KeyValue
typedef HashTableDetail::BucketNode < Key, Value, hash_type >	BucketNode
typedef BucketNode *	Bucket
Private Member Functions
BucketNode *	node_create (hash_type hash, const Key &key, const Value &value)
void	node_destroy (BucketNode *node)
BucketNode *	getFirst ()
BucketNode *	getLast ()
void	initialise ()
hash_type	hashKey (const Key &key)
std::size_t	getBucketId (hash_type hash) const
Bucket &	getBucket (hash_type hash)
BucketNode *	bucket_find (Bucket bucket, hash_type hash, const Key &key)
BucketNode *	bucket_insert (Bucket &bucket, BucketNode *node)
BucketNode *	bucket_next (Bucket &bucket)
void	buckets_resize (std::size_t count)
void	size_increment ()
void	size_decrement ()
	HashTable (const HashTable &other)
HashTable &	operator= (const HashTable &other)
Static Private Member Functions
static Bucket *	buckets_new (std::size_t count)
static void	buckets_delete (Bucket *buckets)
Private Attributes
std::size_t	m_bucketCount
Bucket *	m_buckets
std::size_t	m_size
HashTableDetail::BucketNodeBase	m_list

Detailed Description

template<typename Key, typename Value, typename Hasher, typename KeyEqual = std::equal_to<Key>>
class HashTable< Key, Value, Hasher, KeyEqual >

A hash-table container which maps keys to values.

Inserting or removing elements does not invalidate iterators.
Inserting or retrieving an element for a given key takes O(1) time on average.
Elements are stored in no particular order.

Parameters:

	Key	Uniquely identifies a value. Must provide a copy-constructor.
	Value	The value to be stored . Must provide a default-constructor and a copy-constructor.
	Hasher	Must provide 'stdsize_t operator()(const Key&) const' which always returns the same result if the same argument is given.
	KeyEqual	Must provide 'bool operator==(const Key&, const Key&) const' which returns true only if both arguments are equal.

Definition at line 165 of file hashtable.h.