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 () const
	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 stream_size_type	memory_usage (stream_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 440 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 501 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 547 of file hash_map.h.

549 :

550 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:656

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 626 of file hash_map.h.

626 {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 631 of file hash_map.h.

631 {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:501

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 636 of file hash_map.h.

636 {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:501

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 651 of file hash_map.h.

651 {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:501

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 ( ) const

inline

Clear hash map.

Definition at line 661 of file hash_map.h.

661 {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 619 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 641 of file hash_map.h.

641 {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 646 of file hash_map.h.

646 {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:501

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 562 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 570 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().

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

tpie::hash_map::erase

void erase(const key_t &key)

Erase entry from hash map by key.

Definition: hash_map.h:562

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 602 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 610 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 577 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 528 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 536 of file hash_map.h.

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

static stream_size_type tpie::linear_memory_base< hash_map< key_t, data_t, hash_t, equal_t, index_t, table_t > >::memory_usage ( stream_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<stream_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 586 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 594 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 556 of file hash_map.h.

556 {tbl.resize(size);}

tpie::hash_map::size

size_t size() const

Return number of elements in map.

Definition: hash_map.h:656

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 656 of file hash_map.h.

656 {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