koutil
Loading...
Searching...
No Matches
koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator > Class Template Reference

A hash array with open addressing and linear probing. More...

#include <hash_array.h>

Classes

struct  AdapterWrapper
 
struct  HashWrapper
 

Public Types

using iterator_t = template_hash_array_t::iterator_t
 
using const_iterator_t = template_hash_array_t::const_iterator_t
 

Public Member Functions

 hash_array ()=default
 Default constructor.
 
 hash_array (std::size_t bucket_count)
 Constructor with bucket count.
 
 hash_array (const hash_array &other)
 Copy constructor.
 
 hash_array (hash_array &&other)
 Move constructor.
 
 ~hash_array ()=default
 Destructor.
 
hash_arrayoperator= (const hash_array &other)=default
 Copy assignment operator.
 
hash_arrayoperator= (hash_array &&other)=default
 Move assignment operator.
 
bool empty () const
 Check if the hash_array is empty.
 
std::size_t size () const
 Get the number of elements in the hash_array.
 
std::size_t bucket_count () const
 Returns the number of buckets.
 
float max_load_factor () const
 Returns the maximum load factor.
 
void set_max_load_factor (float factor)
 Sets a new maximum load factor.
 
void clear ()
 Clear all elements from the hash_array.
 
bool try_insert (const key_t &key, const key_id_t &key_id, adapter_t adapter)
 Try to insert a key and key ID into the hash_array.
 
bool try_set (const key_t &key, const key_id_t &new_key_id, adapter_t adapter)
 Try to set new key ID.
 
void erase (const key_t &key, adapter_t adapter)
 Erases an element from the hash table.
 
iterator_t find (const key_t &key, adapter_t adapter)
 Finds an element in the hash table.
 
const_iterator_t find (const key_t &key, adapter_t adapter) const
 Finds an element in the hash table.
 
iterator_t begin ()
 Get an iterator to the beginning of the hash_array.
 
iterator_t end ()
 Get an iterator to the end of the hash_array.
 
const_iterator_t begin () const
 Get a constant iterator to the beginning of the hash_array.
 
const_iterator_t end () const
 Get a constant iterator to the end of the hash_array.
 
const_iterator_t cbegin () const
 Get a constant iterator to the beginning of the hash_array.
 
const_iterator_t cend () const
 Get a constant iterator to the end of the hash_array.
 

Private Types

using key_t = Key
 
using key_id_t = KeyID
 
using value_t = std::size_t
 
using bucket_t = Bucket
 
using hash_t = Hash
 
using bucket_iter = bucket_t::iterator
 
using adapter_t = KeyAdapter
 
using allocator_t = Allocator
 
using template_hash_array_t = template_hash_array<key_t, key_id_t, bool, AdapterWrapper, HashWrapper, bucket_t, allocator_t>
 

Private Attributes

template_hash_array_t m_storage
 

Static Private Attributes

static constexpr bool comptime_value = true
 

Detailed Description

template<typename Key, typename KeyID, is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
class koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >

A hash array with open addressing and linear probing.

Template Parameters
KeyThe key type.
KeyIDThe key ID type.
KeyAdapterThe key adapter type.
HashThe hash function type.
BucketThe bucket type.
AllocatorThe allocator type.

Member Typedef Documentation

◆ adapter_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::adapter_t = KeyAdapter
private

◆ allocator_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::allocator_t = Allocator
private

◆ bucket_iter

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::bucket_iter = bucket_t::iterator
private

◆ bucket_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::bucket_t = Bucket
private

◆ const_iterator_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::const_iterator_t = template_hash_array_t::const_iterator_t

◆ hash_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::hash_t = Hash
private

◆ iterator_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::iterator_t = template_hash_array_t::iterator_t

◆ key_id_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::key_id_t = KeyID
private

◆ key_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::key_t = Key
private

◆ template_hash_array_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::template_hash_array_t = template_hash_array<key_t, key_id_t, bool, AdapterWrapper, HashWrapper, bucket_t, allocator_t>
private

◆ value_t

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
using koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::value_t = std::size_t
private

Constructor & Destructor Documentation

◆ hash_array() [1/4]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::hash_array ( )
default

Default constructor.

◆ hash_array() [2/4]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::hash_array ( std::size_t bucket_count)
inline

Constructor with bucket count.

Parameters
bucket_countNumber of buckets.

◆ hash_array() [3/4]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::hash_array ( const hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator > & other)
inline

Copy constructor.

Parameters
otherAnother hash_array to copy from.

◆ hash_array() [4/4]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::hash_array ( hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator > && other)
inline

Move constructor.

Parameters
otherAnother hash_array to move from.

◆ ~hash_array()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::~hash_array ( )
default

Destructor.

Member Function Documentation

◆ begin() [1/2]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
iterator_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::begin ( )
inline

Get an iterator to the beginning of the hash_array.

Returns
iterator_t Iterator to the beginning.

◆ begin() [2/2]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
const_iterator_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::begin ( ) const
inline

Get a constant iterator to the beginning of the hash_array.

Returns
const_iterator_t Constant iterator to the beginning.

◆ bucket_count()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
std::size_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::bucket_count ( ) const
inlinenodiscard

Returns the number of buckets.

Returns
std::size_t Number of buckets.

◆ cbegin()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
const_iterator_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::cbegin ( ) const
inline

Get a constant iterator to the beginning of the hash_array.

Returns
iterator_t Constant iterator to the beginning.

◆ cend()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
const_iterator_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::cend ( ) const
inline

Get a constant iterator to the end of the hash_array.

Returns
const_iterator_t Constant iterator to the end.

◆ clear()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
void koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::clear ( )
inline

Clear all elements from the hash_array.

◆ empty()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
bool koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::empty ( ) const
inlinenodiscard

Check if the hash_array is empty.

Returns
bool True if empty, false otherwise.

◆ end() [1/2]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
iterator_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::end ( )
inline

Get an iterator to the end of the hash_array.

Returns
iterator_t Iterator to the end.

◆ end() [2/2]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
const_iterator_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::end ( ) const
inline

Get a constant iterator to the end of the hash_array.

Returns
const_iterator_t Constant iterator to the end.

◆ erase()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
void koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::erase ( const key_t & key,
adapter_t adapter )
inline

Erases an element from the hash table.

Parameters
keyKey of the element to erase.
adapterKey adapter for comparison.
Returns
true If the element was successfully erased.
false If the element was not found.

◆ find() [1/2]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
iterator_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::find ( const key_t & key,
adapter_t adapter )
inline

Finds an element in the hash table.

Parameters
keyKey of the element to find.
adapterKey adapter for comparison.
Returns
iterator_t The iterator with found element, if not found end() is returned.

◆ find() [2/2]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
const_iterator_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::find ( const key_t & key,
adapter_t adapter ) const
inline

Finds an element in the hash table.

Parameters
keyKey of the element to find.
adapterKey adapter for comparison.
Returns
const_iterator_t The iterator with found element, if not found end() is returned.

◆ max_load_factor()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
float koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::max_load_factor ( ) const
inlinenodiscard

Returns the maximum load factor.

Returns
float Maximum load factor.

◆ operator=() [1/2]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
hash_array & koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::operator= ( const hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator > & other)
default

Copy assignment operator.

Parameters
otherAnother hash_array to copy from.
Returns
hash_array& Reference to the assigned hash_array.

◆ operator=() [2/2]

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
hash_array & koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::operator= ( hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator > && other)
default

Move assignment operator.

Parameters
otherAnother hash_array to move from.
Returns
hash_array& Reference to the assigned hash_array.

◆ set_max_load_factor()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
void koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::set_max_load_factor ( float factor)
inline

Sets a new maximum load factor.

Parameters
factorNew maximum load factor.

◆ size()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
std::size_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::size ( ) const
inlinenodiscard

Get the number of elements in the hash_array.

Returns
std::size_t Number of elements.

◆ try_insert()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
bool koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::try_insert ( const key_t & key,
const key_id_t & key_id,
adapter_t adapter )
inline

Try to insert a key and key ID into the hash_array.

Parameters
keyThe key to insert.
key_idThe key ID to insert.
Returns
bool True if the key is not inside hash_array, false otherwise.

◆ try_set()

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
bool koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::try_set ( const key_t & key,
const key_id_t & new_key_id,
adapter_t adapter )
inline

Try to set new key ID.

Parameters
keyThe key.
new_key_idThe new key ID.
Returns
bool True if the key ID was changed, false otherwise.

Member Data Documentation

◆ comptime_value

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
bool koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::comptime_value = true
staticconstexprprivate

◆ m_storage

template<typename Key , typename KeyID , is_key_adapter< Key, KeyID > KeyAdapter, is_hash< Key > Hash = std::hash<Key>, is_bucket< KeyID > Bucket = std::vector<std::pair<std::size_t, KeyID>>, is_allocator< Bucket > Allocator = std::allocator<Bucket>>
template_hash_array_t koutil::container::hash_array< Key, KeyID, KeyAdapter, Hash, Bucket, Allocator >::m_storage
private

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