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

#include <tpie/hash_map.h>

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...

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 678 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 709 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 753 of file hash_map.h.

755 :

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

tpie::hash_set::size

size_t size() const

Return number of keys in set.

Definition: hash_map.h:840

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

810 {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 815 of file hash_map.h.

815 {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:709

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

820 {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:709

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

835 {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:709

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

845 {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 805 of file hash_map.h.

805 {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 825 of file hash_map.h.

825 {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 830 of file hash_map.h.

830 {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:709

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

768 {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 774 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().

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

tpie::hash_set::erase

void erase(const key_t &key)

Erase entry from hash set by key.

Definition: hash_map.h:768

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 788 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 796 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 780 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 734 of file hash_map.h.

                                        {
         return tbl_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 742 of file hash_map.h.

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

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

762 {tbl.resize(size);}

tpie::hash_set::size

size_t size() const

Return number of keys in set.

Definition: hash_map.h:840

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

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