A hashmatrix with sparse_hashtable as a backend. More...
#include <ash/sparse_hashmatrix.h>
Public Types | |
typedef Coord::morton_type | key_type |
The type of key associated with objects in the container. | |
typedef Data | data_type |
typedef pair< const key_type, Data > | value_type |
The type of the object the container holds. | |
typedef value_type * | pointer |
The type that serves as a pointer to value_type. | |
typedef value_type const * | const_pointer |
The type that serves as a const pointer to value_type. | |
typedef value_type & | reference |
The type that serves as a reference to value_type. | |
typedef value_type const & | const_reference |
The type that serves as a pointer 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 integral type used to represent the distance between iterators. | |
typedef _Base::morton_type | morton_type |
The type used to represent a hashed/interleaved coordinate. | |
typedef _Base::pcoord_type | pcoord_type |
The type used to represent a coordinate. | |
typedef _Base::point_type | point_type |
The type used to represent a floating-point coordinate. | |
typedef _Base::hasher | hasher |
The functor type used to hash keys. | |
typedef _Base::iterator | iterator |
typedef _Base::const_iterator | const_iterator |
typedef _Base::navigator | navigator |
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 functor used to compare keys for equality. | |
typedef _Base::key_access | key_access |
| |
typedef _Alloc | allocator_type |
| |
Public Member Functions | |
Constructors/Destructors | |
We use the default copy constructor. We use the default destructor. | |
sparse_hashmatrix (size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal()) | |
Default constructor. | |
template<class InputIterator > | |
sparse_hashmatrix (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. | |
Iteration Methods | |
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 |
| |
Bucket Methods | |
size_type | bucket (key_type const &key) const |
| |
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 Methods | |
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. | |
float | load_factor () const |
| |
float | max_load_factor () const |
| |
void | max_load_factor (float new_grow) |
| |
float | min_load_factor () const |
Get the min load factor. | |
void | min_load_factor (float new_shrink) |
Set the min load factor. | |
void | resize (size_type n) |
Resize the container to hold at least n elements. | |
void | rehash (size_type n) |
| |
size_t | dynamic_memory () const |
size_t | memory () const |
Lookup Methods | |
iterator | find (key_type const &key) |
Find an element. | |
const_iterator | find (key_type const &key) const |
Find an element. | |
size_type | count (key_type const &key) const |
Count the number of elements with a given key. | |
iterator_pair | equal_range (key_type const &key) |
Find all elements matching a given key. | |
const_iterator_pair | equal_range (key_type const &key) const |
Find all elements matching a given key. | |
Insertion/Deletion Methods | |
pair< iterator, bool > | insert (const_reference obj) |
Insert an element into the container. | |
template<class InputIterator > | |
void | insert (InputIterator f, InputIterator l) |
Insert a range of elements [f,l) into the container. | |
void | erase (iterator itr) |
Erase an element. | |
void | erase (iterator f, iterator l) |
Erase a range of elements. | |
void | clear () |
Erase all elements. | |
Utility 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. | |
key_type const & | extract_key (value_type const &val) const |
Constructors/Destructors | |
We use the default copy constructor. We use the default destructor. | |
void | swap (hashmatrix &obj) |
| |
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) |
Hash-Matrix concept. ,range_begin(key_type const&,size_type) | |
const_range_iterator | range_begin (key_type const &key, size_type range) const |
Get an iterator to go through all elements in a given range. | |
Path-Iterator Methods | |
Use the normal end() method. | |
path_iterator | path_begin (point_type const &p1, point_type const &p2) |
Get an iterator from point A to point B. | |
const_path_iterator | path_begin (point_type const &p1, point_type const &p2) const |
Get an iterator from point A to point B. | |
Static Public Attributes | |
static const DIM | D = dim_cast<_Morton::D>::D |
| |
static const size_type | empty_key = impl::matrix_keys<_Morton>::empty_key |
| |
static const size_type | deleted_key = impl::matrix_keys<_Morton>::deleted_key |
| |
static const pcoord_type | pcoord_max |
| |
Protected Types | |
typedef _Type | dense_hashmatrix_type |
typedef _Base | hashmatrix_type |
typedef _Base::hashtable_type | hashtable_type |
typedef table_value_allocator < typename _Alloc::template rebind< _Val >::other > | hashtable_allocator |
typedef hashtable_type::iterator | hashtable_iterator |
typedef hashtable_type::const_iterator | hashtable_const_iterator |
typedef hashtable_type::local_iterator | hashtable_local_iterator |
typedef hashtable_type::const_local_iterator | hashtable_const_local_iterator |
typedef matrix_iterator < hashmatrix, hashtable_iterator, trivial > | iterator_base |
typedef matrix_iterator < hashmatrix, hashtable_const_iterator, add_const > | const_iterator_base |
typedef matrix_iterator < hashmatrix, hashtable_local_iterator, trivial > | local_iterator_base |
typedef matrix_iterator < hashmatrix, hashtable_const_local_iterator, add_const > | const_local_iterator_base |
typedef pair< iterator, iterator > | iterator_pair |
convenience | |
typedef pair< const_iterator, const_iterator > | const_iterator_pair |
convenience | |
typedef matrix_navigator < hashmatrix, iterator_base, trivial, D > | navigator_base |
typedef matrix_navigator < hashmatrix, const_iterator_base, add_const, D > | const_navigator_base |
Protected Attributes | |
key_access | access |
hashtable_type | hashtable |
Related Functions | |
(Note that these are not member functions.) | |
void | swap (hashmatrix &x, hashmatrix &y) |
Global swap. |
A hashmatrix with sparse_hashtable as a backend.
Coord | [PCoordXY<>|PCoordXYZ<>] The coordinate type. |
Data | The data type associated with a Key. Also defined as sparse_hashmatrix::data_type. |
Alloc | The allocator type - passed to the base class for implementation. |
A Hash Matrix is a geometric hashed container which implements the STL concepts Unique Hashed Associative Container and Pair Associative Container . As such, it has many similarities with STL's hash_map
. The only area where the hash_map
semantics are not valid for a hash_matrix
is in the template parameters. The major difference is that you cannot specify an arbitrary key type, it must be a pcoord type. In reality you are specifying 2 things this way: the size of the key, and the dimensionality of the data (2D or 3D). Since the key type is mostly pre-defined, the hash functor and key equality functor are also built-in; you cannot specify either. As a result, there are only 3 template parameters:
As a geometric container, it is useful to have a way to iterate through elements by axis, and for this purpose we provide hash_matrix::navigator and hash_matrix::const_navigator. They work similarly to iterators, except that it is not possible to increment and decrement them directly. Instead, they have x, y, and (for 3D) z members, which allow intuitive semantics like ++nav.x, nav.y++, --nav.z, etc. Another important difference is that navigators may be at "empty" locations: they may represent any valid coordinate, but are only dereferenceable if there is an element associated with the coordinate in the container. To determine if the navigator is dereferencable, they provide the valid() method.
typedef _Alloc ash::hashmatrix::allocator_type [inherited] |
typedef value_type const* ash::sparse_hashmatrix< Coord, Data, Alloc >::const_pointer |
The type that serves as a const pointer to value_type.
Concept: stl::container
Reimplemented from ash::hashmatrix.
typedef value_type const& ash::sparse_hashmatrix< Coord, Data, Alloc >::const_reference |
The type that serves as a pointer to value_type.
Concept: stl::container
Reimplemented from ash::hashmatrix.
typedef _Base::difference_type ash::sparse_hashmatrix< Coord, Data, Alloc >::difference_type |
The signed integral type used to represent the distance between iterators.
Reimplemented from ash::hashmatrix.
typedef _Base::hasher ash::sparse_hashmatrix< Coord, Data, Alloc >::hasher |
The functor type used to hash keys.
Concept: stl::hashed_associative_container
Reimplemented from ash::hashmatrix.
typedef _Base::key_access ash::sparse_hashmatrix< Coord, Data, Alloc >::key_access |
Concept: ash::hashmatrix
Reimplemented from ash::hashmatrix.
typedef _Base::key_equal ash::sparse_hashmatrix< Coord, Data, Alloc >::key_equal |
The functor used to compare keys for equality.
Concept: stl::hashed_associative_container
Reimplemented from ash::hashmatrix.
typedef Coord::morton_type ash::sparse_hashmatrix< Coord, Data, Alloc >::key_type |
The type of key associated with objects in the container.
We use this type as the key for conversion convenience. Any method that takes a key_type as an argument may take any of the following:
In the case of a pcoord_type, conversion to key_type will hash it. Otherwise it is treated as a pre-hashed key.
Concept: ash::hash_matrix
Reimplemented from ash::hashmatrix.
typedef _Base::morton_type ash::sparse_hashmatrix< Coord, Data, Alloc >::morton_type |
The type used to represent a hashed/interleaved coordinate.
Conversion-compatible with pcoord_type. Conversion-compatible with size_type.
Reimplemented from ash::hashmatrix.
typedef _Base::pcoord_type ash::sparse_hashmatrix< Coord, Data, Alloc >::pcoord_type |
The type used to represent a coordinate.
Conversion-compatible with morton_type.
Reimplemented from ash::hashmatrix.
typedef _Base::point_type ash::sparse_hashmatrix< Coord, Data, Alloc >::point_type |
The type used to represent a floating-point coordinate.
Reimplemented from ash::hashmatrix.
typedef value_type* ash::sparse_hashmatrix< Coord, Data, Alloc >::pointer |
The type that serves as a pointer to value_type.
Concept: stl::container
Reimplemented from ash::hashmatrix.
typedef value_type& ash::sparse_hashmatrix< Coord, Data, Alloc >::reference |
The type that serves as a reference to value_type.
Concept: stl::container
Reimplemented from ash::hashmatrix.
typedef _Base::size_type ash::sparse_hashmatrix< Coord, Data, Alloc >::size_type |
The unsigned type used to represent the size of the container.
Reimplemented from ash::hashmatrix.
typedef pair<const key_type, Data> ash::sparse_hashmatrix< Coord, Data, Alloc >::value_type |
The type of the object the container holds.
Must be Assignable .
Concept: stl::container
Reimplemented from ash::hashmatrix.
ash::sparse_hashmatrix< Coord, Data, Alloc >::sparse_hashmatrix | ( | size_type | n = 0 , |
hasher const & | h = hasher() , |
||
key_equal const & | k = key_equal() |
||
) | [inline, explicit] |
Default constructor.
n | The number of expected elements. |
h | The hasher object to copy, if any. |
k | The key_equal object to copy, if any. |
ash::sparse_hashmatrix< Coord, Data, Alloc >::sparse_hashmatrix | ( | InputIterator const & | f, |
InputIterator const & | l, | ||
size_type | n = 0 , |
||
hasher const & | h = hasher() , |
||
key_equal const & | k = key_equal() |
||
) | [inline] |
Iterative constructor.
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. |
iterator ash::hashmatrix::begin | ( | ) | [inline, inherited] |
Get an iterator to the beginning.
const_iterator ash::hashmatrix::begin | ( | ) | const [inline, inherited] |
Get an iterator to the beginning.
local_iterator ash::hashmatrix::begin | ( | size_type | i | ) | [inline, inherited] |
Concept: tr1::unordered_associative_container
const_local_iterator ash::hashmatrix::begin | ( | size_type | i | ) | const [inline, inherited] |
Concept: tr1::unordered_associative_container
size_type ash::hashmatrix::bucket | ( | key_type const & | key | ) | const [inline, inherited] |
Concept: tr1::unordered_associative_container
size_type ash::hashmatrix::bucket_count | ( | ) | const [inline, inherited] |
Get the number of buckets the container has.
size_type ash::hashmatrix::bucket_size | ( | size_type | i | ) | const [inline, inherited] |
Concept: tr1::unordered_associative_container
void ash::hashmatrix::clear | ( | ) | [inline, inherited] |
Erase all elements.
Concept: stl::associative_container
size_type ash::hashmatrix::count | ( | key_type const & | key | ) | const [inline, inherited] |
Count the number of elements with a given key.
key | The key to search for. |
key
. Because this is a Unique Associative Container , the return value will be 0 or 1. bool ash::hashmatrix::empty | ( | ) | const [inline, inherited] |
iterator ash::hashmatrix::end | ( | ) | [inline, inherited] |
Get an iterator to the end.
const_iterator ash::hashmatrix::end | ( | ) | const [inline, inherited] |
Get an iterator to the end.
local_iterator ash::hashmatrix::end | ( | size_type | i | ) | [inline, inherited] |
Concept: tr1::unordered_associative_container
const_local_iterator ash::hashmatrix::end | ( | size_type | i | ) | const [inline, inherited] |
Concept: tr1::unordered_associative_container
iterator_pair ash::hashmatrix::equal_range | ( | key_type const & | key | ) | [inline, inherited] |
Find all elements matching a given key.
key | The key to search for. |
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(). const_iterator_pair ash::hashmatrix::equal_range | ( | key_type const & | key | ) | const [inline, inherited] |
Find all elements matching a given key.
key | The key to search for. |
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(). void ash::hashmatrix::erase | ( | iterator | itr | ) | [inline, inherited] |
Erase an element.
itr | An iterator pointing to the element to erase. |
void ash::hashmatrix::erase | ( | iterator | f, |
iterator | l | ||
) | [inline, inherited] |
Erase a range of elements.
f | The beginning of the range to erase. |
l | The end of the range to erase. |
iterator ash::hashmatrix::find | ( | key_type const & | key | ) | [inline, inherited] |
Find an element.
key | The key of the element to search for. |
const_iterator ash::hashmatrix::find | ( | key_type const & | key | ) | const [inline, inherited] |
Find an element.
key | The key of the element to search for. |
hasher ash::hashmatrix::hash_funct | ( | ) | const [inline, inherited] |
Get the hash functor used by the container.
hasher
object. hasher ash::hashmatrix::hash_function | ( | ) | const [inline, inherited] |
Get the hash functor used by the container.
hasher
object. pair<iterator, bool> ash::hashmatrix::insert | ( | const_reference | obj | ) | [inline, inherited] |
Insert an element into the container.
obj | The element to insert. |
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. void ash::hashmatrix::insert | ( | InputIterator | f, |
InputIterator | l | ||
) | [inline, inherited] |
Insert a range of elements [f,l) into the container.
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::hashmatrix::key_eq | ( | ) | const [inline, inherited] |
Get the key comparison functor used by the container.
key_equal
object. float ash::hashmatrix::load_factor | ( | ) | const [inline, inherited] |
Concept: tr1::unordered_associative_container
size_type ash::hashmatrix::max_bucket_count | ( | ) | const [inline, inherited] |
Concept: stl::hashed_associative_container
float ash::hashmatrix::max_load_factor | ( | ) | const [inline, inherited] |
Concept: tr1::unordered_associative_container
void ash::hashmatrix::max_load_factor | ( | float | new_grow | ) | [inline, inherited] |
Concept: tr1::unordered_associative_container
size_type ash::hashmatrix::max_size | ( | ) | const [inline, inherited] |
Get the maximum size of the container.
float ash::hashmatrix::min_load_factor | ( | ) | const [inline, inherited] |
Get the min load factor.
void ash::hashmatrix::min_load_factor | ( | float | new_shrink | ) | [inline, inherited] |
Set the min load factor.
new_shrink | The min load factor before the container shrinks. |
navigator ash::hashmatrix::navigate | ( | key_type const & | key | ) | [inline, inherited] |
Concept: ash::hash_matrix
const_navigator ash::hashmatrix::navigate | ( | key_type const & | key | ) | const [inline, inherited] |
Concept: ash::hash_matrix
data_type& ash::sparse_hashmatrix< Coord, Data, Alloc >::operator[] | ( | key_type const & | key | ) | [inline] |
Element access.
key | The key of the element to access. |
path_iterator ash::hashmatrix::path_begin | ( | point_type const & | p1, |
point_type const & | p2 | ||
) | [inline, inherited] |
Get an iterator from point A to point B.
pa | Point A. |
pb | Point B. |
const_path_iterator ash::hashmatrix::path_begin | ( | point_type const & | p1, |
point_type const & | p2 | ||
) | const [inline, inherited] |
Get an iterator from point A to point B.
pa | Point A. |
pb | Point B. |
range_iterator ash::hashmatrix::range_begin | ( | key_type const & | key, |
size_type | range | ||
) | [inline, inherited] |
Hash-Matrix concept. ,range_begin(key_type const&,size_type)
const_range_iterator ash::hashmatrix::range_begin | ( | key_type const & | key, |
size_type | range | ||
) | const [inline, inherited] |
Get an iterator to go through all elements in a given range.
pos | The center of the area. |
range | The max 1-dimensional distance from pos . |
range
of pos
. void ash::hashmatrix::rehash | ( | size_type | n | ) | [inline, inherited] |
Concept: tr1::unordered_associative_container
void ash::hashmatrix::resize | ( | size_type | n | ) | [inline, inherited] |
Resize the container to hold at least n elements.
n | The number of elements the container is expected to hold. |
size_type ash::hashmatrix::size | ( | ) | const [inline, inherited] |
Get the size of the container.
void ash::hashmatrix::swap | ( | hashmatrix & | obj | ) | [inline, inherited] |
Concept: ash::hash_matrix
const DIM ash::hashmatrix::D = dim_cast<_Morton::D>::D [static, inherited] |
Concept: ash::hash_matrix
const hashmatrix< _Val, _Morton, _KeyAccess, _Alloc, _Ht >::size_type ash::hashmatrix::deleted_key = impl::matrix_keys<_Morton>::deleted_key [static, inherited] |
Concept: ash::hash_matrix
const hashmatrix< _Val, _Morton, _KeyAccess, _Alloc, _Ht >::size_type ash::hashmatrix::empty_key = impl::matrix_keys<_Morton>::empty_key [static, inherited] |
Concept: ash::hash_matrix
const hashmatrix< _Val, _Morton, _KeyAccess, _Alloc, _Ht >::pcoord_type ash::hashmatrix::pcoord_max [static, inherited] |
typename hashmatrix<_Val,_Morton,_KeyAccess,_Alloc,_Ht> ::pcoord_type(impl::matrix_keys<_Morton>::pcoord_max)
Concept: ash::hash_matrix
© 2012 | Licensed under | Hosted by | Generated by 1.7.4 |