ash::sparse_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc > Class Template Reference

Hash table class from the google-sparsehash package, optimized for frugal memory use. More...

#include <ash/impl/sparse_hashtable.h>

List of all members.

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 sparse_hashtable_iterator < Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >	iterator
	The type used to iterate through the contents of the container.
typedef sparse_hashtable_const_iterator < Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >	const_iterator
	The const type used to iterate through the contents of the container.
typedef sparse_hashtable_destructive_iterator < Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >	destructive_iterator
	A special iterator that frees memory as it iterates (used to resize).
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
destructive_iterator	destructive_begin ()
	Get a destructive iterator pointing to the beginning.
destructive_iterator	destructive_end ()
	Get a destructive iterator pointing to the end.
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.
int	num_table_copies () const
	Accessor function for statistics gathering.
void	set_deleted_key (key_type const &key)
void	clear_deleted_key ()
key_type	deleted_key () const
bool	test_deleted (size_type bucknum) const
bool	test_deleted (const iterator &it) const
bool	test_deleted (const const_iterator &it) const
bool	test_deleted (const destructive_iterator &it) const
bool	set_deleted (iterator &it)
bool	clear_deleted (iterator &it)
bool	set_deleted (const_iterator &it)
bool	clear_deleted (const_iterator &it)
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	bucket_size (size_type i) const
size_type	dynamic_memory () const
size_type	memory () const
void	resize (size_type req_elements)
void	get_resizing_parameters (float *shrink, float *grow) const
void	set_resizing_parameters (float shrink, float grow)
	sparse_hashtable (size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal(), KeyAccess const &ka=KeyAccess())
	sparse_hashtable (sparse_hashtable const &ht, size_type n=HT_DEFAULT_STARTING_BUCKETS)
	sparse_hashtable (MoveDontCopyT mover, sparse_hashtable &ht, size_type n=HT_DEFAULT_STARTING_BUCKETS)
sparse_hashtable &	operator= (sparse_hashtable const &ht)
void	swap (sparse_hashtable &ht)
void	clear ()
iterator	find (const key_type &key)
const_iterator	find (const key_type &key) const
size_type	bucket (const key_type &key) const
size_type	count (const key_type &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 (const key_type &key)
void	erase (iterator pos)
void	erase (iterator f, iterator l)
void	erase (const_iterator pos)
void	erase (const_iterator f, const_iterator l)
bool	operator== (sparse_hashtable const &ht) const
bool	write_metadata (FILE *fp)
bool	read_metadata (FILE *fp)
bool	write_nopointer_data (FILE *fp)
bool	read_nopointer_data (FILE *fp)
Static Public Attributes
static const float	HT_OCCUPANCY_FLT = 0.8f
	How full we let the table get before we resize, by default.
static const float	HT_EMPTY_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 (sparse_hashtable< V, K, HF, KA, EqK, TA > &x, sparse_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::sparse_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >

Hash table class from the google-sparsehash package, optimized for frugal memory use.

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.
ExtractKey	Given a Value, returns the unique Key associated with it.
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::sparse_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::allocator_type

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

typedef sparse_hashtable_const_iterator<Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc> ash::sparse_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::sparse_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::sparse_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::sparse_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 sparse_hashtable_destructive_iterator<Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc> ash::sparse_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::destructive_iterator

A special iterator that frees memory as it iterates (used to resize).

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

typedef value_alloc_type::difference_type ash::sparse_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::sparse_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 sparse_hashtable_iterator<Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc> ash::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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>

destructive_iterator ash::sparse_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::destructive_begin

(

)

[inline]

Get a destructive iterator pointing to the beginning.

Returns:

a destructive_iterator pointing to the beginning of the container.

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

destructive_iterator ash::sparse_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::destructive_end

(

)

[inline]

Get a destructive iterator pointing to the end.

Returns:

a destructive_iterator pointing to the end of the container.

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

bool ash::sparse_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::sparse_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::sparse_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::sparse_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::sparse_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>

hasher ash::sparse_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>

key_equal ash::sparse_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::sparse_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::sparse_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>

int ash::sparse_hashtable< Value, Key, HashFx, KeyAccess, EqualKey, TblAlloc >::num_table_copies

(

)

const [inline]

Accessor function for statistics gathering.

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

size_type ash::sparse_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	(	sparse_hashtable< V, K, HF, KA, EqK, TA > &	x,
		sparse_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::sparse_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::sparse_hashtable< V, K, HF, KA, EqK, TA >::HT_EMPTY_FLT [static]

Initial value:

        0.4f * sparse_hashtable<V,K,HF,KA,EqK,TA>::HT_OCCUPANCY_FLT

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::sparse_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::sparse_hashtable< V, K, HF, KA, EqK, TA >::HT_OCCUPANCY_FLT = 0.8f [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/sparse_hashtable.h
• ash/impl/sparse_hashtable.tcc