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

#include <tpie/hash_map.h>

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

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

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

Public Member Functions
	hash_set (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 set. More...

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

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

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

bool	insert (const key_t &key)
	Insert key into set. More...

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

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

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

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

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

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

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

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

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

size_t	size () const
	Return number of keys in set. More...

void	clear () const
	Clear hash set. 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 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 = linear_probing_hash_table>
class tpie::hash_set< key_t, hash_t, equal_t, index_t, table_t >

Hash set implementation backed by a template parameterized hash table.

Template Parameters

key_t	Type of keys to store.
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 615 of file hash_map.h.

Member Typedef Documentation

template<typename key_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 = linear_probing_hash_table>

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

Const iterator type.

Definition at line 646 of file hash_map.h.

Constructor & Destructor Documentation

template<typename key_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 = linear_probing_hash_table>

tpie::hash_set< key_t, hash_t, equal_t, index_t, table_t >::hash_set	(	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 set.

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

692 :

693 tbl(size, u, hash, equal) {}

tpie::hash_set::size

size_t size() const

Return number of keys in set.

Definition: hash_map.h:777

Member Function Documentation

template<typename key_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 = linear_probing_hash_table>

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

inline

Return iterator to beginning of set.

Definition at line 747 of file hash_map.h.

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

template<typename key_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 = linear_probing_hash_table>

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

inline

Return const iterator to beginning of set.

Definition at line 752 of file hash_map.h.

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

tpie::hash_set::const_iterator

iter_base< const tbl_t > const_iterator

Const iterator type.

Definition: hash_map.h:646

template<typename key_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 = linear_probing_hash_table>

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

inline

Return const iterator to beginning of set.

Definition at line 757 of file hash_map.h.

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

tpie::hash_set::const_iterator

iter_base< const tbl_t > const_iterator

Const iterator type.

Definition: hash_map.h:646

template<typename key_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 = linear_probing_hash_table>

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

inline

Return const iterator to end of set.

Definition at line 772 of file hash_map.h.

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

tpie::hash_set::const_iterator

iter_base< const tbl_t > const_iterator

Const iterator type.

Definition: hash_map.h:646

template<typename key_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 = linear_probing_hash_table>

void tpie::hash_set< key_t, hash_t, equal_t, index_t, table_t >::clear ( ) const

inline

Clear hash set.

Definition at line 782 of file hash_map.h.

782 {tbl.clear();}

template<typename key_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 = linear_probing_hash_table>

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

inline

Search for key.

Returns true if the given key exists in the hash set.

Parameters

key	Key to search for.

Definition at line 742 of file hash_map.h.

742 {return tbl.find(key) != tbl.end();}

template<typename key_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 = linear_probing_hash_table>

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

inline

Return iterator to end of set.

Definition at line 762 of file hash_map.h.

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

template<typename key_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 = linear_probing_hash_table>

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

inline

Return const iterator to end of set.

Definition at line 767 of file hash_map.h.

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

tpie::hash_set::const_iterator

iter_base< const tbl_t > const_iterator

Const iterator type.

Definition: hash_map.h:646

template<typename key_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 = linear_probing_hash_table>

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

inline

Erase entry from hash set by key.

Parameters

key	Key of entry to remove.

Definition at line 705 of file hash_map.h.

705 {tbl.erase(key);}

template<typename key_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 = linear_probing_hash_table>

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

inline

Erase entry from hash set by iterator.

Parameters

key	Key of entry to remove.

Definition at line 711 of file hash_map.h.

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

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

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

tpie::hash_set::erase

void erase(const key_t &key)

Erase entry from hash set by key.

Definition: hash_map.h:705

template<typename key_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 = linear_probing_hash_table>

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

inline

Get iterator to element.

Parameters

key	Key to find.

Definition at line 725 of file hash_map.h.

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

template<typename key_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 = linear_probing_hash_table>

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

inline

Get const iterator to element.

Parameters

key	Key to find.

Definition at line 733 of file hash_map.h.

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

template<typename key_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 = linear_probing_hash_table>

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

inline

Insert key into set.

Parameters

key	Key to insert.

Definition at line 717 of file hash_map.h.

                                           {
         return tbl.insert(key).second;
     }

template<typename key_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 = linear_probing_hash_table>

static double tpie::hash_set< key_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 671 of file hash_map.h.

                                        {
         return tbl_t::memory_coefficient();
     }

static memory_size_type tpie::linear_memory_base< hash_set< key_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 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 = linear_probing_hash_table>

static double tpie::hash_set< key_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 679 of file hash_map.h.

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

static memory_size_type tpie::linear_memory_base< hash_set< key_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 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 = linear_probing_hash_table>

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

inline

Resize hash set to given size and remove all entries.

Parameters

size	New size of hash set.

Definition at line 699 of file hash_map.h.

699 {tbl.resize(size);}

tpie::hash_set::size

size_t size() const

Return number of keys in set.

Definition: hash_map.h:777

template<typename key_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 = linear_probing_hash_table>

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

inline

Return number of keys in set.

Definition at line 777 of file hash_map.h.

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

template<typename key_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 = linear_probing_hash_table> class tpie::hash_set< key_t, hash_t, equal_t, index_t, table_t >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<typename key_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 = linear_probing_hash_table>
class tpie::hash_set< key_t, hash_t, equal_t, index_t, table_t >