Hash table class from the google-sparsehash package, optimized for speed. More...

#include <ash/impl/dense_hashtable.h>

Public Types
typedef Key	key_type
	The type used to identify elements.
typedef Value	value_type
	The type of the object the container holds.
typedef HashFx	hasher
	The functor type used to hash keys.
typedef EqualKey	key_equal
	The functor used to compare keys for equality.
typedef TblAlloc	allocator_type

typedef value_alloc_type::size_type	size_type
	The unsigned type used to represent the size of the container.
typedef value_alloc_type::difference_type	difference_type
	The signed integral type used to represent the distance between iterators.
typedef value_alloc_type::reference	reference
	The type that serves as a reference to value_type.
typedef value_alloc_type::const_reference	const_reference
	The type that serves as a pointer to value_type.
typedef value_alloc_type::pointer	pointer
	The type that serves as a pointer to value_type.
typedef value_alloc_type::const_pointer	const_pointer
	The type that serves as a const pointer to value_type.
typedef dense_hashtable_iterator < Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >	iterator
	The type used to iterate through the contents of the container.
typedef dense_hashtable_const_iterator < Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >	const_iterator
	The const type used to iterate through the contents of the container.
typedef iterator	local_iterator
	The type used to iterate through a set of elements that share a hash code.
typedef const_iterator	const_local_iterator
	The const type used to iterate through a set of elements that share a hash code.
Public Member Functions
iterator	begin ()
	Get an iterator to the beginning.
iterator	end ()
	Get an iterator to the end.
const_iterator	begin () const
	Get an iterator to the beginning.
const_iterator	end () const
	Get an iterator to the end.
local_iterator	begin (size_type i)

local_iterator	end (size_type i)

const_local_iterator	begin (size_type i) const

const_local_iterator	end (size_type i) const

hasher	hash_funct () const
	Get the hash functor used by the container.
key_equal	key_eq () const
	Get the key comparison functor used by the container.
void	set_deleted_key (const key_type &key)
void	clear_deleted_key ()
key_type	deleted_key () const
bool	test_deleted (size_type bucknum) const
bool	test_deleted (iterator const &itr) const
bool	test_deleted (const_iterator const &itr) const
bool	set_deleted (iterator &itr)
bool	clear_deleted (iterator &itr)
bool	set_deleted (const_iterator &it)
bool	clear_deleted (const_iterator &it)
bool	test_empty (size_type bucknum) const
bool	test_empty (const iterator &it) const
bool	test_empty (const const_iterator &it) const
void	set_empty_key (const_reference val)
key_type	empty_key () const
size_type	size () const
	Get the size of the container.
size_type	max_size () const
	Get the maximum size of the container.
bool	empty () const
	Check if the container is empty.
size_type	bucket_count () const
	Get the number of buckets the container has.
size_type	max_bucket_count () const

size_type	nonempty_bucket_count () const
size_type	bucket_size (size_type i) const

size_t	dynamic_memory () const
size_t	memory () const
void	resize (size_type n)
	Hashed Associative Container concept.
void	get_resizing_parameters (float shrink, float grow) const
void	set_resizing_parameters (float shrink, float grow)
	dense_hashtable (size_type n=0, hasher const &h=HashFx(), key_equal const &k=EqualKey(), KeyAccess const &ka=KeyAccess())
	dense_hashtable (dense_hashtable const &ht, size_type n=HT_DEFAULT_STARTING_BUCKETS)
dense_hashtable &	operator= (dense_hashtable const &ht)
void	swap (dense_hashtable &ht)
void	clear ()
	Erase all elements.
void	clear_no_resize ()
	Clear the container without resizing it.
iterator	find (key_type const &key)

const_iterator	find (key_type const &key) const

size_type	bucket (key_type const &key) const

size_type	count (key_type const &key) const

pair< iterator, iterator >	equal_range (const key_type &key)

pair< const_iterator, const_iterator >	equal_range (const key_type &key) const

pair< iterator, bool >	insert (const_reference obj)

template<class InputIterator >
void	insert (InputIterator f, InputIterator l)

template<class ForwardIterator >
void	insert (ForwardIterator f, ForwardIterator l, std::forward_iterator_tag)

template<class InputIterator >
void	insert (InputIterator f, InputIterator l, std::input_iterator_tag)

size_type	erase (key_type const &key)

void	erase (iterator itr)

void	erase (iterator f, iterator l)

void	erase (const_iterator itr)

void	erase (const_iterator f, const_iterator l)

bool	operator== (dense_hashtable const &ht) const
bool	write_metadata (FILE *fp)
bool	read_metadata (FILE *fp)
bool	write_nopointer_data (FILE *fp) const
bool	read_nopointer_data (FILE *fp)
Static Public Attributes
static const float	HT_OCCUPANCY_FLT = 0.5f
	How full we let the table get before we resize, by default.
static const float	HT_EMPTY_FLT = 0.4f * dense_hashtable<V,K,HF,KA,EqK,TA>::HT_OCCUPANCY_FLT
	How empty we let the table get before we resize lower, by default.
static const size_type	HT_MIN_BUCKETS = 4
	Minimum size we're willing to let hashtables be.
static const size_type	HT_DEFAULT_STARTING_BUCKETS = 32
	By default, if you don't specify a hashtable size at construction-time, we use this size.
Related Functions
(Note that these are not member functions.)
template<typename V , typename K , class HF , class KA , class EqK , class TA >
void	swap (dense_hashtable< V, K, HF, KA, EqK, TA > &x, dense_hashtable< V, K, HF, KA, EqK, TA > &y)

Detailed Description

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>
class ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >

Hash table class from the google-sparsehash package, optimized for speed.

Template Parameters:

Value	What is stored in the table (each bucket is a Value).
Key	Something in a 1-to-1 correspondence to a Value, that can be used to search for a Value in the table (find() takes a Key).
HashFx	Takes a Key and returns an integer, the more unique the better.
KeyAccess	Given a Value, gets/sets the unique Key associated with it. We guarantee only to set key == deleted_key.
EqualKey	Given two Keys, says whether they are the same (that is, if they are both associated with the same Value).
TblAlloc	Table allocator to use to allocate memory.

Member Typedef Documentation

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef TblAlloc ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::allocator_type

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef dense_hashtable_const_iterator<Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc> ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::const_iterator

The const type used to iterate through the contents of the container.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef const_iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::const_local_iterator

The const type used to iterate through a set of elements that share a hash code.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef value_alloc_type::const_pointer ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::const_pointer

The type that serves as a const pointer to value_type.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef value_alloc_type::const_reference ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::const_reference

The type that serves as a pointer to value_type.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef value_alloc_type::difference_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::difference_type

The signed integral type used to represent the distance between iterators.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef HashFx ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::hasher

The functor type used to hash keys.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef dense_hashtable_iterator<Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc> ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::iterator

The type used to iterate through the contents of the container.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef EqualKey ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::key_equal

The functor used to compare keys for equality.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef Key ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::key_type

The type used to identify elements.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::local_iterator

The type used to iterate through a set of elements that share a hash code.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef value_alloc_type::pointer ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::pointer

The type that serves as a pointer to value_type.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef value_alloc_type::reference ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::reference

The type that serves as a reference to value_type.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef value_alloc_type::size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::size_type

The unsigned type used to represent the size of the container.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

typedef Value ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::value_type

The type of the object the container holds.

Must be Assignable .

Member Function Documentation

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::begin ( ) [inline]

Get an iterator to the beginning.

Returns:: An iterator to the beginning of the container.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

const_iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::begin ( ) const [inline]

Get an iterator to the beginning.

Returns:: An iterator to the beginning of the container.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

local_iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::begin ( size_type i ) [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

const_local_iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::begin ( size_type i ) const [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::bucket ( key_type const & key ) const [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::bucket_count ( ) const [inline]

Get the number of buckets the container has.

Returns:: The number of currently-allocated buckets.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::bucket_size ( size_type i ) const [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::clear ( ) [inline]

Erase all elements.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::clear_no_resize ( ) [inline]

Clear the container without resizing it.

Mimicks the stl_hashtable's behaviour when clear()-ing in that it does not modify the bucket count.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::count ( key_type const & key ) const [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

bool ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::empty ( ) const [inline]

Check if the container is empty.

Returns:: True if the container is empty.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::end ( ) [inline]

Get an iterator to the end.

Returns:: An iterator to the end of the container.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

const_iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::end ( ) const [inline]

Get an iterator to the end.

Returns:: An iterator to the end of the container.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

local_iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::end ( size_type i ) [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

const_local_iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::end ( size_type i ) const [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

pair<iterator, iterator> ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::equal_range ( const key_type & key ) [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

pair<const_iterator, const_iterator> ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::equal_range ( const key_type & key ) const [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::erase ( key_type const & key ) [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::erase ( iterator itr ) [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::erase	(	iterator	f,
		iterator	l
	)		`[inline]`

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::erase ( const_iterator itr ) [inline]

We allow you to erase a const_iterator just like we allow you to erase an iterator. This is in parallel to 'delete': you can delete a const pointer just like a non-const pointer. The logic is that you can't use the object after it's erased anyway, so it doesn't matter if it's const or not.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::erase	(	const_iterator	f,
		const_iterator	l
	)		`[inline]`

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::find ( key_type const & key ) [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

const_iterator ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::find ( key_type const & key ) const [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

hasher ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::hash_funct ( ) const [inline]

Get the hash functor used by the container.

Returns:: A copy of the container's hasher object.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

pair<iterator, bool> ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::insert ( const_reference obj ) [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

template<class InputIterator >

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::insert	(	InputIterator	f,
		InputIterator	l
	)		`[inline]`

When inserting a lot at a time, we specialize on the type of iterator.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

template<class ForwardIterator >

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::insert	(	ForwardIterator	f,
		ForwardIterator	l,
		std::forward_iterator_tag
	)		`[inline]`

Iterator supports operator-, resize before inserting.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

template<class InputIterator >

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::insert	(	InputIterator	f,
		InputIterator	l,
		std::input_iterator_tag
	)		`[inline]`

Arbitrary iterator, can't tell how much to resize.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

key_equal ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::key_eq ( ) const [inline]

Get the key comparison functor used by the container.

Returns:: A copy of the container's key_equal object.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::max_bucket_count ( ) const [inline]

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::max_size ( ) const [inline]

Get the maximum size of the container.

Returns:: The maximum number of elements the container can hold.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::resize ( size_type n ) [inline]

Hashed Associative Container concept.

As a special feature, calling with n%==0 will cause us to shrink if we can, saving space.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

void ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::set_empty_key ( const_reference val ) [inline]

Todo:: csilvers: change all callers of this to pass in a key instead, and take a const key_type instead of const value_type.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::size ( ) const [inline]

Get the size of the container.

Returns:: The number of elements in the container.

Friends And Related Function Documentation

template<typename V , typename K , class HF , class KA , class EqK , class TA >

void swap	(	dense_hashtable< V, K, HF, KA, EqK, TA > &	x,
		dense_hashtable< V, K, HF, KA, EqK, TA > &	y
	)		`[related]`

Member Data Documentation

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

const size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::HT_DEFAULT_STARTING_BUCKETS = 32 [static]

By default, if you don't specify a hashtable size at construction-time, we use this size.

Must be a power of two, and at least HT_MIN_BUCKETS.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

const float ash::dense_hashtable< V, K, HF, KA, EqK, TA >::HT_EMPTY_FLT = 0.4f * dense_hashtable<V,K,HF,KA,EqK,TA>::HT_OCCUPANCY_FLT [static]

How empty we let the table get before we resize lower, by default.

(0.0 means never resize lower.) It should be less than OCCUPANCY_FLT / 2 or we thrash resizing.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

const size_type ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::HT_MIN_BUCKETS = 4 [static]

Minimum size we're willing to let hashtables be.

Must be a power of two, and at least 4. Note, however, that for a given hashtable, the initial size is a function of the first constructor arg, and may be >HT_MIN_BUCKETS.

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>

const float ash::dense_hashtable< V, K, HF, KA, EqK, TA >::HT_OCCUPANCY_FLT = 0.5f [static]

How full we let the table get before we resize, by default.

Knuth says .8 is good -- higher causes us to probe too much, though it saves memory.

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

ash/impl/dense_hashtable.h
ash/impl/dense_hashtable.tcc

Public Types

Public Member Functions

Static Public Attributes

Related Functions

Detailed Description

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc> class ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >

Member Typedef Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<typename Value, typename Key, class HashFx, class KeyAccess, class EqualKey, class TblAlloc>
class ash::dense_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >