ash::sparse_hashgrid< Coord, Data, Alloc > Class Template Reference

A hashgrid with sparse_hashtable as a backend. More...

#include <ash/sparse_hashgrid.h>

Inheritance diagram for ash::sparse_hashgrid< Coord, Data, Alloc >:

List of all members.

Public Types
typedef Coord::morton_type	key_type
	The type of key associated with elements.
typedef Data	data_type
typedef pair< const key_type, data_type >	value_type
	The type of object stored by the container.
typedef value_type *	pointer
	Pointer to value_type.
typedef value_type const *	const_pointer
	Const pointer to value_type.
typedef value_type &	reference
	Reference to value_type.
typedef value_type const &	const_reference
	Const reference to value_type.
typedef _Base::size_type	size_type
	The unsigned type used to represent the size of the container.
typedef _Base::difference_type	difference_type
	The signed type used to represent the distance between iterators.
typedef _Base::morton_type	morton_type
	Interleaved coordinate type.
typedef _Base::pcoord_type	pcoord_type
	Coordinate type.
typedef _Base::point_type	point_type
	Floating-point coordinate type.
typedef _Base::hasher	hasher
	The hash functor used by the container.
typedef _Base::iterator	iterator
	The container's iterator.
typedef _Base::const_iterator	const_iterator
	The container's const_iterator.
typedef _Base::const_navigator	const_navigator
typedef _Base::range_iterator	range_iterator
typedef _Base::const_range_iterator	const_range_iterator
typedef _Base::path_iterator	path_iterator
typedef _Base::const_path_iterator	const_path_iterator
typedef _Base::key_equal	key_equal
	The key comparison functor used by the container.
typedef _Base::key_access	key_access
	Functor to access a key_type from a value_type.
typedef _Base::allocator_type	allocator_type
	The allocator used by the container.
typedef _Base::local_iterator	local_iterator
	The container's local_iterator.
typedef _Base::const_local_iterator	const_local_iterator
	The container's const_local_iterator.
typedef _Base::iterator_pair	iterator_pair
	A pair of iterators (convenience).
typedef _Base::const_iterator_pair	const_iterator_pair
	A pair of const_iterators (convenience).
enum	{ LINKS_PER_NODE = Node::NUM_LINKS }
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.
	sparse_hashgrid (size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Default constructor.
template<class InputIterator >
	sparse_hashgrid (InputIterator const &f, InputIterator const &l, size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Iterative constructor.
Lookup Methods
data_type &	operator[] (key_type const &key)
	Element access.
Insert/Delete
pair< iterator, bool >	insert (const_reference v)
	Insert an element into the container.
template<class InputIterator >
void	insert (InputIterator f, InputIterator const &l)
	Insert a range of elements [f,l) into the container.
Navigator Methods
navigator	navigate (key_type const &key)
const_navigator	navigate (key_type const &key) const
Range-Iterator Methods
Use the normal end() method.
range_iterator	range_begin (key_type const &key, size_type range)
const_range_iterator	range_begin (key_type const &key, size_type range) const
Path-Iterator Methods
Use the normal end() method.
path_iterator	path_begin (point_type const &p1, point_type const &p2)
const_path_iterator	path_begin (point_type const &p1, point_type const &p2) const
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.
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.
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.
Static Public Attributes
static const DIM	D = dim_cast<morton_type::D>::D
Protected Types
typedef _Type	sparse_hashgrid_type
typedef _Base::hashgrid_type	hashgrid_type
typedef _Base::hashgraph_type	hashgraph_type
typedef _Base::hashtable_type	hashtable_type
	The hashtable used as a backend.
typedef _Base::node_type	node_type
typedef _Base::navigator	_Base_nav
typedef _Base::const_navigator	_Base_const_nav
typedef _Base::iterator_base	iterator_base
typedef _Base::const_iterator_base	const_iterator_base
typedef grid_navigator < hashgrid, iterator_base, trivial, D >	navigator_base
typedef grid_navigator < hashgrid, const_iterator_base, add_const, D >	const_navigator_base
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 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).
Protected Attributes
key_access	access_key
hashtable_type	_M_Ht
Related Functions
(Note that these are not member functions.)
template<typename V , class M , class KA , class A , _ASH_HT_IMPL Ht>
void	swap (hashgrid< V, M, KA, A, Ht > &x, hashgrid< V, M, KA, A, Ht > &y)
	Global swap.
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.

---

Detailed Description

template<class Coord, typename Data, class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
class ash::sparse_hashgrid< Coord, Data, Alloc >

A hashgrid with sparse_hashtable as a backend.

Concepts:

ash::hash_grid

Concepts:

stl::unique_hashed_associative_container

Concepts:

stl::pair_associative_container

Template Parameters:

Coord	[PCoordXY<>|PCoordXYZ<>] The coordinate type.
Data	The data type associated with a Key. Also defined as sparse_hashgrid::data_type.
Alloc	The allocator type - passed to the base class for implementation.

---

Member Typedef Documentation

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

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, inherited]

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

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

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

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

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

typedef _Base::allocator_type ash::hashgrid::allocator_type [inherited]

The allocator used by the container.

Reimplemented from ash::hashgraph.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::const_iterator ash::sparse_hashgrid< Coord, Data, Alloc >::const_iterator

The container's const_iterator.

Reimplemented from ash::hashgrid.

typedef _Base::const_iterator_pair ash::hashgrid::const_iterator_pair [inherited]

A pair of const_iterators (convenience).

Reimplemented from ash::hashgraph.

typedef _Base::const_local_iterator ash::hashgrid::const_local_iterator [inherited]

The container's const_local_iterator.

Reimplemented from ash::hashgraph.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef value_type const* ash::sparse_hashgrid< Coord, Data, Alloc >::const_pointer

Const pointer to value_type.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef value_type const& ash::sparse_hashgrid< Coord, Data, Alloc >::const_reference

Const reference to value_type.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::difference_type ash::sparse_hashgrid< Coord, Data, Alloc >::difference_type

The signed type used to represent the distance between iterators.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::hasher ash::sparse_hashgrid< Coord, Data, Alloc >::hasher

The hash functor used by the container.

Reimplemented from ash::hashgrid.

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

The hashtable's allocator.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::hashtable_type ash::sparse_hashgrid< Coord, Data, Alloc >::hashtable_type [protected]

The hashtable used as a backend.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::iterator ash::sparse_hashgrid< Coord, Data, Alloc >::iterator

The container's iterator.

Reimplemented from ash::hashgrid.

typedef _Base::iterator_pair ash::hashgrid::iterator_pair [inherited]

A pair of iterators (convenience).

Reimplemented from ash::hashgraph.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::key_access ash::sparse_hashgrid< Coord, Data, Alloc >::key_access

Functor to access a key_type from a value_type.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::key_equal ash::sparse_hashgrid< Coord, Data, Alloc >::key_equal

The key comparison functor used by the container.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef Coord::morton_type ash::sparse_hashgrid< Coord, Data, Alloc >::key_type

The type of key associated with elements.

Reimplemented from ash::hashgrid.

typedef _Base::local_iterator ash::hashgrid::local_iterator [inherited]

The container's local_iterator.

Reimplemented from ash::hashgraph.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::morton_type ash::sparse_hashgrid< Coord, Data, Alloc >::morton_type

Interleaved coordinate type.

Interchangeable with key_type and pcoord_type for all public methods.

Reimplemented from ash::hashgrid.

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

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

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::node_type ash::sparse_hashgrid< Coord, Data, Alloc >::node_type [protected]

Concept: ash::hash_graph

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::pcoord_type ash::sparse_hashgrid< Coord, Data, Alloc >::pcoord_type

Coordinate type.

Interchangeable with key_type and morton_type for all public methods.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::point_type ash::sparse_hashgrid< Coord, Data, Alloc >::point_type

Floating-point coordinate type.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef value_type* ash::sparse_hashgrid< Coord, Data, Alloc >::pointer

Pointer to value_type.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef value_type& ash::sparse_hashgrid< Coord, Data, Alloc >::reference

Reference to value_type.

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef _Base::size_type ash::sparse_hashgrid< Coord, Data, Alloc >::size_type

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

Reimplemented from ash::hashgrid.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

typedef pair<const key_type, data_type> ash::sparse_hashgrid< Coord, Data, Alloc >::value_type

The type of object stored by the container.

Reimplemented from ash::hashgrid.

---

Constructor & Destructor Documentation

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

ash::sparse_hashgrid< Coord, Data, Alloc >::sparse_hashgrid	(	size_type	n = 0,
		hasher const &	h = hasher(),
		key_equal const &	k = key_equal()
	)		[inline, explicit]

Default constructor.

Parameters:

n	The number of expected elements.
h	The hasher object to copy, if any.
k	The key_equal object to copy, if any.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

template<class InputIterator >

ash::sparse_hashgrid< Coord, Data, Alloc >::sparse_hashgrid	(	InputIterator const &	f,
		InputIterator const &	l,
		size_type	n = 0,
		hasher const &	h = hasher(),
		key_equal const &	k = key_equal()
	)		[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 expected elements.
h	The hasher object to copy, if any.
k	The key_equal object to copy, if any.

---

Member Function Documentation

iterator ash::hashgraph::begin

(

)

[inline, inherited]

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, inherited]

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, inherited]

Concept: tr1::unordered_associative_container

const_local_iterator ash::hashgraph::begin

(

size_type

i

)

const [inline, inherited]

Concept: tr1::unordered_associative_container

size_type ash::hashgraph::bucket

(

key_type const &

key

)

const [inline, inherited]

Concept: tr1::unordered_associative_container

size_type ash::hashgraph::bucket_count

(

)

const [inline, inherited]

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, inherited]

Erase all elements.

Concept: stl::associative_container

size_type ash::hashgraph::count

(

key_type const &

k

)

const [inline, inherited]

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, inherited]

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, inherited]

Check if the container is empty.

Returns:

True if the container is empty.

Concept: stl::container

iterator ash::hashgraph::end

(

)

[inline, inherited]

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, inherited]

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, inherited]

Concept: tr1::unordered_associative_container

const_local_iterator ash::hashgraph::end

(

size_type

i

)

const [inline, inherited]

Concept: tr1::unordered_associative_container

iterator_pair ash::hashgraph::equal_range

(

key_type const &

k

)

[inline, inherited]

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, inherited]

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, inherited]

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, inherited]

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, inherited]

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, inherited]

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, inherited]

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, inherited]

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, inherited]

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::hashgrid::insert

(

const_reference

v

)

[inline, inherited]

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

Reimplemented from ash::hashgraph.

template<class InputIterator >

void ash::hashgrid::insert	(	InputIterator	f,
		InputIterator const &	l
	)		[inline, inherited]

Insert a range of elements [f,l) into the container.

Parameters:

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

Elements with duplicate keys will be ignored.

Concept: stl::unique_associative_container

key_equal ash::hashgraph::key_eq

(

)

const [inline, inherited]

Get the key comparison functor used by the container.

Returns:

A copy of the container's key_equal object.

Concept: stl::hashed_associative_container

float ash::hashgraph::load_factor

(

)

const [inline, inherited]

Concept: tr1::unordered_associative_container

float ash::hashgraph::max_load_factor

(

)

const [inline, inherited]

Concept: tr1::unordered_associative_container

float ash::hashgraph::max_load_factor

(

size_type

new_grow

)

[inline, inherited]

Concept: tr1::unordered_associative_container

size_type ash::hashgraph::max_size

(

)

const [inline, inherited]

Get the maximum size of the container.

Returns:

The maximum number of elements the container can hold.

Concept: stl::container

size_t ash::hashgraph::memory

(

)

const [inline, inherited]

Get the container's total memory load.

Returns:

The amount of memory used by the container in bytes.

Reimplemented in ash::hashlist.

float ash::hashgraph::min_load_factor

(

)

const [inline, inherited]

Get the min load factor.

Returns:

The min load factor before the container shrinks.

float ash::hashgraph::min_load_factor

(

size_type

new_shrink

)

[inline, inherited]

Set the min load factor.

Parameters:

new_shrink

The min load factor before the container shrinks.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>

data_type& ash::sparse_hashgrid< Coord, Data, Alloc >::operator[]

(

key_type const &

key

)

[inline]

Element access.

Parameters:

key	The key of the element to access.

Returns:

A reference to the corresponding data value. If an element with the key does not exist, it will be inserted.

void ash::hashgraph::rehash

(

size_type

n

)

[inline, inherited]

Concept: tr1::unordered_associative_container

void ash::hashgraph::resize

(

size_type

n

)

[inline, inherited]

Resize the container to hold at least n elements.

Parameters:

n	The number of elements the container is expected to hold.

Concept: stl::hashed_associative_container

size_type ash::hashgraph::size

(

)

const [inline, inherited]

Get the size of the container.

Returns:

The number of elements in the container.

Concept: stl::container

void ash::hashgraph::swap

(

hashgraph &

hg

)

[inline, inherited]

Swap method.

Concept: stl::container

---

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

• ash/sparse_hashgrid.h