Hash map implementation backed by a template parameterized hash table. More...

#include <tpie/hash_map.h>

Inherits tpie::linear_memory_base< hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t > >.

Classes
class	iterator
	Non-const iterator type. More...

Public Types
typedef std::pair< key_t, data_t >	value_t

typedef iter_base< const tbl_t >	const_iterator
	Const iterator type. More...

Public Member Functions
	hash_map (size_t size=0, const hash_t &hash=hash_t(), const equal_t &equal=equal_t(), value_t u=default_unused< value_t >::v())
	Construct hash map. More...

void	resize (size_t size)
	Resize hash map to given size and remove all entries. More...

void	erase (const key_t &key)
	Erase entry from hash map by key. More...

void	erase (const iterator &iter)
	Erase entry from hash map by iterator. More...

bool	insert (const key_t &key, const data_t &data)
	Insert data into the hash map. More...

data_t &	operator[] (const key_t &key)
	Look up data by key, creating an unused entry if it does not exist. More...

const data_t &	operator[] (const key_t &key) const
	Look up data by key. More...

iterator	find (const key_t &key)
	Get iterator to element. More...

const_iterator	find (const key_t &key) const
	Get iterator to element. More...

bool	contains (const key_t &key) const
	Search for element with key. More...

iterator	begin ()
	Return iterator to beginning of map. More...

const_iterator	begin () const
	Return const iterator to beginning of map. More...

const_iterator	cbegin () const
	Return const iterator to beginning of map. More...

iterator	end ()
	Return iterator to end of map. More...

const_iterator	end () const
	Return const iterator to end of map. More...

const_iterator	cend () const
	Return const iterator to end of map. More...

size_t	size () const
	Return number of elements in map. More...

void	clear ()
	Clear hash map. More...

Static Public Member Functions
static double	memory_coefficient ()
	Return the memory coefficient of the structure. More...

static double	memory_overhead ()
	Return the memory overhead of the structure. More...

static memory_size_type	memory_usage (memory_size_type size)
	Return the number of bytes required to create a data structure supporting a given number of elements. More...

static memory_size_type	memory_fits (memory_size_type memory)
	Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes. More...

Detailed Description

template<typename key_t, typename data_t, typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>
class tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >

Hash map implementation backed by a template parameterized hash table.

Template Parameters

key_t	Type of keys to store.
data_t	Type of data associated with each key.
hash_t	(Optional) Hash function to use.
equal_t	(Optional) Equality predicate.
index_t	(Optional) Index type into bucket array. Always size_t.
table_t	(Optional) Hash table implementation.

Definition at line 377 of file hash_map.h.

Member Typedef Documentation

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

typedef iter_base<const tbl_t> tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::const_iterator

Const iterator type.

Definition at line 438 of file hash_map.h.

Constructor & Destructor Documentation

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::hash_map	(	size_t	size = `0`,
		const hash_t &	hash = `hash_t()`,
		const equal_t &	equal = `equal_t()`,
		value_t	u = `default_unused<value_t>::v()`
	)

inline

Construct hash map.

Parameters

size	Number of buckets in initial hash map.
hash	Hash function to use.
equal	Equality predicate to use.
u	Value to use for unused bucket entries.

Definition at line 484 of file hash_map.h.

486 :

487 tbl(size, u, key_hash_t(hash), key_equal_t(equal)) {}

tpie::hash_map::size

size_t size() const

Return number of elements in map.

Definition: hash_map.h:593

Member Function Documentation

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

iterator tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::begin ( )

inline

Return iterator to beginning of map.

Definition at line 563 of file hash_map.h.

563 {return iterator(tbl, tbl.begin());}

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

const_iterator tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::begin ( ) const

inline

Return const iterator to beginning of map.

Definition at line 568 of file hash_map.h.

568 {return const_iterator(tbl, tbl.begin());}

tpie::hash_map::const_iterator

iter_base< const tbl_t > const_iterator

Const iterator type.

Definition: hash_map.h:438

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

const_iterator tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::cbegin ( ) const

inline

Return const iterator to beginning of map.

Definition at line 573 of file hash_map.h.

573 {return const_iterator(tbl, tbl.begin());}

tpie::hash_map::const_iterator

iter_base< const tbl_t > const_iterator

Const iterator type.

Definition: hash_map.h:438

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

const_iterator tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::cend ( ) const

inline

Return const iterator to end of map.

Definition at line 588 of file hash_map.h.

588 {return const_iterator(tbl, tbl.end());}

tpie::hash_map::const_iterator

iter_base< const tbl_t > const_iterator

Const iterator type.

Definition: hash_map.h:438

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

void tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::clear ( )

inline

Clear hash map.

Definition at line 598 of file hash_map.h.

598 {tbl.clear();}

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

bool tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::contains ( const key_t & key ) const

inline

Search for element with key.

Returns true if an element with the given key exists in the hash map.

Parameters

key	Key of element to search for.

Definition at line 556 of file hash_map.h.

                                                   {
         return tbl.find(value_t(key, tbl.unused.second)) != tbl.end();
     }

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

iterator tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::end ( )

inline

Return iterator to end of map.

Definition at line 578 of file hash_map.h.

578 {return iterator(tbl, tbl.end());}

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

const_iterator tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::end ( ) const

inline

Return const iterator to end of map.

Definition at line 583 of file hash_map.h.

583 {return const_iterator(tbl, tbl.end());}

tpie::hash_map::const_iterator

iter_base< const tbl_t > const_iterator

Const iterator type.

Definition: hash_map.h:438

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

void tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::erase ( const key_t & key )

inline

Erase entry from hash map by key.

Parameters

key	Key of entry to remove.

Definition at line 499 of file hash_map.h.

                                          {
         tbl.erase(value_t(key, tbl.unused.second));
     }

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

void tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::erase ( const iterator & iter )

inline

Erase entry from hash map by iterator.

Parameters

iter	Entry to remove.

Definition at line 507 of file hash_map.h.

References tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::erase().

Referenced by tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::erase().

507 {erase(iter.key());}

tpie::hash_map::erase

void erase(const key_t &key)

Erase entry from hash map by key.

Definition: hash_map.h:499

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

iterator tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::find ( const key_t & key )

inline

Get iterator to element.

Parameters

key	Key of element to find.

Definition at line 539 of file hash_map.h.

                                             {
         return iterator(tbl, tbl.find(value_t(key, tbl.unused.second)));
     }

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

const_iterator tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::find ( const key_t & key ) const

inline

Get iterator to element.

Parameters

key	Key of element to find.

Definition at line 547 of file hash_map.h.

                                                         {
         return const_iterator(tbl, tbl.find(value_t(key, tbl.unused.second)));
     }

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

bool tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::insert	(	const key_t &	key,
		const data_t &	data
	)

inline

Insert data into the hash map.

Parameters

key	Key of data to insert.
data	Data to associate with given key.

Definition at line 514 of file hash_map.h.

                                                                {
         return tbl.insert(value_t(key, data)).second;
     }

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

static double tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::memory_coefficient ( )

inlinestatic

Return the memory coefficient of the structure.

Allocating a structure with n elements will use at most $\lfloor \mathrm{memory\_coefficient} \cdot n + \mathrm{memory\_overhead} \rfloor$ bytes. This does not include memory overhead incurred if the structure is allocated using new.

Returns: The memory coefficient of the structure.

Definition at line 465 of file hash_map.h.

                                        {
         return tbl_t::memory_coefficient();
     }

static memory_size_type tpie::linear_memory_base< hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t > >::memory_fits ( memory_size_type memory )

inlinestaticinherited

Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes.

Parameters

memory The number of bytes the structure is allowed to occupy

Returns: The number of elements that will fit in the structure

Definition at line 93 of file util.h.

                                                                         {
         return static_cast<memory_size_type>(
             floor((memory - child_t::memory_overhead()) / child_t::memory_coefficient()));
     }

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

static double tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::memory_overhead ( )

inlinestatic

Return the memory overhead of the structure.

See also: memory_coefficient()

Returns: The memory overhead.

Definition at line 473 of file hash_map.h.

                                     {
         return tbl_t::memory_overhead() - sizeof(tbl_t) + sizeof(hash_map);
     }

static memory_size_type tpie::linear_memory_base< hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t > >::memory_usage ( memory_size_type size )

inlinestaticinherited

Return the number of bytes required to create a data structure supporting a given number of elements.

Parameters

size	The number of elements to support

Returns: The amount of memory required in bytes

Definition at line 81 of file util.h.

                                                                 {
         return static_cast<memory_size_type>(
             floor(static_cast<double>(size) * child_t::memory_coefficient() + child_t::memory_overhead()));
     }

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

data_t& tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::operator[] ( const key_t & key )

inline

Look up data by key, creating an unused entry if it does not exist.

Parameters

key	Key to look up.

Definition at line 523 of file hash_map.h.

                                                   {
         return tbl.get(tbl.insert(value_t(key, tbl.unused.second)).first).second;
     }

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

const data_t& tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::operator[] ( const key_t & key ) const

inline

Look up data by key.

Parameters

key	Key to look up.

Definition at line 531 of file hash_map.h.

                                                               {
         return tbl.get(tbl.find(key))->second;
     }

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

void tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::resize ( size_t size )

inline

Resize hash map to given size and remove all entries.

Parameters

size	New size of hash map.

Definition at line 493 of file hash_map.h.

493 {tbl.resize(size);}

tpie::hash_map::size

size_t size() const

Return number of elements in map.

Definition: hash_map.h:593

template<typename key_t , typename data_t , typename hash_t = hash<key_t>, typename equal_t = std::equal_to<key_t>, typename index_t = size_t, template< typename, typename, typename, typename > class table_t = chaining_hash_table>

size_t tpie::hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t >::size ( ) const

inline

Return number of elements in map.

Definition at line 593 of file hash_map.h.

593 {return tbl.size;}

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

hash_map.h

TPIE

Classes

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation