aGrUM  0.13.2
gum::HashTable< Key, Val, Alloc > Class Template Reference

The class for generic Hash Tables. More...

#include <agrum/core/hashTable.h>

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

Public Member Functions

template<typename... Args>
INLINE HashTable< Key, Val, Alloc >::value_typeemplace (Args &&...args)
 
template<typename Mount , typename OtherAlloc >
HashTable< Key, Mount, OtherAlloc > INLINE map (Mount(*f)(Val), Size size, bool resize_pol, bool key_uniqueness_pol) const
 
template<typename Mount , typename OtherAlloc >
HashTable< Key, Mount, OtherAlloc > INLINE map (Mount(*f)(Val &), Size size, bool resize_pol, bool key_uniqueness_pol) const
 
template<typename Mount , typename OtherAlloc >
HashTable< Key, Mount, OtherAlloc > INLINE map (Mount(*f)(const Val &), Size size, bool resize_pol, bool key_uniqueness_pol) const
 
template<typename Mount , typename OtherAlloc >
HashTable< Key, Mount, OtherAlloc > INLINE map (const Mount &val, Size size, bool resize_pol, bool key_uniqueness_pol) const
 
template<typename OtherAlloc >
INLINE bool operator!= (const HashTable< Key, Val, OtherAlloc > &from) const
 
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. More...
 
 HashTable (std::initializer_list< std::pair< Key, Val > > list)
 Initializer list constructor. More...
 
 HashTable (const HashTable< Key, Val, Alloc > &from)
 Copy constructor. More...
 
template<typename OtherAlloc >
 HashTable (const HashTable< Key, Val, OtherAlloc > &from)
 Generalized copy constructor. More...
 
 HashTable (HashTable< Key, Val, Alloc > &&from)
 Move constructor. More...
 
 ~HashTable ()
 Class destructor. More...
 
Operators
HashTable< Key, Val, Alloc > & operator= (const HashTable< Key, Val, Alloc > &from)
 Copy operator. More...
 
template<typename OtherAlloc >
HashTable< Key, Val, Alloc > & operator= (const HashTable< Key, Val, OtherAlloc > &from)
 Generalized copy operator. More...
 
HashTable< Key, Val, Alloc > & operator= (HashTable< Key, Val, Alloc > &&from)
 Move operator. More...
 
Val & operator[] (const Key &key)
 Returns a reference on the value the key of which is passed in argument. More...
 
const Val & operator[] (const Key &key) const
 returns a reference on the value the key of which is passed in argument More...
 
template<typename OtherAlloc >
bool operator== (const HashTable< Key, Val, OtherAlloc > &from) const
 Checks whether two hashtables contain the same elements. More...
 
template<typename OtherAlloc >
bool operator!= (const HashTable< Key, Val, OtherAlloc > &from) const
 Checks whether two hashtables contain different sets of elements. More...
 
Fine tuning
Size capacity () const noexcept
 Returns the number of slots in the 'nodes' vector of the hashtable. More...
 
void resize (Size new_size)
 Changes the number of slots in the 'nodes' vector of the hash table. More...
 
void setResizePolicy (const bool new_policy) noexcept
 Enables the user to change dynamically the resizing policy. More...
 
bool resizePolicy () const noexcept
 Returns the current resizing policy. More...
 
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. More...
 
bool keyUniquenessPolicy () const noexcept
 Returns the current checking policy. More...
 
Accessors / Modifiers
Size size () const noexcept
 Returns the number of elements stored into the hashtable. More...
 
bool exists (const Key &key) const
 Checks whether there exists an element with a given key in the hashtable. More...
 
value_typeinsert (const Key &key, const Val &val)
 Adds a new element (actually a copy of this element) into the hash table. More...
 
value_typeinsert (Key &&key, Val &&val)
 Moves a new element in the hash table. More...
 
value_typeinsert (const std::pair< Key, Val > &elt)
 Adds a new element (actually a copy of this element) into the hash table. More...
 
value_typeinsert (std::pair< Key, Val > &&elt)
 Moves a new element in the hash table. More...
 
template<typename... Args>
value_typeemplace (Args &&...args)
 Emplace a new element into the hashTable. More...
 
mapped_typegetWithDefault (const Key &key, const Val &default_value)
 Returns a reference on the element the key of which is passed in argument. More...
 
mapped_typegetWithDefault (Key &&key, Val &&default_value)
 Returns a reference on the element the key of which is passed in argument. More...
 
void set (const Key &key, const Val &default_value)
 Add a new property or modify it if it already existed. More...
 
void reset (const Key &key)
 Removes a property (i.e., remove an element). More...
 
void erase (const Key &key)
 Removes a given element from the hash table. More...
 
void erase (const iterator_safe &iter)
 Removes a given element from the hash table. More...
 
void erase (const const_iterator_safe &iter)
 Removes a given element from the hash table. More...
 
void eraseByVal (const Val &val)
 Removes a given element from the hash table. More...
 
const Key & keyByVal (const Val &val) const
 Returns a reference on the key given a value. More...
 
const Key & key (const Key &key) const
 Returns a reference on a given key. More...
 
void eraseAllVal (const Val &val)
 Removes all the elements having a certain value from the hash table. More...
 
void clear ()
 Removes all the elements in the hash table. More...
 
bool empty () const noexcept
 Indicates whether the hash table is empty. More...
 
template<typename Mount , typename OtherAlloc = typename Alloc::template rebind< std::pair< Key, Mount > >::other>
HashTable< Key, Mount, OtherAlloc > map (Mount(*f)(Val), 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. More...
 
template<typename Mount , typename OtherAlloc = typename Alloc::template rebind< std::pair< Key, Mount > >::other>
HashTable< Key, Mount, OtherAlloc > map (Mount(*f)(Val &), 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. More...
 
template<typename Mount , typename OtherAlloc = typename Alloc::template rebind< std::pair< Key, Mount > >::other>
HashTable< Key, Mount, OtherAlloc > map (Mount(*f)(const Val &), 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. More...
 
template<typename Mount , typename OtherAlloc = typename Alloc::template rebind< std::pair< Key, Mount > >::other>
HashTable< Key, Mount, OtherAlloc > map (const Mount &val, 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. More...
 

Public Types

using Bucket = HashTableBucket< Key, Val >
 The buckets where data are stored. More...
 
using BucketAllocator = typename Alloc::template rebind< Bucket >::other
 The Bucket allocator. More...
 
using key_type = Key
 Types for STL compliance. More...
 
using mapped_type = Val
 Types for STL compliance. More...
 
using value_type = std::pair< const Key, Val >
 Types for STL compliance. More...
 
using reference = value_type &
 Types for STL compliance. More...
 
using const_reference = const value_type &
 Types for STL compliance. More...
 
using pointer = value_type *
 Types for STL compliance. More...
 
using const_pointer = const value_type *
 Types for STL compliance. More...
 
using size_type = std::size_t
 Types for STL compliance. More...
 
using difference_type = std::ptrdiff_t
 Types for STL compliance. More...
 
using allocator_type = Alloc
 Types for STL compliance. More...
 
using iterator = HashTableIterator< Key, Val >
 Types for STL compliance. More...
 
using const_iterator = HashTableConstIterator< Key, Val >
 Types for STL compliance. More...
 
using iterator_safe = HashTableIteratorSafe< Key, Val >
 Types for STL compliance. More...
 
using const_iterator_safe = HashTableConstIteratorSafe< Key, Val >
 Types for STL compliance. More...
 

Friends

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

Iterators

const iteratorend () noexcept
 Returns the unsafe iterator pointing to the end of the hashtable. More...
 
const const_iteratorend () const noexcept
 Returns the unsafe const_iterator pointing to the end of the hashtable. More...
 
const const_iteratorcend () const noexcept
 Returns the unsafe const_iterator pointing to the end of the hashtable. More...
 
iterator begin ()
 Returns an unsafe iterator pointing to the beginning of the hashtable. More...
 
const_iterator begin () const
 Returns an unsafe const_iterator pointing to the beginning of the hashtable. More...
 
const_iterator cbegin () const
 Returns an unsafe const_iterator pointing to the beginning of the hashtable. More...
 
const iterator_safeendSafe () noexcept
 Returns the safe iterator pointing to the end of the hashtable. More...
 
const const_iterator_safeendSafe () const noexcept
 Returns the safe const_iterator pointing to the end of the hashtable. More...
 
const const_iterator_safecendSafe () const noexcept
 Returns the safe const_iterator pointing to the end of the hashtable. More...
 
iterator_safe beginSafe ()
 Returns the safe iterator pointing to the beginning of the hashtable. More...
 
const_iterator_safe beginSafe () const
 Returns the safe const_iterator pointing to the beginning of the hashtable. More...
 
const_iterator_safe cbeginSafe () const
 Returns the safe const_iterator pointing to the beginning of the hashtable. More...
 
static const iteratorend4Statics ()
 Returns the end iterator for other classes' statics (read the detailed description of this method). More...
 
static const const_iteratorconstEnd4Statics ()
 Returns the end iterator for other classes' statics (read the detailed description of this method). More...
 
static const iterator_safeendSafe4Statics ()
 Returns the end iterator for other classes' statics (read the detailed description of this method). More...
 
static const const_iterator_safeconstEndSafe4Statics ()
 Returns the end iterator for other classes' statics (read the detailed description of this method). More...
 

Detailed Description

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
class gum::HashTable< Key, Val, Alloc >

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 wether 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 );
Template Parameters
KeyThe type for keys in a gum::HashTable.
ValThe type for values in a gum::HashTable.
AllocThe gum::HashTable allocator.

Definition at line 676 of file hashTable.h.

Member Typedef Documentation

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::allocator_type = Alloc

Types for STL compliance.

Definition at line 689 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::Bucket = HashTableBucket< Key, Val >

The buckets where data are stored.

Definition at line 697 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::BucketAllocator = typename Alloc::template rebind< Bucket >::other

The Bucket allocator.

Definition at line 700 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::const_iterator = HashTableConstIterator< Key, Val >

Types for STL compliance.

Definition at line 691 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::const_iterator_safe = HashTableConstIteratorSafe< Key, Val >

Types for STL compliance.

Definition at line 693 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::const_pointer = const value_type*

Types for STL compliance.

Definition at line 686 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::const_reference = const value_type&

Types for STL compliance.

Definition at line 684 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 688 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::iterator = HashTableIterator< Key, Val >

Types for STL compliance.

Definition at line 690 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::iterator_safe = HashTableIteratorSafe< Key, Val >

Types for STL compliance.

Definition at line 692 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::key_type = Key

Types for STL compliance.

Definition at line 680 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::mapped_type = Val

Types for STL compliance.

Definition at line 681 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::pointer = value_type*

Types for STL compliance.

Definition at line 685 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::reference = value_type&

Types for STL compliance.

Definition at line 683 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::size_type = std::size_t

Types for STL compliance.

Definition at line 687 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
using gum::HashTable< Key, Val, Alloc >::value_type = std::pair< const Key, Val >

Types for STL compliance.

Definition at line 682 of file hashTable.h.

Constructor & Destructor Documentation

template<typename Key , typename Val , typename Alloc >
gum::HashTable< Key, Val, Alloc >::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_paramThe initial size of the gum::HashTable.
resize_polThe policy for resizing the hashtable when new elements are added (possible values: true = automatic resize and false = manual resize).
key_uniqueness_polUniqueness policy : should we prevent inserting the same key more than once in the table?

Definition at line 379 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__create(), gum::__hashTableLog2(), gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy, gum::HashTable< Key, Val, Alloc >::__resize_policy, and gum::HashTable< Key, Val, Alloc >::__size.

381  :
382  // size must be >= 2 else we lose all the bits of the hash function
383  __size{Size(1) << __hashTableLog2(std::max(Size(2), size_param))},
384  __resize_policy{resize_pol}, __key_uniqueness_policy{key_uniqueness_pol} {
385  // for debugging purposes
386  GUM_CONSTRUCTOR(HashTable);
387 
388  // finalize the creation
389  __create(__size);
390  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
void __create(Size size)
Used by all default constructors (general and specialized).
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730
unsigned int __hashTableLog2(const Size &nb)
Returns the size in bits - 1 necessary to store the smallest power of 2 greater or equal to nb...

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc >
gum::HashTable< Key, Val, Alloc >::HashTable ( std::initializer_list< std::pair< Key, Val > >  list)
explicit

Initializer list constructor.

Parameters
listThe initialized list.

Definition at line 393 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__create(), gum::__hashTableLog2(), gum::HashTable< Key, Val, Alloc >::__size, and gum::HashTable< Key, Val, Alloc >::insert().

394  :
395  // size must be >= 2 else we lose all the bits of the hash function
397  std::max< Size >(Size(2), Size(list.size()) / 2))} {
398  // for debugging purposes
399  GUM_CONSTRUCTOR(HashTable);
400 
401  // setup the __nodes vector (contains only empty lists)
402  __create(__size);
403 
404  // insert all the elements
405  for (const auto& elt : list) {
406  insert(elt);
407  }
408  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
void __create(Size size)
Used by all default constructors (general and specialized).
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
unsigned int __hashTableLog2(const Size &nb)
Returns the size in bits - 1 necessary to store the smallest power of 2 greater or equal to nb...
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc>
gum::HashTable< Key, Val, Alloc >::HashTable ( const HashTable< Key, Val, Alloc > &  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
fromThe gum::HashTable to copy.

Definition at line 411 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__copy(), gum::HashTable< Key, Val, Alloc >::__create(), gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy, gum::HashTable< Key, Val, Alloc >::__resize_policy, and gum::HashTable< Key, Val, Alloc >::__size.

412  :
413  __size{table.__size},
414  __resize_policy{table.__resize_policy},
415  __key_uniqueness_policy{table.__key_uniqueness_policy},
416  __begin_index{table.__begin_index} {
417  // for debugging purposes
418  GUM_CONS_CPY(HashTable);
419 
420  // setup the __nodes vector (contains only empty lists)
421  __create(__size);
422 
423  // fill with the content of table
424  __copy(table);
425  }
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
void __create(Size size)
Used by all default constructors (general and specialized).
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
void __copy(const HashTable< Key, Val, OtherAlloc > &table)
A function used to perform copies of HashTables.

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc >
template<typename OtherAlloc >
gum::HashTable< Key, Val, Alloc >::HashTable ( const HashTable< Key, Val, OtherAlloc > &  from)

Generalized 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 'table'

Parameters
fromThe gum::HashTable to copy.

Definition at line 429 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__copy(), gum::HashTable< Key, Val, Alloc >::__create(), gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy, gum::HashTable< Key, Val, Alloc >::__resize_policy, and gum::HashTable< Key, Val, Alloc >::__size.

430  :
431  __size{table.__size},
432  __resize_policy{table.__resize_policy},
433  __key_uniqueness_policy{table.__key_uniqueness_policy},
434  __begin_index{table.__begin_index} {
435  // for debugging purposes
436  GUM_CONS_CPY(HashTable);
437 
438  // setup the __nodes vector (contains only empty lists)
439  __create(__size);
440 
441  // fill with the content of table
442  __copy(table);
443  }
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
void __create(Size size)
Used by all default constructors (general and specialized).
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
void __copy(const HashTable< Key, Val, OtherAlloc > &table)
A function used to perform copies of HashTables.

+ Here is the call graph for this function:

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

Move constructor.

Parameters
fromThe gum::HashTable to move.

Definition at line 446 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy, gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::__resize_policy, and gum::HashTable< Key, Val, Alloc >::__safe_iterators.

446  :
447  __nodes(std::move(table.__nodes)), __size{table.__size},
448  __nb_elements{table.__nb_elements}, __hash_func{table.__hash_func},
449  __resize_policy{table.__resize_policy},
450  __key_uniqueness_policy{table.__key_uniqueness_policy},
451  __begin_index{table.__begin_index},
452  __safe_iterators(std::move(table.__safe_iterators)),
453  __alloc(std::move(table.__alloc)) {
454  // for debugging purposes
455  table.__size = 0;
456  GUM_CONS_MOV(HashTable);
457  }
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
std::vector< HashTableConstIteratorSafe< Key, Val > * > __safe_iterators
The list of safe iterators pointing to the hash table.
Definition: hashTable.h:1750
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
template<typename Key , typename Val , typename Alloc >
INLINE gum::HashTable< Key, Val, Alloc >::~HashTable ( )

Class destructor.

Definition at line 481 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__clearIterators(), and gum::HashTable< Key, Val, Alloc >::operator=().

481  {
482  // for debugging purposes
483  GUM_DESTRUCTOR(HashTable);
484 
485  // update all the registered iterators: they should now point to nullptr
486  // and their hashtable should be set to nullptr
488  }
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
void __clearIterators()
Clear all the safe iterators.

+ Here is the call graph for this function:

Member Function Documentation

template<typename Key , typename Val , typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::__clearIterators ( )
private

Clear all the safe iterators.

Definition at line 460 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__safe_iterators, and gum::HashTable< Key, Val, Alloc >::clear().

Referenced by gum::HashTable< Key, Val, Alloc >::clear(), and gum::HashTable< Key, Val, Alloc >::~HashTable().

460  {
461  Size len = Size(__safe_iterators.size());
462  for (Size i = 0; i < len; ++i)
463  __safe_iterators[i]->clear();
464  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
std::vector< HashTableConstIteratorSafe< Key, Val > * > __safe_iterators
The list of safe iterators pointing to the hash table.
Definition: hashTable.h:1750
void clear()
Removes all the elements in the hash table.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key, typename Val, typename Alloc >
template<typename OtherAlloc >
void gum::HashTable< Key, Val, Alloc >::__copy ( const HashTable< Key, Val, OtherAlloc > &  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
tableThe gum::HashTable to copy.
Template Parameters
OtherAllocThe other gum::HashTable allocator.

Definition at line 307 of file hashTable_tpl.h.

References gum::HashTableList< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::__size, and gum::HashTableList< Key, Val, Alloc >::clear().

Referenced by gum::HashTable< Key, Val, Alloc >::HashTable(), and gum::HashTable< Key, Val, Alloc >::operator=().

308  {
309  // in debug mode, check that this and table have '__nodes' arrays of the
310  // same size
311  GUM_ASSERT(table.__size == __size);
312 
313  // try to fill the array of chained lists
314  for (Size i = 0; i < table.__size; ++i) {
315  try {
316  __nodes[i] = table.__nodes[i];
317  } catch (...) {
318  // here we could allocate the __nodes[j], j=0..i-1, so we should
319  // deallocate them
320  for (Size j = 0; j < __size; ++j)
321  __nodes[j].clear();
322 
323  __nb_elements = 0;
324 
325  // propagate the exception
326  throw;
327  }
328  }
329 
330  __nb_elements = table.__nb_elements;
331  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
void clear()
Removes all the elements in the hash table.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::__create ( Size  size)
private

Used by all default constructors (general and specialized).

Parameters
sizeThe size of the gum::HashTable to create.

Definition at line 362 of file hashTable_tpl.h.

Referenced by gum::HashTable< Key, Val, Alloc >::HashTable().

362  {
363  // setup the __nodes vector (contains only empty lists)
364  __nodes.resize(size);
365 
366  for (auto& list : __nodes) {
367  list.setAllocator(__alloc);
368  }
369 
370  // set up properly the hash function
371  __hash_func.resize(size);
372 
373  // make sure the end() iterator is constructed properly
374  end4Statics();
375  endSafe4Statics();
376  }
static const iterator_safe & endSafe4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...
Size size() const noexcept
Returns the number of elements stored into the hashtable.
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
static const iterator & end4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...

+ Here is the caller graph for this function:

template<typename Key, typename Val, typename Alloc >
void gum::HashTable< Key, Val, Alloc >::__erase ( HashTableBucket< Key, Val > *  bucket,
Size  index 
)
private

Erases a given bucket.

Definition at line 986 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::__safe_iterators, and gum::HashTable< Key, Val, Alloc >::empty().

Referenced by gum::HashTable< Key, Val, Alloc >::erase(), gum::HashTable< Key, Val, Alloc >::eraseAllVal(), and gum::HashTable< Key, Val, Alloc >::eraseByVal().

987  {
988  if (bucket == nullptr) return;
989 
990  // update the registered iterators pointing to this bucket
991  for (auto iter : __safe_iterators) {
992  if (iter->__bucket == bucket) {
993  iter->operator++();
994  iter->__next_bucket = iter->__bucket;
995  iter->__bucket = nullptr;
996  } else if (iter->__next_bucket == bucket) {
997  iter->__bucket = bucket;
998  iter->operator++();
999  iter->__next_bucket = iter->__bucket;
1000  iter->__bucket = nullptr;
1001  }
1002  }
1003 
1004  // remove the element from the __nodes vector
1005  __nodes[index].erase(bucket);
1006 
1007  --__nb_elements;
1008 
1009  if ((index == __begin_index) && __nodes[index].empty()) {
1010  __begin_index = std::numeric_limits< Size >::max();
1011  }
1012  }
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
std::vector< HashTableConstIteratorSafe< Key, Val > * > __safe_iterators
The list of safe iterators pointing to the hash table.
Definition: hashTable.h:1750
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
bool empty() const noexcept
Indicates whether the hash table is empty.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
void gum::HashTable< Key, Val, Alloc >::__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
bucketThe bucket inserted in the hash table.
Exceptions
DuplicateElementis 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 837 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy, gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::__resize_policy, gum::HashTable< Key, Val, Alloc >::__size, gum::HashTableConst::default_mean_val_by_slot, gum::HashTable< Key, Val, Alloc >::exists(), GUM_ERROR, gum::HashTableBucket< Key, Val >::key(), and gum::HashTable< Key, Val, Alloc >::resize().

Referenced by gum::HashTable< Key, Val, Alloc >::emplace(), and gum::HashTable< Key, Val, Alloc >::insert().

837  {
838  Size hash_key = __hash_func(bucket->key());
839 
840  // check that there does not already exist an element with the same key
841  if (__key_uniqueness_policy && __nodes[hash_key].exists(bucket->key())) {
842  // remove the bucket from memory
843  __alloc.destroy(bucket);
844  __alloc.deallocate(bucket, 1);
845  GUM_ERROR(DuplicateElement,
846  "the hashtable contains an element with the same key");
847  }
848 
849  // check whether there is sufficient space to insert the new pair
850  // if not, resize the current hashtable
851  if (__resize_policy
853  resize(__size << 1);
854  hash_key = __hash_func(bucket->key());
855  }
856 
857  // add the new pair
858  __nodes[hash_key].insert(bucket);
859  ++__nb_elements;
860 
861  // recompute the index of the beginning of the hashtable if possible
862  // WARNING: if __begin_index = std::numeric_limits<Size>::max (), we CANNOT
863  // recompute the index because we cannot know whether the current index is
864  // equal to max because there was no element in the hashtable or whether a
865  // previous __erase() has set the index to max.
866  if (__begin_index < hash_key) { __begin_index = hash_key; }
867  }
void resize(Size new_size)
Changes the number of slots in the &#39;nodes&#39; vector of the hash table.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
static constexpr unsigned int default_mean_val_by_slot
The average number of elements admissible by slots.
Definition: hashTable.h:84
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE HashTable< Key, Val, Alloc >::iterator gum::HashTable< Key, Val, Alloc >::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 632 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, and gum::HashTable< Key, Val, Alloc >::end().

Referenced by gum::Regress< GUM_SCALAR, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::__findRetrogradeVariables(), gum::MultiDimFunctionGraphOperator< GUM_SCALAR, FUNCTOR, TerminalNodePolicy >::__findRetrogradeVariables(), gum::learning::Miic::_orientation_3off2(), gum::learning::Miic::_orientation_miic(), gum::prm::PRMSystem< GUM_SCALAR >::begin(), gum::Estimator< GUM_SCALAR >::confidence(), gum::HashTable< Key, Val, Alloc >::keyByVal(), gum::HashTable< Key, Val, Alloc >::map(), gum::HashTable< Key, Val, Alloc >::operator==(), and gum::SmallObjectAllocator::~SmallObjectAllocator().

632  {
633  // if the table is empty, make the begin and end point to the same element
634  if (__nb_elements == 0)
635  return iterator{end()};
636  else
637  return iterator{*this};
638  }
const iterator & end() noexcept
Returns the unsafe iterator pointing to the end of the hashtable.
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
HashTableIterator< Key, Val > iterator
Types for STL compliance.
Definition: hashTable.h:690

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE HashTable< Key, Val, Alloc >::const_iterator gum::HashTable< Key, Val, Alloc >::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 642 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, and gum::HashTable< Key, Val, Alloc >::end().

642  {
643  // if the table is empty, make the begin and end point to the same element
644  if (__nb_elements == 0)
645  return const_iterator{end()};
646  else
647  return const_iterator{*this};
648  }
const iterator & end() noexcept
Returns the unsafe iterator pointing to the end of the hashtable.
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
HashTableConstIterator< Key, Val > const_iterator
Types for STL compliance.
Definition: hashTable.h:691

+ Here is the call graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE HashTable< Key, Val, Alloc >::iterator_safe gum::HashTable< Key, Val, Alloc >::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 692 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, and gum::HashTable< Key, Val, Alloc >::endSafe().

Referenced by gum::SetTerminalNodePolicy< GUM_SCALAR >::clearAllTerminalNodes(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::LeafAggregator::leavesMap(), gum::Set< Key, Alloc >::operator*=(), gum::StructuredPlaner< GUM_SCALAR >::optimalPolicy2String(), gum::SetTerminalNodePolicy< GUM_SCALAR >::terminalNodeId(), gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::toDot(), gum::ITI< AttributeSelection, isScalar >::updateGraph(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::~IncrementalGraphLearner(), gum::MultiDimFunctionGraphOperator< GUM_SCALAR, FUNCTOR, TerminalNodePolicy >::~MultiDimFunctionGraphOperator(), and gum::Regress< GUM_SCALAR, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::~Regress().

692  {
693  // if the table is empty, make the begin and end point to the same element
694  if (__nb_elements == 0)
695  return iterator_safe{endSafe()};
696  else
697  return iterator_safe{*this};
698  }
const iterator_safe & endSafe() noexcept
Returns the safe iterator pointing to the end of the hashtable.
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
HashTableIteratorSafe< Key, Val > iterator_safe
Types for STL compliance.
Definition: hashTable.h:692

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE HashTable< Key, Val, Alloc >::const_iterator_safe gum::HashTable< Key, Val, Alloc >::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 702 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, and gum::HashTable< Key, Val, Alloc >::endSafe().

702  {
703  // if the table is empty, make the begin and end point to the same element
704  if (__nb_elements == 0)
705  return const_iterator_safe{endSafe()};
706  else
707  return const_iterator_safe{*this};
708  }
const iterator_safe & endSafe() noexcept
Returns the safe iterator pointing to the end of the hashtable.
HashTableConstIteratorSafe< Key, Val > const_iterator_safe
Types for STL compliance.
Definition: hashTable.h:693
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721

+ Here is the call graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE Size gum::HashTable< Key, Val, Alloc >::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 737 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__size.

Referenced by gum::ArcGraphPart::ArcGraphPart(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::capacity(), gum::Set< Key, Alloc >::capacity(), and gum::BijectionImplementation< T1, T2, Alloc, Gen >::operator=().

737  {
738  return __size;
739  }
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE HashTable< Key, Val, Alloc >::const_iterator gum::HashTable< Key, Val, Alloc >::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 652 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, and gum::HashTable< Key, Val, Alloc >::cend().

Referenced by gum::DAGCycleDetector::__addWeightedSet(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::__copy(), gum::DAGCycleDetector::__delWeightedSet(), gum::DAGCycleDetector::__restrictWeightedSet(), gum::credal::InferenceEngine< GUM_SCALAR >::_updateCredalSets(), gum::DAGCycleDetector::addArc(), gum::DAGCycleDetector::eraseArc(), gum::HashTable< Key, Val, Alloc >::eraseByVal(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::Set< Key, Alloc >::hashMap(), gum::Set< Key, Alloc >::listMap(), gum::Set< Key, Alloc >::operator*(), gum::Set< Key, Alloc >::operator+(), gum::Set< Key, Alloc >::operator-(), gum::Set< Key, Alloc >::operator==(), and gum::learning::StructuralConstraintSliceOrder::StructuralConstraintSliceOrder().

652  {
653  // if the table is empty, make the begin and end point to the same element
654  if (__nb_elements == 0)
655  return const_iterator{cend()};
656  else
657  return const_iterator{*this};
658  }
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
const const_iterator & cend() const noexcept
Returns the unsafe const_iterator pointing to the end of the hashtable.
HashTableConstIterator< Key, Val > const_iterator
Types for STL compliance.
Definition: hashTable.h:691

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE HashTable< Key, Val, Alloc >::const_iterator_safe gum::HashTable< Key, Val, Alloc >::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 712 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, and gum::HashTable< Key, Val, Alloc >::cendSafe().

Referenced by gum::IMDDI< AttributeSelection, isScalar >::__rebuildFunctionGraph(), gum::LeastSquareTestPolicy< GUM_SCALAR >::add(), gum::ContingencyTable< Idx, GUM_SCALAR >::attrABeginSafe(), gum::ContingencyTable< Idx, GUM_SCALAR >::attrBBeginSafe(), gum::SetTerminalNodePolicy< GUM_SCALAR >::beginValues(), and gum::HashTable< Key, Val, Alloc >::eraseAllVal().

712  {
713  // if the table is empty, make the begin and end point to the same element
714  if (__nb_elements == 0)
715  return const_iterator_safe{cendSafe()};
716  else
717  return const_iterator_safe{*this};
718  }
HashTableConstIteratorSafe< Key, Val > const_iterator_safe
Types for STL compliance.
Definition: hashTable.h:693
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
const const_iterator_safe & cendSafe() const noexcept
Returns the safe const_iterator pointing to the end of the hashtable.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::const_iterator & gum::HashTable< Key, Val, Alloc >::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 622 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::__HashTableIterEnd.

Referenced by gum::DAGCycleDetector::__addWeightedSet(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::__copy(), gum::DAGCycleDetector::__delWeightedSet(), gum::DAGCycleDetector::__restrictWeightedSet(), gum::credal::InferenceEngine< GUM_SCALAR >::_updateCredalSets(), gum::DAGCycleDetector::addArc(), gum::HashTable< Key, Val, Alloc >::cbegin(), gum::DAGCycleDetector::eraseArc(), gum::HashTable< Key, Val, Alloc >::eraseByVal(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::Set< Key, Alloc >::hashMap(), gum::Set< Key, Alloc >::listMap(), gum::Set< Key, Alloc >::operator*(), gum::Set< Key, Alloc >::operator+(), gum::Set< Key, Alloc >::operator-(), gum::Set< Key, Alloc >::operator==(), and gum::learning::StructuralConstraintSliceOrder::StructuralConstraintSliceOrder().

622  {
623  // note that, here, we know for sure that HashTableIterEnd has been properly
624  // initialized as it is initialized by end4Statics, which is called by
625  // all hashtables' constructors
626  return *(reinterpret_cast< const const_iterator* >(
628  }
static const HashTableIterator< int, int > * __HashTableIterEnd
The unsafe iterator used by everyone.
Definition: hashTable.h:1831
HashTableConstIterator< Key, Val > const_iterator
Types for STL compliance.
Definition: hashTable.h:691

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::const_iterator_safe & gum::HashTable< Key, Val, Alloc >::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 682 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::__HashTableIterEndSafe.

Referenced by gum::IMDDI< AttributeSelection, isScalar >::__rebuildFunctionGraph(), gum::LeastSquareTestPolicy< GUM_SCALAR >::add(), gum::ContingencyTable< Idx, GUM_SCALAR >::attrAEndSafe(), gum::ContingencyTable< Idx, GUM_SCALAR >::attrBEndSafe(), gum::HashTable< Key, Val, Alloc >::cbeginSafe(), gum::HashTable< Key, Val, Alloc >::eraseAllVal(), gum::SetTerminalNodePolicy< GUM_SCALAR >::hasValue(), and gum::ITI< AttributeSelection, isScalar >::updateGraph().

682  {
683  // note that, here, we know for sure that HashTableIterEnd has been properly
684  // initialized as it is initialized by end4Statics, which is called by
685  // all hashtables' constructors
686  return *(reinterpret_cast< const const_iterator_safe* >(
688  }
HashTableConstIteratorSafe< Key, Val > const_iterator_safe
Types for STL compliance.
Definition: hashTable.h:693
static const HashTableIteratorSafe< int, int > * __HashTableIterEndSafe
The safe iterator used by everyone.
Definition: hashTable.h:1834

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::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 467 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__clearIterators(), gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::__nodes, and gum::HashTable< Key, Val, Alloc >::__size.

Referenced by gum::HashTable< Key, Val, Alloc >::__clearIterators(), gum::Regress< GUM_SCALAR, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::__findRetrogradeVariables(), gum::MultiDimFunctionGraphOperator< GUM_SCALAR, FUNCTOR, TerminalNodePolicy >::__findRetrogradeVariables(), gum::credal::InferenceEngine< GUM_SCALAR >::_initExpectations(), gum::credal::InferenceEngine< GUM_SCALAR >::_initMarginals(), gum::credal::InferenceEngine< GUM_SCALAR >::_initMarginalSets(), gum::credal::MultipleInferenceEngine< GUM_SCALAR, BNInferenceEngine >::_initThreadsData(), gum::credal::InferenceEngine< GUM_SCALAR >::_repetitiveInit(), gum::credal::CredalNet< GUM_SCALAR >::approximatedBinarization(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::BijectionImplementation(), gum::Estimator< GUM_SCALAR >::clear(), gum::Set< Key, Alloc >::clear(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::clear(), gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::clear(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::clear(), gum::SetTerminalNodePolicy< GUM_SCALAR >::clearAllTerminalNodes(), gum::credal::InferenceEngine< GUM_SCALAR >::eraseAllEvidence(), gum::MultiDimSparse< GUM_SCALAR >::fill(), gum::credal::InferenceEngine< GUM_SCALAR >::insertEvidence(), gum::credal::InferenceEngine< GUM_SCALAR >::insertEvidenceFile(), gum::credal::InferenceEngine< GUM_SCALAR >::insertQuery(), gum::credal::InferenceEngine< GUM_SCALAR >::insertQueryFile(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::operator=(), gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::operator=(), gum::HashTable< Key, Val, Alloc >::operator=(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::PriorityQueueImplementation(), gum::SequenceImplementation< Key, Alloc, Gen >::resize(), and gum::Chi2::setConfidenceProba().

467  {
468  // update all the registered iterators: they should now point to nullptr
469  // and they are positioned to the end of the hashtable.
471 
472  // remove the buckets
473  for (Size i = 0; i < __size; ++i)
474  __nodes[i].clear();
475 
476  __nb_elements = 0;
477  __begin_index = std::numeric_limits< Size >::max();
478  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
void __clearIterators()
Clear all the safe iterators.
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
void clear()
Removes all the elements in the hash table.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::const_iterator & gum::HashTable< Key, Val, Alloc >::constEnd4Statics ( )
static

Returns the end iterator for other classes' statics (read the detailed description of this method).

To reduce memory consumption of hash tables (which are heavily used in aGrUM) while allowing fast for(iter=begin(); iter!=end();++iter) loops, end iterators are created just once as a static member of a non-template hashtable. While this scheme is efficient and it works quite effectively when manipulating hashtables, it has a drawback: other classes with static members using the HashTable's end() iterator may fail to work due to the well known "static initialization order fiasco" (see Marshall Cline's C++ FAQ for more details about this C++ feature). OK, so what is the problem? Consider for instance class Set. A Set contains a hashtable that stores all its elements in a convenient way. To reduce memory consumption, Set::end iterator is a static member that is initialized with a HashTable's end iterator. If the compiler decides to initialize Set::end before initializing HashTable::end, then Set::end will be in an incoherent state. Unfortunately, we cannot know for sure in which order static members will be initialized (the order is a compiler's decision). Hence, we shall enforce the fact that HashTable::end is initialized before Set::end. Using method HashTable::end4Statics will ensure this fact: it uses the C++ "construct on first use" idiom (see the C++ FAQ) that ensures that the order fiasco is avoided. More precisely, end4Statics initializes a global variable that is the very end iterator used by all hashtables. Now, this induces a small overhead. So, we also provide a HashTable::end() method that returns the end iterator without this small overhead, but assuming that function end4Statics has already been called once (which is always the case) when a hashtable has been created.

So, to summarize: when initializing static members, use constEnd4Statics() rather than cend(). In all the other cases, use simply the usual method cend().

Returns
Returns the end iterator for other classes' statics (read the detailed description of this method).

Definition at line 342 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::constEnd4Statics().

342  {
343  return *(reinterpret_cast< const const_iterator* >(
345  }
static const HashTableConstIterator< int, int > * constEnd4Statics()
Creates (if needed) and returns the iterator __HashTableIterEnd.
HashTableConstIterator< Key, Val > const_iterator
Types for STL compliance.
Definition: hashTable.h:691

+ Here is the call graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::const_iterator_safe & gum::HashTable< Key, Val, Alloc >::constEndSafe4Statics ( )
static

Returns the end iterator for other classes' statics (read the detailed description of this method).

To reduce memory consumption of hash tables (which are heavily used in aGrUM) while allowing fast for(iter=begin(); iter!=end();++iter) loops, end iterators are created just once as a static member of a non-template hashtable. While this scheme is efficient and it works quite effectively when manipulating hashtables, it has a drawback: other classes with static members using the HashTable's end() iterator may fail to work due to the well known "static initialization order fiasco" (see Marshall Cline's C++ FAQ for more details about this C++ feature). OK, so what is the problem? Consider for instance class Set. A Set contains a hashtable that stores all its elements in a convenient way. To reduce memory consumption, Set::end iterator is a static member that is initialized with a HashTable's end iterator. If the compiler decides to initialize Set::end before initializing HashTable::end, then Set::end will be in an incoherent state. Unfortunately, we cannot know for sure in which order static members will be initialized (the order is a compiler's decision). Hence, we shall enforce the fact that HashTable::end is initialized before Set::end. Using method HashTable::end4Statics will ensure this fact: it uses the C++ "construct on first use" idiom (see the C++ FAQ) that ensures that the order fiasco is avoided. More precisely, end4Statics initializes a global variable that is the very end iterator used by all hashtables. Now, this induces a small overhead. So, we also provide a HashTable::end() method that returns the end iterator without this small overhead, but assuming that function end4Statics has already been called once (which is always the case) when a hashtable has been created.

So, to summarize: when initializing static members, use constEndSafe4Statics() rather than cendSafe(). In all the other cases, use simply the usual method cendSafe().

Returns
Returns the end iterator for other classes' statics (read the detailed description of this method).

Definition at line 356 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::constEndSafe4Statics().

356  {
357  return *(reinterpret_cast< const const_iterator_safe* >(
359  }
HashTableConstIteratorSafe< Key, Val > const_iterator_safe
Types for STL compliance.
Definition: hashTable.h:693
static const HashTableConstIteratorSafe< int, int > * constEndSafe4Statics()
Creates (if needed) and returns the iterator __HashTableIterEndSafe.

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename... Args>
INLINE HashTable< Key, Val, Alloc >::value_type& gum::HashTable< Key, Val, Alloc >::emplace ( Args &&...  args)

Definition at line 936 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__insert(), and gum::HashTableBucket< Key, Val >::elt().

936  {
937  Bucket* bucket = __alloc.allocate(1);
938 
939  try {
940  __alloc.construct(bucket,
942  std::forward< Args >(args)...);
943  } catch (...) {
944  __alloc.deallocate(bucket, 1);
945  throw;
946  }
947 
948  __insert(bucket);
949  return bucket->elt();
950  }
void __insert(Bucket *bucket)
Adds a new element (actually a copy of this element) in the hash table.
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename... Args>
value_type& gum::HashTable< Key, Val, Alloc >::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
DuplicateElementis 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
argsThe element to emplace.
template<typename Key , typename Val , typename Alloc >
INLINE bool gum::HashTable< Key, Val, Alloc >::empty ( ) const
noexcept
template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::iterator & gum::HashTable< Key, Val, Alloc >::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 602 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::__HashTableIterEnd.

Referenced by gum::Regress< GUM_SCALAR, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::__findRetrogradeVariables(), gum::MultiDimFunctionGraphOperator< GUM_SCALAR, FUNCTOR, TerminalNodePolicy >::__findRetrogradeVariables(), gum::learning::Miic::_orientation_3off2(), gum::learning::Miic::_orientation_miic(), gum::HashTable< Key, Val, Alloc >::begin(), gum::Estimator< GUM_SCALAR >::confidence(), gum::prm::PRMSystem< GUM_SCALAR >::end(), gum::HashTable< Key, Val, Alloc >::keyByVal(), gum::HashTable< Key, Val, Alloc >::map(), gum::HashTable< Key, Val, Alloc >::operator==(), and gum::SmallObjectAllocator::~SmallObjectAllocator().

602  {
603  // note that, here, we know for sure that HashTableIterEnd has been properly
604  // initialized as it is initialized by end4Statics, which is called by
605  // all hashtables' constructors
606  return *(reinterpret_cast< const iterator* >(
608  }
static const HashTableIterator< int, int > * __HashTableIterEnd
The unsafe iterator used by everyone.
Definition: hashTable.h:1831
HashTableIterator< Key, Val > iterator
Types for STL compliance.
Definition: hashTable.h:690

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::const_iterator & gum::HashTable< Key, Val, Alloc >::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 612 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::__HashTableIterEnd.

612  {
613  // note that, here, we know for sure that HashTableIterEnd has been properly
614  // initialized as it is initialized by end4Statics, which is called by
615  // all hashtables' constructors
616  return *(reinterpret_cast< const const_iterator* >(
618  }
static const HashTableIterator< int, int > * __HashTableIterEnd
The unsafe iterator used by everyone.
Definition: hashTable.h:1831
HashTableConstIterator< Key, Val > const_iterator
Types for STL compliance.
Definition: hashTable.h:691
template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::iterator & gum::HashTable< Key, Val, Alloc >::end4Statics ( )
static

Returns the end iterator for other classes' statics (read the detailed description of this method).

To reduce memory consumption of hash tables (which are heavily used in aGrUM) while allowing fast for(iter=begin(); iter!=end();++iter) loops, end iterators are created just once as a static member of a non-template hashtable. While this scheme is efficient and it works quite effectively when manipulating hashtables, it has a drawback: other classes with static members using the HashTable's end() iterator may fail to work due to the well known "static initialization order fiasco" (see Marshall Cline's C++ FAQ for more details about this C++ feature). OK, so what is the problem? Consider for instance class Set. A Set contains a hashtable that stores all its elements in a convenient way. To reduce memory consumption, Set::end iterator is a static member that is initialized with a HashTable's end iterator. If the compiler decides to initialize Set::end before initializing HashTable::end, then Set::end will be in an incoherent state. Unfortunately, we cannot know for sure in which order static members will be initialized (the order is a compiler's decision). Hence, we shall enforce the fact that HashTable::end is initialized before Set::end. Using method HashTable::end4Statics will ensure this fact: it uses the C++ "construct on first use" idiom (see the C++ FAQ) that ensures that the order fiasco is avoided. More precisely, end4Statics initializes a global variable that is the very end iterator used by all hashtables. Now, this induces a small overhead. So, we also provide a HashTable::end() method that returns the end iterator without this small overhead, but assuming that function end4Statics has already been called once (which is always the case) when a hashtable has been created.

So, to summarize: when initializing static members, use end4Statics() rather than end(). In all the other cases, use simply the usual method end().

Returns
Returns the end iterator for other classes' statics (read the detailed description of this method).

Definition at line 335 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::end4Statics().

335  {
336  return *(reinterpret_cast< const iterator* >(
338  }
static const HashTableIterator< int, int > * end4Statics()
Creates (if needed) and returns the iterator __HashTableIterEnd.
HashTableIterator< Key, Val > iterator
Types for STL compliance.
Definition: hashTable.h:690

+ Here is the call graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::iterator_safe & gum::HashTable< Key, Val, Alloc >::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 662 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::__HashTableIterEndSafe.

Referenced by gum::HashTable< Key, Val, Alloc >::beginSafe(), gum::SetTerminalNodePolicy< GUM_SCALAR >::clearAllTerminalNodes(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::LeafAggregator::leavesMap(), gum::Set< Key, Alloc >::operator*=(), gum::StructuredPlaner< GUM_SCALAR >::optimalPolicy2String(), gum::SetTerminalNodePolicy< GUM_SCALAR >::terminalNodeId(), gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::toDot(), gum::ITI< AttributeSelection, isScalar >::updateGraph(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::~IncrementalGraphLearner(), gum::MultiDimFunctionGraphOperator< GUM_SCALAR, FUNCTOR, TerminalNodePolicy >::~MultiDimFunctionGraphOperator(), and gum::Regress< GUM_SCALAR, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::~Regress().

662  {
663  // note that, here, we know for sure that HashTableIterEnd has been properly
664  // initialized as it is initialized by end4Statics, which is called by
665  // all hashtables' constructors
666  return *(reinterpret_cast< const iterator_safe* >(
668  }
static const HashTableIteratorSafe< int, int > * __HashTableIterEndSafe
The safe iterator used by everyone.
Definition: hashTable.h:1834
HashTableIteratorSafe< Key, Val > iterator_safe
Types for STL compliance.
Definition: hashTable.h:692

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::const_iterator_safe & gum::HashTable< Key, Val, Alloc >::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 672 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::__HashTableIterEndSafe.

672  {
673  // note that, here, we know for sure that HashTableIterEnd has been properly
674  // initialized as it is initialized by end4Statics, which is called by
675  // all hashtables' constructors
676  return *(reinterpret_cast< const const_iterator_safe* >(
678  }
HashTableConstIteratorSafe< Key, Val > const_iterator_safe
Types for STL compliance.
Definition: hashTable.h:693
static const HashTableIteratorSafe< int, int > * __HashTableIterEndSafe
The safe iterator used by everyone.
Definition: hashTable.h:1834
template<typename Key , typename Val , typename Alloc >
INLINE const HashTable< Key, Val, Alloc >::iterator_safe & gum::HashTable< Key, Val, Alloc >::endSafe4Statics ( )
static

Returns the end iterator for other classes' statics (read the detailed description of this method).

To reduce memory consumption of hash tables (which are heavily used in aGrUM) while allowing fast for(iter=begin(); iter!=end();++iter) loops, end iterators are created just once as a static member of a non-template hashtable. While this scheme is efficient and it works quite effectively when manipulating hashtables, it has a drawback: other classes with static members using the HashTable's end() iterator may fail to work due to the well known "static initialization order fiasco" (see Marshall Cline's C++ FAQ for more details about this C++ feature). OK, so what is the problem? Consider for instance class Set. A Set contains a hashtable that stores all its elements in a convenient way. To reduce memory consumption, Set::end iterator is a static member that is initialized with a HashTable's end iterator. If the compiler decides to initialize Set::end before initializing HashTable::end, then Set::end will be in an incoherent state. Unfortunately, we cannot know for sure in which order static members will be initialized (the order is a compiler's decision). Hence, we shall enforce the fact that HashTable::end is initialized before Set::end. Using method HashTable::end4Statics will ensure this fact: it uses the C++ "construct on first use" idiom (see the C++ FAQ) that ensures that the order fiasco is avoided. More precisely, end4Statics initializes a global variable that is the very end iterator used by all hashtables. Now, this induces a small overhead. So, we also provide a HashTable::end() method that returns the end iterator without this small overhead, but assuming that function end4Statics has already been called once (which is always the case) when a hashtable has been created.

So, to summarize: when initializing static members, use endSafe4Statics() rather than endSafe(). In all the other cases, use simply the usual method endSafe().

Returns
Returns the end iterator for other classes' statics (read the detailed description of this method).

Definition at line 349 of file hashTable_tpl.h.

References gum::HashTableIteratorStaticEnd::endSafe4Statics().

349  {
350  return *(reinterpret_cast< const iterator_safe* >(
352  }
static const HashTableIteratorSafe< int, int > * endSafe4Statics()
Creates (if needed) and returns the iterator __HashTableIterEndSafe.
HashTableIteratorSafe< Key, Val > iterator_safe
Types for STL compliance.
Definition: hashTable.h:692

+ Here is the call graph for this function:

template<typename Key, typename Val , typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::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
keyThe key of the element to remove.

Definition at line 1015 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__erase(), gum::HashTable< Key, Val, Alloc >::__hash_func, and gum::HashTable< Key, Val, Alloc >::__nodes.

Referenced by gum::BijectionImplementation< T1, T2, Alloc, Gen >::__copy(), gum::DAGCycleDetector::__delWeightedSet(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::__insert(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::_convertNode2Leaf(), gum::ITI< AttributeSelection, isScalar >::_removeNode(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::_removeNode(), gum::Set< Key, Alloc >::erase(), gum::SequenceImplementation< Key, Alloc, Gen >::erase(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::eraseByPos(), gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::eraseByPos(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::eraseFirst(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::eraseSecond(), gum::SetTerminalNodePolicy< GUM_SCALAR >::eraseTerminalNode(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::insert(), gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::insert(), gum::Set< Key, Alloc >::operator*=(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::operator=(), gum::SequenceImplementation< Key, Alloc, Gen >::operator=(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::operator=(), gum::BayesBall::relevantPotentials(), gum::prm::PRMInference< GUM_SCALAR >::removeEvidence(), gum::HashTable< Key, Val, Alloc >::reset(), and gum::SequenceImplementation< Key, Alloc, Gen >::setAtPos().

1015  {
1016  // get the hashed key
1017  Size hash = __hash_func(key);
1018 
1019  // get the bucket containing the element to erase
1020  HashTableBucket< Key, Val >* bucket = __nodes[hash].bucket(key);
1021 
1022  __erase(bucket, hash);
1023  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
const Key & key(const Key &key) const
Returns a reference on a given key.
void __erase(HashTableBucket< Key, Val > *bucket, Size index)
Erases a given bucket.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key, typename Val , typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::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
iterAn iterator over the element to remove.

Definition at line 1026 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__erase(), gum::HashTableConstIteratorSafe< Key, Val >::__getBucket(), and gum::HashTableConstIteratorSafe< Key, Val >::__getIndex().

1026  {
1027  __erase(iter.__getBucket(), iter.__getIndex());
1028  }
void __erase(HashTableBucket< Key, Val > *bucket, Size index)
Erases a given bucket.

+ Here is the call graph for this function:

template<typename Key, typename Val , typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::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
iterAn iterator over the element to remove.

Definition at line 1032 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__erase(), gum::HashTableConstIteratorSafe< Key, Val >::__getBucket(), and gum::HashTableConstIteratorSafe< Key, Val >::__getIndex().

1032  {
1033  __erase(iter.__getBucket(), iter.__getIndex());
1034  }
void __erase(HashTableBucket< Key, Val > *bucket, Size index)
Erases a given bucket.

+ Here is the call graph for this function:

template<typename Key , typename Val, typename Alloc >
void gum::HashTable< Key, Val, Alloc >::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
valThe value to remove.

Definition at line 1071 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__erase(), gum::HashTable< Key, Val, Alloc >::cbeginSafe(), and gum::HashTable< Key, Val, Alloc >::cendSafe().

1071  {
1072  for (auto iterAll = cbeginSafe(); iterAll != cendSafe(); ++iterAll) {
1073  if (iterAll.__bucket->val() == val) {
1074  __erase(iterAll.__bucket, iterAll.__index);
1075  }
1076  }
1077  }
const const_iterator_safe & cendSafe() const noexcept
Returns the safe const_iterator pointing to the end of the hashtable.
void __erase(HashTableBucket< Key, Val > *bucket, Size index)
Erases a given bucket.
const_iterator_safe cbeginSafe() const
Returns the safe const_iterator pointing to the beginning of the hashtable.

+ Here is the call graph for this function:

template<typename Key , typename Val, typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::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
valThe value to remove.

Definition at line 1037 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__erase(), gum::HashTable< Key, Val, Alloc >::cbegin(), and gum::HashTable< Key, Val, Alloc >::cend().

1037  {
1038  for (auto iter = cbegin(); iter != cend(); ++iter)
1039  if (iter.__bucket->val() == val) {
1040  __erase(iter.__getBucket(), iter.__getIndex());
1041  return;
1042  }
1043  }
const_iterator cbegin() const
Returns an unsafe const_iterator pointing to the beginning of the hashtable.
const const_iterator & cend() const noexcept
Returns the unsafe const_iterator pointing to the end of the hashtable.
void __erase(HashTableBucket< Key, Val > *bucket, Size index)
Erases a given bucket.

+ Here is the call graph for this function:

template<typename Key, typename Val , typename Alloc >
INLINE bool gum::HashTable< Key, Val, Alloc >::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
keyThe key to test for existence.
Returns
True if key is in this gum::HashTable.

Definition at line 742 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__hash_func, and gum::HashTable< Key, Val, Alloc >::__nodes.

Referenced by gum::DAGCycleDetector::__addWeightedSet(), gum::prm::o3prm::O3ClassFactory< GUM_SCALAR >::__checkImplementation(), gum::BayesNetFactory< GUM_SCALAR >::__checkVariableName(), gum::Regress< GUM_SCALAR, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::__compute(), gum::MultiDimFunctionGraphOperator< GUM_SCALAR, FUNCTOR, TerminalNodePolicy >::__compute(), gum::DAGCycleDetector::__delWeightedSet(), gum::learning::Miic::__existsDirectedPath(), gum::prm::StructuredBayesBall< GUM_SCALAR >::__fromChild(), gum::prm::StructuredBayesBall< GUM_SCALAR >::__fromParent(), gum::HashTable< Key, Val, Alloc >::__insert(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::__label(), gum::IMDDI< AttributeSelection, isScalar >::__rebuildFunctionGraph(), gum::StructuredPlaner< GUM_SCALAR >::__recurArgMaxCopy(), gum::StructuredPlaner< GUM_SCALAR >::__recurExtractOptPol(), gum::prm::PRMFactory< GUM_SCALAR >::__retrieveCommonType(), gum::credal::CredalNet< GUM_SCALAR >::__sort_varType(), gum::learning::Miic::_orientation_3off2(), gum::learning::Miic::_propagatesHead(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::_removeNode(), gum::prm::PRMSystem< GUM_SCALAR >::addArray(), gum::prm::PRMInference< GUM_SCALAR >::addEvidence(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::addObservation(), gum::SetTerminalNodePolicy< GUM_SCALAR >::addTerminalNode(), gum::SmallObjectAllocator::allocate(), gum::ContingencyTable< Idx, GUM_SCALAR >::attrAMarginal(), gum::ContingencyTable< Idx, GUM_SCALAR >::attrBMarginal(), gum::BayesNetFactory< GUM_SCALAR >::BayesNetFactory(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::contains(), gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::contains(), gum::Set< Key, Alloc >::contains(), gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::copyAndMultiplyByScalar(), gum::ArcGraphPart::directedPath(), gum::ArcGraphPart::directedUnorientedPath(), gum::SetTerminalNodePolicy< GUM_SCALAR >::eraseTerminalNode(), gum::prm::PRMSystem< GUM_SCALAR >::exists(), gum::SequenceImplementation< Key, Alloc, Gen >::exists(), gum::Set< Key, Alloc >::exists(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::existsFirst(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::existsSecond(), gum::SetTerminalNodePolicy< GUM_SCALAR >::existsTerminalNodeWithId(), gum::MultiDimSparse< GUM_SCALAR >::get(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::prm::PRMInference< GUM_SCALAR >::hasEvidence(), gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::insert(), gum::prm::PRMSystem< GUM_SCALAR >::isArray(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::isTerminal(), gum::ContingencyTable< Idx, GUM_SCALAR >::joint(), gum::LeafAggregator::leavesMap(), gum::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::Set< Key, Alloc >::operator*(), gum::Set< Key, Alloc >::operator*=(), gum::Set< Key, Alloc >::operator+(), gum::Set< Key, Alloc >::operator+=(), gum::Set< Key, Alloc >::operator-(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::operator=(), gum::SequenceImplementation< Key, Alloc, Gen >::operator=(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::operator=(), gum::Set< Key, Alloc >::operator==(), gum::StructuredPlaner< GUM_SCALAR >::optimalPolicy2String(), gum::Estimator< GUM_SCALAR >::posterior(), gum::BayesBall::relevantPotentials(), gum::prm::PRMInference< GUM_SCALAR >::removeEvidence(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveClass(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveClassElement(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveInterface(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveSlotType(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveType(), gum::Estimator< GUM_SCALAR >::setFromBN(), gum::EliminationSequenceStrategy::setGraph(), gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::toDot(), gum::credal::InferenceEngine< GUM_SCALAR >::toString(), gum::EdgeGraphPart::undirectedPath(), gum::Estimator< GUM_SCALAR >::update(), and gum::BayesNetFactory< GUM_SCALAR >::variableName().

742  {
743  return __nodes[__hash_func(key)].exists(key);
744  }
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
const Key & key(const Key &key) const
Returns a reference on a given key.
template<typename Key, typename Val, typename Alloc >
INLINE HashTable< Key, Val, Alloc >::mapped_type & gum::HashTable< Key, Val, Alloc >::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
keyThe key for wich we want the value.
default_valueThe 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 954 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::insert(), and gum::HashTableBucket< Key, Val >::val().

955  {
956  Bucket* bucket = __nodes[__hash_func(key)].bucket(key);
957 
958  if (bucket == nullptr)
959  return insert(key, default_value).second;
960  else
961  return bucket->val();
962  }
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
const Key & key(const Key &key) const
Returns a reference on a given key.
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc >
INLINE HashTable< Key, Val, Alloc >::mapped_type & gum::HashTable< Key, Val, Alloc >::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
keyThe key for wich we want the value.
default_valueThe 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 966 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::insert(), gum::HashTable< Key, Val, Alloc >::key(), and gum::HashTableBucket< Key, Val >::val().

966  {
967  Bucket* bucket = __nodes[__hash_func(key)].bucket(key);
968 
969  if (bucket == nullptr)
970  return insert(std::move(key), std::move(default_value)).second;
971  else
972  return bucket->val();
973  }
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
const Key & key(const Key &key) const
Returns a reference on a given key.
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc >
INLINE HashTable< Key, Val, Alloc >::value_type & gum::HashTable< Key, Val, Alloc >::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
DuplicateElementis 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
keyThe key to add.
valThe value to add.
Returns
The value added by copy to this gum::HashTable.

Definition at line 871 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__insert(), and gum::HashTableBucket< Key, Val >::elt().

Referenced by gum::prm::SVE< GUM_SCALAR >::__addDelayedVariable(), gum::prm::o3prm::O3SystemFactory< GUM_SCALAR >::__addInstances(), gum::prm::o3prm::O3InterfaceFactory< GUM_SCALAR >::__addInterface2Dag(), gum::prm::ClassDependencyGraph< GUM_SCALAR >::__addNode(), gum::prm::o3prm::O3TypeFactory< GUM_SCALAR >::__addTypes2Dag(), gum::DAGCycleDetector::__addWeightedSet(), gum::prm::o3prm::O3ClassFactory< GUM_SCALAR >::__checkAndAddNodesToDag(), gum::MaxInducedWidthMCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::__checkConditions(), gum::Regress< GUM_SCALAR, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::__compute(), gum::MultiDimFunctionGraphOperator< GUM_SCALAR, FUNCTOR, TerminalNodePolicy >::__compute(), gum::DefaultJunctionTreeStrategy::__computeJunctionTree(), gum::StaticTriangulation::__computeMaxPrimeJunctionTree(), gum::StaticTriangulation::__computeRecursiveThinning(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::__copy(), gum::SequenceImplementation< Key, Alloc, Gen >::__copy(), gum::learning::Miic::__existsDirectedPath(), gum::prm::PRMFormAttribute< GUM_SCALAR >::__fillCpf(), gum::prm::StructuredBayesBall< GUM_SCALAR >::__fillMaps(), gum::Regress< GUM_SCALAR, COMBINEOPERATOR, PROJECTOPERATOR, TerminalNodePolicy >::__findRetrogradeVariables(), gum::MultiDimFunctionGraphOperator< GUM_SCALAR, FUNCTOR, TerminalNodePolicy >::__findRetrogradeVariables(), gum::prm::StructuredBayesBall< GUM_SCALAR >::__fromChild(), gum::prm::StructuredBayesBall< GUM_SCALAR >::__fromParent(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::__insert(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::__label(), gum::learning::genericBNLearner::__prepare_miic_3off2(), gum::IMDDI< AttributeSelection, isScalar >::__rebuildFunctionGraph(), gum::StructuredPlaner< GUM_SCALAR >::__recurArgMaxCopy(), gum::StructuredPlaner< GUM_SCALAR >::__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::BruteForceKL< GUM_SCALAR >::_computeKL(), gum::GibbsKL< GUM_SCALAR >::_computeKL(), gum::credal::InferenceEngine< GUM_SCALAR >::_initExpectations(), gum::credal::InferenceEngine< GUM_SCALAR >::_initMarginals(), gum::credal::InferenceEngine< GUM_SCALAR >::_initMarginalSets(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::_insertInternalNode(), gum::ITI< AttributeSelection, isScalar >::_insertNode(), gum::credal::InferenceEngine< GUM_SCALAR >::_repetitiveInit(), gum::prm::PRMClassElementContainer< GUM_SCALAR >::_setIOFlag(), gum::IncrementalGraphLearner< AttributeSelection, isScalar >::_transpose(), gum::prm::PRMSystem< GUM_SCALAR >::add(), gum::DAGCycleDetector::addArc(), gum::prm::PRMSystem< GUM_SCALAR >::addArray(), gum::prm::PRMInference< GUM_SCALAR >::addEvidence(), gum::prm::PRMFactory< GUM_SCALAR >::addInstance(), gum::prm::gspan::DFSTree< GUM_SCALAR >::addRoot(), gum::SetTerminalNodePolicy< GUM_SCALAR >::addTerminalNode(), gum::BarrenNodesFinder::barrenNodes(), gum::BarrenNodesFinder::barrenPotentials(), gum::BayesNetFactory< GUM_SCALAR >::BayesNetFactory(), gum::prm::ClassDependencyGraph< GUM_SCALAR >::ClassDependencyGraph(), gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::copyAndMultiplyByScalar(), gum::Chi2::criticalValue(), gum::learning::genericBNLearner::Database::Database(), gum::ArcGraphPart::directedPath(), gum::ArcGraphPart::directedUnorientedPath(), gum::SequenceImplementation< Key, Alloc, Gen >::emplace(), gum::BayesNetFactory< GUM_SCALAR >::endVariableDeclaration(), gum::DAGCycleDetector::eraseArc(), gum::Estimator< GUM_SCALAR >::Estimator(), gum::MultiDimFunctionGraphGenerator::generate(), gum::SimpleBayesNetGenerator< GUM_SCALAR, ICPTGenerator >::generateBN(), gum::HashTable< Key, Val, Alloc >::getWithDefault(), gum::DAGCycleDetector::hasCycleFromModifications(), gum::HashTable< Key, Val, Alloc >::HashTable(), gum::AdaptiveRMaxPlaner::initialize(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::insert(), gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::insert(), gum::Set< Key, Alloc >::insert(), gum::SequenceImplementation< Key, Alloc, Gen >::insert(), gum::credal::InferenceEngine< GUM_SCALAR >::insertEvidence(), gum::credal::InferenceEngine< GUM_SCALAR >::insertEvidenceFile(), gum::credal::InferenceEngine< GUM_SCALAR >::insertQuery(), gum::credal::InferenceEngine< GUM_SCALAR >::insertQueryFile(), gum::ITI< AttributeSelection, isScalar >::ITI(), gum::LeafAggregator::leavesMap(), gum::HashTable< Key, Val, Alloc >::map(), gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::minimizeSize(), gum::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::Set< Key, Alloc >::operator*(), gum::Set< Key, Alloc >::operator+(), gum::Set< Key, Alloc >::operator+=(), gum::Set< Key, Alloc >::operator-(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::operator=(), gum::SequenceImplementation< Key, Alloc, Gen >::operator=(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::operator=(), gum::StructuredPlaner< GUM_SCALAR >::optimalPolicy2String(), gum::prm::gspan::Pattern::Pattern(), gum::BayesBall::relevantPotentials(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveClass(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveClassElement(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveInterface(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveSlotType(), gum::prm::o3prm::O3NameSolver< GUM_SCALAR >::resolveType(), gum::prm::PRMClass< GUM_SCALAR >::scope(), gum::HashTable< Key, Val, Alloc >::set(), gum::SequenceImplementation< Key, Alloc, Gen >::setAtPos(), gum::DAGCycleDetector::setDAG(), gum::Estimator< GUM_SCALAR >::setFromBN(), gum::Estimator< GUM_SCALAR >::setFromLBP(), gum::DAGmodel::setProperty(), gum::BayesNetFactory< GUM_SCALAR >::setVariable(), gum::TaxiSimulator::TaxiSimulator(), gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::toDot(), gum::EdgeGraphPart::undirectedPath(), and gum::ITI< AttributeSelection, isScalar >::updateGraph().

871  {
872  Bucket* bucket = __alloc.allocate(1);
873 
874  try {
875  __alloc.construct(bucket, thekey, theval);
876  } catch (...) {
877  __alloc.deallocate(bucket, 1);
878  throw;
879  }
880 
881  __insert(bucket);
882  return bucket->elt();
883  }
void __insert(Bucket *bucket)
Adds a new element (actually a copy of this element) in the hash table.
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc >
INLINE HashTable< Key, Val, Alloc >::value_type & gum::HashTable< Key, Val, Alloc >::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
DuplicateElementis 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
keyThe key to move.
valThe value to move.
Returns
The value moved to this gum::HashTable.

Definition at line 887 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__insert(), and gum::HashTableBucket< Key, Val >::elt().

887  {
888  Bucket* bucket = __alloc.allocate(1);
889 
890  try {
891  __alloc.construct(bucket, std::move(thekey), std::move(theval));
892  } catch (...) {
893  __alloc.deallocate(bucket, 1);
894  throw;
895  }
896 
897  __insert(bucket);
898  return bucket->elt();
899  }
void __insert(Bucket *bucket)
Adds a new element (actually a copy of this element) in the hash table.
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc >
INLINE HashTable< Key, Val, Alloc >::value_type & gum::HashTable< Key, Val, Alloc >::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
DuplicateElementis 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
eltThe pair of key value to add.
Returns
The value added by copy to this gum::HashTable.

Definition at line 903 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__insert(), and gum::HashTableBucket< Key, Val >::elt().

903  {
904  Bucket* bucket = __alloc.allocate(1);
905 
906  try {
907  __alloc.construct(bucket, reinterpret_cast< const value_type& >(elt));
908  } catch (...) {
909  __alloc.deallocate(bucket, 1);
910  throw;
911  }
912 
913  __insert(bucket);
914  return bucket->elt();
915  }
void __insert(Bucket *bucket)
Adds a new element (actually a copy of this element) in the hash table.
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc >
INLINE HashTable< Key, Val, Alloc >::value_type & gum::HashTable< Key, Val, Alloc >::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
DuplicateElementis 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
eltThe pair of key value to move in this gum::HashTable.
Returns
The value moved to this gum::HashTable.

Definition at line 919 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__insert(), and gum::HashTableBucket< Key, Val >::elt().

919  {
920  Bucket* bucket = __alloc.allocate(1);
921 
922  try {
923  __alloc.construct(bucket, std::move(reinterpret_cast< value_type& >(elt)));
924  } catch (...) {
925  __alloc.deallocate(bucket, 1);
926  throw;
927  }
928 
929  __insert(bucket);
930  return bucket->elt();
931  }
void __insert(Bucket *bucket)
Adds a new element (actually a copy of this element) in the hash table.
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760

+ Here is the call graph for this function:

template<typename Key, typename Val , typename Alloc >
INLINE const Key & gum::HashTable< Key, Val, Alloc >::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
keyThe key to return.
Returns
Returns a reference on a given key.
Exceptions
NotFoundRaised if the element cannot be found.

Definition at line 1059 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__nodes, GUM_ERROR, and gum::HashTableBucket< Key, Val >::key().

Referenced by gum::HashTable< Key, Val, Alloc >::getWithDefault(), gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::insert(), gum::HashTable< Key, Val, Alloc >::operator[](), gum::StructuredPlaner< GUM_SCALAR >::optimalPolicy2String(), and gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::toDot().

1059  {
1060  // get the bucket corresponding to the key
1061  Bucket* bucket = __nodes[__hash_func(key)].bucket(key);
1062 
1063  if (bucket == nullptr) {
1064  GUM_ERROR(NotFound, "key does not belong to the hashtable");
1065  }
1066 
1067  return bucket->key();
1068  }
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
const Key & key(const Key &key) const
Returns a reference on a given key.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val, typename Alloc >
INLINE const Key & gum::HashTable< Key, Val, Alloc >::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
valThe value for which the key is returned.
Returns
Returns a reference on the key given a value.
Exceptions
NotFoundRaised if the element cannot be found.

Definition at line 1051 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::begin(), gum::HashTable< Key, Val, Alloc >::end(), and GUM_ERROR.

1051  {
1052  for (auto iter = begin(); iter != end(); ++iter)
1053  if (iter.__bucket->val() == val) return iter.key();
1054 
1055  GUM_ERROR(NotFound, "not enough elements in the chained list");
1056  }
iterator begin()
Returns an unsafe iterator pointing to the beginning of the hashtable.
const iterator & end() noexcept
Returns the unsafe iterator pointing to the end of the hashtable.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE bool gum::HashTable< Key, Val, Alloc >::keyUniquenessPolicy ( ) const
noexcept

Returns the current checking policy.

Returns
Returns the current checking policy.

Definition at line 764 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy.

764  {
766  }
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730
template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename Mount , typename OtherAlloc >
HashTable< Key, Mount, OtherAlloc > INLINE gum::HashTable< Key, Val, Alloc >::map ( Mount(*)(Val)  f,
Size  size,
bool  resize_pol,
bool  key_uniqueness_pol 
) const

Definition at line 1086 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::begin(), gum::HashTable< Key, Val, Alloc >::end(), and gum::HashTable< Key, Val, Alloc >::insert().

1087  {
1088  // determine the proper size of the hashtable
1089  // by default, the size of the table is set so that the table does not take
1090  // too much space while allowing to add a few elements without needing to
1091  // resize in autmatic resizing mode
1092  if (size == 0) size = std::max(Size(2), __nb_elements / 2);
1093 
1094  // create a new table
1095  HashTable< Key, Mount, OtherAlloc > table(
1096  size, resize_pol, key_uniqueness_pol);
1097 
1098  // fill the new hash table
1099  for (auto iter = begin(); iter != end(); ++iter) {
1100  table.insert(iter.key(), f(iter.val()));
1101  }
1102 
1103  return table;
1104  }
iterator begin()
Returns an unsafe iterator pointing to the beginning of the hashtable.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
const iterator & end() noexcept
Returns the unsafe iterator pointing to the end of the hashtable.
Size size() const noexcept
Returns the number of elements stored into the hashtable.
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename Mount , typename OtherAlloc >
HashTable< Key, Mount, OtherAlloc > INLINE gum::HashTable< Key, Val, Alloc >::map ( Mount(*)(Val &)  f,
Size  size,
bool  resize_pol,
bool  key_uniqueness_pol 
) const

Definition at line 1108 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::begin(), gum::HashTable< Key, Val, Alloc >::end(), and gum::HashTable< Key, Val, Alloc >::insert().

1109  {
1110  // determine the proper size of the hashtable
1111  // by default, the size of the table is set so that the table does not take
1112  // too much space while allowing to add a few elements without needing to
1113  // resize in autmatic resizing mode
1114  if (size == 0) size = std::max(Size(2), __nb_elements / 2);
1115 
1116  // create a new table
1117  HashTable< Key, Mount, OtherAlloc > table(
1118  size, resize_pol, key_uniqueness_pol);
1119 
1120  // fill the new hash table
1121  for (auto iter = begin(); iter != end(); ++iter) {
1122  table.insert(iter.key(), f(const_cast< Val& >(iter.val())));
1123  }
1124 
1125  return table;
1126  }
iterator begin()
Returns an unsafe iterator pointing to the beginning of the hashtable.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
const iterator & end() noexcept
Returns the unsafe iterator pointing to the end of the hashtable.
Size size() const noexcept
Returns the number of elements stored into the hashtable.
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename Mount , typename OtherAlloc >
HashTable< Key, Mount, OtherAlloc > INLINE gum::HashTable< Key, Val, Alloc >::map ( Mount(*)(const Val &)  f,
Size  size,
bool  resize_pol,
bool  key_uniqueness_pol 
) const

Definition at line 1131 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::begin(), gum::HashTable< Key, Val, Alloc >::end(), and gum::HashTable< Key, Val, Alloc >::insert().

1134  {
1135  // determine the proper size of the hashtable
1136  // by default, the size of the table is set so that the table does not take
1137  // too much space while allowing to add a few elements without needing to
1138  // resize in autmatic resizing mode
1139  if (size == 0) size = std::max(Size(2), __nb_elements / 2);
1140 
1141  // create a new table
1142  HashTable< Key, Mount, OtherAlloc > table(
1143  size, resize_pol, key_uniqueness_pol);
1144 
1145  // fill the new hash table
1146  for (auto iter = begin(); iter != end(); ++iter) {
1147  table.insert(iter.key(), f(iter.val()));
1148  }
1149 
1150  return table;
1151  }
iterator begin()
Returns an unsafe iterator pointing to the beginning of the hashtable.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
const iterator & end() noexcept
Returns the unsafe iterator pointing to the end of the hashtable.
Size size() const noexcept
Returns the number of elements stored into the hashtable.
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename Mount , typename OtherAlloc >
HashTable< Key, Mount, OtherAlloc > INLINE gum::HashTable< Key, Val, Alloc >::map ( const Mount &  val,
Size  size,
bool  resize_pol,
bool  key_uniqueness_pol 
) const

Definition at line 1155 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::begin(), gum::HashTable< Key, Val, Alloc >::end(), gum::HashTable< Key, Val, Alloc >::insert(), and gum::HashTable< Key, Val, Alloc >::operator==().

1156  {
1157  // determine the proper size of the hashtable
1158  // by default, the size of the table is set so that the table does not take
1159  // too much space while allowing to add a few elements without needing to
1160  // resize in autmatic resizing mode
1161  if (size == 0) size = std::max(Size(2), __nb_elements / 2);
1162 
1163  // create a new table
1164  HashTable< Key, Mount, OtherAlloc > table(
1165  size, resize_pol, key_uniqueness_pol);
1166 
1167  // fill the new hash table
1168  for (auto iter = begin(); iter != end(); ++iter) {
1169  table.insert(iter.key(), val);
1170  }
1171 
1172  return table;
1173  }
iterator begin()
Returns an unsafe iterator pointing to the beginning of the hashtable.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
const iterator & end() noexcept
Returns the unsafe iterator pointing to the end of the hashtable.
Size size() const noexcept
Returns the number of elements stored into the hashtable.
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename Mount , typename OtherAlloc = typename Alloc::template rebind< std::pair< Key, Mount > >::other>
HashTable< Key, Mount, OtherAlloc > gum::HashTable< Key, Val, Alloc >::map ( Mount(*)(Val)  f,
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
fA function that maps any Val element into a Mount.
sizeThe 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_polthe resizing policy (automatic or manual resizing)
key_uniqueness_poluniqueness policy
Returns
Returns the gum::HashTable of mountains.
template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename Mount , typename OtherAlloc = typename Alloc::template rebind< std::pair< Key, Mount > >::other>
HashTable< Key, Mount, OtherAlloc > gum::HashTable< Key, Val, Alloc >::map ( Mount(*)(Val &)  f,
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
fA function that maps any Val element into a Mount.
sizeThe 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_polthe resizing policy (automatic or manual resizing)
key_uniqueness_poluniqueness policy
Returns
Returns the gum::HashTable of mountains.
template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename Mount , typename OtherAlloc = typename Alloc::template rebind< std::pair< Key, Mount > >::other>
HashTable< Key, Mount, OtherAlloc > gum::HashTable< Key, Val, Alloc >::map ( Mount(*)(const Val &)  f,
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
fA function that maps any Val element into a Mount.
sizeThe 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_polthe resizing policy (automatic or manual resizing)
key_uniqueness_poluniqueness policy
Returns
Returns the gum::HashTable of mountains.
template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename Mount , typename OtherAlloc = typename Alloc::template rebind< std::pair< Key, Mount > >::other>
HashTable< Key, Mount, OtherAlloc > gum::HashTable< Key, Val, Alloc >::map ( const Mount &  val,
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
valThe value taken by all the elements of the resulting hashtable.
sizeThe 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_polthe resizing policy (automatic or manual resizing)
key_uniqueness_poluniqueness policy
Returns
Returns the gum::HashTable of mountains.
template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename OtherAlloc >
bool gum::HashTable< Key, Val, Alloc >::operator!= ( const HashTable< Key, Val, OtherAlloc > &  from) const

Checks whether two hashtables contain different sets of elements.

Two hashtables are considered different if they contain different pairs (key,val). Two pairs are different if their keys have different hashed values, or if they are different in the sense of !=, or if their val's are different in the sense of !=.

Parameters
fromThe gum::HashTable to test for inequality.
Returns
True if this and from are not equal.

Referenced by gum::HashTable< Key, Val, Alloc >::operator==().

+ Here is the caller graph for this function:

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename OtherAlloc >
INLINE bool gum::HashTable< Key, Val, Alloc >::operator!= ( const HashTable< Key, Val, OtherAlloc > &  from) const

Definition at line 1195 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::operator==().

1195  {
1196  return !operator==(from);
1197  }
bool operator==(const HashTable< Key, Val, OtherAlloc > &from) const
Checks whether two hashtables contain the same elements.

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc>
HashTable< Key, Val, Alloc > & gum::HashTable< Key, Val, Alloc >::operator= ( const HashTable< Key, Val, Alloc > &  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
fromThe gum::HashTable to copy.
Returns
Returns this gum::HashTable.

Definition at line 492 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__copy(), gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::__resize_policy, gum::HashTable< Key, Val, Alloc >::__size, and gum::HashTable< Key, Val, Alloc >::clear().

Referenced by gum::HashTable< Key, Val, Alloc >::operator=(), and gum::HashTable< Key, Val, Alloc >::~HashTable().

492  {
493  // avoid self assignment
494  if (this != &from) {
495  // for debugging purposes
496  GUM_OP_CPY(HashTable);
497 
498  // first remove the current content of the hashtable and make
499  // the iterators point to end
500  clear();
501 
502  // if sizes of from's and this' __nodes vectors are not the same,
503  // we need to remove the current __nodes' array and to create a
504  // new array with the correct size
505  if (__size != from.__size) {
506  __nodes.resize(from.__size);
507 
508  for (Size i = 0; i < from.__size; ++i) {
509  __nodes[i].setAllocator(__alloc);
510  }
511 
512  __size = from.__size;
513 
514  // update the hash function : this is important as the computation of
515  // the hash values heavily depends on the size of the hash table
516  __hash_func.resize(__size);
517  }
518 
519  __resize_policy = from.__resize_policy;
520  __key_uniqueness_policy = from.__key_uniqueness_policy;
521  __begin_index = from.__begin_index;
522 
523  // perform the copy
524  __copy(from);
525  }
526 
527  return *this;
528  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
void clear()
Removes all the elements in the hash table.
void __copy(const HashTable< Key, Val, OtherAlloc > &table)
A function used to perform copies of HashTables.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key, typename Val, typename Alloc >
template<typename OtherAlloc >
HashTable< Key, Val, Alloc > & gum::HashTable< Key, Val, Alloc >::operator= ( const HashTable< Key, Val, OtherAlloc > &  from)

Generalized 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
fromThe gum::HashTable to copy.
Returns
Returns this gum::HashTable.

Definition at line 533 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__copy(), gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::__resize_policy, gum::HashTable< Key, Val, Alloc >::__size, gum::HashTable< Key, Val, Alloc >::clear(), and gum::HashTable< Key, Val, Alloc >::operator=().

533  {
534  // avoid self assignment
535  if (this != reinterpret_cast< const HashTable< Key, Val, Alloc >* >(&from)) {
536  // for debugging purposes
537  GUM_OP_CPY(HashTable);
538 
539  // first remove the current content of the hashtable and make
540  // the iterators point to end
541  clear();
542 
543  // if sizes of from's and this' __nodes vectors are not the same,
544  // we need to remove the current __nodes' array and to create a
545  // new array with the correct size
546  if (__size != from.__size) {
547  __nodes.resize(from.__size);
548 
549  for (Size i = 0; i < from.__size; ++i) {
550  __nodes[i].setAllocator(__alloc);
551  }
552 
553  __size = from.__size;
554 
555  // update the hash function : this is important as the computation of
556  // the hash values heavily depends on the size of the hash table
557  __hash_func.resize(__size);
558  }
559 
560  __resize_policy = from.__resize_policy;
561  __key_uniqueness_policy = from.__key_uniqueness_policy;
562  __begin_index = from.__begin_index;
563 
564  // perform the copy
565  __copy(from);
566  }
567 
568  return *this;
569  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
void clear()
Removes all the elements in the hash table.
void __copy(const HashTable< Key, Val, OtherAlloc > &table)
A function used to perform copies of HashTables.

+ Here is the call graph for this function:

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

Move operator.

Parameters
fromThe gum::HashTable to move.
Returns
Returns this gum::HashTable.

Definition at line 573 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy, gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::__resize_policy, gum::HashTable< Key, Val, Alloc >::__safe_iterators, gum::HashTable< Key, Val, Alloc >::__size, and gum::HashTable< Key, Val, Alloc >::clear().

573  {
574  // avoid self assignment
575  if (this != &table) {
576  // for debugging purposes
577  GUM_OP_MOV(HashTable);
578 
579  // first remove the current content of the hashtable and make
580  // the iterators point to end
581  clear();
582 
583  __nodes = std::move(table.__nodes);
584  __safe_iterators = std::move(table.__safe_iterators);
585  __alloc = std::move(table.__alloc);
586  __size = table.__size;
587  __nb_elements = table.__nb_elements;
588  __hash_func = table.__hash_func;
589  __resize_policy = table.__resize_policy;
590  __key_uniqueness_policy = table.__key_uniqueness_policy;
591  __begin_index = table.__begin_index;
592 
593  table.__size = 0; // necessary if we wish to perform moves iteratively,
594  // i.e. x = std::move ( y ); y = std::move ( z ); ...
595  }
596 
597  return *this;
598  }
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
std::vector< HashTableConstIteratorSafe< Key, Val > * > __safe_iterators
The list of safe iterators pointing to the hash table.
Definition: hashTable.h:1750
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
void clear()
Removes all the elements in the hash table.

+ Here is the call graph for this function:

template<typename Key, typename Val, typename Alloc >
template<typename OtherAlloc >
bool gum::HashTable< Key, Val, Alloc >::operator== ( const HashTable< Key, Val, OtherAlloc > &  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
fromThe gum::HashTable to test for equality.
Returns
True if this and from are equal.

Definition at line 1178 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::begin(), gum::HashTable< Key, Val, Alloc >::end(), and gum::HashTable< Key, Val, Alloc >::operator!=().

Referenced by gum::HashTable< Key, Val, Alloc >::map(), and gum::HashTable< Key, Val, Alloc >::operator!=().

1178  {
1179  // checks whether the two hashtables contain the same number of elements
1180  if (from.__nb_elements != __nb_elements) return false;
1181 
1182  // parse this and check that each element also belongs to from
1183  for (auto iter = begin(); iter != end(); ++iter) {
1184  try {
1185  if (iter.val() != from[iter.key()]) return false;
1186  } catch (NotFound&) { return false; }
1187  }
1188 
1189  return true;
1190  }
iterator begin()
Returns an unsafe iterator pointing to the beginning of the hashtable.
const iterator & end() noexcept
Returns the unsafe iterator pointing to the end of the hashtable.
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key, typename Val , typename Alloc >
INLINE Val & gum::HashTable< Key, Val, Alloc >::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
keyThe key of the value to return.
Returns
Returns the value matching the given key.
Exceptions
NotFoundexception is thrown if the element cannot be found.

Definition at line 721 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__nodes, and gum::HashTable< Key, Val, Alloc >::key().

721  {
722  return __nodes[__hash_func(key)][key];
723  }
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
const Key & key(const Key &key) const
Returns a reference on a given key.

+ Here is the call graph for this function:

template<typename Key, typename Val , typename Alloc >
INLINE const Val & gum::HashTable< Key, Val, Alloc >::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
NotFoundexception is thrown if the element cannot be found.

Definition at line 727 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__nodes, and gum::HashTable< Key, Val, Alloc >::key().

727  {
728  return __nodes[__hash_func(key)][key];
729  }
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
const Key & key(const Key &key) const
Returns a reference on a given key.

+ Here is the call graph for this function:

template<typename Key, typename Val , typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::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
keyThe property to remove.

Definition at line 1046 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::erase().

Referenced by gum::MultiDimSparse< GUM_SCALAR >::set().

1046  {
1047  erase(key);
1048  }
void erase(const Key &key)
Removes a given element from the hash table.
const Key & key(const Key &key) const
Returns a reference on a given key.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
void gum::HashTable< Key, Val, Alloc >::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_sizeThe new number of slots in the gum::HashTable.

Definition at line 769 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__alloc, gum::HashTable< Key, Val, Alloc >::__begin_index, gum::HashTable< Key, Val, Alloc >::__hash_func, gum::__hashTableLog2(), gum::HashTable< Key, Val, Alloc >::__nb_elements, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::__resize_policy, gum::HashTable< Key, Val, Alloc >::__safe_iterators, gum::HashTable< Key, Val, Alloc >::__size, gum::HashTableConst::default_mean_val_by_slot, gum::HashTableBucket< Key, Val >::key(), gum::HashTableBucket< Key, Val >::next, and gum::credal::lp::swap().

Referenced by gum::HashTable< Key, Val, Alloc >::__insert(), gum::operator<<(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::operator=(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::operator=(), gum::BayesBall::relevantPotentials(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::resize(), gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::resize(), gum::SequenceImplementation< Key, Alloc, Gen >::resize(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::resize(), and gum::Set< Key, Alloc >::resize().

769  {
770  // new_size must be >= 2 else all the bits of the hash function are lost
771  new_size = std::max(Size(2), new_size);
772 
773  // find the real size for allocation (the smallest power of 2 greater
774  // than or equal to new_size) and get its base-2 logarithm
775  int log_size = __hashTableLog2(new_size);
776  new_size = Size(1) << log_size;
777 
778  // check if the new size is different from the actual size
779  // if not, nothing else need be done
780 
781  if (new_size != __size) {
782  // under automatic resize policy, check if the new size leaves
783  // enough space for storing all the current elements
784  if (!__resize_policy
785  || (__nb_elements
787  // create a new array of __nodes to store the elements
788  std::vector< HashTableList< Key, Val, Alloc > > new_nodes(new_size);
789 
790  for (auto& list : new_nodes) {
791  list.setAllocator(__alloc);
792  }
793 
794  // set the new hash function
795  __hash_func.resize(new_size);
796 
797  // put all the elements of the current __nodes array into the new one
798  Bucket* bucket;
799  Size new_hashed_key;
800 
801  for (Size i = 0; i < __size; ++i) {
802  while ((bucket = __nodes[i].__deb_list) != nullptr) {
803  // compute the new hashed key
804  new_hashed_key = __hash_func(bucket->key());
805 
806  // remove the bucket from the list of buckets of the current
807  // node vector
808  __nodes[i].__deb_list = bucket->next;
809 
810  // put the bucket into the new __nodes vector
811  new_nodes[new_hashed_key].insert(bucket);
812  }
813  }
814 
815  // update the size of the hash table
816  __size = new_size;
817  __begin_index = std::numeric_limits< Size >::max();
818 
819  // substitute the current __nodes array by the new one
820  std::swap(__nodes, new_nodes);
821 
822  // update the iterators
823  for (auto iter : __safe_iterators) {
824  if (iter->__bucket)
825  iter->__index = __hash_func(iter->__bucket->key());
826  else {
827  iter->__next_bucket = nullptr;
828  iter->__index = 0;
829  }
830  }
831  }
832  }
833  }
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
void swap(HashTable< LpCol, double > *&a, HashTable< LpCol, double > *&b)
Swap the addresses of two pointers to hashTables.
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
std::vector< HashTableConstIteratorSafe< Key, Val > * > __safe_iterators
The list of safe iterators pointing to the hash table.
Definition: hashTable.h:1750
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
Size __begin_index
Returns where the begin index should be.
Definition: hashTable.h:1746
unsigned int __hashTableLog2(const Size &nb)
Returns the size in bits - 1 necessary to store the smallest power of 2 greater or equal to nb...
static constexpr unsigned int default_mean_val_by_slot
The average number of elements admissible by slots.
Definition: hashTable.h:84

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE bool gum::HashTable< Key, Val, Alloc >::resizePolicy ( ) const
noexcept

Returns the current resizing policy.

Returns
Returns the current resizing policy.

Definition at line 753 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__resize_policy.

Referenced by gum::BijectionImplementation< T1, T2, Alloc, Gen >::operator=(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::resizePolicy(), and gum::Set< Key, Alloc >::resizePolicy().

753  {
754  return __resize_policy;
755  }
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727

+ Here is the caller graph for this function:

template<typename Key, typename Val, typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::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
keyThe key of the value to add or set.
default_valueThe value to set or add.

Definition at line 976 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__hash_func, gum::HashTable< Key, Val, Alloc >::__nodes, gum::HashTable< Key, Val, Alloc >::insert(), and gum::HashTableBucket< Key, Val >::val().

Referenced by gum::SmallObjectAllocator::allocate(), and gum::MultiDimSparse< GUM_SCALAR >::set().

976  {
977  Bucket* bucket = __nodes[__hash_func(key)].bucket(key);
978 
979  if (bucket == nullptr)
980  insert(key, value);
981  else
982  bucket->val() = value;
983  }
HashTableBucket< Key, Val > Bucket
The buckets where data are stored.
Definition: hashTable.h:697
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
const Key & key(const Key &key) const
Returns a reference on a given key.
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::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 758 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy.

Referenced by gum::SmallObjectAllocator::SmallObjectAllocator().

759  {
760  __key_uniqueness_policy = new_policy;
761  }
bool __key_uniqueness_policy
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1730

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE void gum::HashTable< Key, Val, Alloc >::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_policyThe new resizing policy, true implies automatic resizing.

Definition at line 748 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__resize_policy.

Referenced by gum::BijectionImplementation< T1, T2, Alloc, Gen >::operator=(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::setResizePolicy(), and gum::Set< Key, Alloc >::setResizePolicy().

748  {
749  __resize_policy = new_policy;
750  }
bool __resize_policy
Is resizing performed automatically?
Definition: hashTable.h:1727

+ Here is the caller graph for this function:

template<typename Key , typename Val , typename Alloc >
INLINE Size gum::HashTable< Key, Val, Alloc >::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 732 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nb_elements.

Referenced by gum::credal::CNMonteCarloSampling< GUM_SCALAR, BNInferenceEngine >::__insertEvidence(), gum::credal::CredalNet< GUM_SCALAR >::__sort_varType(), gum::credal::InferenceEngine< GUM_SCALAR >::_computeEpsilon(), gum::credal::CredalNet< GUM_SCALAR >::approximatedBinarization(), gum::SequenceImplementation< Key, Alloc, Gen >::atPos(), gum::ContingencyTable< Idx, GUM_SCALAR >::attrASize(), gum::ContingencyTable< Idx, GUM_SCALAR >::attrBSize(), gum::SequenceImplementation< Key, Alloc, Gen >::emplace(), gum::SequenceImplementation< Key, Alloc, Gen >::erase(), gum::Set< Key, Alloc >::hashMap(), gum::SequenceImplementation< Key, Alloc, Gen >::insert(), gum::Set< Key, Alloc >::operator*(), gum::operator<<(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::operator=(), gum::SequenceImplementation< Key, Alloc, Gen >::operator=(), gum::Set< Key, Alloc >::operator==(), gum::MultiDimSparse< GUM_SCALAR >::realSize(), gum::SequenceImplementation< Key, Alloc, Gen >::resize(), gum::SequenceImplementation< Key, Alloc, Gen >::setAtPos(), gum::DAGCycleDetector::setDAG(), gum::Set< Key, Alloc >::size(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::size(), and gum::SequenceImplementation< Key, Alloc, Gen >::toString().

732  {
733  return __nb_elements;
734  }
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721

+ Here is the caller graph for this function:

Friends And Related Function Documentation

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename K , typename V , typename A >
friend class HashTable
friend

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

Definition at line 1695 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
template<typename T1 , typename T2 , typename A >
friend class Bijection
friend

For bijections to quickly access data.

Definition at line 1708 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
friend class HashTableConstIterator< Key, Val >
friend

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

Definition at line 1697 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
friend class HashTableConstIteratorSafe< Key, Val >
friend

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

Definition at line 1699 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
friend class HashTableIterator< Key, Val >
friend

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

Definition at line 1696 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
friend class HashTableIteratorSafe< Key, Val >
friend

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

Definition at line 1698 of file hashTable.h.

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
std::ostream& operator<< ( std::ostream &  s,
const HashTable< Key, Val, Alloc > &  table 
)
friend

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

Definition at line 1236 of file hashTable_tpl.h.

1237  {
1238  bool deja = false;
1239  stream << "{";
1240 
1241  for (Size i = 0; i < table.__size; ++i)
1242  for (auto ptr = table.__nodes[i].__deb_list; ptr; ptr = ptr->next) {
1243  if (deja) stream << " , ";
1244 
1245  stream << ptr->key() << "=>" << ptr->val();
1246 
1247  deja = true;
1248  }
1249 
1250  stream << "}";
1251 
1252  return stream;
1253  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
std::ostream& operator<< ( std::ostream &  s,
const HashTable< Key *, Val, Alloc > &  table 
)
friend

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

Definition at line 1256 of file hashTable_tpl.h.

1257  {
1258  bool deja = false;
1259  stream << "{";
1260 
1261  for (Size i = 0; i < table.__size; ++i)
1262  for (auto ptr = table.__nodes[i].__deb_list; ptr; ptr = ptr->next) {
1263  if (deja) stream << " , ";
1264 
1265  stream << ptr->key() << "=>" << ptr->val();
1266 
1267  deja = true;
1268  }
1269 
1270  stream << "}";
1271 
1272  return stream;
1273  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50

Member Data Documentation

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
BucketAllocator gum::HashTable< Key, Val, Alloc >::__alloc
private

The allocator for the buckets.

Warning
the allocator field should compulsorily be the last of field of the class. As such, for K and V fixed, all hashTable<K,V,A> are the same (up to the allocator) for all allocators A. This feature proves useful to avoid passing the allocator as a template parameter to iterators.

Definition at line 1760 of file hashTable.h.

Referenced by gum::HashTable< Key, Val, Alloc >::__insert(), gum::HashTable< Key, Val, Alloc >::emplace(), gum::HashTable< Key, Val, Alloc >::HashTable(), gum::HashTable< Key, Val, Alloc >::insert(), gum::HashTable< Key, Val, Alloc >::operator=(), and gum::HashTable< Key, Val, Alloc >::resize().

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
Size gum::HashTable< Key, Val, Alloc >::__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 1746 of file hashTable.h.

Referenced by gum::HashTable< Key, Val, Alloc >::__erase(), gum::HashTable< Key, Val, Alloc >::__insert(), gum::HashTable< Key, Val, Alloc >::clear(), gum::HashTable< Key, Val, Alloc >::HashTable(), gum::HashTableConstIterator< Key, Val >::HashTableConstIterator(), gum::HashTableConstIteratorSafe< Key, Val >::HashTableConstIteratorSafe(), gum::HashTable< Key, Val, Alloc >::operator=(), and gum::HashTable< Key, Val, Alloc >::resize().

template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
bool gum::HashTable< Key, Val, Alloc >::__key_uniqueness_policy {true}
private
template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
bool gum::HashTable< Key, Val, Alloc >::__resize_policy {true}
private
template<typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > >>
std::vector< HashTableConstIteratorSafe< Key, Val >* > gum::HashTable< Key, Val, Alloc >::__safe_iterators
mutableprivate

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