A base class which adds a graph layer to a hashtable. More...

#include <ash/impl/hashgraph.h>

Inheritance diagram for ash::hashgraph:

Classes
struct	const_iterator
	The const type used to iterate through the contents of the container. More...
struct	const_navigator
	The hashgraph's const_navigator. More...
struct	iterator
	The type used to iterate through the contents of the container. More...
struct	navigator
	The hashgraph's navigator. More...
Public Types
enum	{ LINKS_PER_NODE = Node::NUM_LINKS }
typedef Node	node_type

typedef Key	key_type
	The type used to identify elements.
typedef Node::value_type	value_type
	The type of object stored in the container.
typedef HashFx	hasher
	The functor type used to hash keys.
typedef EqualKey	key_equal
	The functor used to compare keys for equality.
typedef KeyAccess	key_access
	Functor that gets/sets the key_type of a value_type.
typedef Alloc::template rebind < value_type >::other	allocator_type

typedef allocator_type::pointer	pointer
	The type that serves as a pointer to value_type.
typedef allocator_type::const_pointer	const_pointer
	The type that serves as a const pointer to value_type.
typedef allocator_type::reference	reference
	The type that serves as a reference to value_type.
typedef allocator_type::const_reference	const_reference
	The type that serves as a pointer to value_type.
typedef allocator_type::size_type	size_type
	The unsigned type used to represent the size of the container.
typedef allocator_type::difference_type	difference_type
	The signed integral type used to represent the distance between iterators.
typedef iterator	local_iterator
	TODO.
typedef const_iterator	const_local_iterator
	TODO.
typedef pair< iterator, iterator >	iterator_pair
	A pair of iterators (convenience).
typedef pair< const_iterator, const_iterator >	const_iterator_pair
	A pair of const_iterators (convenience).
Public Member Functions
void	swap (hashgraph &hg)
	Swap method.
size_type	bucket (key_type const &key) const

bool	operator== (hashgraph const &hg) const
Constructors/Destructors
We use the default copy constructor. We use the default destructor.
	hashgraph (size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal(), key_access const &ka=key_access())
	Default constructor.
template<class InputIterator >
	hashgraph (InputIterator const &f, InputIterator const &l, size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal(), key_access const &ka=key_access())
	Iterative constructor.
Iterator Functions
iterator	begin ()
	Get an iterator to the beginning.
const_iterator	begin () const
	Get an iterator to the beginning.
local_iterator	begin (size_type i)

const_local_iterator	begin (size_type i) const

iterator	end ()
	Get an iterator to the end.
const_iterator	end () const
	Get an iterator to the end.
local_iterator	end (size_type i)

const_local_iterator	end (size_type i) const

Size Functions
size_type	size () const
	Get the size of the container.
size_type	max_size () const
	Get the maximum size of the container.
size_t	dynamic_memory () const
	Get the container's dynamic memory load.
size_t	memory () const
	Get the container's total memory load.
bool	empty () const
	Check if the container is empty.
size_type	bucket_count () const
	Get the number of buckets the container has.
void	resize (size_type n)
	Resize the container to hold at least n elements.
void	rehash (size_type n)

Accessor Methods
hasher	hash_funct () const
	Get the hash functor used by the container.
hasher	hash_function () const
	Get the hash functor used by the container.
key_equal	key_eq () const
	Get the key comparison functor used by the container.
Lookup
iterator	find (key_type const &k)
	Find an element.
const_iterator	find (key_type const &k) const
	Find an element.
size_type	count (key_type const &k) const
	Count the number of elements with a given key.
iterator_pair	equal_range (key_type const &k)
	Find all elements matching a given key.
const_iterator_pair	equal_range (key_type const &k) const
	Find all elements matching a given key.
Hash Container Functions
float	load_factor () const

float	max_load_factor () const

float	max_load_factor (size_type new_grow)

float	min_load_factor () const
	Get the min load factor.
float	min_load_factor (size_type new_shrink)
	Set the min load factor.
Protected Types
typedef f_access_node< Node, KeyAccess >	node_key_access
	Functor to get/set the key of a node (wrapper for key_access).
typedef table_node_allocator < allocator_type >	hashtable_allocator
	The hashtable's allocator.
typedef Ht< node_type, key_type, hasher, node_key_access, key_equal, hashtable_allocator >	hashtable_type
	The hashtable used as a backend.
typedef hashtable_type::iterator	_Ht_iterator
	The hashtable's iterator - we'll wrap it with our own.
typedef hashtable_type::const_iterator	_Ht_const_iterator
	The hashtable's const_iterator - we'll wrap it with our own.
typedef pair< _Ht_iterator, _Ht_iterator >	_Ht_iterator_pair
	A pair of the hashtable's iterators (convenience).
typedef pair < _Ht_const_iterator, _Ht_const_iterator >	_Ht_const_iterator_pair
	A pair of the hashtable's const_iterators (convenience).
typedef graph_iterator < hashgraph, _Ht_iterator, trivial >	iterator_base
typedef graph_iterator < hashgraph, _Ht_const_iterator, add_const >	const_iterator_base
typedef graph_navigator < hashgraph, iterator_base, trivial >	navigator_base
typedef graph_navigator < hashgraph, const_iterator_base, add_const >	const_navigator_base
Protected Attributes
key_access	access_key
hashtable_type	_M_Ht
Related Functions
(Note that these are not member functions.)
template<class N , typename K , class HF , class KA , class EK , class A , _ASH_HT_IMPL HT>
void	swap (hashgraph< N, K, HF, KA, EK, A, HT > &x, hashgraph< N, K, HF, KA, EK, A, HT > &y)
	Global swap.
Insert/Delete
void	erase (iterator pos)
	Erase an element.
size_type	erase (key_type const &k)
	Erase an element.
void	erase (iterator first, iterator const &last)
	Erase a range of elements.
void	clear ()
	Erase all elements.
pair< iterator, bool >	insert (const_reference v)
	Insert an element into the container.

Detailed Description

A base class which adds a graph layer to a hashtable.

Concepts:: ash::hash_graph

Template Parameters:

Node	The node type. Also defined as hashgraph::node_type. The graph_node<> class or any derived class is valid.
Key	The key type associated with values. Also defined as hashgraph::key_type.
HashFx	The hash functor.
KeyAccess	A functor to get/set the Key of a Node::value_type.
EqualKey	Functor to test keys for equality.
Alloc	The allocator type. Also defined as hashgraph::allocator_type.
Ht	The hashtable type to use as a backend.

The hashgraph class aims to provide all necessary components for a entries in a hashtable to be linked together in an arbitrary manner. This allows any linked data structure to take advantage of the fast lookups a hashtable provides. Relative memory overhead is determined by the hashtable implementation.

Note:: Derived classes are responsible for linking a node after insertion, the hashgraph only maintains the linked structure on top of the hashtable.

Member Typedef Documentation

typedef hashtable_type::const_iterator ash::hashgraph::_Ht_const_iterator [protected]

The hashtable's const_iterator - we'll wrap it with our own.

typedef pair<_Ht_const_iterator, _Ht_const_iterator> ash::hashgraph::_Ht_const_iterator_pair [protected]

A pair of the hashtable's const_iterators (convenience).

typedef hashtable_type::iterator ash::hashgraph::_Ht_iterator [protected]

The hashtable's iterator - we'll wrap it with our own.

typedef pair<_Ht_iterator, _Ht_iterator> ash::hashgraph::_Ht_iterator_pair [protected]

A pair of the hashtable's iterators (convenience).

typedef Alloc::template rebind<value_type>::other ash::hashgraph::allocator_type

Concept: tr1::container

Reimplemented in ash::hashgrid, and ash::hashlist.

typedef pair<const_iterator, const_iterator> ash::hashgraph::const_iterator_pair

A pair of const_iterators (convenience).

Reimplemented in ash::hashgrid.

typedef allocator_type::const_pointer ash::hashgraph::const_pointer

The type that serves as a const pointer to value_type.

Concept: stl::container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef allocator_type::const_reference ash::hashgraph::const_reference

The type that serves as a pointer to value_type.

Concept: stl::container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef allocator_type::difference_type ash::hashgraph::difference_type

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

Concept: stl::container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef HashFx ash::hashgraph::hasher

The functor type used to hash keys.

Concept: stl::hashed_associative_container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef table_node_allocator<allocator_type> ash::hashgraph::hashtable_allocator [protected]

The hashtable's allocator.

typedef Ht< node_type, key_type, hasher, node_key_access, key_equal, hashtable_allocator > ash::hashgraph::hashtable_type [protected]

The hashtable used as a backend.

Reimplemented in ash::hashgrid, ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef pair<iterator, iterator> ash::hashgraph::iterator_pair

A pair of iterators (convenience).

Reimplemented in ash::hashgrid.

typedef KeyAccess ash::hashgraph::key_access

Functor that gets/sets the key_type of a value_type.

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef EqualKey ash::hashgraph::key_equal

The functor used to compare keys for equality.

Concept: stl::hashed_associative_container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef Key ash::hashgraph::key_type

The type used to identify elements.

Concept: stl::associative_container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef f_access_node<Node, KeyAccess> ash::hashgraph::node_key_access [protected]

Functor to get/set the key of a node (wrapper for key_access).

typedef Node ash::hashgraph::node_type

Concept: ash::hash_graph

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >, ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef allocator_type::pointer ash::hashgraph::pointer

The type that serves as a pointer to value_type.

Concept: stl::container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef allocator_type::reference ash::hashgraph::reference

The type that serves as a reference to value_type.

Concept: stl::container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef allocator_type::size_type ash::hashgraph::size_type

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

Concept: stl::container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

typedef Node::value_type ash::hashgraph::value_type

The type of object stored in the container.

Concept: stl::pair_associative_container

Reimplemented in ash::hashgrid, ash::hashlist, ash::dense_hashgrid< Coord, Data, Alloc >, ash::sparse_hashgrid< Coord, Data, Alloc >, ash::dense_hashlist< Key, Data, HashFx, EqualKey, Alloc >, and ash::sparse_hashlist< Key, Data, HashFx, EqualKey, Alloc >.

Constructor & Destructor Documentation

ash::hashgraph::hashgraph	(	size_type	n = `0`,
		hasher const &	h = `hasher()`,
		key_equal const &	k = `key_equal()`,
		key_access const &	ka = `key_access()`
	)		`[inline, explicit]`

Default constructor.

Parameters:

n	The number of elements the hashgraph is expected to hold.
h	The hasher object to copy, if any.
k	The key_equal object to copy, if any.
ka	The key_access object to copy, if any.

template<class InputIterator >

ash::hashgraph::hashgraph	(	InputIterator const &	f,
		InputIterator const &	l,
		size_type	n = `0`,
		hasher const &	h = `hasher()`,
		key_equal const &	k = `key_equal()`,
		key_access const &	ka = `key_access()`
	)		`[inline]`

Iterative constructor.

Parameters:

f	The beginning of the range of elements to insert.
l	The end of the range of elements to insert.
n	The number of elements the hashgraph is expected to hold.
h	The hasher object to copy, if any.
k	The key_equal object to copy, if any.
ka	The key_access object to copy, if any.

Member Function Documentation

iterator ash::hashgraph::begin ( ) [inline]

Get an iterator to the beginning.

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

Concept: stl::container

Reimplemented in ash::hashlist.

const_iterator ash::hashgraph::begin ( ) const [inline]

Get an iterator to the beginning.

Returns:: A const_iterator to the beginning of the container.

Concept: stl::container

Reimplemented in ash::hashlist.

local_iterator ash::hashgraph::begin ( size_type i ) [inline]

Concept: tr1::unordered_associative_container

const_local_iterator ash::hashgraph::begin ( size_type i ) const [inline]

Concept: tr1::unordered_associative_container

size_type ash::hashgraph::bucket ( key_type const & key ) const [inline]

Concept: tr1::unordered_associative_container

size_type ash::hashgraph::bucket_count ( ) const [inline]

Get the number of buckets the container has.

Returns:: The number of currently-allocated buckets.

Concept: stl::hashed_associative_container

void ash::hashgraph::clear ( ) [inline]

Erase all elements.

Concept: stl::associative_container

size_type ash::hashgraph::count ( key_type const & k ) const [inline]

Count the number of elements with a given key.

Parameters:

key	The key to search for.

Returns:: The number of elements matching key. Because this is a Unique Associative Container , the return value will be 0 or 1.

Concept: stl::unique_associative_container

size_t ash::hashgraph::dynamic_memory ( ) const [inline]

Get the container's dynamic memory load.

Returns:: The amount of dynamic memory used by the container in bytes.

bool ash::hashgraph::empty ( ) const [inline]

Check if the container is empty.

Returns:: True if the container is empty.

Concept: stl::container

iterator ash::hashgraph::end ( ) [inline]

Get an iterator to the end.

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

Concept: stl::container

Reimplemented in ash::hashlist.

const_iterator ash::hashgraph::end ( ) const [inline]

Get an iterator to the end.

Returns:: A const_iterator to the end of the container.

Concept: stl::container

Reimplemented in ash::hashlist.

local_iterator ash::hashgraph::end ( size_type i ) [inline]

Concept: tr1::unordered_associative_container

const_local_iterator ash::hashgraph::end ( size_type i ) const [inline]

Concept: tr1::unordered_associative_container

iterator_pair ash::hashgraph::equal_range ( key_type const & k ) [inline]

Find all elements matching a given key.

Parameters:

key	The key to search for.

Returns:: A pair of iterators for the range of elements [first,second). Because this is a Unique Associative Container , the first iterator points to the element, or to the end() if not found. The second iterator points to 1 past the first, or to the end().

Concept: stl::unique_associative_container

Reimplemented in ash::hashlist.

const_iterator_pair ash::hashgraph::equal_range ( key_type const & k ) const [inline]

Find all elements matching a given key.

Parameters:

key	The key to search for.

Returns:: A pair of const_iterators for the range of elements [first,second). Because this is a Unique Associative Container , the first const_iterator points to the element, or to the end() if not found. The second const_iterator points to 1 past the first, or to the end().

Concept: stl::unique_associative_container

Reimplemented in ash::hashlist.

void ash::hashgraph::erase ( iterator pos ) [inline]

Erase an element.

Parameters:

itr	An iterator pointing to the element to erase.

Concept: stl::associative_container

Reimplemented in ash::hashlist.

size_type ash::hashgraph::erase ( key_type const & k ) [inline]

Erase an element.

Parameters:

key	The key of the element to erase.

Returns:: The number of erased elements.

Concept: stl::associative_container

void ash::hashgraph::erase	(	iterator	first,
		iterator const &	last
	)		`[inline]`

Erase a range of elements.

Parameters:

f	The beginning of the range to erase.
l	The end of the range to erase.

Concept: stl::associative_container

Reimplemented in ash::hashlist.

iterator ash::hashgraph::find ( key_type const & k ) [inline]

Find an element.

Parameters:

key	The key of the element to search for.

Returns:: An iterator to the element, or to the end() if not found.

Concept: stl::associative_container

Reimplemented in ash::hashlist.

const_iterator ash::hashgraph::find ( key_type const & k ) const [inline]

Find an element.

Parameters:

key	The key of the element to search for.

Returns:: A const_iterator to the element, or to the end() if not found.

Concept: stl::associative_container

Reimplemented in ash::hashlist.

hasher ash::hashgraph::hash_funct ( ) const [inline]

Get the hash functor used by the container.

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

Concept: stl::hashed_associative_container

hasher ash::hashgraph::hash_function ( ) const [inline]

Get the hash functor used by the container.

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

Concept: tr1::unordered_associative_container

pair<iterator, bool> ash::hashgraph::insert ( const_reference v ) [inline, protected]

Insert an element into the container.

Parameters:

obj	The element to insert.

Returns:: An iterator and a bool. The iterator points to the inserted element, or to another with the same key if one is already in the container. The bool is true if the element was inserted, and false in the case of a duplicate key.

Concept: stl::unique_associative_container