Self-adjusting dynamic hash table. More...

#include <tpl_dynSetHash.H>

Inheritance diagram for Aleph::DynHashTable< Key, HashTable, Cmp >:

Collaboration diagram for Aleph::DynHashTable< Key, HashTable, Cmp >:

Classes
class	Iterator

Public Types
using	Hash_Fct = typename Base::Hash_Fct
	Hash function type.

using	Hash_Fct_Ptr = typename Base::Hash_Fct_Ptr

using	Key_Type = Key

using	Item_Type = Key

Public Types inherited from StlAlephIterator< SetName >
using	iterator = StlIterator< SetName >

using	const_iterator = StlConstIterator< SetName >

Public Member Functions
	DynHashTable (size_t len=Primes::DefaultPrime, Hash_Fct_Ptr hash_fct=Aleph::dft_hash_ptr_fct< Key >, Cmp cmp=Cmp(), float lower_alpha=hash_default_lower_alpha, float upper_alpha=hash_default_upper_alpha)
	Creates a dynamic linear hash table.

	DynHashTable (size_t len, Hash_Fct hash_fct, Cmp cmp, float lower_alpha, float upper_alpha)

	DynHashTable (const DynHashTable &other)
	Copy constructor.

	DynHashTable (DynHashTable &&other) noexcept

template<template< typename > class List>
	DynHashTable (const List< Key > &l)

template<class It >
	DynHashTable (It b, It e)

	DynHashTable (std::initializer_list< Key > l)

	~DynHashTable ()

void	clear ()
	Empties the container.

bool	contains (const Key &key) const noexcept
	Return true if the key exists in the table.

bool	is_empty () const noexcept
	Checks if the container is empty.

DynHashTable &	operator= (const DynHashTable &other)

DynHashTable &	operator= (DynHashTable &&other) noexcept

Key *	insert (const Key &key)
	Inserts key into the hash set.

Key *	insert (Key &&key)

Key *	search_or_insert (const Key &key)

Key *	search_or_insert (Key &&key)

std::pair< Key *, bool >	contains_or_insert (const Key &key)

std::pair< Key *, bool >	contains_or_insert (Key &&key)

Key *	add (const Key &key)

Key *	add (Key &&key)

Key *	append (const Key &key)

Key *	append (Key &&key)

Key *	search (const Key &key) const noexcept
	Searches for a key in the hash table.

bool	has (const Key &key) const noexcept
	Checks if a key exists in the hash table.

const Key &	find (const Key &key) const

Key &	find (const Key &key)

void	remove (Key *key)
	Removes a key from the hash table using its pointer.

Key	remove (const Key &key)

const Key &	get_first () const

Key &	get_first ()

const Key &	get_last () const

Key &	get_last ()

Public Member Functions inherited from GenericTraverse< Container >
template<class Operation >
bool	traverse (Operation &operation) noexcept(traverse_is_noexcept< Operation >())
	Traverse the container via its iterator and performs a conditioned operation on each item.

template<class Operation >
bool	traverse (Operation &operation) const noexcept(traverse_is_noexcept< Operation >())
	Const overload of `traverse(Operation&)`.

template<class Operation >
bool	traverse (Operation &&operation) const noexcept(traverse_is_noexcept< Operation >())
	Overload of `traverse(Operation&) const` that accepts rvalues.

template<class Operation >
bool	traverse (Operation &&operation) noexcept(traverse_is_noexcept< Operation >())
	Overload of `traverse(Operation&)` that accepts rvalues.

Public Member Functions inherited from LocateFunctions< Container, Type >
auto	get_it () const
	Return a properly initialized iterator positioned at the first item on the container.

auto	get_it (const size_t pos) const
	Return a properly initialized iterator positioned at the `pos` item on the container.

auto	get_itor () const
	Alias of `get_it()`.

Type &	nth_ne (const size_t n) noexcept
	Return the n‑th element without bounds checking.

const Type &	nth_ne (const size_t n) const noexcept
	Const overload of `nth_ne(size_t)`.

Type &	nth (const size_t n)
	Return the n-th item of the container.

const Type &	nth (const size_t n) const
	Const overload of `nth(size_t)`.

template<class Operation >
Type *	find_ptr (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Find a pointer to an item in the container according to a searching criterion.

template<class Operation >
const Type *	find_ptr (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Const overload of `find_ptr(Operation&)`.

template<class Operation >
const Type *	find_ptr (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_ptr() const that accepts rvalues.

template<class Operation >
Type *	find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of find_ptr() that accepts rvalues.

template<class Operation >
size_t	find_index (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Find the position of an item in the container according to a searching criterion.

template<class Operation >
size_t	find_index (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_index() that accepts rvalues.

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Safe sequential searching of an item matching a criterion.

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &operation) const noexcept(operation_is_noexcept< Operation >())

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of find_item() that accepts rvalues.

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_item() const that accepts rvalues.

template<class Operation >
bool	contains_if (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Test if an item satisfying a criterion is present in the container.

bool	contains (const Type &item) const
	Test if an item is present in the container using equality.

Public Member Functions inherited from FunctionalMethods< Container, T >
template<typename ... Args>
void	emplace (Args &&... args)
	Appends a new element into the container by constructing it in-place with the given args.

template<typename ... Args>
void	emplace_end (Args &&... args)

template<typename ... Args>
void	emplace_ins (Args &&... args)
	Insert a new element into the container by constructing it in-place with the given args.

template<typename ... Args>
size_t	ninsert (Args ... args)
	Insert n variadic items.

template<typename ... Args>
size_t	nappend (Args ... args)
	Append n variadic items.

template<class Operation >
void	for_each (Operation &operation)
	Traverse all the container and performs an operation on each element.

template<class Operation >
void	for_each (Operation &operation) const
	Const overload of `for_each(Operation&)`.

template<class Operation >
void	for_each (Operation &&operation) const
	Overload of for_each() const that accepts rvalues.

template<class Operation >
void	for_each (Operation &&operation)
	Overload of for_each() that accepts rvalues.

template<class Operation >
void	each (Operation &operation)
	Alias of `for_each(Operation&)`.

template<class Operation >
void	each (Operation &operation) const
	Const alias of `for_each(Operation&)`.

template<class Operation >
void	each (Operation &&operation) const
	Const alias of each() that accepts rvalues.

template<class Operation >
void	each (Operation &&operation)
	Alias of each() that accepts rvalues.

template<class Operation >
void	each (size_t pos, const size_t slice, Operation &operation) const
	Traverse the container starting at `pos` taking one item every `slice`, performing a mutable operation on each visited element.

template<class Operation >
void	each (const size_t pos, const size_t slice, Operation &&operation) const

template<class Operation >
void	mutable_for_each (Operation &operation)
	Apply a mutable operation to each element of the container.

template<class Operation >
void	mutable_for_each (Operation &&operation)

template<class Operation >
bool	all (Operation &operation) const
	Check if all the elements of the container satisfy a condition.

template<class Operation >
bool	all (Operation &&operation) const
	Overload of all() that accepts rvalues.

template<class Operation >
bool	exists (Operation &op) const
	Test for existence in the container of an element satisfying a criterion.

template<class Operation >
bool	exists (Operation &&op) const
	Overload of exists() that accepts rvalues.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<T, __T>>
Aleph::DynList< __T >	maps (Operation &op) const
	Map the elements of the container.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<__T, __T>>
Aleph::DynList< __T >	maps (Operation &&op) const
	Overload of maps() that accepts rvalues.

template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &op) const
	Conditional mapping of the elements of the container.

template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &&op) const
	Overload of maps_if() that accepts rvalues.

Aleph::DynList< T >	to_dynlist () const
	Convert container to DynList.

std::vector< T >	to_vector () const
	Convert container to std::vector.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &op) const
	Fold the elements of the container to a specific result.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &&op=Op()) const
	Overload of foldl() that accepts rvalues.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &op) const
	Alias for foldl with the same accumulator type.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &&op=Op()) const
	Overload of fold_left() that accepts rvalues.

template<class Operation >
T	fold (const T &init, Operation &operation) const
	Simplified version of foldl() where the folded type is the same type of elements stored in the container.

template<class Operation >
T	fold (const T &init, Operation &&operation) const
	Overload of fold() that accepts rvalues.

template<class Operation >
Aleph::DynList< T >	filter (Operation &operation) const
	Filter the elements of a container according to a matching criterion.

template<class Operation >
Aleph::DynList< T >	filter (Operation &&operation) const
	Overload of filter() that accepts rvalues.

template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &operation) const
	Filter the elements of a container according to a matching criterion and return a pointer to the matched items in the container.

template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &&operation) const
	Overload of ptr_filter() that accepts rvalues.

template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &operation) const
	Filter the elements of a container according to a matching criterion and determine its positions respect to the traversal of container.

template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &&operation) const
	Overload of pfilter() that accepts rvalues.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &op) const
	Exclusive partition of container according to a filter criterion.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &&op) const
	Overload of partition() that accepts rvalues.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (size_t n) const
	Exclusive partition of container in the nth item.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	split_half () const
	Split the container into two halves by alternating elements.

template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &op) const
	Exclusive partition of container according to a filter criterion.

template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &&op) const
	Overload of tpartition() that accepts rvalues.

size_t	length () const noexcept
	Count the number of elements of a container.

Aleph::DynList< T >	rev () const
	Return a list with the elements of container in reverse order respect to its traversal order.

Aleph::DynList< T >	take (const size_t n) const
	Return a list with the first n elements seen in the container during its traversal.

Aleph::DynList< T >	take (size_t i, const size_t j, const size_t step=1) const
	Return a list with elements seen in the container between i and j position respect to its traversal.

Aleph::DynList< T >	drop (const size_t n) const
	Drop the first n elements seen in the container during its traversal.

void	mutable_drop (const size_t n)
	Drop the first n elements seen from container.

Public Member Functions inherited from GenericItems< Container, T >
Aleph::DynList< T >	items () const
	Return a list of all the elements of a container sorted by traversal order.

Aleph::DynList< T >	keys () const

Public Member Functions inherited from EqualToMethod< Container >
bool	equal_to (const Container &r) const noexcept
	Test if elements of `this` are exactly contained in another container.

bool	operator== (const Container &r) const noexcept

bool	operator!= (const Container &r) const noexcept
	Negation of equal_to()

Public Member Functions inherited from StlAlephIterator< SetName >
iterator	begin () noexcept
	Return an STL-compatible iterator to the first element.

iterator	end () noexcept
	Return an STL-compatible end iterator.

const_iterator	begin () const noexcept
	Return a const iterator to the first element.

const_iterator	end () const noexcept
	Return a const end iterator.

const_iterator	cbegin () const noexcept
	Return a const iterator to the first element.

const_iterator	cend () const noexcept
	Return a const end iterator.

Protected Types
using	Base = HashTable< Key, Cmp >

using	Bucket = typename HashTable< Key, Cmp >::Bucket

Protected Member Functions
Key *	insert_bucket (Bucket *bucket)

std::pair< Key *, bool >	search_or_insert_bucket (Bucket *bucket)

Static Protected Member Functions
static Bucket *	key_to_bucket (Key *key)

Private Member Functions
void	copy (const DynHashTable &other)

Additional Inherited Members
Related Symbols inherited from FunctionalMethods< Container, T >
	each

	each

	each

Detailed Description

template<typename Key, template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>
requires EqualityComparator<Cmp, Key>
class Aleph::DynHashTable< Key, HashTable, Cmp >

Self-adjusting dynamic hash table.

DynHashTable<Key> implements a linear, dynamic hash table where the user does not need to worry about the table size; it is automatically adjusted according to load-factor thresholds defined at construction time.

Parameters

Key	The domain type used to index the table.

See also: LinearHashTable

Definition at line 78 of file tpl_dynSetHash.H.

Member Typedef Documentation

◆ Base

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

using Aleph::DynHashTable< Key, HashTable, Cmp >::Base = HashTable<Key, Cmp>

protected

Definition at line 88 of file tpl_dynSetHash.H.

◆ Bucket

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

using Aleph::DynHashTable< Key, HashTable, Cmp >::Bucket = typename HashTable<Key, Cmp>::Bucket

protected

Definition at line 90 of file tpl_dynSetHash.H.

◆ Hash_Fct

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

using Aleph::DynHashTable< Key, HashTable, Cmp >::Hash_Fct = typename Base::Hash_Fct

Hash function type.

Definition at line 94 of file tpl_dynSetHash.H.

◆ Hash_Fct_Ptr

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

using Aleph::DynHashTable< Key, HashTable, Cmp >::Hash_Fct_Ptr = typename Base::Hash_Fct_Ptr

Definition at line 96 of file tpl_dynSetHash.H.

◆ Item_Type

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

using Aleph::DynHashTable< Key, HashTable, Cmp >::Item_Type = Key

Definition at line 100 of file tpl_dynSetHash.H.

◆ Key_Type

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

using Aleph::DynHashTable< Key, HashTable, Cmp >::Key_Type = Key

Definition at line 98 of file tpl_dynSetHash.H.

Constructor & Destructor Documentation

◆ DynHashTable() [1/7]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Aleph::DynHashTable< Key, HashTable, Cmp >::DynHashTable	(	size_t	len = `Primes::DefaultPrime`,
		Hash_Fct_Ptr	hash_fct = `Aleph::dft_hash_ptr_fct<Key>`,
		Cmp	cmp = `Cmp()`,
		float	lower_alpha = `hash_default_lower_alpha`,
		float	upper_alpha = `hash_default_upper_alpha`
	)

inline

Creates a dynamic linear hash table.

Parameters

[in]	hash_fct	Hash function.
	cmp	Key comparison functor.
[in]	len	Initial and minimum table size. The table will never shrink below this value.
[in]	lower_alpha	Lower load threshold; the table shrinks when the load factor goes below this value.
[in]	upper_alpha	Upper load threshold; the table grows when the load factor goes above this value.

Definition at line 113 of file tpl_dynSetHash.H.

◆ DynHashTable() [2/7]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Aleph::DynHashTable< Key, HashTable, Cmp >::DynHashTable	(	size_t	len,
		Hash_Fct	hash_fct,
		Cmp	cmp,
		float	lower_alpha,
		float	upper_alpha
	)

inline

Definition at line 123 of file tpl_dynSetHash.H.

◆ DynHashTable() [3/7]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Aleph::DynHashTable< Key, HashTable, Cmp >::DynHashTable ( const DynHashTable< Key, HashTable, Cmp > & other )

inline

Copy constructor.

Creates a copy with the same table size as the original. This preserves the performance characteristics and avoids the overhead of recalculating an optimal size.

Note: The copy will have the same table size (len) as the original, even if the original has been expanded and then shrunk through deletions. This may temporarily use more memory than strictly necessary, but the dynamic resizing will adjust the size automatically as elements are added or removed.; The const_cast on get_compare() is necessary because the base class's get_compare() method is not marked const. This is a limitation of the base HashTable class.

Definition at line 156 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::copy(), and Aleph::divide_and_conquer_partition_dp().

◆ DynHashTable() [4/7]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Aleph::DynHashTable< Key, HashTable, Cmp >::DynHashTable ( DynHashTable< Key, HashTable, Cmp > && other )

inlinenoexcept

Definition at line 164 of file tpl_dynSetHash.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::swap().

◆ DynHashTable() [5/7]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

template<template< typename > class List>

Aleph::DynHashTable< Key, HashTable, Cmp >::DynHashTable ( const List< Key > & l )

inline

Definition at line 171 of file tpl_dynSetHash.H.

◆ DynHashTable() [6/7]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

template<class It >

Aleph::DynHashTable< Key, HashTable, Cmp >::DynHashTable	(	It	b,
		It	e
	)

inline

Definition at line 171 of file tpl_dynSetHash.H.

◆ DynHashTable() [7/7]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Aleph::DynHashTable< Key, HashTable, Cmp >::DynHashTable ( std::initializer_list< Key > l )

inline

Definition at line 171 of file tpl_dynSetHash.H.

◆ ~DynHashTable()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Aleph::DynHashTable< Key, HashTable, Cmp >::~DynHashTable ( )

inline

Definition at line 173 of file tpl_dynSetHash.H.

Member Function Documentation

◆ add() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::add ( const Key & key )

inline

Definition at line 282 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::insert_bucket().

Referenced by TEST().

◆ add() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::add ( Key && key )

inline

Definition at line 287 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::insert_bucket().

◆ append() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::append ( const Key & key )

inline

Definition at line 292 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::insert_bucket().

Referenced by TEST().

◆ append() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::append ( Key && key )

inline

Definition at line 297 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::insert_bucket().

◆ clear()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

void Aleph::DynHashTable< Key, HashTable, Cmp >::clear ( )

inline

Empties the container.

Exceptions

none

See also: empty()

Definition at line 183 of file tpl_dynSetHash.H.

Referenced by TEST(), and TEST().

◆ contains()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

bool Aleph::DynHashTable< Key, HashTable, Cmp >::contains ( const Key & key ) const

inlinenoexcept

Return true if the key exists in the table.

Checks if a key exists in the table.

Parameters

[in] key key to search for.

Returns: true if key is present, false otherwise.

Exceptions

none

Definition at line 192 of file tpl_dynSetHash.H.

Referenced by demo_dynset_lhash(), demo_dynset_linhash(), demo_performance(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ contains_or_insert() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

std::pair< Key *, bool > Aleph::DynHashTable< Key, HashTable, Cmp >::contains_or_insert ( const Key & key )

inline

Definition at line 272 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::search_or_insert_bucket().

Referenced by TEST().

◆ contains_or_insert() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

std::pair< Key *, bool > Aleph::DynHashTable< Key, HashTable, Cmp >::contains_or_insert ( Key && key )

inline

Definition at line 277 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::search_or_insert_bucket().

◆ copy()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

void Aleph::DynHashTable< Key, HashTable, Cmp >::copy ( const DynHashTable< Key, HashTable, Cmp > & other )

inlineprivate

Definition at line 131 of file tpl_dynSetHash.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::DynHashTable< Key, HashTable, Cmp >::insert().

Referenced by Aleph::DynHashTable< Key, HashTable, Cmp >::DynHashTable(), and Aleph::DynHashTable< Key, HashTable, Cmp >::operator=().

◆ find() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key & Aleph::DynHashTable< Key, HashTable, Cmp >::find ( const Key & key )

inline

Definition at line 333 of file tpl_dynSetHash.H.

References ah_domain_error_if.

◆ find() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

const Key & Aleph::DynHashTable< Key, HashTable, Cmp >::find ( const Key & key ) const

inline

Definition at line 325 of file tpl_dynSetHash.H.

References ah_domain_error_if.

Referenced by TEST(), and TEST().

◆ get_first() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key & Aleph::DynHashTable< Key, HashTable, Cmp >::get_first ( )

inline

Definition at line 424 of file tpl_dynSetHash.H.

References LocateFunctions< Container, Type >::get_it().

◆ get_first() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

const Key & Aleph::DynHashTable< Key, HashTable, Cmp >::get_first ( ) const

inline

Definition at line 419 of file tpl_dynSetHash.H.

References LocateFunctions< Container, Type >::get_it().

Referenced by TEST().

◆ get_last() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key & Aleph::DynHashTable< Key, HashTable, Cmp >::get_last ( )

inline

Definition at line 436 of file tpl_dynSetHash.H.

References LocateFunctions< Container, Type >::get_it().

◆ get_last() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

const Key & Aleph::DynHashTable< Key, HashTable, Cmp >::get_last ( ) const

inline

Definition at line 429 of file tpl_dynSetHash.H.

References LocateFunctions< Container, Type >::get_it().

Referenced by TEST().

◆ has()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

bool Aleph::DynHashTable< Key, HashTable, Cmp >::has ( const Key & key ) const

inlinenoexcept

Checks if a key exists in the hash table.

Parameters

[in] key the key to check

Returns: true if the key exists, false otherwise

Definition at line 320 of file tpl_dynSetHash.H.

Referenced by TEST(), and TEST().

◆ insert() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::insert ( const Key & key )

inline

Inserts key into the hash set.

Returns a pointer to the stored key if it was inserted, or nullptr if the key was not inserted.

Definition at line 250 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::insert_bucket().

◆ insert() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::insert ( Key && key )

inline

Definition at line 255 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::insert_bucket().

◆ insert_bucket()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::insert_bucket ( Bucket * bucket )

inlineprotected

Definition at line 223 of file tpl_dynSetHash.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::DynHashTable< Key, HashTable, Cmp >::add(), Aleph::DynHashTable< Key, HashTable, Cmp >::add(), Aleph::DynHashTable< Key, HashTable, Cmp >::append(), Aleph::DynHashTable< Key, HashTable, Cmp >::append(), Aleph::DynHashTable< Key, HashTable, Cmp >::insert(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::insert(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::insert(), Aleph::DynHashTable< Key, HashTable, Cmp >::insert(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::insert(), and Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::insert().

◆ is_empty()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

bool Aleph::DynHashTable< Key, HashTable, Cmp >::is_empty ( ) const

inlinenoexcept

Checks if the container is empty.

Returns: true if empty, false otherwise.

Exceptions

none

Definition at line 199 of file tpl_dynSetHash.H.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ key_to_bucket()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

static Bucket * Aleph::DynHashTable< Key, HashTable, Cmp >::key_to_bucket ( Key * key )

inlinestaticprotected

Definition at line 343 of file tpl_dynSetHash.H.

References Aleph::divide_and_conquer_partition_dp(), and offset.

Referenced by Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::remove(), and Aleph::DynHashTable< Key, HashTable, Cmp >::remove().

◆ operator=() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

DynHashTable & Aleph::DynHashTable< Key, HashTable, Cmp >::operator= ( const DynHashTable< Key, HashTable, Cmp > & other )

inline

Definition at line 201 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::copy(), and Aleph::divide_and_conquer_partition_dp().

◆ operator=() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

DynHashTable & Aleph::DynHashTable< Key, HashTable, Cmp >::operator= ( DynHashTable< Key, HashTable, Cmp > && other )

inlinenoexcept

Definition at line 212 of file tpl_dynSetHash.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::swap().

◆ remove() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key Aleph::DynHashTable< Key, HashTable, Cmp >::remove ( const Key & key )

inline

Definition at line 373 of file tpl_dynSetHash.H.

References ah_domain_error_if, and Aleph::divide_and_conquer_partition_dp().

◆ remove() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

void Aleph::DynHashTable< Key, HashTable, Cmp >::remove ( Key * key )

inline

Removes a key from the hash table using its pointer.

Warning: The key pointer MUST be obtained from a previous call to insert() or search(). Passing any other pointer will result in undefined behavior and likely cause a segmentation fault.

This method uses pointer arithmetic to recover the bucket containing the key, which only works if the pointer truly points to a key stored inside the hash table.

Parameters

[in] key pointer to the key to remove (must come from insert/search)

See also: remove(const Key &) for a safer alternative that searches by value

Definition at line 366 of file tpl_dynSetHash.H.

References Aleph::DynHashTable< Key, HashTable, Cmp >::key_to_bucket().

Referenced by demo_dynset_lhash(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::remove(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::remove_by_data(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ search()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::search ( const Key & key ) const

inlinenoexcept

Searches for a key in the hash table.

Parameters

[in] key the key to search for

Returns: pointer to the key if found, nullptr otherwise

Note: This method is noexcept if the hash function and comparison function do not throw exceptions.

Definition at line 309 of file tpl_dynSetHash.H.

Referenced by Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::search(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::search(), TEST(), TEST(), and TEST().

◆ search_or_insert() [1/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::search_or_insert ( const Key & key )

inline

Definition at line 260 of file tpl_dynSetHash.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::DynHashTable< Key, HashTable, Cmp >::search_or_insert_bucket().

Referenced by Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::operator[](), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::operator[](), and TEST().

◆ search_or_insert() [2/2]

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

Key * Aleph::DynHashTable< Key, HashTable, Cmp >::search_or_insert ( Key && key )

inline

Definition at line 265 of file tpl_dynSetHash.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::DynHashTable< Key, HashTable, Cmp >::search_or_insert_bucket().

◆ search_or_insert_bucket()

template<typename Key , template< typename, class > class HashTable = LhashTable, class Cmp = Aleph::equal_to<Key>>

std::pair< Key *, bool > Aleph::DynHashTable< Key, HashTable, Cmp >::search_or_insert_bucket ( Bucket * bucket )

inlineprotected

Definition at line 235 of file tpl_dynSetHash.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::DynHashTable< Key, HashTable, Cmp >::contains_or_insert(), Aleph::DynHashTable< Key, HashTable, Cmp >::contains_or_insert(), Aleph::DynHashTable< Key, HashTable, Cmp >::search_or_insert(), and Aleph::DynHashTable< Key, HashTable, Cmp >::search_or_insert().

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

tpl_dynSetHash.H

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Private Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Base

◆ Bucket

◆ Hash_Fct

◆ Hash_Fct_Ptr

◆ Item_Type

◆ Key_Type

Constructor & Destructor Documentation

◆ DynHashTable() [1/7]

◆ DynHashTable() [2/7]

◆ DynHashTable() [3/7]

◆ DynHashTable() [4/7]

◆ DynHashTable() [5/7]

◆ DynHashTable() [6/7]

◆ DynHashTable() [7/7]

◆ ~DynHashTable()

Member Function Documentation

◆ add() [1/2]

◆ add() [2/2]

◆ append() [1/2]

◆ append() [2/2]

◆ clear()

◆ contains()

◆ contains_or_insert() [1/2]

◆ contains_or_insert() [2/2]

◆ copy()

◆ find() [1/2]

◆ find() [2/2]

◆ get_first() [1/2]

◆ get_first() [2/2]

◆ get_last() [1/2]

◆ get_last() [2/2]

◆ has()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_bucket()

◆ is_empty()

◆ key_to_bucket()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove() [1/2]

◆ remove() [2/2]

◆ search()

◆ search_or_insert() [1/2]

◆ search_or_insert() [2/2]

◆ search_or_insert_bucket()