Open addressing hash map for key-value pairs. More...

#include <tpl_dynMapOhash.H>

Inheritance diagram for Aleph::MapOpenHash< Key, Data, Cmp, HashTable >:

Collaboration diagram for Aleph::MapOpenHash< Key, Data, Cmp, HashTable >:

Public Types
using	Pair = std::pair< Key, Data >
	The key-value pair type stored in the map.

using	Base = HashTable< std::pair< Key, Data >, Dft_Pair_Cmp< Key, Data, Cmp > >
	The base hash table type.

using	Hash_Fct = std::function< size_t(const Key &)>
	Function type for hash functions.

using	Hash_Fct_Ptr = size_t(*)(const Key &)
	Function pointer type for hash functions.

using	Key_Type = Key
	The type of keys in the map.

using	Data_Type = Data
	The type of mapped values.

using	Value_Type = Data
	Alias for Data_Type (compatibility with other containers).

using	Item_Type = Pair
	The item type stored in the map (key-value pair).

using	Set_Type = MapOpenHash
	Self-reference type for generic programming.

using	Iterator = typename Base::Iterator
	Iterator type for traversing the map.

Public Member Functions
	MapOpenHash (size_t len=Primes::DefaultPrime, Hash_Fct_Ptr first_hash_fct=dft_hash_ptr_fct< Key >, Hash_Fct_Ptr second_hash_fct=snd_hash_ptr_fct< Key >, Cmp cmp=Cmp(), float lower_alpha=hash_default_lower_alpha, float upper_alpha=hash_default_upper_alpha, bool with_resize=true)
	Construct a map with specified parameters.

Pair *	insert (const Key &key, const Data &data)
	Insert a key-value pair (copy semantics).

Pair *	insert (const Key &key, Data &&data)
	Insert a key-value pair (move data).

Pair *	insert (Key &&key, Data &&data)
	Insert a key-value pair (move both).

Pair *	insert (Key &&key, const Data &data)
	Insert a key-value pair (move key, copy data).

Pair *	search (const Key &key) const noexcept
	Search for a key in the map.

Pair *	search (Key &&key) const noexcept
	Search for a key in the map (move semantics).

bool	has (const Key &key) const noexcept
	Check if a key exists in the map.

bool	has (Key &&key) const noexcept
	Check if a key exists in the map (move semantics).

bool	contains (const Key &key) const noexcept
	Check if a key exists in the map.

bool	contains (Key &&key) const noexcept
	Check if a key exists in the map (move semantics).

Data &	find (const Key &key)
	Find and return the value for a key.

Data &	find (Key &&key)
	Find and return the value for a key (move semantics).

const Data &	find (const Key &key) const
	Find and return the value for a key (const).

const Data &	find (Key &&key) const
	Find and return the value for a key (const, move).

Data &	operator[] (const Key &key)
	Access or insert a value by key.

const Data &	operator[] (const Key &key) const
	Access value by key (const version).

Data &	operator[] (Key &&key)
	Access or insert a value by key (move semantics).

const Data &	operator[] (Key &&key) const
	Access value by key (const, move).

void	remove_by_data (Data &data)
	Remove an entry by its data pointer.

void	remove (const Key &key)
	Remove an entry by key.

void	remove (Key &&key)
	Remove an entry by key (move semantics).

DynList< Key >	keys () const
	Get a list of all keys in the map.

DynList< Data >	values () const
	Get a list of all values in the map.

DynList< Data * >	values_ptr ()
	Get a list of pointers to all values.

DynList< Pair * >	items_ptr ()
	Get a list of pointers to all pairs.

Static Public Member Functions
static Pair *	key_to_pair (Key *ptr) noexcept
	Convert a key pointer to its containing pair pointer.

static const Pair *	key_to_pair (const Key *ptr) noexcept

static Pair *	data_to_pair (Data *ptr) noexcept
	Convert a data pointer to its containing pair pointer.

static const Pair *	data_to_pair (const Data *ptr) noexcept

static Data &	get_data (Key &key) noexcept
	Get the data associated with a key by reference.

static const Data &	get_data (const Key &key) noexcept

static const Key &	get_key (Data *data_ptr) noexcept
	Get the key associated with a data pointer.

static const Key &	get_key (const Data *data_ptr) noexcept

Detailed Description

template<typename Key, typename Data, class Cmp = Aleph::equal_to<Key>, template< typename, class > class HashTable = ODhashTable>
requires EqualityComparator<Cmp, Key>
struct Aleph::MapOpenHash< Key, Data, Cmp, HashTable >

Open addressing hash map for key-value pairs.

MapOpenHash<Key, Data, Cmp, HashTable> implements an associative container that maps keys to values using open addressing hash tables. It provides O(1) average-case complexity for insert, search, and delete operations.

Features

Open addressing: Uses either linear probing (OLhashTable) or double hashing (ODhashTable) for collision resolution
Automatic resizing: Table grows/shrinks based on load factor thresholds
STL-compatible interface: Supports operator[], find(), contains(), etc.
Functional interface: Inherits traverse(), maps(), filter(), foldl(), etc.

Example Usage

// Create a map with string keys and int values
MapODhash<std::string, int> ages;
 
// Insert elements
ages.insert("Alice", 30);
ages["Bob"] = 25;
 
// Search and access
if (ages.has("Alice"))
  std::cout << "Alice's age: " << ages["Alice"] << '\n';
 
// Iterate
ages.traverse([](auto& pair) {
  std::cout << pair.first << ": " << pair.second << '\n';
  return true;
});
 
// Remove
ages.remove("Bob");

Hash Table Variants

MapODhash: Uses double hashing (better distribution, more complex)
MapOLhash: Uses linear probing (simpler, better cache locality)

Thread Safety

This class is not thread-safe. External synchronization is required for concurrent access from multiple threads.

Template Parameters

Key	Type of keys. Must be hashable and equality-comparable.
Data	Type of mapped values.
Cmp	Equality comparator for keys (default: Aleph::equal_to<Key>).
HashTable	Underlying hash table type (default: ODhashTable).

See also: MapODhash Double hashing variant; MapOLhash Linear probing variant; ODhashTable Underlying double hashing table; OLhashTable Underlying linear probing table

Definition at line 117 of file tpl_dynMapOhash.H.

Member Typedef Documentation

◆ Base

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Base = HashTable<std::pair<Key, Data>, Dft_Pair_Cmp<Key, Data, Cmp> >

The base hash table type.

Definition at line 123 of file tpl_dynMapOhash.H.

◆ Data_Type

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Data_Type = Data

The type of mapped values.

Definition at line 142 of file tpl_dynMapOhash.H.

◆ Hash_Fct

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Hash_Fct = std::function<size_t(const Key &)>

Function type for hash functions.

Definition at line 133 of file tpl_dynMapOhash.H.

◆ Hash_Fct_Ptr

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Hash_Fct_Ptr = size_t (*)(const Key &)

Function pointer type for hash functions.

Definition at line 136 of file tpl_dynMapOhash.H.

◆ Item_Type

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Item_Type = Pair

The item type stored in the map (key-value pair).

Definition at line 148 of file tpl_dynMapOhash.H.

◆ Iterator

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Iterator = typename Base::Iterator

Iterator type for traversing the map.

Definition at line 528 of file tpl_dynMapOhash.H.

◆ Key_Type

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Key_Type = Key

The type of keys in the map.

Definition at line 139 of file tpl_dynMapOhash.H.

◆ Pair

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Pair = std::pair<Key, Data>

The key-value pair type stored in the map.

Definition at line 120 of file tpl_dynMapOhash.H.

◆ Set_Type

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Set_Type = MapOpenHash

Self-reference type for generic programming.

Definition at line 151 of file tpl_dynMapOhash.H.

◆ Value_Type

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

using Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::Value_Type = Data

Alias for Data_Type (compatibility with other containers).

Definition at line 145 of file tpl_dynMapOhash.H.

Constructor & Destructor Documentation

◆ MapOpenHash()

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

Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::MapOpenHash	(	size_t	len = `Primes::DefaultPrime`,
		Hash_Fct_Ptr	first_hash_fct = `dft_hash_ptr_fct<Key>`,
		Hash_Fct_Ptr	second_hash_fct = `snd_hash_ptr_fct<Key>`,
		Cmp	cmp = `Cmp()`,
		float	lower_alpha = `hash_default_lower_alpha`,
		float	upper_alpha = `hash_default_upper_alpha`,
		bool	with_resize = `true`
	)

inline

Construct a map with specified parameters.

Parameters

[in]	len	Initial table size (default: DefaultPrime).
[in]	first_hash_fct	Primary hash function.
[in]	second_hash_fct	Secondary hash function (for double hashing).
[in]	cmp	Equality comparator for keys.
[in]	lower_alpha	Lower load factor threshold for shrinking.
[in]	upper_alpha	Upper load factor threshold for growing.
[in]	with_resize	Enable automatic resizing.

Exceptions

std::bad_alloc If memory allocation fails.

Definition at line 165 of file tpl_dynMapOhash.H.

Member Function Documentation

◆ contains() [1/2]

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

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

inlinenoexcept

Check if a key exists in the map.

Alias for has().

Parameters

[in] key The key to check.

Returns: true if the key exists, false otherwise.

Definition at line 363 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::has().

◆ contains() [2/2]

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

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

inlinenoexcept

Check if a key exists in the map (move semantics).

Parameters

[in] key The key to check.

Returns: true if the key exists, false otherwise.

Definition at line 373 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::has().

◆ data_to_pair() [1/2]

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

static const Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::data_to_pair ( const Data * ptr )

inlinestaticnoexcept

Definition at line 217 of file tpl_dynMapOhash.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ data_to_pair() [2/2]

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

static Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::data_to_pair ( Data * ptr )

inlinestaticnoexcept

Convert a data pointer to its containing pair pointer.

Given a pointer to the data (second) member of a pair, returns a pointer to the enclosing pair.

Parameters

[in] ptr Pointer to data within a pair.

Returns: Pointer to the containing pair.

Warning: Only valid for pointers obtained from pairs in this map.

Definition at line 212 of file tpl_dynMapOhash.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::get_key(), Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::get_key(), and Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::remove_by_data().

◆ find() [1/4]

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

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

inline

Find and return the value for a key.

Parameters

[in] key The key to find.

Returns: Reference to the associated value.

Exceptions

std::domain_error If the key is not found.

Definition at line 385 of file tpl_dynMapOhash.H.

Referenced by Aleph::Gen_Mo_On_Trees< GT, Policy >::build(), Aleph::Gen_Mo_On_Tree_Node< T, Policy >::build(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::index_nodes(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::index_nodes(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes(), Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::operator[](), and Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::operator[]().

◆ find() [2/4]

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

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

inline

Find and return the value for a key (const).

Parameters

[in] key The key to find.

Returns: Const reference to the associated value.

Exceptions

std::domain_error If the key is not found.

Definition at line 413 of file tpl_dynMapOhash.H.

◆ find() [3/4]

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

Data & Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::find ( Key && key )

inline

Find and return the value for a key (move semantics).

Parameters

[in] key The key to find.

Returns: Reference to the associated value.

Exceptions

std::domain_error If the key is not found.

Definition at line 399 of file tpl_dynMapOhash.H.

◆ find() [4/4]

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

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

inline

Find and return the value for a key (const, move).

Parameters

[in] key The key to find.

Returns: Const reference to the associated value.

Exceptions

std::domain_error If the key is not found.

Definition at line 427 of file tpl_dynMapOhash.H.

◆ get_data() [1/2]

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

static const Data & Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::get_data ( const Key & key )

inlinestaticnoexcept

Definition at line 238 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::key_to_pair().

◆ get_data() [2/2]

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

static Data & Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::get_data ( Key & key )

inlinestaticnoexcept

Get the data associated with a key by reference.

Given a reference to a key that is stored in the map, returns a reference to its associated data.

Parameters

[in] key Reference to a key within a stored pair.

Returns: Reference to the associated data.

Warning: Only valid for keys obtained from pairs in this map.

Definition at line 233 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::key_to_pair().

◆ get_key() [1/2]

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

static const Key & Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::get_key ( const Data * data_ptr )

inlinestaticnoexcept

Definition at line 258 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::data_to_pair().

◆ get_key() [2/2]

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

static const Key & Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::get_key ( Data * data_ptr )

inlinestaticnoexcept

Get the key associated with a data pointer.

Given a pointer to data stored in the map, returns a reference to its associated key.

Parameters

[in] data_ptr Pointer to data within a stored pair.

Returns: Reference to the associated key.

Warning: Only valid for data pointers obtained from this map.

Definition at line 253 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::data_to_pair().

◆ has() [1/2]

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

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

inlinenoexcept

Check if a key exists in the map.

Parameters

[in] key The key to check.

Returns: true if the key exists, false otherwise.

Definition at line 341 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::search().

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

◆ has() [2/2]

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

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

inlinenoexcept

Check if a key exists in the map (move semantics).

Parameters

[in] key The key to check.

Returns: true if the key exists, false otherwise.

Definition at line 351 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::search().

◆ insert() [1/4]

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

Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::insert	(	const Key &	key,
		const Data &	data
	)

inline

Insert a key-value pair (copy semantics).

Inserts a new key-value pair into the map. If the key already exists, no insertion occurs.

Parameters

[in]	key	The key to insert.
[in]	data	The value to associate with the key.

Returns: Pointer to the inserted pair, or nullptr if key exists.

Exceptions

std::bad_alloc If memory allocation fails during resize.

Definition at line 274 of file tpl_dynMapOhash.H.

Referenced by Aleph::Gen_Mo_On_Trees< GT, Policy >::build(), Aleph::Gen_Mo_On_Tree_Node< T, Policy >::build(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::index_nodes(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::index_nodes(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::index_nodes(), MapODhashTest::populate_int_map(), MapODhashTest::populate_map(), MapOLhashTest::populate_map(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ insert() [2/4]

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

Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::insert	(	const Key &	key,
		Data &&	data
	)

inline

Insert a key-value pair (move data).

Parameters

[in]	key	The key to insert.
[in]	data	The value to move into the map.

Returns: Pointer to the inserted pair, or nullptr if key exists.

Definition at line 285 of file tpl_dynMapOhash.H.

◆ insert() [3/4]

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

Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::insert	(	Key &&	key,
		const Data &	data
	)

inline

Insert a key-value pair (move key, copy data).

Parameters

[in]	key	The key to move into the map.
[in]	data	The value to copy into the map.

Returns: Pointer to the inserted pair, or nullptr if key exists.

Definition at line 307 of file tpl_dynMapOhash.H.

◆ insert() [4/4]

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

Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::insert	(	Key &&	key,
		Data &&	data
	)

inline

Insert a key-value pair (move both).

Parameters

[in]	key	The key to move into the map.
[in]	data	The value to move into the map.

Returns: Pointer to the inserted pair, or nullptr if key exists.

Definition at line 296 of file tpl_dynMapOhash.H.

◆ items_ptr()

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

DynList< Pair * > Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::items_ptr ( )

inline

Get a list of pointers to all pairs.

Returns: DynList containing pointers to all pairs in the map.

Note: The pointers remain valid until the map is modified.

Definition at line 574 of file tpl_dynMapOhash.H.

References Aleph::DynList< T >::append(), and Aleph::blossom_maximum_cardinality_matching().

◆ key_to_pair() [1/2]

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

static const Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::key_to_pair ( const Key * ptr )

inlinestaticnoexcept

Definition at line 197 of file tpl_dynMapOhash.H.

◆ key_to_pair() [2/2]

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

static Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::key_to_pair ( Key * ptr )

inlinestaticnoexcept

Convert a key pointer to its containing pair pointer.

Given a pointer to the key member of a pair, returns a pointer to the enclosing pair. This relies on the fact that the key is the first member of std::pair.

Parameters

[in] ptr Pointer to a key within a pair.

Returns: Pointer to the containing pair.

Warning: Only valid for pointers obtained from pairs in this map.

Definition at line 192 of file tpl_dynMapOhash.H.

Referenced by Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::get_data(), and Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::get_data().

◆ keys()

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

DynList< Key > Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::keys ( ) const

inline

Get a list of all keys in the map.

Returns: DynList containing copies of all keys.

Definition at line 534 of file tpl_dynMapOhash.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator[]() [1/4]

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

Data & Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::operator[] ( const Key & key )

inline

Access or insert a value by key.

If the key exists, returns a reference to its value. If not, inserts a new pair with default-constructed value and returns a reference to it.

Parameters

[in] key The key to access or insert.

Returns: Reference to the value associated with the key.

Exceptions

std::bad_alloc If insertion requires memory allocation.

Definition at line 445 of file tpl_dynMapOhash.H.

◆ operator[]() [2/4]

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

const Data & Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::operator[] ( const Key & key ) const

inline

Access value by key (const version).

Parameters

[in] key The key to access.

Returns: Const reference to the value.

Exceptions

std::domain_error If the key is not found.

Definition at line 459 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::find().

◆ operator[]() [3/4]

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

Data & Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::operator[] ( Key && key )

inline

Access or insert a value by key (move semantics).

Parameters

[in] key The key to access or insert.

Returns: Reference to the value associated with the key.

Definition at line 469 of file tpl_dynMapOhash.H.

◆ operator[]() [4/4]

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

const Data & Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::operator[] ( Key && key ) const

inline

Access value by key (const, move).

Parameters

[in] key The key to access.

Returns: Const reference to the value.

Exceptions

std::domain_error If the key is not found.

Definition at line 483 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::find().

◆ remove() [1/2]

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

void Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::remove ( const Key & key )

inline

Remove an entry by key.

Parameters

[in] key The key to remove.

Exceptions

std::domain_error If the key is not found.

Definition at line 507 of file tpl_dynMapOhash.H.

Referenced by TEST(), and TEST().

◆ remove() [2/2]

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

void Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::remove ( Key && key )

inline

Remove an entry by key (move semantics).

Parameters

[in] key The key to remove.

Exceptions

std::domain_error If the key is not found.

Definition at line 520 of file tpl_dynMapOhash.H.

◆ remove_by_data()

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

void Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::remove_by_data ( Data & data )

inline

Remove an entry by its data pointer.

Removes the key-value pair that contains the given data pointer.

Parameters

[in] data Reference to data within a stored pair.

Warning: Only valid for data references obtained from this map.

Definition at line 496 of file tpl_dynMapOhash.H.

References Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::data_to_pair().

◆ search() [1/2]

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

Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::search ( const Key & key ) const

inlinenoexcept

Search for a key in the map.

Parameters

[in] key The key to search for.

Returns: Pointer to the pair if found, nullptr otherwise.

Definition at line 317 of file tpl_dynMapOhash.H.

Referenced by Aleph::Gen_Mo_On_Trees< GT, Policy >::build(), Aleph::Gen_Mo_On_Tree_Node< T, Policy >::build(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_adjacency(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::build_simple_adjacency(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::build_simple_adjacency(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency(), Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::has(), Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::has(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::id_of(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::id_of(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_of(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::id_of(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::index_nodes(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::index_nodes(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::index_nodes(), Aleph::Gen_Mo_On_Trees< GT, Policy >::path_solve(), Aleph::Gen_Mo_On_Tree_Node< T, Policy >::path_solve(), Aleph::Gen_Mo_On_Trees< GT, Policy >::subtree_solve(), and Aleph::Gen_Mo_On_Tree_Node< T, Policy >::subtree_solve().

◆ search() [2/2]

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

Pair * Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::search ( Key && key ) const

inlinenoexcept

Search for a key in the map (move semantics).

Parameters

[in] key The key to search for.

Returns: Pointer to the pair if found, nullptr otherwise.

Definition at line 329 of file tpl_dynMapOhash.H.

◆ values()

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

DynList< Data > Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::values ( ) const

inline

Get a list of all values in the map.

Returns: DynList containing copies of all values.

Definition at line 546 of file tpl_dynMapOhash.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ values_ptr()

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

DynList< Data * > Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::values_ptr ( )

inline

Get a list of pointers to all values.

Returns: DynList containing pointers to all values in the map.

Note: The pointers remain valid until the map is modified.

Definition at line 560 of file tpl_dynMapOhash.H.

References Aleph::DynList< T >::append(), and Aleph::blossom_maximum_cardinality_matching().

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

tpl_dynMapOhash.H

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Features

Example Usage

Hash Table Variants

Thread Safety

Member Typedef Documentation

◆ Base

◆ Data_Type

◆ Hash_Fct

◆ Hash_Fct_Ptr

◆ Item_Type

◆ Iterator

◆ Key_Type

◆ Pair

◆ Set_Type

◆ Value_Type

Constructor & Destructor Documentation

◆ MapOpenHash()

Member Function Documentation

◆ contains() [1/2]

◆ contains() [2/2]

◆ data_to_pair() [1/2]

◆ data_to_pair() [2/2]

◆ find() [1/4]

◆ find() [2/4]

◆ find() [3/4]

◆ find() [4/4]

◆ get_data() [1/2]

◆ get_data() [2/2]

◆ get_key() [1/2]

◆ get_key() [2/2]

◆ has() [1/2]

◆ has() [2/2]

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ items_ptr()

◆ key_to_pair() [1/2]

◆ key_to_pair() [2/2]

◆ keys()

◆ operator[]() [1/4]

◆ operator[]() [2/4]

◆ operator[]() [3/4]

◆ operator[]() [4/4]

◆ remove() [1/2]

◆ remove() [2/2]

◆ remove_by_data()

◆ search() [1/2]

◆ search() [2/2]

◆ values()

◆ values_ptr()