The class for generic Hash Tables. More...

#include <agrum/base/core/hashTable.h>

Collaboration diagram for gum::HashTable< Key, Val >:

Public Types
using	Bucket = HashTableBucket< Key, Val >
	The buckets where data are stored.

using	key_type = Key
	Types for STL compliance.
using	mapped_type = Val
	Types for STL compliance.
using	value_type = std::pair< const Key, Val >
	Types for STL compliance.
using	reference = value_type&
	Types for STL compliance.
using	const_reference = const value_type&
	Types for STL compliance.
using	pointer = value_type*
	Types for STL compliance.
using	const_pointer = const value_type*
	Types for STL compliance.
using	size_type = Size
	Types for STL compliance.
using	difference_type = std::ptrdiff_t
	Types for STL compliance.
using	iterator = HashTableIterator< Key, Val >
	Types for STL compliance.
using	const_iterator = HashTableConstIterator< Key, Val >
	Types for STL compliance.
using	iterator_safe = HashTableIteratorSafe< Key, Val >
	Types for STL compliance.
using	const_iterator_safe = HashTableConstIteratorSafe< Key, Val >
	Types for STL compliance.

Public Member Functions
Constructors / Destructors
	HashTable (Size size_param=HashTableConst::default_size, bool resize_pol=HashTableConst::default_resize_policy, bool key_uniqueness_pol=HashTableConst::default_uniqueness_policy)
	Default constructor.
	HashTable (std::initializer_list< std::pair< Key, Val > > list)
	Initializer list constructor.
	HashTable (const HashTable< Key, Val > &from)
	Copy constructor.
	HashTable (HashTable< Key, Val > &&from) noexcept
	Move constructor.
	~HashTable ()
	Class destructor.
Iterators
const iterator &	end () noexcept
	Returns the unsafe iterator pointing to the end of the hashtable.
const const_iterator &	end () const noexcept
	Returns the unsafe const_iterator pointing to the end of the hashtable.
const const_iterator &	cend () const noexcept
	Returns the unsafe const_iterator pointing to the end of the hashtable.
iterator	begin ()
	Returns an unsafe iterator pointing to the beginning of the hashtable.
const_iterator	begin () const
	Returns an unsafe const_iterator pointing to the beginning of the hashtable.
const_iterator	cbegin () const
	Returns an unsafe const_iterator pointing to the beginning of the hashtable.
const iterator_safe &	endSafe () noexcept
	Returns the safe iterator pointing to the end of the hashtable.
const const_iterator_safe &	endSafe () const noexcept
	Returns the safe const_iterator pointing to the end of the hashtable.
const const_iterator_safe &	cendSafe () const noexcept
	Returns the safe const_iterator pointing to the end of the hashtable.
iterator_safe	beginSafe ()
	Returns the safe iterator pointing to the beginning of the hashtable.
const_iterator_safe	beginSafe () const
	Returns the safe const_iterator pointing to the beginning of the hashtable.
const_iterator_safe	cbeginSafe () const
	Returns the safe const_iterator pointing to the beginning of the hashtable.
Operators
HashTable< Key, Val > &	operator= (const HashTable< Key, Val > &from)
	Copy operator.
HashTable< Key, Val > &	operator= (HashTable< Key, Val > &&from) noexcept
	Move operator.
Val &	operator[] (const Key &key)
	Returns a reference on the value the key of which is passed in argument.
const Val &	operator[] (const Key &key) const
	returns a reference on the value the key of which is passed in argument
template<typename K>
Val &	operator[] (const K &key)
	Heterogeneous lookup: operator[] without string allocation (accepts string_view, const char*, etc.).
template<typename K>
const Val &	operator[] (const K &key) const
	Heterogeneous lookup: operator[] const without string allocation.
bool	operator== (const HashTable< Key, Val > &from) const
	Checks whether two hashtables contain the same elements.
Fine tuning
Size	capacity () const noexcept
	Returns the number of slots in the 'nodes' vector of the hashtable.
void	resize (Size new_size)
	Changes the number of slots in the 'nodes' vector of the hash table.
void	setResizePolicy (const bool new_policy) noexcept
	Enables the user to change dynamically the resizing policy.
bool	resizePolicy () const noexcept
	Returns the current resizing policy.
void	setKeyUniquenessPolicy (const bool new_policy) noexcept
	Enables the user to change dynamically the policy for checking whether there can exist several elements in the table with identical keys.
bool	keyUniquenessPolicy () const noexcept
	Returns the current checking policy.
Accessors / Modifiers
Size	size () const noexcept
	Returns the number of elements stored into the hashtable.
bool	exists (const Key &key) const
	Checks whether there exists an element with a given key in the hashtable.
template<typename K>
bool	exists (const K &key) const
	Heterogeneous lookup: exists() without string allocation (accepts string_view, const char*, etc.).
optional_ref< Val >	tryGet (const Key &key)
	Returns a pointer to the value associated with a given key, or nullptr if the key does not exist.
optional_ref< const Val >	tryGet (const Key &key) const
	Returns a pointer to the value associated with a given key, or nullptr if the key does not exist.
template<typename K>
optional_ref< Val >	tryGet (const K &key)
	Heterogeneous lookup: tryGet() without string allocation (accepts string_view, const char*, etc.).
template<typename K>
optional_ref< const Val >	tryGet (const K &key) const
	Heterogeneous lookup: tryGet() const without string allocation.
value_type &	insert (const Key &key, const Val &val)
	Adds a new element (actually a copy of this element) into the hash table.
value_type &	insert (Key &&key, Val &&val)
	Moves a new element in the hash table.
value_type &	insert (const std::pair< Key, Val > &elt)
	Adds a new element (actually a copy of this element) into the hash table.
value_type &	insert (std::pair< Key, Val > &&elt)
	Moves a new element in the hash table.
template<typename... Args>
value_type &	emplace (Args &&... args)
	Emplace a new element into the hashTable.
mapped_type &	getWithDefault (const Key &key, const Val &default_value)
	Returns a reference on the element the key of which is passed in argument.
mapped_type &	getWithDefault (Key &&key, Val &&default_value)
	Returns a reference on the element the key of which is passed in argument.
void	set (const Key &key, const Val &default_value)
	Add a new property or modify it if it already existed.
void	reset (const Key &key)
	Removes a property (i.e., remove an element).
void	erase (const Key &key)
	Removes a given element from the hash table.
template<typename K>
void	erase (const K &key)
	Heterogeneous lookup: erase() without string allocation (accepts string_view, const char*, etc.).
void	erase (const iterator_safe &iter)
	Removes a given element from the hash table.
void	erase (const const_iterator_safe &iter)
	Removes a given element from the hash table.
void	eraseByVal (const Val &val)
	Removes a given element from the hash table.
const Key &	keyByVal (const Val &val) const
	Returns a reference on the key given a value.
const Key &	key (const Key &key) const
	Returns a reference on a given key.
optional_ref< const Key >	tryGetKey (const Key &key) const
	Returns an optional reference to a given key, or nullptr if the hash table does not contain it.
void	eraseAllVal (const Val &val)
	Removes all the elements having a certain value from the hash table.
void	clear ()
	Removes all the elements in the hash table.
bool	empty () const noexcept
	Indicates whether the hash table is empty.
template<typename Mount>
HashTable< Key, Mount >	map (Mount(*f)(Val), Size size=Size(0), bool resize_pol=HashTableConst::default_resize_policy, bool key_uniqueness_pol=HashTableConst::default_uniqueness_policy) const
	Transforms a hashtable of vals into a hashtable of mountains.
template<typename Mount>
HashTable< Key, Mount >	map (Mount(*f)(Val &), Size size=Size(0), bool resize_pol=HashTableConst::default_resize_policy, bool key_uniqueness_pol=HashTableConst::default_uniqueness_policy) const
	Transforms a hashtable of vals into a hashtable of mountains.
template<typename Mount>
HashTable< Key, Mount >	map (Mount(*f)(const Val &), Size size=Size(0), bool resize_pol=HashTableConst::default_resize_policy, bool key_uniqueness_pol=HashTableConst::default_uniqueness_policy) const
	Transforms a hashtable of vals into a hashtable of mountains.
template<typename Mount>
HashTable< Key, Mount >	map (const Mount &val, Size size=Size(0), bool resize_pol=HashTableConst::default_resize_policy, bool key_uniqueness_pol=HashTableConst::default_uniqueness_policy) const
	Creates a hashtable of mounts with a given value from a hashtable of vals.

Private Member Functions
void	_erase_ (HashTableBucket< Key, Val > *bucket, Size index)
	Erases a given bucket.
void	_copy_ (const HashTable< Key, Val > &table)
	A function used to perform copies of HashTables.
void	_create_ (Size size)
	Used by all default constructors (general and specialized).
void	_clearIterators_ ()
	Clear all the safe iterators.
void	_insert_ (Bucket *bucket)
	Adds a new element (actually a copy of this element) in the hash table.

Private Attributes
std::vector< HashTableList< Key, Val > >	_nodes_
	The hash table is represented as a vector of chained lists.
Size	_size_
	The number of nodes in vector ' __nodes'.
Size	_nb_elements_ {Size(0)}
	Number of elements of type Val stored in the hash table.
HashFunc< Key >	_hash_func_
	The function used to hash keys (may change when the table is resized).
bool	_resize_policy_ {true}
	Is resizing performed automatically?
bool	_key_uniqueness_policy_ {true}
	Shall we check for key uniqueness in the table?
Size	_begin_index_ {std::numeric_limits< Size >::max()}
	Returns where the begin index should be.
std::vector< HashTableConstIteratorSafe< Key, Val > * >	_safe_iterators_
	The list of safe iterators pointing to the hash table.

Friends

class	HashTableIterator< Key, Val >
	Friends to optimize the access to data, iterators must be friends.
class	HashTableConstIterator< Key, Val >
	Friends to optimize the access to data, iterators must be friends.
class	HashTableIteratorSafe< Key, Val >
	Friends to optimize the access to data, iterators must be friends.
class	HashTableConstIteratorSafe< Key, Val >
	Friends to optimize the access to data, iterators must be friends.
template<typename T1, typename T2>
class	Bijection
	For bijections to quickly access data.
std::ostream &	operator<< (std::ostream &s, const HashTable< Key, Val > &table)
	Prints the content of a gum::HashTable in the stream.
std::ostream &	operator<< (std::ostream &s, const HashTable< Key *, Val > &table)
	Prints the content of a gum::HashTable with pointers key in the stream.

Detailed Description

template<typename Key, typename Val>
class gum::HashTable< Key, Val >

The class for generic Hash Tables.

In aGrUM, a hashtable is a vector of chained lists (collision problems are fixed by chaining). Each slot of the vector contains a list of elements sharing the same hashed value. To be computationally efficient, the hash table should not contain too many elements as compared to its number of slots. Therefore, it is sometimes useful to resize the chained lists vector. aGrUM's hash tables are designed to automatically double their size when there is in average more than 3 elements per slot. However, when memory consumption is a concern, this feature can be turned off either by passing false as an optional resize_pol argument to the constructor of the hash table or by using method setResizePolicy when the instance of the class has already been constructed. Similarly, the default number of slots of the hash table may be parameterized as an optional argument of the constructor (size_param). Beware: when inserting elements of a given class into a hash table, unless the element is an r-value, only a copy of this element is stored into the table (this is compulsory if the hashtable is to be generic and can be used to store both complex classes and built-in types like integers). HashTable have different kinds of iterators: HashTableIteratorSafe and HashTableConstIteratorSafe (a.k.a. HashTable<>::iterator_safe and HashTable<>::const_iterator_safe) allow safe parsing of the hash tables. By safe, we mean that whenever the element pointed to by such an iterator is removed from the hashtable, accessing it through the iterator (*iter) does not result in a segmentation fault but rather in an exception being thrown. This safety is ensured at a very low cost (actually, our experiments show that our HashTables and HashTable's safe iterators significantly outperform the standard library unordered_maps). Of course, if there is no possibility for an iterator to point to a deleted element, the user can use "unsafe" iterators HashTableIterator and HashTableConstIterator (a.k.a. HashTable<>::iterator and HashTable<>::const_iterator). These iterators are slightly faster than their safe counterparts. However, as in the standard library, accessing through them a deleted element usually results in a mess (most probably a segfault).

Warning: HashTables guarantee that any element stored within them will have the same location in memory until it is removed from the hashtable (and this holds whatever operation is performed on the hashtable like new insertions, deletions, resizing, etc.).

Usage example:: // creation of an empty hash table

HashTable<int,string> table1;

// insert two elements into the hash table

table1.insert (10,"xxx");

table1.insert (20,"yyy");

table1.emplace (30,"zzz");

// creation of a nonempty hashtable using initializer lists

HashTable<int,bool> table { std::make_pair(3,true), std::make_pair(2,false)

};

// display the content of the hash table

cerr << table1;

// get the number of elements stored into the hash table

cerr << "number of elements in table1 = " << table1.size () << endl;

// create two copies of the hash table

HashTable<int,string> table2, table3 = table1;

table2 = table3;

// get the element whose key is 10

cerr << table1[10] << " = xxx" << endl;

// check whether there exists an element with key 20

if (table1.exists (20)) cerr << "element found" << endl;

// transform the hashtable of string into a hashtable of int assuming f is

// defined as: int f (const string& str) { return str.size (); }

HashTable<int,int> table = table1.map (f);

// remove two elements from table1 and table2

table1.erase (10); // key = 10

table1.eraseByVal ("yyy"); // val = "yyy"

table2.clear ();

// check whether the hash table is empty

if (!table1.empty ()) cerr << "table not empty" << endl;

// check whether hashtables contain the same elements

if ((table1 == table2) && (table1 != table3))

cerr << "check for equality/inequality" << endl;

// parse the content of a hashtable using an unsafe iterator

for (HashTable<int,string>::const_iterator iter = table1.cbegin();

iter != table1.cend(); ++iter)

cerr << *iter;

HashTable<int,string>::iterator iter = table1.begin();

iter += 2;

cerr << iter.key () << " " << iter.val ();

// use an iterator to point the element we wish to erase

HashTable<int,string>::iterator_safe iterS = table1.beginSafe ();

table1.erase ( table1.beginSafe () + 4 );

table1.erase ( iterS ); // this is safe because the iterator is safe

// check for iterator's safety

for (HashTable<int,string>::iterator_safe iter = table1.beginSafe ();

iter != table1.endSafe (); ++iter )

table1.eraseByVal ( *iter );

gum::HashTable
The class for generic Hash Tables.
Definition hashTable.h:640

gum::HashTable::iterator
HashTableIterator< Key, Val > iterator
Types for STL compliance.
Definition hashTable.h:653

gum::HashTable::insert
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
Definition hashTable_tpl.h:754

gum::HashTable::clear
void clear()
Removes all the elements in the hash table.
Definition hashTable_tpl.h:379

gum::HashTable::emplace
value_type & emplace(Args &&... args)
Emplace a new element into the hashTable.
Definition hashTable_tpl.h:787

gum::HashTable::size
Size size() const noexcept
Returns the number of elements stored into the hashtable.
Definition hashTable_tpl.h:581

gum::HashTable::map
HashTable< Key, Mount > map(Mount(*f)(Val), Size size=Size(0), bool resize_pol=HashTableConst::default_resize_policy, bool key_uniqueness_pol=HashTableConst::default_uniqueness_policy) const
Transforms a hashtable of vals into a hashtable of mountains.
Definition hashTable_tpl.h:934

gum::HashTable::const_iterator
HashTableConstIterator< Key, Val > const_iterator
Types for STL compliance.
Definition hashTable.h:654

gum::HashTable::HashTable
HashTable(Size size_param=HashTableConst::default_size, bool resize_pol=HashTableConst::default_resize_policy, bool key_uniqueness_pol=HashTableConst::default_uniqueness_policy)
Default constructor.
Definition hashTable_tpl.h:314

gum::HashTable::iterator_safe
HashTableIteratorSafe< Key, Val > iterator_safe
Types for STL compliance.
Definition hashTable.h:655

Template Parameters

Key	The type for keys in a gum::HashTable.
Val	The type for values in a gum::HashTable.

Definition at line 640 of file hashTable.h.

Member Typedef Documentation

◆ Bucket

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::Bucket = HashTableBucket< Key, Val >

The buckets where data are stored.

Definition at line 660 of file hashTable.h.

◆ const_iterator

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::const_iterator = HashTableConstIterator< Key, Val >

Types for STL compliance.

Definition at line 654 of file hashTable.h.

◆ const_iterator_safe

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::const_iterator_safe = HashTableConstIteratorSafe< Key, Val >

Types for STL compliance.

Definition at line 656 of file hashTable.h.

◆ const_pointer

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::const_pointer = const value_type*

Types for STL compliance.

Definition at line 650 of file hashTable.h.

◆ const_reference

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::const_reference = const value_type&

Types for STL compliance.

Definition at line 648 of file hashTable.h.

◆ difference_type

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 652 of file hashTable.h.

◆ iterator

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::iterator = HashTableIterator< Key, Val >

Types for STL compliance.

Definition at line 653 of file hashTable.h.

◆ iterator_safe

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::iterator_safe = HashTableIteratorSafe< Key, Val >

Types for STL compliance.

Definition at line 655 of file hashTable.h.

◆ key_type

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::key_type = Key

Types for STL compliance.

Definition at line 644 of file hashTable.h.

◆ mapped_type

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::mapped_type = Val

Types for STL compliance.

Definition at line 645 of file hashTable.h.

◆ pointer

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::pointer = value_type*

Types for STL compliance.

Definition at line 649 of file hashTable.h.

◆ reference

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::reference = value_type&

Types for STL compliance.

Definition at line 647 of file hashTable.h.

◆ size_type

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::size_type = Size

Types for STL compliance.

Definition at line 651 of file hashTable.h.

◆ value_type

template<typename Key, typename Val>

using gum::HashTable< Key, Val >::value_type = std::pair< const Key, Val >

Types for STL compliance.

Definition at line 646 of file hashTable.h.

Constructor & Destructor Documentation

◆ HashTable() [1/4]

template<typename Key, typename Val>

gum::HashTable< Key, Val >::HashTable	(	Size	size_param = HashTableConst::default_size,
		bool	resize_pol = HashTableConst::default_resize_policy,
		bool	key_uniqueness_pol = HashTableConst::default_uniqueness_policy )

explicit

Default constructor.

The true capacity (vector's size) of the hashtable will be the lowest number greater than or equal to size_param that is also a power of 2. The second optional argument is the resizing policy. By default, each time there is an average of 3 elements by node, the size of the hashtable is automatically multiplied by 2. But the user may pass false as argument to resize_pol to disable this feature.

Parameters

size_param	The initial size of the gum::HashTable.
resize_pol	The policy for resizing the hashtable when new elements are added (possible values: true = automatic resize and false = manual resize).
key_uniqueness_pol	Uniqueness policy : should we prevent inserting the same key more than once in the table?

Definition at line 314 of file hashTable_tpl.h.

                                                                                            :
      // size must be >= 2 else we lose all the bits of the hash function
      _size_{Size(1) << _hashTableLog2_(std::max(Size(2), size_param))},
      _resize_policy_{resize_pol}, _key_uniqueness_policy_{key_uniqueness_pol} {
    // for debugging purposes
    GUM_CONSTRUCTOR(HashTable);
 
    // finalize the creation
    _create_(_size_);
  }

References HashTable(), _create_(), gum::_hashTableLog2_(), _key_uniqueness_policy_, _resize_policy_, and _size_.

Referenced by HashTable(), HashTable(), HashTable(), HashTable(), ~HashTable(), _copy_(), map(), map(), map(), map(), operator=(), operator=(), operator==(), operator[](), and operator[]().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HashTable() [2/4]

template<typename Key, typename Val>

gum::HashTable< Key, Val >::HashTable ( std::initializer_list< std::pair< Key, Val > > list )

explicit

Initializer list constructor.

Parameters

list	The initialized list.

Definition at line 326 of file hashTable_tpl.h.

                                                                                  :
      // size must be >= 2 else we lose all the bits of the hash function
      _size_{Size(1) << _hashTableLog2_(std::max< Size >(Size(2), Size(list.size()) / 2))} {
    // for debugging purposes
    GUM_CONSTRUCTOR(HashTable);
 
    // setup the  _nodes_ vector (contains only empty lists)
    _create_(_size_);
 
    // insert all the elements
    for (const auto& elt: list) {
      insert(elt);
    }
  }

References HashTable(), _create_(), gum::_hashTableLog2_(), _size_, insert(), and size().

Here is the call graph for this function:

◆ HashTable() [3/4]

template<typename Key, typename Val>

gum::HashTable< Key, Val >::HashTable ( const HashTable< Key, Val > & from )

Copy constructor.

This creates a new hashtable the content of which is similar to that of the table passed in argument. Beware: similar does not mean that both tables share the same objects, but rather that the objects stored in the newly created table are copies of those of the table passed in argument. In particular, the new hash table inherits the parameters (resize policy, uniqueness policy) of table 'from'.

Parameters

from	The gum::HashTable to copy.

Definition at line 342 of file hashTable_tpl.h.

                                                                     :
      _size_{table._size_}, _resize_policy_{table._resize_policy_},
      _key_uniqueness_policy_{table._key_uniqueness_policy_}, _begin_index_{table._begin_index_} {
    // for debugging purposes
    GUM_CONS_CPY(HashTable);
 
    // setup the  _nodes_ vector (contains only empty lists)
    _create_(_size_);
 
    // fill with the content of table
    _copy_(table);
  }

References HashTable(), _begin_index_, _copy_(), _create_(), _key_uniqueness_policy_, _resize_policy_, and _size_.

Here is the call graph for this function:

◆ HashTable() [4/4]

template<typename Key, typename Val>

gum::HashTable< Key, Val >::HashTable ( HashTable< Key, Val > && from )

noexcept

Move constructor.

Parameters

from	The gum::HashTable to move.

Definition at line 356 of file hashTable_tpl.h.

                                                                         :
      _nodes_(std::move(table._nodes_)), _size_{table._size_}, _nb_elements_{table._nb_elements_},
      _hash_func_{table._hash_func_}, _resize_policy_{table._resize_policy_},
      _key_uniqueness_policy_{table._key_uniqueness_policy_}, _begin_index_{table._begin_index_} {
    // clear the safe iterators that pointed to the table
    for (auto* iter: table._safe_iterators_) {
      iter->clear();
    }
 
    // for debugging purposes
    table._size_        = 0;
    table._nb_elements_ = 0;
    GUM_CONS_MOV(HashTable);
  }

References HashTable(), _nodes_, and _size_.

Here is the call graph for this function:

◆ ~HashTable()

template<typename Key, typename Val>

gum::HashTable< Key, Val >::~HashTable ( )

Class destructor.

Definition at line 393 of file hashTable_tpl.h.

                                    {
    // for debugging purposes
    GUM_DESTRUCTOR(HashTable);
 
    // update all the registered iterators: they should now point to nullptr
    // and their hashtable should be set to nullptr
    _clearIterators_();
  }

References HashTable(), and _clearIterators_().

Here is the call graph for this function:

Member Function Documentation

◆ _clearIterators_()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::_clearIterators_ ( )

private

Clear all the safe iterators.

Definition at line 372 of file hashTable_tpl.h.

                                               {
    const Size len = _safe_iterators_.size();
    for (Size i = Size(0); i < len; ++i)
      _safe_iterators_[i]->clear();
  }

References _safe_iterators_, and clear().

Referenced by ~HashTable(), and clear().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _copy_()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::_copy_ ( const HashTable< Key, Val > & table )

private

A function used to perform copies of HashTables.

This code is shared by the copy constructor and the copy operator. The function ensures that when a memory allocation problem occurs:

no memory leak occurs
the hashtable returned is empty but in a coherent state
an exception is thrown

The function assumes that both this and table have arrays ' __nodes' of the same size.

Parameters

table The gum::HashTable to copy.

Definition at line 279 of file hashTable_tpl.h.

                                                                       {
    // in debug mode, check that this and table have ' __nodes' arrays of the
    // same size
    GUM_ASSERT(table._size_ == _size_);
 
    // try to fill the array of chained lists
    for (Size i = 0; i < table._size_; ++i) {
      try {
        _nodes_[i] = table._nodes_[i];
      } catch (...) {
        // here we could allocate the  _nodes_[j], j=0..i-1, so we should
        // deallocate them
        for (Size j = 0; j < _size_; ++j)
          _nodes_[j].clear();
 
        _nb_elements_ = Size(0);
 
        // propagate the exception
        throw;
      }
    }
 
    _nb_elements_ = table._nb_elements_;
  }

References HashTable(), and _size_.

Referenced by HashTable().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _create_()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::_create_ ( Size size )

private

Used by all default constructors (general and specialized).

Parameters

size	The size of the gum::HashTable to create.

Definition at line 305 of file hashTable_tpl.h.

                                                {
    // setup the  _nodes_ vector (contains only empty lists)
    _nodes_.resize(size);
 
    // set up properly the hash function
    _hash_func_.resize(size);
  }

References _hash_func_, _nodes_, and size().

Referenced by HashTable(), HashTable(), and HashTable().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _erase_()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::_erase_	(	HashTableBucket< Key, Val > *	bucket,
		Size	index )

private

Erases a given bucket.

Definition at line 821 of file hashTable_tpl.h.

                                                                                     {
    if (bucket == nullptr) return;
 
    // update the registered iterators pointing to this bucket
    for (auto iter: _safe_iterators_) {
      if (iter->_bucket_ == bucket) {
        iter->operator++();
        iter->_next_bucket_ = iter->_bucket_;
        iter->_bucket_      = nullptr;
      } else if (iter->_next_bucket_ == bucket) {
        iter->_bucket_ = bucket;
        iter->operator++();
        iter->_next_bucket_ = iter->_bucket_;
        iter->_bucket_      = nullptr;
      }
    }
 
    // remove the element from the  _nodes_ vector
    _nodes_[index].erase(bucket);
 
    --_nb_elements_;
 
    if ((index == _begin_index_) && _nodes_[index].empty()) {
      _begin_index_ = std::numeric_limits< Size >::max();
    }
  }

References _nb_elements_, _nodes_, and _safe_iterators_.

Referenced by erase(), erase(), and erase().

Here is the caller graph for this function:

◆ _insert_()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::_insert_ ( Bucket * bucket )

private

Adds a new element (actually a copy of this element) in the hash table.

If there already exists an element with the same key in the list and the uniqueness policy prevents multiple identical keys to belong to the same hashtable, an exception DuplicateElement is thrown. If the uniqueness policy is not set, the method runs in the worst case in constant time, else if the automatic resizing policy is set, it runs in constant time in average linear in the number of elements by slot.

Parameters

bucket The bucket inserted in the hash table.

Exceptions

DuplicateElement is thrown when attempting to insert a pair (key,val) in a hash table containing already a pair with the same key and when the hash table's uniqueness policy is set.

Definition at line 722 of file hashTable_tpl.h.

                                                                          {
    Size hash_key = _hash_func_(bucket->key());
 
    // check that there does not already exist an element with the same key
    if (_key_uniqueness_policy_ && _nodes_[hash_key].exists(bucket->key())) {
      // remove the bucket from memory
      Key k = bucket->key();
      delete bucket;
      GUM_ERROR(DuplicateElement,
                "the hashtable contains an element with the same key (" << k << ")");
    }
 
    // check whether there is sufficient space to insert the new pair
    // if not, resize the current hashtable
    if (_resize_policy_ && (_nb_elements_ >= _size_ * HashTableConst::default_mean_val_by_slot)) {
      resize(_size_ << 1);
      hash_key = _hash_func_(bucket->key());
    }
 
    // add the new pair
    _nodes_[hash_key].insert(bucket);
    ++_nb_elements_;
 
    // recompute the index of the beginning of the hashtable if possible
    // WARNING: if  _begin_index_ = std::numeric_limits<Size>::max (), we CANNOT
    // recompute the index because we cannot know whether the current index is
    // equal to max because there was no element in the hashtable or whether a
    // previous  _erase_() has set the index to max.
    if (_begin_index_ < hash_key) { _begin_index_ = hash_key; }
  }

References _hash_func_, _key_uniqueness_policy_, _nodes_, exists(), GUM_ERROR, and gum::HashTableBucket< Key, Val >::key().

Referenced by emplace(), insert(), insert(), and insert().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ begin() [1/2]

template<typename Key, typename Val>

HashTable< Key, Val >::iterator gum::HashTable< Key, Val >::begin ( )

Returns an unsafe iterator pointing to the beginning of the hashtable.

Unsafe iterators are slightly faster than safe iterators. However, BE CAREFUL when using them: they should ONLY be used when you have the guarantee that they will never point to a deleted element. If unsure, prefer using the safe iterators (those are only slightly slower).

Returns: Returns an unsafe iterator pointing to the beginning of the hashtable.

Definition at line 490 of file hashTable_tpl.h.

                                                                      {
    // if the table is empty, make the begin and end point to the same element
    if (_nb_elements_ == Size(0)) return iterator{end()};
    else return iterator{*this};
  }

References _nb_elements_, and end().

Referenced by gum::MultiDimFunctionGraphOperator< GUM_ELEMENT, FUNCTOR, TerminalNodePolicy >::_findRetrogradeVariables_(), gum::Regress< GUM_ELEMENT, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::_findRetrogradeVariables_(), keyByVal(), map(), map(), operator==(), and gum::learning::SimpleMiic::orientationMiic_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ begin() [2/2]

template<typename Key, typename Val>

HashTable< Key, Val >::const_iterator gum::HashTable< Key, Val >::begin ( ) const

Returns an unsafe const_iterator pointing to the beginning of the hashtable.

Unsafe iterators are slightly faster than safe iterators. However, BE CAREFUL when using them: they should ONLY be used when you have the guarantee that they will never point to a deleted element. If unsure, prefer using the safe iterators (those are only slightly slower).

Returns: Returns an unsafe const_iterator pointing to the beginning of the hashtable.

Definition at line 497 of file hashTable_tpl.h.

                                                                                  {
    // if the table is empty, make the begin and end point to the same element
    if (_nb_elements_ == Size(0)) return const_iterator{end()};
    else return const_iterator{*this};
  }

References _nb_elements_, and end().

Here is the call graph for this function:

◆ beginSafe() [1/2]

template<typename Key, typename Val>

HashTable< Key, Val >::iterator_safe gum::HashTable< Key, Val >::beginSafe ( )

Returns the safe iterator pointing to the beginning of the hashtable.

Safe iterators are slightly slower than unsafe ones but they guarantee that you will never get a segfault if they try to access to a deleted element or if they try a ++ operation from a deleted element.

Returns: Returns the safe iterator pointing to the beginning of the hashtable.

Definition at line 528 of file hashTable_tpl.h.

                                                                               {
    // if the table is empty, make the begin and end point to the same element
    if (_nb_elements_ == Size(0)) return iterator_safe{endSafe()};
    else return iterator_safe{*this};
  }

References _nb_elements_, and endSafe().

Referenced by gum::DAGCycleDetector::hasCycleFromModifications(), gum::LeafAggregator::leavesMap(), gum::MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy >::toDot(), and gum::ITI< AttributeSelection, isScalar >::updateGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ beginSafe() [2/2]

template<typename Key, typename Val>

HashTable< Key, Val >::const_iterator_safe gum::HashTable< Key, Val >::beginSafe ( ) const

Returns the safe const_iterator pointing to the beginning of the hashtable.

Safe iterators are slightly slower than unsafe ones but they guarantee that you will never get a segfault if they try to access to a deleted element or if they try a ++ operation from a deleted element.

Returns: Returns the safe const_iterator pointing to the beginning of the hashtable.

Definition at line 535 of file hashTable_tpl.h.

                                                                                           {
    // if the table is empty, make the begin and end point to the same element
    if (_nb_elements_ == Size(0)) return const_iterator_safe{endSafe()};
    else return const_iterator_safe{*this};
  }

References _nb_elements_, and endSafe().

Here is the call graph for this function:

◆ capacity()

template<typename Key, typename Val>

Size gum::HashTable< Key, Val >::capacity ( ) const

noexcept

Returns the number of slots in the 'nodes' vector of the hashtable.

The method runs in constant time.

Returns: Returns the number of slots in the 'nodes' vector of the hashtable.

Definition at line 586 of file hashTable_tpl.h.

                                                      {
    return _size_;
  }

References _size_.

Referenced by gum::ArcGraphPart::ArcGraphPart().

Here is the caller graph for this function:

◆ cbegin()

template<typename Key, typename Val>

HashTable< Key, Val >::const_iterator gum::HashTable< Key, Val >::cbegin ( ) const

Returns an unsafe const_iterator pointing to the beginning of the hashtable.

Unsafe iterators are slightly faster than safe iterators. However, BE CAREFUL when using them: they should ONLY be used when you have the guarantee that they will never point to a deleted element. If unsure, prefer using the safe iterators (those are only slightly slower).

Returns: Returns an unsafe const_iterator pointing to the beginning of the hashtable.

Definition at line 504 of file hashTable_tpl.h.

                                                                                   {
    // if the table is empty, make the begin and end point to the same element
    if (_nb_elements_ == Size(0)) return const_iterator{cend()};
    else return const_iterator{*this};
  }

References _nb_elements_, and cend().

Referenced by gum::learning::StructuralConstraintSliceOrder::StructuralConstraintSliceOrder(), gum::DAGCycleDetector::_addWeightedSet_(), gum::BijectionImplementation< T1, T2, Gen >::_copy_(), gum::DAGCycleDetector::_delWeightedSet_(), gum::DAGCycleDetector::_restrictWeightedSet_(), gum::DAGCycleDetector::addArc(), gum::DAGCycleDetector::eraseArc(), gum::DAGCycleDetector::hasCycleFromModifications(), and gum::Set< Key >::operator+().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cbeginSafe()

template<typename Key, typename Val>

HashTable< Key, Val >::const_iterator_safe gum::HashTable< Key, Val >::cbeginSafe ( ) const

Returns the safe const_iterator pointing to the beginning of the hashtable.

Safe iterators are slightly slower than unsafe ones but they guarantee that you will never get a segfault if they try to access to a deleted element or if they try a ++ operation from a deleted element.

Returns: Returns the safe const_iterator pointing to the beginning of the hashtable.

Definition at line 542 of file hashTable_tpl.h.

                                                                                            {
    // if the table is empty, make the begin and end point to the same element
    if (_nb_elements_ == Size(0)) return const_iterator_safe{cendSafe()};
    else return const_iterator_safe{*this};
  }

References _nb_elements_, and cendSafe().

Referenced by gum::IMDDI< AttributeSelection, isScalar >::_rebuildFunctionGraph_(), and gum::LeastSquareTestPolicy< GUM_ELEMENT >::add().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cend()

template<typename Key, typename Val>

const HashTable< Key, Val >::const_iterator & gum::HashTable< Key, Val >::cend ( ) const

noexcept

Returns the unsafe const_iterator pointing to the end of the hashtable.

Unsafe iterators are slightly faster than safe iterators. However, BE CAREFUL when using them: they should ONLY be used when you have the guarantee that they will never point to a deleted element. If unsure, prefer using the safe iterators (those are only slightly slower).

Returns: Returns the unsafe const_iterator pointing to the end of the hashtable.

Definition at line 485 of file hashTable_tpl.h.

                                                 {
    return *(reinterpret_cast< const const_iterator* >(_HashTable_cend_));
  }

Referenced by gum::learning::StructuralConstraintSliceOrder::StructuralConstraintSliceOrder(), gum::DAGCycleDetector::_addWeightedSet_(), gum::BijectionImplementation< T1, T2, Gen >::_copy_(), gum::DAGCycleDetector::_delWeightedSet_(), gum::DAGCycleDetector::_restrictWeightedSet_(), gum::DAGCycleDetector::addArc(), cbegin(), gum::DAGCycleDetector::eraseArc(), gum::DAGCycleDetector::hasCycleFromModifications(), and gum::Set< Key >::operator+().

Here is the caller graph for this function:

◆ cendSafe()

template<typename Key, typename Val>

const HashTable< Key, Val >::const_iterator_safe & gum::HashTable< Key, Val >::cendSafe ( ) const

noexcept

Returns the safe const_iterator pointing to the end of the hashtable.

Safe iterators are slightly slower than unsafe ones but they guarantee that you will never get a segfault if they try to access to a deleted element or if they try a ++ operation from a deleted element.

Returns: Returns the safe const_iterator pointing to the end of the hashtable.

Definition at line 523 of file hashTable_tpl.h.

                                                     {
    return *(reinterpret_cast< const const_iterator_safe* >(_HashTable_cend_safe_));
  }

Referenced by gum::IMDDI< AttributeSelection, isScalar >::_rebuildFunctionGraph_(), gum::LeastSquareTestPolicy< GUM_ELEMENT >::add(), cbeginSafe(), and gum::ITI< AttributeSelection, isScalar >::updateGraph().

Here is the caller graph for this function:

◆ clear()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::clear ( )

Removes all the elements in the hash table.

The function does not resize the nodes vector (even if the size of this one has been increased after the creation of the hash table) and it resets the iterators on the hash table to end. The method runs in linear time w.r.t. the number of iterators pointing to the hash table.

Definition at line 379 of file hashTable_tpl.h.

                                    {
    // update all the registered iterators: they should now point to nullptr
    // and they are positioned to the end of the hashtable.
    _clearIterators_();
 
    // remove the buckets
    for (Size i = Size(0); i < _size_; ++i)
      _nodes_[i].clear();
 
    _nb_elements_ = Size(0);
    _begin_index_ = std::numeric_limits< Size >::max();
  }

References _clearIterators_(), _nodes_, _size_, and clear().

Referenced by _clearIterators_(), gum::MultiDimFunctionGraphOperator< GUM_ELEMENT, FUNCTOR, TerminalNodePolicy >::_findRetrogradeVariables_(), gum::Regress< GUM_ELEMENT, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::_findRetrogradeVariables_(), and clear().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ emplace()

template<typename Key, typename Val>

template<typename... Args>

HashTable< Key, Val >::value_type & gum::HashTable< Key, Val >::emplace ( Args &&... args )

Emplace a new element into the hashTable.

If there already exists an element with the same key in the list and the uniqueness policy prevents multiple identical keys to belong to the same hashtable, an exception DuplicateElement is thrown. If the uniqueness policy is not set, the method runs in the worst case in constant time, else if the automatic resizing policy is set, it runs in constant time in average linear in the number of elements by slot.

Returns: a reference to the pair (key,val) inserted in the hash table.

Exceptions

DuplicateElement is thrown when attempting to insert a pair (key,val) in a hash table containing already a pair with the same key and when the hash table's uniqueness policy is set.

Parameters

args	The element to emplace.

Definition at line 787 of file hashTable_tpl.h.

                                                                                         {
    auto bucket
        = new Bucket(HashTableBucket< Key, Val >::Emplace::EMPLACE, std::forward< Args >(args)...);
    _insert_(bucket);
    return bucket->elt();
  }

References _insert_(), gum::HashTableBucket< Key, Val >::elt(), and gum::HashTableBucket< Key, Val >::EMPLACE.

Here is the call graph for this function:

◆ empty()

template<typename Key, typename Val>

bool gum::HashTable< Key, Val >::empty ( ) const

noexcept

Indicates whether the hash table is empty.

Returns: Returns true if the gum::HashTable is empty.

Definition at line 928 of file hashTable_tpl.h.

                                                   {
    return (_nb_elements_ == Size(0));
  }

References _nb_elements_.

Referenced by gum::prm::PRMFactory< GUM_SCALAR >::addInstance(), gum::causalImpact(), gum::Counterfactual< GUM_ELEMENT >::counterFactualModel(), gum::counterfactualModel(), gum::BayesBall::relevantTensors(), and gum::dSeparationAlgorithm::relevantTensors().

Here is the caller graph for this function:

◆ end() [1/2]

template<typename Key, typename Val>

const HashTable< Key, Val >::const_iterator & gum::HashTable< Key, Val >::end ( ) const

noexcept

Returns the unsafe const_iterator pointing to the end of the hashtable.

Unsafe iterators are slightly faster than safe iterators. However, BE CAREFUL when using them: they should ONLY be used when you have the guarantee that they will never point to a deleted element. If unsure, prefer using the safe iterators (those are only slightly slower).

Returns: Returns the unsafe const_iterator pointing to the end of the hashtable.

Definition at line 479 of file hashTable_tpl.h.

                                                {
    return *(reinterpret_cast< const const_iterator* >(_HashTable_cend_));
  }

◆ end() [2/2]

template<typename Key, typename Val>

const HashTable< Key, Val >::iterator & gum::HashTable< Key, Val >::end ( )

noexcept

Returns the unsafe iterator pointing to the end of the hashtable.

Unsafe iterators are slightly faster than safe iterators. However, BE CAREFUL when using them: they should ONLY be used when you have the guarantee that they will never point to a deleted element. If unsure, prefer using the safe iterators (those are only slightly slower).

Returns: Returns the unsafe iterator pointing to the end of the hashtable.

Definition at line 473 of file hashTable_tpl.h.

                                                                                    {
    return *(reinterpret_cast< const iterator* >(_HashTable_end_));
  }

Referenced by gum::MultiDimFunctionGraphOperator< GUM_ELEMENT, FUNCTOR, TerminalNodePolicy >::_findRetrogradeVariables_(), gum::Regress< GUM_ELEMENT, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::_findRetrogradeVariables_(), begin(), begin(), keyByVal(), map(), map(), operator==(), and gum::learning::SimpleMiic::orientationMiic_().

Here is the caller graph for this function:

◆ endSafe() [1/2]

template<typename Key, typename Val>

const HashTable< Key, Val >::const_iterator_safe & gum::HashTable< Key, Val >::endSafe ( ) const

noexcept

Returns the safe const_iterator pointing to the end of the hashtable.

Safe iterators are slightly slower than unsafe ones but they guarantee that you will never get a segfault if they try to access to a deleted element or if they try a ++ operation from a deleted element.

Returns: Returns the safe const_iterator pointing to the end of the hashtable.

Definition at line 517 of file hashTable_tpl.h.

                                                    {
    return *(reinterpret_cast< const const_iterator_safe* >(_HashTable_cend_safe_));
  }

◆ endSafe() [2/2]

template<typename Key, typename Val>

const HashTable< Key, Val >::iterator_safe & gum::HashTable< Key, Val >::endSafe ( )

noexcept

Returns the safe iterator pointing to the end of the hashtable.

Safe iterators are slightly slower than unsafe ones but they guarantee that you will never get a segfault if they try to access to a deleted element or if they try a ++ operation from a deleted element.

Returns: Returns the safe iterator pointing to the end of the hashtable.

Definition at line 511 of file hashTable_tpl.h.

                                                                                             {
    return *(reinterpret_cast< const iterator_safe* >(_HashTable_end_safe_));
  }

Referenced by beginSafe(), beginSafe(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::LeafAggregator::leavesMap(), gum::MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy >::toDot(), and gum::ITI< AttributeSelection, isScalar >::updateGraph().

Here is the caller graph for this function:

◆ erase() [1/4]

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::erase ( const const_iterator_safe & iter )

Removes a given element from the hash table.

This method updates all the safe iterators pointing to the deleted element, i.e., when trying to dereference those iterators, an exception will be raised because they will know that the element they point to no longer exists.

Parameters

iter	An iterator over the element to remove.

Definition at line 876 of file hashTable_tpl.h.

                                                                   {
    _erase_(iter._getBucket_(), iter._getIndex_());
  }

References _erase_(), gum::HashTableConstIteratorSafe< Key, Val >::_getBucket_(), and gum::HashTableConstIteratorSafe< Key, Val >::_getIndex_().

Here is the call graph for this function:

◆ erase() [2/4]

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::erase ( const iterator_safe & iter )

Removes a given element from the hash table.

This method updates all the safe iterators pointing to the deleted element, i.e., when trying to dereference those iterators, an exception will be raised because they will know that the element they point to no longer exists.

Parameters

iter	An iterator over the element to remove.

Definition at line 871 of file hashTable_tpl.h.

                                                             {
    _erase_(iter._getBucket_(), iter._getIndex_());
  }

References _erase_().

Here is the call graph for this function:

◆ erase() [3/4]

template<typename Key, typename Val>

template<typename K>

void gum::HashTable< Key, Val >::erase ( const K & key )

Heterogeneous lookup: erase() without string allocation (accepts string_view, const char*, etc.).

Definition at line 863 of file hashTable_tpl.h.

                                                {
    std::string_view             sv{key};
    Size                         hash   = _hash_func_(sv);
    HashTableBucket< Key, Val >* bucket = _nodes_[hash].bucket(sv);
    _erase_(bucket, hash);
  }

References _erase_(), _hash_func_, _nodes_, erase(), and key().

Here is the call graph for this function:

◆ erase() [4/4]

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::erase ( const Key & key )

Removes a given element from the hash table.

The element is the first one encountered in the list (from begin() to end()) having the specified key. If no such element can be found, nothing is done (in particular, it does not throw any exception). The function never resizes the nodes vector (even if the resizing policy would enable to decrease this size). The method runs in average in time linear to the number of iterators pointing to the table if the automatic resizing policy is set (else it is in linear time in the number of elements of the hash table plus the number of iterators).

Parameters

key	The key of the element to remove.

Definition at line 849 of file hashTable_tpl.h.

                                                  {
    // get the hashed key
    Size hash = _hash_func_(key);
 
    // get the bucket containing the element to erase
    HashTableBucket< Key, Val >* bucket = _nodes_[hash].bucket(key);
 
    _erase_(bucket, hash);
  }

References _hash_func_, _nodes_, and key().

Referenced by gum::DAGCycleDetector::_delWeightedSet_(), gum::prm::StructuredBayesBall< GUM_SCALAR >::_fillMaps_(), erase(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), and reset().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ eraseAllVal()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::eraseAllVal ( const Val & val )

Removes all the elements having a certain value from the hash table.

If no such element can be found, nothing is done (in particular, it does not throw any exception). The function never resizes the nodes vector (even if the resizing policy would enable to decrease this size). Comparisons between Val instances are performed through == operators.

Parameters

val	The value to remove.

Definition at line 921 of file hashTable_tpl.h.

                                                        {
    for (auto iterAll = cbeginSafe(); iterAll != cendSafe(); ++iterAll) {
      if (iterAll._bucket_->val() == val) { _erase_(iterAll._bucket_, iterAll._index_); }
    }
  }

◆ eraseByVal()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::eraseByVal ( const Val & val )

Removes a given element from the hash table.

The element is the first one encountered in the list (from begin() to end()) having the specified value. If no such element can be found, nothing is done (in particular, it does not throw any exception). The function never resizes the nodes vector (even if the resizing policy would enable to decrease this size). Comparisons between Val instances are performed through == operators. Logically, this method should have been named "erase", however, this would have prevented creating hash tables where both keys and vals have the same type. Hence we chose to add "ByVal" after erase to make a difference between erasing by key and erasing by val.

Parameters

val	The value to remove.

Definition at line 881 of file hashTable_tpl.h.

                                                       {
    for (auto iter = cbegin(); iter != cend(); ++iter)
      if (iter._bucket_->val() == val) {
        _erase_(iter._getBucket_(), iter._getIndex_());
        return;
      }
  }

◆ exists() [1/2]

template<typename Key, typename Val>

template<typename K>

bool gum::HashTable< Key, Val >::exists ( const K & key ) const

Heterogeneous lookup: exists() without string allocation (accepts string_view, const char*, etc.).

Definition at line 599 of file hashTable_tpl.h.

                                                       {
    std::string_view sv{key};
    return _nodes_[_hash_func_(sv)].bucket(sv) != nullptr;
  }

References _hash_func_, _nodes_, exists(), and key().

Here is the call graph for this function:

◆ exists() [2/2]

template<typename Key, typename Val>

bool gum::HashTable< Key, Val >::exists ( const Key & key ) const

Checks whether there exists an element with a given key in the hashtable.

The method runs in average in constant time if the resizing policy is set.

Parameters

key	The key to test for existence.

Returns: True if key is in this gum::HashTable.

Definition at line 591 of file hashTable_tpl.h.

                                                         {
    return _nodes_[_hash_func_(key)].exists(key);
  }

References _hash_func_, _nodes_, and key().

Referenced by gum::SetIteratorSafe< const gum::DiscreteVariable * >::SetIteratorSafe(), gum::DAGCycleDetector::_addWeightedSet_(), gum::DAGCycleDetector::_delWeightedSet_(), _insert_(), gum::IMDDI< AttributeSelection, isScalar >::_rebuildFunctionGraph_(), gum::StructuredPlaner< GUM_ELEMENT >::_recurArgMaxCopy_(), gum::StructuredPlaner< GUM_ELEMENT >::_recurExtractOptPol_(), gum::credal::CredalNet< GUM_SCALAR >::_sort_varType_(), gum::prm::GSpan< GUM_SCALAR >::_subgraph_mining_(), gum::graph::chainComponents(), gum::graph::connectedComponents(), gum::graph::directedPath(), gum::graph::directedUnorientedPath(), gum::learning::FCI::doDdpOrientation_(), exists(), gum::ASTsum< GUM_SCALAR >::fastToLatex(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::LeafAggregator::leavesMap(), gum::graph::mixedOrientedPath(), gum::graph::mixedUnorientedPath(), gum::Set< Key >::operator*=(), gum::Set< Key >::operator+(), gum::Set< Key >::operator-(), gum::MultiDimFunctionGraphProjector< GUM_ELEMENT, FUNCTOR, TerminalNodePolicy >::project(), gum::graph::detail::reconstructPath(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::Tensor< GUM_SCALAR >::reorganize(), gum::EliminationSequenceStrategy::setGraph(), gum::MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy >::toDot(), gum::CausalFormula< GUM_SCALAR >::toLatex(), and gum::graph::undirectedPath().

Here is the call graph for this function:

◆ getWithDefault() [1/2]

template<typename Key, typename Val>

HashTable< Key, Val >::mapped_type & gum::HashTable< Key, Val >::getWithDefault	(	const Key &	key,
		const Val &	default_value )

Returns a reference on the element the key of which is passed in argument.

In case of multiple identical keys in the hash table, the first value encountered is returned. The method runs in constant time. In case of not found key, (key,default_value) is inserted in *this.

Parameters

key	The key for which we want the value.
default_value	The default value to return if key does not match any value.

Returns: Returns a reference on the element the key of which is passed in argument.

Definition at line 796 of file hashTable_tpl.h.

                                                                                    {
    Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
 
    if (bucket == nullptr) return insert(key, default_value).second;
    else return bucket->val();
  }

References _hash_func_, _nodes_, insert(), key(), and gum::HashTableBucket< Key, Val >::val().

Referenced by gum::graph::_bayesBall_(), and gum::ASTtree< GUM_SCALAR >::_latexCorrect().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getWithDefault() [2/2]

template<typename Key, typename Val>

HashTable< Key, Val >::mapped_type & gum::HashTable< Key, Val >::getWithDefault	(	Key &&	key,
		Val &&	default_value )

Returns a reference on the element the key of which is passed in argument.

In case of multiple identical keys in the hash table, the first value encountered is returned. The method runs in constant time. In case of not found key, (key,default_value) is inserted in *this.

Parameters

key	The key for which we want the value.
default_value	The default value to return if key does not match any value.

Returns: Returns a reference on the element the key of which is passed in argument.

Definition at line 805 of file hashTable_tpl.h.

                                                                          {
    Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
 
    if (bucket == nullptr) return insert(std::move(key), std::move(default_value)).second;
    else return bucket->val();
  }

◆ insert() [1/4]

template<typename Key, typename Val>

HashTable< Key, Val >::value_type & gum::HashTable< Key, Val >::insert	(	const Key &	key,
		const Val &	val )

Adds a new element (actually a copy of this element) into the hash table.

If there already exists an element with the same key in the table and the uniqueness policy prevents multiple identical keys to belong to the same hashtable, an exception DuplicateElement is thrown. If the uniqueness policy is not set, the method runs in the worst case in constant time, else if the automatic resizing policy is set, it runs in constant time in average linear in the number of elements by slot.

Returns: As only a copy of val is inserted into the hashtable, the method returns a reference on a copy of the pair (key,val).

Exceptions

DuplicateElement is thrown when attempting to insert a pair (key,val) in a hash table containing already a pair with the same key and when the hash table's uniqueness policy is set.

Parameters

key	The key to add.
val	The value to add.

Returns: The value added by copy to this gum::HashTable.

Definition at line 754 of file hashTable_tpl.h.

                                                                                               {
    auto bucket = new Bucket(thekey, theval);
    _insert_(bucket);
    return bucket->elt();
  }

References _insert_(), and gum::HashTableBucket< Key, Val >::elt().

Referenced by gum::learning::IBNLearner::Database::Database(), gum::learning::IBNLearner::Database::Database(), HashTable(), gum::prm::gspan::Pattern::Pattern(), gum::SetIteratorSafe< const gum::DiscreteVariable * >::SetIteratorSafe(), gum::DAGCycleDetector::_addWeightedSet_(), gum::MaxInducedWidthMCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::_checkConditions_(), gum::DefaultJunctionTreeStrategy::_computeJunctionTree_(), gum::StaticTriangulation::_computeMaxPrimeJunctionTree_(), gum::StaticTriangulation::_computeRecursiveThinning_(), gum::prm::PRMFormAttribute< GUM_SCALAR >::_fillCpf_(), gum::prm::StructuredBayesBall< GUM_SCALAR >::_fillMaps_(), gum::MultiDimFunctionGraphOperator< GUM_ELEMENT, FUNCTOR, TerminalNodePolicy >::_findRetrogradeVariables_(), gum::Regress< GUM_ELEMENT, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::_findRetrogradeVariables_(), gum::prm::StructuredBayesBall< GUM_SCALAR >::_fromChild_(), gum::prm::StructuredBayesBall< GUM_SCALAR >::_fromParent_(), gum::Counterfactual< GUM_ELEMENT >::_idAssignToNameAssign_(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::_label_(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::_label_(), gum::IMDDI< AttributeSelection, isScalar >::_rebuildFunctionGraph_(), gum::StructuredPlaner< GUM_ELEMENT >::_recurArgMaxCopy_(), gum::StructuredPlaner< GUM_ELEMENT >::_recurExtractOptPol_(), gum::DAGCycleDetector::_restrictWeightedSet_(), gum::prm::PRMFactory< GUM_SCALAR >::_retrieveCommonType_(), gum::credal::CredalNet< GUM_SCALAR >::_sort_varType_(), gum::prm::GSpan< GUM_SCALAR >::_subgraph_mining_(), gum::DAGCycleDetector::addArc(), gum::prm::gspan::DFSTree< GUM_SCALAR >::addRoot(), gum::credal::CredalNet< GUM_SCALAR >::approximatedBinarization(), gum::BarrenNodesFinder::barrenNodes(), gum::BarrenNodesFinder::barrenTensors(), gum::graph::chainComponents(), gum::CausalModel< GUM_ELEMENT >::children(), gum::SetIteratorSafe< const gum::DiscreteVariable * >::clear(), gum::ExactBNdistance< GUM_SCALAR >::computeKL_(), gum::GibbsBNdistance< GUM_SCALAR >::computeKL_(), gum::MCBNDistance< GUM_SCALAR >::computeKL_(), gum::graph::connectedComponents(), gum::graph::directedPath(), gum::graph::directedUnorientedPath(), gum::DAGCycleDetector::eraseArc(), gum::ASTsum< GUM_SCALAR >::fastToLatex(), gum::MultiDimFunctionGraphGenerator::generate(), gum::InfluenceDiagramGenerator< GUM_SCALAR >::generateID(), getWithDefault(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::graph::hasUndirectedCycle(), gum::LeafAggregator::leavesMap(), map(), gum::graph::mixedOrientedPath(), gum::graph::mixedUnorientedPath(), gum::Set< Key >::operator+(), gum::Set< Key >::operator-(), gum::learning::Miic::orientationMiic_(), gum::MultiDimFunctionGraphProjector< GUM_ELEMENT, FUNCTOR, TerminalNodePolicy >::project(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::Tensor< GUM_SCALAR >::reorganize(), gum::learning::FCI::ruleR4_(), gum::prm::PRMClass< GUM_SCALAR >::scope(), gum::DAGCycleDetector::setDAG(), gum::learning::IBNLearner::setSliceOrder(), gum::MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy >::toDot(), gum::CausalFormula< GUM_SCALAR >::toLatex(), gum::graph::topologicalOrder(), gum::graph::undirectedPath(), and gum::ITI< AttributeSelection, isScalar >::updateGraph().

Here is the call graph for this function:

◆ insert() [2/4]

template<typename Key, typename Val>

HashTable< Key, Val >::value_type & gum::HashTable< Key, Val >::insert ( const std::pair< Key, Val > & elt )

Adds a new element (actually a copy of this element) into the hash table.

If there already exists an element with the same key in the table and the uniqueness policy prevents multiple identical keys to belong to the same hashtable, an exception DuplicateElement is thrown. If the uniqueness policy is not set, the method runs in the worst case in constant time, else if the automatic resizing policy is set, it runs in constant time in average linear in the number of elements by slot.

Returns: As only a copy of val is inserted into the hashtable, the method returns a reference on a copy of the pair (key,val).

Exceptions

DuplicateElement is thrown when attempting to insert a pair (key,val) in a hash table containing already a pair with the same key and when the hash table's uniqueness policy is set.

Parameters

elt	The pair of key value to add.

Returns: The value added by copy to this gum::HashTable.

Definition at line 771 of file hashTable_tpl.h.

                                                                  {
    auto bucket = new Bucket(reinterpret_cast< const value_type& >(elt));
    _insert_(bucket);
    return bucket->elt();
  }

References _insert_(), and gum::HashTableBucket< Key, Val >::elt().

Here is the call graph for this function:

◆ insert() [3/4]

template<typename Key, typename Val>

HashTable< Key, Val >::value_type & gum::HashTable< Key, Val >::insert	(	Key &&	key,
		Val &&	val )

Moves a new element in the hash table.

If there already exists an element with the same key in the table and the uniqueness policy prevents multiple identical keys to belong to the same hashtable, an exception DuplicateElement is thrown. If the uniqueness policy is not set, the method runs in the worst case in constant time, else if the automatic resizing policy is set, it runs in constant time in average linear in the number of elements by slot.

Returns: a reference to the pair (key,val) in the hashtable.

Exceptions

DuplicateElement is thrown when attempting to insert a pair (key,val) in a hash table containing already a pair with the same key and when the hash table's uniqueness policy is set.

Parameters

key	The key to move.
val	The value to move.

Returns: The value moved to this gum::HashTable.

Definition at line 762 of file hashTable_tpl.h.

                                                                                          {
    auto bucket = new Bucket(std::move(thekey), std::move(theval));
    _insert_(bucket);
    return bucket->elt();
  }

◆ insert() [4/4]

template<typename Key, typename Val>

HashTable< Key, Val >::value_type & gum::HashTable< Key, Val >::insert ( std::pair< Key, Val > && elt )

Moves a new element in the hash table.

If there already exists an element with the same key in the table and the uniqueness policy prevents multiple identical keys to belong to the same hashtable, an exception DuplicateElement is thrown. If the uniqueness policy is not set, the method runs in the worst case in constant time, else if the automatic resizing policy is set, it runs in constant time in average linear in the number of elements by slot.

Returns: a reference to the pair (key,val) in the hashtable.

Exceptions

DuplicateElement is thrown when attempting to insert a pair (key,val) in a hash table containing already a pair with the same key and when the hash table's uniqueness policy is set.

Parameters

elt	The pair of key value to move in this gum::HashTable.

Returns: The value moved to this gum::HashTable.

Definition at line 779 of file hashTable_tpl.h.

                                                             {
    auto bucket = new Bucket(std::move(reinterpret_cast< value_type& >(elt)));
    _insert_(bucket);
    return bucket->elt();
  }

References _insert_(), and gum::HashTableBucket< Key, Val >::elt().

Here is the call graph for this function:

◆ key()

template<typename Key, typename Val>

const Key & gum::HashTable< Key, Val >::key ( const Key & key ) const

Returns a reference on a given key.

Some complex structures use pointers on keys of hashtables. These structures thus require that we do not only get a copy of a given key, but the key stored in the hashtable itself. This is the very purpose of this function.

Parameters

key	The key to return.

Returns: Returns a reference on a given key.

Exceptions

NotFound Raised if the element cannot be found.

Definition at line 903 of file hashTable_tpl.h.

                                                            {
    // get the bucket corresponding to the key
    Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
 
    if (bucket == nullptr) { GUM_ERROR(NotFound, "key does not belong to the hashtable") }
 
    return bucket->key();
  }

References _hash_func_, _nodes_, GUM_ERROR, key(), and gum::HashTableBucket< Key, Val >::key().

Referenced by erase(), erase(), exists(), exists(), getWithDefault(), key(), operator[](), operator[](), operator[](), operator[](), reset(), set(), tryGet(), tryGet(), tryGet(), tryGet(), and tryGetKey().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ keyByVal()

template<typename Key, typename Val>

const Key & gum::HashTable< Key, Val >::keyByVal ( const Val & val ) const

Returns a reference on the key given a value.

In case of multiple identical values in the hash table, the first key encountered is returned. The method runs in linear time.

Parameters

val	The value for which the key is returned.

Returns: Returns a reference on the key given a value.

Exceptions

NotFound Raised if the element cannot be found.

Definition at line 895 of file hashTable_tpl.h.

                                                                 {
    for (auto iter = begin(); iter != end(); ++iter)
      if (iter._bucket_->val() == val) return iter.key();
 
    GUM_ERROR(NotFound, "not enough elements in the chained list")
  }

References begin(), end(), and GUM_ERROR.

Here is the call graph for this function:

◆ keyUniquenessPolicy()

template<typename Key, typename Val>

bool gum::HashTable< Key, Val >::keyUniquenessPolicy ( ) const

noexcept

Returns the current checking policy.

Returns: Returns the current checking policy.

Definition at line 656 of file hashTable_tpl.h.

                                                                 {
    return _key_uniqueness_policy_;
  }

References _key_uniqueness_policy_.

◆ map() [1/4]

template<typename Key, typename Val>

template<typename Mount>

HashTable< Key, Mount > gum::HashTable< Key, Val >::map	(	const Mount &	val,
		Size	size = Size(0),
		bool	resize_pol = HashTableConst::default_resize_policy,
		bool	key_uniqueness_pol = HashTableConst::default_uniqueness_policy ) const

Creates a hashtable of mounts with a given value from a hashtable of vals.

Warning: Although the resulting hashtable has the same number of elements as the original hashtable, by default, the size of the former may not be equal to that of the latter. Hence iterators on the original hashtable may not parse it in the same order as iterators on the resulting hashtable. To guarrantee that both hashtables have the same size (and thus have the elements in the same order), set the size argument to the size of the original hashtable.

Parameters

val	The value taken by all the elements of the resulting hashtable.
size	The size of the resulting hashtable. When equal to 0, a default size is computed that is a good trade-off between space consumption and efficiency of new elements insertions
resize_pol	the resizing policy (automatic or manual resizing)
key_uniqueness_pol	uniqueness policy

Returns: Returns the gum::HashTable of mountains.

Definition at line 1003 of file hashTable_tpl.h.

                                                                                            {
    // determine the proper size of the hashtable
    // by default, the size of the table is set so that the table does not take
    // too much space while allowing to add a few elements without needing to
    // resize in autmatic resizing mode
    if (size == Size(0)) size = std::max(Size(2), _nb_elements_ / 2);
 
    // create a new table
    HashTable< Key, Mount > table(size, resize_pol, key_uniqueness_pol);
 
    // fill the new hash table
    for (auto iter = begin(); iter != end(); ++iter) {
      table.insert(iter.key(), val);
    }
 
    return table;
  }

References HashTable(), and size().

Here is the call graph for this function:

◆ map() [2/4]

template<typename Key, typename Val>

template<typename Mount>

HashTable< Key, Mount > gum::HashTable< Key, Val >::map	(	Mount(*	f )(const Val &),
		Size	size = Size(0),
		bool	resize_pol = HashTableConst::default_resize_policy,
		bool	key_uniqueness_pol = HashTableConst::default_uniqueness_policy ) const

Transforms a hashtable of vals into a hashtable of mountains.

Warning: Although the resulting hashtable has the same number of elements as the original hashtable, by default, the size of the former may not be equal to that of the latter. Hence iterators on the original hashtable may not parse it in the same order as iterators on the resulting hashtable. To guarrantee that both hashtables have the same size (and thus have the elements in the same order), set the size argument to the size of the original hashtable.

Parameters

f	A function that maps any Val element into a Mount.
size	The size of the resulting hashtable. When equal to 0, a default size is computed that is a good trade-off between space consumption and efficiency of new elements insertions
resize_pol	the resizing policy (automatic or manual resizing)
key_uniqueness_pol	uniqueness policy

Returns: Returns the gum::HashTable of mountains.

Definition at line 980 of file hashTable_tpl.h.

                                                                                    {
    // determine the proper size of the hashtable
    // by default, the size of the table is set so that the table does not take
    // too much space while allowing to add a few elements without needing to
    // resize in autmatic resizing mode
    if (size == Size(0)) size = std::max(Size(2), _nb_elements_ / 2);
 
    // create a new table
    HashTable< Key, Mount > table(size, resize_pol, key_uniqueness_pol);
 
    // fill the new hash table
    for (auto iter = begin(); iter != end(); ++iter) {
      table.insert(iter.key(), f(iter.val()));
    }
 
    return table;
  }

References HashTable(), _nb_elements_, and size().

Here is the call graph for this function:

◆ map() [3/4]

template<typename Key, typename Val>

template<typename Mount>

HashTable< Key, Mount > gum::HashTable< Key, Val >::map	(	Mount(*	f )(Val &),
		Size	size = Size(0),
		bool	resize_pol = HashTableConst::default_resize_policy,
		bool	key_uniqueness_pol = HashTableConst::default_uniqueness_policy ) const

Transforms a hashtable of vals into a hashtable of mountains.

Warning: Although the resulting hashtable has the same number of elements as the original hashtable, by default, the size of the former may not be equal to that of the latter. Hence iterators on the original hashtable may not parse it in the same order as iterators on the resulting hashtable. To guarrantee that both hashtables have the same size (and thus have the elements in the same order), set the size argument to the size of the original hashtable.

Parameters

f	A function that maps any Val element into a Mount.
size	The size of the resulting hashtable. When equal to 0, a default size is computed that is a good trade-off between space consumption and efficiency of new elements insertions
resize_pol	the resizing policy (automatic or manual resizing)
key_uniqueness_pol	uniqueness policy

Returns: Returns the gum::HashTable of mountains.

Definition at line 957 of file hashTable_tpl.h.

                                                                                    {
    // determine the proper size of the hashtable
    // by default, the size of the table is set so that the table does not take
    // too much space while allowing to add a few elements without needing to
    // resize in autmatic resizing mode
    if (size == Size(0)) size = std::max(Size(2), _nb_elements_ / 2);
 
    // create a new table
    HashTable< Key, Mount > table(size, resize_pol, key_uniqueness_pol);
 
    // fill the new hash table
    for (auto iter = begin(); iter != end(); ++iter) {
      table.insert(iter.key(), f(const_cast< Val& >(iter.val())));
    }
 
    return table;
  }

References HashTable(), _nb_elements_, begin(), end(), and size().

Here is the call graph for this function:

◆ map() [4/4]

template<typename Key, typename Val>

template<typename Mount>

HashTable< Key, Mount > gum::HashTable< Key, Val >::map	(	Mount(*	f )(Val),
		Size	size = Size(0),
		bool	resize_pol = HashTableConst::default_resize_policy,
		bool	key_uniqueness_pol = HashTableConst::default_uniqueness_policy ) const

Transforms a hashtable of vals into a hashtable of mountains.

Warning: Although the resulting hashtable has the same number of elements as the original hashtable, by default, the size of the former may not be equal to that of the latter. Hence iterators on the original hashtable may not parse it in the same order as iterators on the resulting hashtable. To guarrantee that both hashtables have the same size (and thus have the elements in the same order), set the size argument to the size of the original hashtable.

Parameters

f	A function that maps any Val element into a Mount.
size	The size of the resulting hashtable. When equal to 0, a default size is computed that is a good trade-off between space consumption and efficiency of new elements insertions
resize_pol	the resizing policy (automatic or manual resizing)
key_uniqueness_pol	uniqueness policy

Returns: Returns the gum::HashTable of mountains.

Definition at line 934 of file hashTable_tpl.h.

                                                                                    {
    // determine the proper size of the hashtable
    // by default, the size of the table is set so that the table does not take
    // too much space while allowing to add a few elements without needing to
    // resize in autmatic resizing mode
    if (size == 0) size = std::max(Size(2), _nb_elements_ / 2);
 
    // create a new table
    HashTable< Key, Mount > table(size, resize_pol, key_uniqueness_pol);
 
    // fill the new hash table
    for (auto iter = begin(); iter != end(); ++iter) {
      table.insert(iter.key(), f(iter.val()));
    }
 
    return table;
  }

References HashTable(), _nb_elements_, begin(), end(), insert(), and size().

Here is the call graph for this function:

◆ operator=() [1/2]

template<typename Key, typename Val>

HashTable< Key, Val > & gum::HashTable< Key, Val >::operator= ( const HashTable< Key, Val > & from )

Copy operator.

The copy operators ensures that whenever a memory allocation problem occurs, no memory leak occurs as well and it also guarantees that in this case the hashtable returned is in a coherent state (it is an empty hashtable). Note that the copy not only involves copying pairs (key,value) but also the copy of the resize and key uniqueness policies.

Parameters

from	The gum::HashTable to copy.

Returns: Returns this gum::HashTable.

Definition at line 403 of file hashTable_tpl.h.

                                                                                         {
    // avoid self assignment
    if (this != &from) {
      // for debugging purposes
      GUM_OP_CPY(HashTable);
 
      // first remove the current content of the hashtable and make
      // the iterators point to end
      clear();
 
      // if sizes of from's and this'  _nodes_ vectors are not the same,
      // we need to remove the current  _nodes_' array and to create a
      // new array with the correct size
      if (_size_ != from._size_) {
        _nodes_.resize(from._size_);
        _size_ = from._size_;
 
        // update the hash function : this is important as the computation of
        // the hash values heavily depends on the size of the hash table
        _hash_func_.resize(_size_);
      }
 
      _resize_policy_         = from._resize_policy_;
      _key_uniqueness_policy_ = from._key_uniqueness_policy_;
      _begin_index_           = from._begin_index_;
 
      // perform the copy
      _copy_(from);
    }
 
    return *this;
  }

References HashTable().

Here is the call graph for this function:

◆ operator=() [2/2]

template<typename Key, typename Val>

HashTable< Key, Val > & gum::HashTable< Key, Val >::operator= ( HashTable< Key, Val > && from )

noexcept

Move operator.

Parameters

from	The gum::HashTable to move.

Returns: Returns this gum::HashTable.

Definition at line 437 of file hashTable_tpl.h.

                                                                                              {
    // avoid self assignment
    if (this != &table) {
      // for debugging purposes
      GUM_OP_MOV(HashTable);
 
      // make the iterators point to nothing
      for (auto* iter: table._safe_iterators_) {
        iter->clear();
      }
 
      // remove the current content of the hashtable and make
      // the safe iterators of this point to end
      clear();
 
      // also make the safe iterators of table point to end
      for (auto* iter: table._safe_iterators_) {
        iter->clear();
      }
 
      _nodes_                 = std::move(table._nodes_);
      _size_                  = table._size_;
      _nb_elements_           = table._nb_elements_;
      _hash_func_             = table._hash_func_;
      _resize_policy_         = table._resize_policy_;
      _key_uniqueness_policy_ = table._key_uniqueness_policy_;
      _begin_index_           = table._begin_index_;
 
      table._size_        = 0;   // necessary if we wish to perform moves iteratively,
      table._nb_elements_ = 0;   // i.e. x = std::move ( y ); y = std::move ( z ); ...
    }
 
    return *this;
  }

References HashTable(), and _safe_iterators_.

Here is the call graph for this function:

◆ operator==()

template<typename Key, typename Val>

bool gum::HashTable< Key, Val >::operator== ( const HashTable< Key, Val > & from ) const

Checks whether two hashtables contain the same elements.

Two hashtables are considered equal if they contain the identical pairs (key,val). Two pairs are identical if their keys have the same hashed value, these two keys are equal in the sense of ==, and their val's are also equal in the sense of ==.

Parameters

from	The gum::HashTable to test for equality.

Returns: True if this and from are equal.

Definition at line 1025 of file hashTable_tpl.h.

                                                                              {
    // checks whether the two hashtables contain the same number of elements
    if (from._nb_elements_ != _nb_elements_) return false;
 
    // parse this and check that each element also belongs to from
    for (auto iter = begin(); iter != end(); ++iter) {
      if (auto p = from.tryGet(iter.key()); !p || iter.val() != *p) return false;
    }
 
    return true;
  }

References HashTable(), _nb_elements_, begin(), end(), and tryGet().

Here is the call graph for this function:

◆ operator[]() [1/4]

template<typename Key, typename Val>

template<typename K>

Val & gum::HashTable< Key, Val >::operator[] ( const K & key )

Heterogeneous lookup: operator[] without string allocation (accepts string_view, const char*, etc.).

Definition at line 562 of file hashTable_tpl.h.

                                                     {
    std::string_view sv{key};
    Bucket*          b = _nodes_[_hash_func_(sv)].bucket(sv);
    if (b == nullptr) { GUM_ERROR(NotFound, "No element with the key <" << sv << ">") }
    return b->val();
  }

References HashTable(), _hash_func_, _nodes_, GUM_ERROR, key(), and gum::HashTableBucket< Key, Val >::val().

Here is the call graph for this function:

◆ operator[]() [2/4]

template<typename Key, typename Val>

template<typename K>

const Val & gum::HashTable< Key, Val >::operator[] ( const K & key ) const

Heterogeneous lookup: operator[] const without string allocation.

Definition at line 573 of file hashTable_tpl.h.

                                                                 {
    std::string_view sv{key};
    const Bucket*    b = _nodes_[_hash_func_(sv)].bucket(sv);
    if (b == nullptr) { GUM_ERROR(NotFound, "No element with the key <" << sv << ">") }
    return b->pair.second;
  }

References HashTable(), _hash_func_, _nodes_, GUM_ERROR, key(), and gum::HashTableBucket< Key, Val >::pair.

Here is the call graph for this function:

◆ operator[]() [3/4]

template<typename Key, typename Val>

Val & gum::HashTable< Key, Val >::operator[] ( const Key & key )

Returns a reference on the value the key of which is passed in argument.

In case of multiple identical keys in the hash table, the first value encountered is returned. The method runs in constant time.

Parameters

key	The key of the value to return.

Returns: Returns the value matching the given key.

Exceptions

NotFound exception is thrown if the element cannot be found.

Definition at line 549 of file hashTable_tpl.h.

                                                       {
    return _nodes_[_hash_func_(key)][key];
  }

References _hash_func_, _nodes_, and key().

Here is the call graph for this function:

◆ operator[]() [4/4]

template<typename Key, typename Val>

const Val & gum::HashTable< Key, Val >::operator[] ( const Key & key ) const

returns a reference on the value the key of which is passed in argument

In case of multiple identical keys in the hash table, the first value encountered is returned. The method runs in constant time.

Exceptions

NotFound exception is thrown if the element cannot be found.

Definition at line 554 of file hashTable_tpl.h.

                                                                   {
    return _nodes_[_hash_func_(key)][key];
  }

References _hash_func_, _nodes_, and key().

Here is the call graph for this function:

◆ reset()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::reset ( const Key & key )

Removes a property (i.e., remove an element).

Reset removes a property (i.e., a pair (key,val)) if it exists. This is an alias for erase but it is quite convenient when dealing with "dynamic property lists".

Parameters

key	The property to remove.

Definition at line 890 of file hashTable_tpl.h.

                                                  {
    erase(key);
  }

References erase(), and key().

Here is the call graph for this function:

◆ resize()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::resize ( Size new_size )

Changes the number of slots in the 'nodes' vector of the hash table.

Usually, method resize enables the user to resize manually the hashtable. When in automatic resize mode, the function will actually resize the table only if resizing policy is compatible with the new size, i.e., the new size is not so small that there would be too many elements per slot in the table (this would lead to a significant loss in performance). However, the resizing policy may be changed by using method setResizePolicy. The method runs in linear time in the size of the hashtable. Upon memory allocation problem, the fuction guarantees that no data is lost and that the hash table and its iterators are in a coherent state. In such a case, a bad_alloc exception is thrown.

Parameters

new_size The new number of slots in the gum::HashTable.

Definition at line 661 of file hashTable_tpl.h.

                                                  {
    // new_size must be >= 2 else all the bits of the hash function are lost
    new_size = std::max(Size(2), new_size);
 
    // find the real size for allocation (the smallest power of 2 greater
    // than or equal to new_size) and get its base-2 logarithm
    int log_size = _hashTableLog2_(new_size);
    new_size     = Size(1) << log_size;
 
    // check if the new size is different from the actual size
    // if not, nothing else need be done
 
    if (new_size != _size_) {
      // under automatic resize policy, check if the new size leaves
      // enough space for storing all the current elements
      if (!_resize_policy_
          || (_nb_elements_ <= new_size * HashTableConst::default_mean_val_by_slot)) {
        // create a new array of  _nodes_ to store the elements
        std::vector< HashTableList< Key, Val > > new_nodes(new_size);
 
        // set the new hash function
        _hash_func_.resize(new_size);
 
        // put all the elements of the current  _nodes_ array into the new one
        Bucket* bucket;
        Size    new_hashed_key;
 
        for (Size i = Size(0); i < _size_; ++i) {
          while ((bucket = _nodes_[i]._deb_list_) != nullptr) {
            // compute the new hashed key
            new_hashed_key = _hash_func_(bucket->key());
 
            // remove the bucket from the list of buckets of the current
            // node vector
            _nodes_[i]._deb_list_ = bucket->next;
 
            // put the bucket into the new  _nodes_ vector
            new_nodes[new_hashed_key].insert(bucket);
          }
        }
 
        // update the size of the hash table
        _size_        = new_size;
        _begin_index_ = std::numeric_limits< Size >::max();
 
        // substitute the current  _nodes_ array by the new one
        std::swap(_nodes_, new_nodes);
 
        // update the iterators
        for (auto iter: _safe_iterators_) {
          if (iter->_bucket_) iter->_index_ = _hash_func_(iter->_bucket_->key());
          else {
            iter->_next_bucket_ = nullptr;
            iter->_index_       = 0;
          }
        }
      }
    }
  }

References _hash_func_, gum::_hashTableLog2_(), _nb_elements_, _resize_policy_, _size_, and gum::HashTableConst::default_mean_val_by_slot.

Here is the call graph for this function:

◆ resizePolicy()

template<typename Key, typename Val>

bool gum::HashTable< Key, Val >::resizePolicy ( ) const

noexcept

Returns the current resizing policy.

Returns: Returns the current resizing policy.

Definition at line 646 of file hashTable_tpl.h.

                                                          {
    return _resize_policy_;
  }

References _resize_policy_.

◆ set()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::set	(	const Key &	key,
		const Val &	default_value )

Add a new property or modify it if it already existed.

When used as a "dynamic property list", it may be convenient to use this function. Function set inserts a new pair (key,val) if the key does not already exists, or it changes the value associated with key if a pair (key,val) already exists in the hash table.

Parameters

key	The key of the value to add or set.
default_value	The value to set or add.

Definition at line 813 of file hashTable_tpl.h.

                                                                  {
    Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
 
    if (bucket == nullptr) insert(key, value);
    else bucket->val() = value;
  }

References _hash_func_, _nodes_, and key().

Referenced by gum::learning::FCI::ruleR4_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setKeyUniquenessPolicy()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::setKeyUniquenessPolicy ( const bool new_policy )

noexcept

Enables the user to change dynamically the policy for checking whether there can exist several elements in the table with identical keys.

By default, we should always check that there does not exist duplicate keys. However, this test slows the insertion of elements in the table. So, when we know for sure that no duplicate key will be entered into the table, we may avoid uniqueness checks.

Warning: When setting the key policy to "uniqueness", the function does not check whether there are already different elements with identical keys in the table. It thus only ensures that elements inserted from now on will have unique keys.

Definition at line 651 of file hashTable_tpl.h.

                                                                                   {
    _key_uniqueness_policy_ = new_policy;
  }

References _key_uniqueness_policy_.

◆ setResizePolicy()

template<typename Key, typename Val>

void gum::HashTable< Key, Val >::setResizePolicy ( const bool new_policy )

noexcept

Enables the user to change dynamically the resizing policy.

In most cases, this should be useless. However, when available memory becomes rare, avoiding automatic resizing may speed-up new insertions in the table.

Warning: This function never resizes the hashtable by itself: even if you set the new policy to be an automatic resizing and the number of elements in the table is sufficiently high that we should resize the table, function setResizePolicy won't perform this resizing. The resizing will happen only if you insert a new element or if use method resize.

Parameters

new_policy The new resizing policy, true implies automatic resizing.

Definition at line 641 of file hashTable_tpl.h.

                                                                            {
    _resize_policy_ = new_policy;
  }

References _resize_policy_.

◆ size()

template<typename Key, typename Val>

Size gum::HashTable< Key, Val >::size ( ) const

noexcept

Returns the number of elements stored into the hashtable.

The method runs in constant time.

Returns: Returns the number of elements stored into the hashtable.

Definition at line 581 of file hashTable_tpl.h.

                                                  {
    return _nb_elements_;
  }

References _nb_elements_.

Referenced by HashTable(), _create_(), map(), map(), map(), and map().

Here is the caller graph for this function:

◆ tryGet() [1/4]

template<typename Key, typename Val>

template<typename K>

optional_ref< Val > gum::HashTable< Key, Val >::tryGet ( const K & key )

Heterogeneous lookup: tryGet() without string allocation (accepts string_view, const char*, etc.).

Definition at line 622 of file hashTable_tpl.h.

                                                                {
    std::string_view sv{key};
    Bucket*          b = _nodes_[_hash_func_(sv)].bucket(sv);
    if (b == nullptr) return {};
    return b->val();
  }

References _hash_func_, _nodes_, key(), tryGet(), and gum::HashTableBucket< Key, Val >::val().

Here is the call graph for this function:

◆ tryGet() [2/4]

template<typename Key, typename Val>

template<typename K>

optional_ref< const Val > gum::HashTable< Key, Val >::tryGet ( const K & key ) const

Heterogeneous lookup: tryGet() const without string allocation.

Definition at line 633 of file hashTable_tpl.h.

                                                                            {
    std::string_view sv{key};
    const Bucket*    b = _nodes_[_hash_func_(sv)].bucket(sv);
    if (b == nullptr) return {};
    return optional_ref< const Val >{b->pair.second};
  }

References _hash_func_, _nodes_, key(), gum::HashTableBucket< Key, Val >::pair, and tryGet().

Here is the call graph for this function:

◆ tryGet() [3/4]

template<typename Key, typename Val>

optional_ref< Val > gum::HashTable< Key, Val >::tryGet ( const Key & key )

Returns a pointer to the value associated with a given key, or nullptr if the key does not exist.

This avoids the double lookup of exists() + operator[].

Parameters

key	The key to search for.

Returns: A pointer to the mapped value, or nullptr if not found.

Definition at line 605 of file hashTable_tpl.h.

                                                                  {
    Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
    if (bucket == nullptr) return {};
    return bucket->val();
  }

References _hash_func_, _nodes_, key(), and gum::HashTableBucket< Key, Val >::val().

Referenced by gum::learning::IBNLearner::Database::Database(), gum::prm::StructuredBayesBall< GUM_SCALAR >::_fromChild_(), gum::prm::StructuredBayesBall< GUM_SCALAR >::_fromParent_(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::_label_(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::_label_(), gum::prm::PRMFactory< GUM_SCALAR >::_retrieveCommonType_(), operator==(), gum::GraphicalModel::property(), tryGet(), and tryGet().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ tryGet() [4/4]

template<typename Key, typename Val>

optional_ref< const Val > gum::HashTable< Key, Val >::tryGet ( const Key & key ) const

Returns a pointer to the value associated with a given key, or nullptr if the key does not exist.

This avoids the double lookup of exists() + operator[].

Parameters

key	The key to search for.

Returns: A pointer to the mapped value, or nullptr if not found.

Definition at line 612 of file hashTable_tpl.h.

                                                                              {
    const Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
    if (bucket == nullptr) return {};
    return bucket->pair.second;
  }

References _hash_func_, _nodes_, key(), and gum::HashTableBucket< Key, Val >::pair.

Here is the call graph for this function:

◆ tryGetKey()

template<typename Key, typename Val>

optional_ref< const Key > gum::HashTable< Key, Val >::tryGetKey ( const Key & key ) const

Returns an optional reference to a given key, or nullptr if the hash table does not contain it.

Some complex structures use pointers on keys of hashtables. These structures thus require that we do not only get a copy of a given key, but the key stored in the hashtable itself. This is the very purpose of this function.

Parameters

key	The key to return.

Returns: Returns a pointer on a given key, or nullptr if the hash table does not contain it.

Exceptions

NotFound Raised if the element cannot be found.

Definition at line 913 of file hashTable_tpl.h.

                                                                                 {
    // get the bucket corresponding to the key
    Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
    return (bucket != nullptr) ? optional_ref< const Key >{bucket->key()}
                               : optional_ref< const Key >();
  }

References _hash_func_, _nodes_, key(), and gum::HashTableBucket< Key, Val >::key().

Here is the call graph for this function:

◆ Bijection

template<typename Key, typename Val>

template<typename T1, typename T2>

friend class Bijection

friend

For bijections to quickly access data.

Definition at line 1522 of file hashTable.h.

◆ HashTableConstIterator< Key, Val >

template<typename Key, typename Val>

friend class HashTableConstIterator< Key, Val >

friend

Friends to optimize the access to data, iterators must be friends.

Definition at line 1501 of file hashTable.h.

◆ HashTableConstIteratorSafe< Key, Val >

template<typename Key, typename Val>

friend class HashTableConstIteratorSafe< Key, Val >

friend

Friends to optimize the access to data, iterators must be friends.

Definition at line 1501 of file hashTable.h.

◆ HashTableIterator< Key, Val >

template<typename Key, typename Val>

friend class HashTableIterator< Key, Val >

friend

Friends to optimize the access to data, iterators must be friends.

Definition at line 1501 of file hashTable.h.

◆ HashTableIteratorSafe< Key, Val >

template<typename Key, typename Val>

friend class HashTableIteratorSafe< Key, Val >

friend

Friends to optimize the access to data, iterators must be friends.

Definition at line 1501 of file hashTable.h.

◆ operator<< [1/2]

template<typename Key, typename Val>

std::ostream & operator<<	(	std::ostream &	s,
		const HashTable< Key *, Val > &	table )

friend

Prints the content of a gum::HashTable with pointers key in the stream.

Definition at line 1091 of file hashTable_tpl.h.

                                                                                  {
    bool deja = false;
    stream << "{";
 
    for (Size i = Size(0); i < table._size_; ++i)
      for (auto ptr = table._nodes_[i]._deb_list_; ptr; ptr = ptr->next) {
        if (deja) stream << " , ";
 
        stream << ptr->key() << "=>" << ptr->val();
 
        deja = true;
      }
 
    stream << "}";
 
    return stream;
  }

◆ operator<< [2/2]

template<typename Key, typename Val>

std::ostream & operator<<	(	std::ostream &	s,
		const HashTable< Key, Val > &	table )

friend

Prints the content of a gum::HashTable in the stream.

Definition at line 1072 of file hashTable_tpl.h.

                                                                                 {
    bool deja = false;
    stream << "{";
 
    for (Size i = Size(0); i < table._size_; ++i)
      for (auto ptr = table._nodes_[i]._deb_list_; ptr; ptr = ptr->next) {
        if (deja) stream << " , ";
 
        stream << ptr->key() << "=>" << ptr->val();
 
        deja = true;
      }
 
    stream << "}";
 
    return stream;
  }

Member Data Documentation

◆ _begin_index_

template<typename Key, typename Val>

Size gum::HashTable< Key, Val >::_begin_index_ {std::numeric_limits< Size >::max()}

mutableprivate

Returns where the begin index should be.

Beware: the beginning of a HashTable is the end of its nodes vector, i.e., the Bucket at the highest index in nodes. This enables a slightly faster parsing than if it were the lowest index.

Warning: std::numeric_limits<Size>::max() means that we do not know where the beginning of the table really is (this can mean either that there is not yet any element in the hash table or that an erase operation has been performed and that we lost track of the element that should correspond to the begin().

Returns: Returns where the begin index should be.

Definition at line 1560 of file hashTable.h.

1560{std::numeric_limits< Size >::max()};

Referenced by HashTable().

◆ _hash_func_

template<typename Key, typename Val>

HashFunc< Key > gum::HashTable< Key, Val >::_hash_func_

private

The function used to hash keys (may change when the table is resized).

Definition at line 1538 of file hashTable.h.

Referenced by _create_(), _insert_(), erase(), erase(), exists(), exists(), getWithDefault(), key(), operator[](), operator[](), operator[](), operator[](), resize(), set(), tryGet(), tryGet(), tryGet(), tryGet(), and tryGetKey().

◆ _key_uniqueness_policy_

template<typename Key, typename Val>

bool gum::HashTable< Key, Val >::_key_uniqueness_policy_ {true}

private

Shall we check for key uniqueness in the table?

Definition at line 1544 of file hashTable.h.

1544{true};

Referenced by HashTable(), HashTable(), _insert_(), keyUniquenessPolicy(), and setKeyUniquenessPolicy().

◆ _nb_elements_

template<typename Key, typename Val>

Size gum::HashTable< Key, Val >::_nb_elements_ {Size(0)}

private

Number of elements of type Val stored in the hash table.

Definition at line 1535 of file hashTable.h.

1535{Size(0)};

Referenced by _erase_(), begin(), begin(), beginSafe(), beginSafe(), cbegin(), cbeginSafe(), empty(), map(), map(), map(), operator==(), resize(), and size().

◆ _nodes_

template<typename Key, typename Val>

std::vector< HashTableList< Key, Val > > gum::HashTable< Key, Val >::_nodes_

private

The hash table is represented as a vector of chained lists.

' __nodes' is this very vector.

Definition at line 1529 of file hashTable.h.

Referenced by HashTable(), _create_(), _erase_(), _insert_(), clear(), erase(), erase(), exists(), exists(), getWithDefault(), key(), gum::HashTableList< Key, Val >::operator<<, gum::HashTableList< Key, Val >::operator<<, operator[](), operator[](), operator[](), operator[](), set(), tryGet(), tryGet(), tryGet(), tryGet(), and tryGetKey().

◆ _resize_policy_

template<typename Key, typename Val>

bool gum::HashTable< Key, Val >::_resize_policy_ {true}

private

Is resizing performed automatically?

Definition at line 1541 of file hashTable.h.

1541{true};

Referenced by HashTable(), HashTable(), resize(), resizePolicy(), and setResizePolicy().

◆ _safe_iterators_

template<typename Key, typename Val>

std::vector< HashTableConstIteratorSafe< Key, Val >* > gum::HashTable< Key, Val >::_safe_iterators_

mutableprivate

The list of safe iterators pointing to the hash table.

Definition at line 1563 of file hashTable.h.

Referenced by _clearIterators_(), _erase_(), and operator=().

◆ _size_

template<typename Key, typename Val>

Size gum::HashTable< Key, Val >::_size_

private

The number of nodes in vector ' __nodes'.

Definition at line 1532 of file hashTable.h.

Referenced by HashTable(), HashTable(), HashTable(), HashTable(), _copy_(), capacity(), clear(), gum::HashTableList< Key, Val >::operator<<, gum::HashTableList< Key, Val >::operator<<, and resize().

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

agrum/base/core/hashTable.h
agrum/base/core/hashTable_tpl.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Bucket

◆ const_iterator

◆ const_iterator_safe

◆ const_pointer

◆ const_reference

◆ difference_type

◆ iterator

◆ iterator_safe

◆ key_type

◆ mapped_type

◆ pointer

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ HashTable() [1/4]

◆ HashTable() [2/4]

◆ HashTable() [3/4]

◆ HashTable() [4/4]

◆ ~HashTable()

Member Function Documentation

◆ _clearIterators_()

◆ _copy_()

◆ _create_()

◆ _erase_()

◆ _insert_()

◆ begin() [1/2]

◆ begin() [2/2]

◆ beginSafe() [1/2]

◆ beginSafe() [2/2]

◆ capacity()

◆ cbegin()

◆ cbeginSafe()

◆ cend()

◆ cendSafe()

◆ clear()

◆ emplace()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ endSafe() [1/2]

◆ endSafe() [2/2]

◆ erase() [1/4]

◆ erase() [2/4]

◆ erase() [3/4]

◆ erase() [4/4]

◆ eraseAllVal()

◆ eraseByVal()

◆ exists() [1/2]

◆ exists() [2/2]

◆ getWithDefault() [1/2]

◆ getWithDefault() [2/2]

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ key()

◆ keyByVal()

◆ keyUniquenessPolicy()

◆ map() [1/4]

◆ map() [2/4]

◆ map() [3/4]

◆ map() [4/4]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]() [1/4]

◆ operator[]() [2/4]

◆ operator[]() [3/4]

◆ operator[]() [4/4]

◆ reset()

◆ resize()

◆ resizePolicy()