AGX Dynamics 2.42.3.1
Loading...
Searching...
No Matches
agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > Class Template Reference

A simple hash table using quadratic probing. More...

#include <QuadraticProbingHashTable.h>

+ Inheritance diagram for agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >:

Classes

class  Bucket
 
class  insert_iterator
 
class  template_iterator
 

Public Types

typedef template_iterator< const QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > > const_iterator
 
typedef HashT hash_fn_type
 
typedef template_iterator< QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > > iterator
 Iterators.
 
typedef KeyT key_type
 
typedef DataT value_type
 
- Public Types inherited from agx::Container
enum  ClearPolicy { SHRINK_BUFFER , SHRINK_BUFFER_AVERAGED , MAINTAIN_BUFFER }
 agxData::Values from this enumeration is passed to the subclasses' 'clear' method in order to control what should become of the container's memory. More...
 

Public Member Functions

 QuadraticProbingHashTableImplementation (const AllocatorT &allocator=AllocatorT())
 Constructor.
 
 QuadraticProbingHashTableImplementation (const QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > &other)
 Copy constructor.
 
 ~QuadraticProbingHashTableImplementation ()
 Destructor.
 
AllocatorT & allocator ()
 
const AllocatorT & allocator () const
 
iterator begin ()
 Iterator to first element in hash table.
 
const_iterator begin () const
 
void clear (ClearPolicy policy=SHRINK_BUFFER_AVERAGED)
 Remove all elements.
 
bool contains (const KeyT &key) const
 Boolean query to test existence of an element.
 
iterator end ()
 Iterator marking end of hash table.
 
const_iterator end () const
 
iterator erase (const iterator &it)
 Erase an element using an iterator.
 
bool erase (const KeyT &key)
 Erase an element from the hash table.
 
iterator find (const KeyT &key)
 Find an element.
 
const_iterator find (const KeyT &key) const
 
const Bucket * getBucketBuffer () const
 
size_t getMaxProbeLength () const
 
size_t getNumBuckets () const
 
DataT & getOrCreate (const KeyT &key)
 Returns value given key.
 
insert_iterator insert (const KeyT &key, const DataT &data)
 Insert an element, overwriting if key already exists.
 
QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > & operator= (const QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > &other)
 Assignment operator.
 
DataT & operator[] (const KeyT &key)
 Index operator for accessing elements in the hash, inserting it if not found.
 
const DataT & operator[] (const KeyT &key) const
 
template<typename T >
void purge (T purger)
 Purge the hash table.
 
void reserve (size_t size)
 Reserve capacity in the hash table.
 
- Public Member Functions inherited from agx::Container
size_t capacity () const
 Returns the size of the memory are used by the container to store its elements.
 
bool empty () const
 
void * ptr ()
 
const void * ptr () const
 
size_t size () const
 

Protected Member Functions

Bucket * buckets () const
 
bool eraseBucket (size_t index)
 
template<typename T2 >
size_t findBucket (const T2 &key) const
 
size_t & numBuckets ()
 
size_t numBuckets () const
 
size_t & numFilled ()
 
size_t numFilled () const
 
void rebuild (size_t size)
 Rebuild, and optionally resize hash table.
 
- Protected Member Functions inherited from agx::Container
 Container ()
 
 Container (const Container &other)
 
 Container (Container &&other)
 
 ~Container ()
 

Additional Inherited Members

- Protected Attributes inherited from agx::Container
void * m_buffer
 
size_t m_capacity
 
size_t m_size
 

Detailed Description

template<typename KeyT, typename DataT, typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
class agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >

A simple hash table using quadratic probing.

Built-in support for keys of type int, agx::String, and pointers. To use other types of keys, a custom hash functor must be supplied.

\todo implement [] operator

Definition at line 47 of file QuadraticProbingHashTable.h.

Member Typedef Documentation

◆ const_iterator

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
typedef template_iterator< const QuadraticProbingHashTableImplementation<KeyT, DataT, HashT, AllocatorT> > agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::const_iterator

Definition at line 228 of file QuadraticProbingHashTable.h.

◆ hash_fn_type

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
typedef HashT agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::hash_fn_type

Definition at line 52 of file QuadraticProbingHashTable.h.

◆ iterator

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
typedef template_iterator< QuadraticProbingHashTableImplementation<KeyT, DataT, HashT, AllocatorT> > agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::iterator

Iterators.

Definition at line 227 of file QuadraticProbingHashTable.h.

◆ key_type

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
typedef KeyT agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::key_type

Definition at line 51 of file QuadraticProbingHashTable.h.

◆ value_type

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
typedef DataT agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::value_type

Definition at line 50 of file QuadraticProbingHashTable.h.

Constructor & Destructor Documentation

◆ QuadraticProbingHashTableImplementation() [1/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::QuadraticProbingHashTableImplementation ( const AllocatorT &  allocator = AllocatorT())
inline

Constructor.

Definition at line 259 of file QuadraticProbingHashTable.h.

◆ QuadraticProbingHashTableImplementation() [2/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::QuadraticProbingHashTableImplementation ( const QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > &  other)
inline

Copy constructor.

Definition at line 263 of file QuadraticProbingHashTable.h.

◆ ~QuadraticProbingHashTableImplementation()

Member Function Documentation

◆ allocator() [1/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
AllocatorT & agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::allocator ( )
inline

Definition at line 565 of file QuadraticProbingHashTable.h.

◆ allocator() [2/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
const AllocatorT & agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::allocator ( ) const
inline

Definition at line 566 of file QuadraticProbingHashTable.h.

◆ begin() [1/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
iterator agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::begin ( )
inline

Iterator to first element in hash table.

Definition at line 419 of file QuadraticProbingHashTable.h.

Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator=().

◆ begin() [2/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
const_iterator agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::begin ( ) const
inline

Definition at line 422 of file QuadraticProbingHashTable.h.

◆ buckets()

◆ clear()

◆ contains()

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
bool agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::contains ( const KeyT &  key) const
inline

◆ end() [1/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
iterator agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::end ( )
inline

◆ end() [2/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
const_iterator agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::end ( ) const
inline

◆ erase() [1/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
iterator agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::erase ( const iterator &  it)
inline

Erase an element using an iterator.

Returns
An iterator to the next element

Definition at line 449 of file QuadraticProbingHashTable.h.

References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::eraseBucket().

◆ erase() [2/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
bool agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::erase ( const KeyT &  key)
inline

◆ eraseBucket()

◆ find() [1/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
iterator agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::find ( const KeyT &  key)
inline

◆ find() [2/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
const_iterator agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::find ( const KeyT &  key) const
inline

◆ findBucket()

◆ getBucketBuffer()

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
const Bucket * agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::getBucketBuffer ( ) const
inline

◆ getMaxProbeLength()

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
size_t agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::getMaxProbeLength ( ) const
inline

Definition at line 574 of file QuadraticProbingHashTable.h.

◆ getNumBuckets()

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
size_t agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::getNumBuckets ( ) const
inline

◆ getOrCreate()

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
DataT & agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::getOrCreate ( const KeyT &  key)
inline

Returns value given key.

If the key doesn't exist, the key is inserted and the default value is returned.

Parameters
key- key
Returns
data for key

Definition at line 321 of file QuadraticProbingHashTable.h.

◆ insert()

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
insert_iterator agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert ( const KeyT &  key,
const DataT &  data 
)
inline

Insert an element, overwriting if key already exists.

Returns
An iterator to the inserted pair

Definition at line 330 of file QuadraticProbingHashTable.h.

References AGX_HASH_TABLE_GROW_FACTOR, AGX_HASH_TABLE_GROW_THRESHOLD, AGX_HASH_TABLE_MAX_PROBE_LENGTH, agxAssert, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::buckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::first, agx::hashKeyEqual(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::isActive(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::isValid(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numFilled(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::rebuild(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::second, and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::VALID.

Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator=(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator[](), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::rebuild().

◆ numBuckets() [1/2]

◆ numBuckets() [2/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
size_t agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets ( ) const
inlineprotected

Definition at line 587 of file QuadraticProbingHashTable.h.

References agx::Container::m_capacity.

◆ numFilled() [1/2]

◆ numFilled() [2/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
size_t agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numFilled ( ) const
inlineprotected

Definition at line 588 of file QuadraticProbingHashTable.h.

References agx::Container::m_size.

◆ operator=()

◆ operator[]() [1/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
DataT & agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator[] ( const KeyT &  key)
inline

◆ operator[]() [2/2]

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
const DataT & agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator[] ( const KeyT &  key) const
inline

◆ purge()

◆ rebuild()

◆ reserve()

template<typename KeyT , typename DataT , typename HashT = HashFn<KeyT>, typename AllocatorT = ByteAllocator>
void agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::reserve ( size_t  size)
inline

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