aGrUM 3.1.1
a C++ library for (probabilistic) graphical models
gum::HashTableList< Key, Val > Class Template Reference

A chained list used by gum::HashTable. More...

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

Public Types

using key_type = Key
 types for STL compliance
using mapped_type = Val
 types for STL compliance
using value_type = std::pair< const Key, Val >
 types for STL compliance
using reference = value_type&
 types for STL compliance
using const_reference = const value_type&
 types for STL compliance
using pointer = value_type*
 types for STL compliance
using const_pointer = const value_type*
 types for STL compliance
using size_type = Size
 types for STL compliance
using Bucket = HashTableBucket< Key, Val >
 types for STL compliance

Public Member Functions

Constructors / Destructors
 HashTableList () noexcept
 Basic constructor that creates an empty list.
 HashTableList (const HashTableList< Key, Val > &from)
 Copy constructor.
 HashTableList (HashTableList< Key, Val > &&from) noexcept
 Move constructor.
 ~HashTableList ()
 Class destructor.
Operators
HashTableList< Key, Val > & operator= (const HashTableList< Key, Val > &from)
 Assignment operator.
HashTableList< Key, Val > & operator= (HashTableList< Key, Val > &&from) noexcept
 Move operator.
Accessors / Modifiers
value_typeat (Size i)
 Function at returns the ith element in the current chained list.
const value_typeat (Size i) const
 Function at returns the ith element in the current chained list.
mapped_typeoperator[] (const key_type &key)
 Returns the value corresponding to a given key.
const mapped_typeoperator[] (const key_type &key) const
 Returns the value corresponding to a given key.
bool exists (const key_type &key) const
 Returns true if a value with the given key exists.
void insert (Bucket *new_elt) noexcept
 Inserts a new element in the chained list.
void erase (Bucket *ptr)
 Removes an element from this chained list.
void clear ()
 Removes all the elements of this chained list.
bool empty () const noexcept
 Returns true if this chained list is empty.
Bucketbucket (const Key &key) const
 A method to get the bucket corresponding to a given key.
Bucketbucket (std::string_view key) const
 Heterogeneous lookup: find bucket by string_view without allocation.

Private Member Functions

void _copy_ (const HashTableList< Key, Val > &from)
 A function used to perform copies of HashTableLists.

Private Attributes

HashTableBucket< Key, Val > * _deb_list_ {nullptr}
 A pointer on the first element of the chained list.
HashTableBucket< Key, Val > * _end_list_ {nullptr}
 A pointer on the last element of the chained list.
Size _nb_elements_ {Size(0)}
 The number of elements in the chained list.

Friends

class HashTable< Key, Val >
 Friend for faster access.
class HashTableIterator< Key, Val >
 Friend for faster access.
class HashTableConstIterator< Key, Val >
 Friend for faster access.
class HashTableIteratorSafe< Key, Val >
 Friend for faster access.
class HashTableConstIteratorSafe< Key, Val >
 Friend for faster access.
std::ostream & operator<< (std::ostream &s, const HashTableList< Key, Val > &list)
 Prints the content of a gum::HashTableList in the stream.
std::ostream & operator<< (std::ostream &s, const HashTableList< Key *, Val > &list)
 Prints the content of a gum::HashTableList with pointers key in the stream.
std::ostream & operator<< (std::ostream &s, const HashTable< Key, Val > &table)
 Prints the content of a gum::HashTable in the stream.
std::ostream & operator<< (std::ostream &s, const HashTable< Key *, Val > &table)
 Prints the content of a gum::HashTable with pointers key in the stream.

Detailed Description

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

A chained list used by gum::HashTable.

Template Parameters
KeyThe type for keys in a gum::HashTable.
ValThe type for values in a gum::HashTable.

Definition at line 316 of file hashTable.h.

Member Typedef Documentation

◆ Bucket

template<typename Key, typename Val>
using gum::HashTableList< Key, Val >::Bucket = HashTableBucket< Key, Val >

types for STL compliance

Definition at line 328 of file hashTable.h.

◆ const_pointer

template<typename Key, typename Val>
using gum::HashTableList< Key, Val >::const_pointer = const value_type*

types for STL compliance

Definition at line 326 of file hashTable.h.

◆ const_reference

template<typename Key, typename Val>
using gum::HashTableList< Key, Val >::const_reference = const value_type&

types for STL compliance

Definition at line 324 of file hashTable.h.

◆ key_type

template<typename Key, typename Val>
using gum::HashTableList< Key, Val >::key_type = Key

types for STL compliance

Definition at line 320 of file hashTable.h.

◆ mapped_type

template<typename Key, typename Val>
using gum::HashTableList< Key, Val >::mapped_type = Val

types for STL compliance

Definition at line 321 of file hashTable.h.

◆ pointer

template<typename Key, typename Val>
using gum::HashTableList< Key, Val >::pointer = value_type*

types for STL compliance

Definition at line 325 of file hashTable.h.

◆ reference

template<typename Key, typename Val>
using gum::HashTableList< Key, Val >::reference = value_type&

types for STL compliance

Definition at line 323 of file hashTable.h.

◆ size_type

template<typename Key, typename Val>
using gum::HashTableList< Key, Val >::size_type = Size

types for STL compliance

Definition at line 327 of file hashTable.h.

◆ value_type

template<typename Key, typename Val>
using gum::HashTableList< Key, Val >::value_type = std::pair< const Key, Val >

types for STL compliance

Definition at line 322 of file hashTable.h.

Constructor & Destructor Documentation

◆ HashTableList() [1/3]

template<typename Key, typename Val>
gum::HashTableList< Key, Val >::HashTableList ( )
defaultnoexcept

Basic constructor that creates an empty list.

This is what is used basically by gum::HashTable.

References HashTableList(), at(), bucket(), clear(), empty(), erase(), exists(), and insert().

Referenced by HashTableList(), HashTableList(), HashTable< Key, Val >, and operator<<.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ HashTableList() [2/3]

template<typename Key, typename Val>
gum::HashTableList< Key, Val >::HashTableList ( const HashTableList< Key, Val > & from)

Copy constructor.

The new list and that which is copied do not share elements: the new list contains new instances of the keys and values stored in the copied list. Of course, if these values are pointers, the new values point toward the same elements.

Parameters
fromThe gum::HashTableList to copy.

Definition at line 147 of file hashTable_tpl.h.

147 {
148 _copy_(from);
149 }
A chained list used by gum::HashTable.
Definition hashTable.h:316
void _copy_(const HashTableList< Key, Val > &from)
A function used to perform copies of HashTableLists.

References HashTableList(), and _copy_().

Here is the call graph for this function:

◆ HashTableList() [3/3]

template<typename Key, typename Val>
gum::HashTableList< Key, Val >::HashTableList ( HashTableList< Key, Val > && from)
noexcept

Move constructor.

Parameters
fromThe gum::HashTableList to move.

Definition at line 152 of file hashTable_tpl.h.

152 :
154 from._deb_list_ = nullptr;
155 from._end_list_ = nullptr;
157 }
HashTableBucket< Key, Val > * _end_list_
A pointer on the last element of the chained list.
Definition hashTable.h:506
HashTableBucket< Key, Val > * _deb_list_
A pointer on the first element of the chained list.
Definition hashTable.h:503
Size _nb_elements_
The number of elements in the chained list.
Definition hashTable.h:509

References _deb_list_.

◆ ~HashTableList()

template<typename Key, typename Val>
gum::HashTableList< Key, Val >::~HashTableList ( )

Class destructor.

Definition at line 160 of file hashTable_tpl.h.

160 {
161 for (Bucket *next_ptr, *ptr = _deb_list_; ptr != nullptr; ptr = next_ptr) {
162 next_ptr = ptr->next;
163 delete ptr;
164 }
165 }
HashTableBucket< Key, Val > Bucket
types for STL compliance
Definition hashTable.h:328

References _deb_list_, and gum::HashTableBucket< Key, Val >::next.

Member Function Documentation

◆ _copy_()

template<typename Key, typename Val>
void gum::HashTableList< Key, Val >::_copy_ ( const HashTableList< Key, Val > & from)
private

A function used to perform copies of HashTableLists.

This code is shared by the copy constructor and the copy operator. If it cannot perform the necessary allocations, no memory leak occurs and the list is set to the empty list.

Parameters
fromThe gum::HashTableList to copy.

Definition at line 63 of file hashTable_tpl.h.

63 {
64 Bucket *ptr, *old_ptr{nullptr}, *new_elt{nullptr};
65 // set the defaults
66 _deb_list_ = nullptr;
67
68 // copy from's list
69 try {
70 for (ptr = from._deb_list_; ptr != nullptr; ptr = ptr->next) {
71 // copy the current from's bucket (may throw an exception either because
72 // new cannot allocate the bucket or because the copy constructor of Val
73 // throws an exception)
74 new_elt = new Bucket(*ptr);
75
76 // rechain properly the new list
77 new_elt->prev = old_ptr;
78
79 if (old_ptr != nullptr) old_ptr->next = new_elt;
80 else _deb_list_ = new_elt;
81
83 }
84
85 if (old_ptr != nullptr) old_ptr->next = nullptr;
86
87 // update the number of elements stored into the list and the end of the
88 // list
91 } catch (...) {
92 // problem: we could not allocate an element in the list => we delete
93 // the elements created so far and we throw an exception
94 while (_deb_list_ != nullptr) {
95 Bucket* next_elt = _deb_list_->next;
96 delete _deb_list_;
98 }
99
100 _nb_elements_ = 0;
101 _end_list_ = nullptr;
102
103 throw;
104 }
105 }

References _deb_list_, _end_list_, _nb_elements_, and gum::HashTableBucket< Key, Val >::next.

Referenced by HashTableList(), and operator=().

Here is the caller graph for this function:

◆ at() [1/2]

template<typename Key, typename Val>
HashTableList< Key, Val >::value_type & gum::HashTableList< Key, Val >::at ( Size i)

Function at returns the ith element in the current chained list.

The first element has index 0.

Parameters
iThe index to look up.
Returns
Returns the value at index i.
Exceptions
NotFoundRaised if the list has fewer than i elements.

Definition at line 206 of file hashTable_tpl.h.

206 {
207 if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
208
209 Bucket* ptr;
210
211 for (ptr = _deb_list_; i; --i, ptr = ptr->next) {}
212
213 return ptr->elt();
214 }
#define GUM_ERROR(type, msg)
Definition exceptions.h:76

References _deb_list_, _nb_elements_, gum::HashTableBucket< Key, Val >::elt(), GUM_ERROR, and gum::HashTableBucket< Key, Val >::next.

Referenced by HashTableList().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ at() [2/2]

template<typename Key, typename Val>
const HashTableList< Key, Val >::value_type & gum::HashTableList< Key, Val >::at ( Size i) const

Function at returns the ith element in the current chained list.

The first element has index 0.

Parameters
iThe index to look up.
Returns
Returns the value at index i.
Exceptions
NotFoundRaised if the list has fewer than i elements.

Definition at line 218 of file hashTable_tpl.h.

218 {
219 if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
220
221 Bucket* ptr;
222
223 for (ptr = _deb_list_; i; --i, ptr = ptr->next) {}
224
225 return ptr->elt();
226 }

References _deb_list_, _nb_elements_, gum::HashTableBucket< Key, Val >::elt(), GUM_ERROR, and gum::HashTableBucket< Key, Val >::next.

Here is the call graph for this function:

◆ bucket() [1/2]

template<typename Key, typename Val>
HashTableBucket< Key, Val > * gum::HashTableList< Key, Val >::bucket ( const Key & key) const

A method to get the bucket corresponding to a given key.

This enables efficient removals of buckets.

Parameters
keyThe key of the bucket to return.
Returns
Returns the buckket matching key.

Definition at line 108 of file hashTable_tpl.h.

108 {
109 for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
110 if (ptr->key() == key) return ptr;
111
112 return nullptr;
113 }

References _deb_list_.

Referenced by HashTableList(), and HashTable< Key, Val >.

Here is the caller graph for this function:

◆ bucket() [2/2]

template<typename Key, typename Val>
requires std::same_as< Key, std::string >
HashTableBucket< Key, Val > * gum::HashTableList< Key, Val >::bucket ( std::string_view key) const

Heterogeneous lookup: find bucket by string_view without allocation.

Definition at line 116 of file hashTable_tpl.h.

118 {
119 for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
120 if (ptr->key() == key) return ptr;
121
122 return nullptr;
123 }

References _deb_list_.

◆ clear()

template<typename Key, typename Val>
void gum::HashTableList< Key, Val >::clear ( )

Removes all the elements of this chained list.

Definition at line 168 of file hashTable_tpl.h.

168 {
169 for (Bucket *next_ptr, *ptr = _deb_list_; ptr != nullptr; ptr = next_ptr) {
170 next_ptr = ptr->next;
171 delete ptr;
172 }
173
174 _nb_elements_ = Size(0);
175 _deb_list_ = nullptr;
176 _end_list_ = nullptr;
177 }

References _deb_list_, _end_list_, _nb_elements_, and gum::HashTableBucket< Key, Val >::next.

Referenced by HashTableList(), and operator=().

Here is the caller graph for this function:

◆ empty()

template<typename Key, typename Val>
bool gum::HashTableList< Key, Val >::empty ( ) const
noexcept

Returns true if this chained list is empty.

Returns
Returns true if this chained list is empty.

Definition at line 256 of file hashTable_tpl.h.

256 {
257 return (_nb_elements_ == Size(0));
258 }

References _nb_elements_.

Referenced by HashTableList().

Here is the caller graph for this function:

◆ erase()

template<typename Key, typename Val>
void gum::HashTableList< Key, Val >::erase ( Bucket * ptr)

Removes an element from this chained list.

Parameters
ptrThe element to remove.

Definition at line 126 of file hashTable_tpl.h.

126 {
127 // check that the pointer is not nullptr
128 if (ptr == nullptr) { GUM_ERROR(NullElement, "trying to erase a nullptr bucket") }
129
130 // relink properly the doubly chained list
131 if (ptr->prev != nullptr) ptr->prev->next = ptr->next;
132 else _deb_list_ = ptr->next;
133
134 if (ptr->next != nullptr) ptr->next->prev = ptr->prev;
135 else _end_list_ = ptr->prev;
136
137 // remove the current element from the list
138 delete ptr;
139
141 }

References _deb_list_, _end_list_, _nb_elements_, GUM_ERROR, gum::HashTableBucket< Key, Val >::next, and gum::HashTableBucket< Key, Val >::prev.

Referenced by HashTableList().

Here is the caller graph for this function:

◆ exists()

template<typename Key, typename Val>
bool gum::HashTableList< Key, Val >::exists ( const key_type & key) const

Returns true if a value with the given key exists.

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

Parameters
keyThe key to test for existence.
Returns
Returns true if a value with the given key exists.

Definition at line 247 of file hashTable_tpl.h.

247 {
248 for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next) {
249 if (ptr->key() == key) { return true; }
250 }
251
252 return false;
253 }

References _deb_list_.

Referenced by HashTableList().

Here is the caller graph for this function:

◆ insert()

template<typename Key, typename Val>
void gum::HashTableList< Key, Val >::insert ( Bucket * new_elt)
noexcept

Inserts a new element in the chained list.

The element is inserted at the beginning of the list.

Parameters
new_eltThe element to add in the gum::HashTableList.

Definition at line 261 of file hashTable_tpl.h.

261 {
262 // place the bucket at the beginning of the list
263 new_elt->prev = nullptr;
264 new_elt->next = _deb_list_;
265
266 if (_deb_list_ != nullptr) _deb_list_->prev = new_elt;
267 else _end_list_ = new_elt;
268
270
272 }

References _deb_list_, _end_list_, and _nb_elements_.

Referenced by HashTableList().

Here is the caller graph for this function:

◆ operator=() [1/2]

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

Assignment operator.

The new list and that which is copied do not share elements: the new list contains new instances of the keys and values stored in the copied list. Of course, if these values are pointers, the new values point toward the same elements.

If some allocation problem occurs or if copying the Val elements cannot be performed properly, exceptions may be raised. In this case, the function guarantees that no memory leak occurs and that the list is kept in a coherent state (that of an empty list).

Parameters
fromThe gum::HashTableList to copy.
Returns
Returns this gum::HashTableList.

Definition at line 181 of file hashTable_tpl.h.

181 {
182 // avoid self assignment
183 if (this != &from) {
184 clear();
185 _copy_(from);
186 }
187
188 return *this;
189 }
void clear()
Removes all the elements of this chained list.

References _copy_(), and clear().

Here is the call graph for this function:

◆ operator=() [2/2]

template<typename Key, typename Val>
HashTableList< Key, Val > & gum::HashTableList< Key, Val >::operator= ( HashTableList< Key, Val > && from)
noexcept

Move operator.

Parameters
fromThe gum::HashTableList to copy.
Returns
Returns this gum::HashTableList.

Definition at line 193 of file hashTable_tpl.h.

193 {
194 // avoid self assignment
195 if (this != &from) {
199 from._deb_list_ = nullptr;
200 }
201
202 return *this;
203 }

References _deb_list_, _end_list_, and _nb_elements_.

◆ operator[]() [1/2]

template<typename Key, typename Val>
HashTableList< Key, Val >::mapped_type & gum::HashTableList< Key, Val >::operator[] ( const key_type & key)

Returns the value corresponding to a given key.

Parameters
keyThe key for which a value is returned.
Returns
Returns the value corresponding to a given key.
Exceptions
NotFoundis raised if the element cannot be found

Definition at line 239 of file hashTable_tpl.h.

239 {
240 for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
241 if (ptr->key() == key) return ptr->val();
242
243 GUM_ERROR(NotFound, "No element with the key <" << key << ">")
244 }

References _deb_list_, and GUM_ERROR.

◆ operator[]() [2/2]

template<typename Key, typename Val>
const HashTableList< Key, Val >::mapped_type & gum::HashTableList< Key, Val >::operator[] ( const key_type & key) const

Returns the value corresponding to a given key.

Parameters
keyThe key for which a value is returned.
Returns
Returns the value corresponding to a given key.
Exceptions
NotFoundis raised if the element cannot be found

Definition at line 230 of file hashTable_tpl.h.

230 {
231 for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
232 if (ptr->key() == key) return ptr->val();
233
234 GUM_ERROR(NotFound, "No element with the key <" << key << ">")
235 }

References _deb_list_, and GUM_ERROR.

◆ HashTable< Key, Val >

template<typename Key, typename Val>
friend class HashTable< Key, Val >
friend

Friend for faster access.

Definition at line 483 of file hashTable.h.

References HashTableList(), and bucket().

Referenced by operator<<.

◆ HashTableConstIterator< Key, Val >

template<typename Key, typename Val>
friend class HashTableConstIterator< Key, Val >
friend

Friend for faster access.

Definition at line 483 of file hashTable.h.

◆ HashTableConstIteratorSafe< Key, Val >

template<typename Key, typename Val>
friend class HashTableConstIteratorSafe< Key, Val >
friend

Friend for faster access.

Definition at line 483 of file hashTable.h.

◆ HashTableIterator< Key, Val >

template<typename Key, typename Val>
friend class HashTableIterator< Key, Val >
friend

Friend for faster access.

Definition at line 483 of file hashTable.h.

◆ HashTableIteratorSafe< Key, Val >

template<typename Key, typename Val>
friend class HashTableIteratorSafe< Key, Val >
friend

Friend for faster access.

Definition at line 483 of file hashTable.h.

◆ operator<< [1/4]

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

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

Definition at line 1091 of file hashTable_tpl.h.

1091 {
1092 bool deja = false;
1093 stream << "{";
1094
1095 for (Size i = Size(0); i < table._size_; ++i)
1096 for (auto ptr = table._nodes_[i]._deb_list_; ptr; ptr = ptr->next) {
1097 if (deja) stream << " , ";
1098
1099 stream << ptr->key() << "=>" << ptr->val();
1100
1101 deja = true;
1102 }
1103
1104 stream << "}";
1105
1106 return stream;
1107 }

References gum::HashTable< Key, Val >::_nodes_, and gum::HashTable< Key, Val >::_size_.

◆ operator<< [2/4]

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

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

Definition at line 1072 of file hashTable_tpl.h.

1072 {
1073 bool deja = false;
1074 stream << "{";
1075
1076 for (Size i = Size(0); i < table._size_; ++i)
1077 for (auto ptr = table._nodes_[i]._deb_list_; ptr; ptr = ptr->next) {
1078 if (deja) stream << " , ";
1079
1080 stream << ptr->key() << "=>" << ptr->val();
1081
1082 deja = true;
1083 }
1084
1085 stream << "}";
1086
1087 return stream;
1088 }

References gum::HashTable< Key, Val >::_nodes_, gum::HashTable< Key, Val >::_size_, and HashTable< Key, Val >.

◆ operator<< [3/4]

template<typename Key, typename Val>
std::ostream & operator<< ( std::ostream & s,
const HashTableList< Key *, Val > & list )
friend

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

Definition at line 1055 of file hashTable_tpl.h.

1055 {
1056 bool deja = false;
1057 stream << "[";
1058
1060 ptr = ptr->list.next, deja = true) {
1061 if (deja) stream << " , ";
1062
1063 stream << ptr->key() << "=>" << ptr->val();
1064 }
1065
1066 stream << "]";
1067
1068 return stream;
1069 }

References HashTableList(), and _deb_list_.

◆ operator<< [4/4]

template<typename Key, typename Val>
std::ostream & operator<< ( std::ostream & s,
const HashTableList< Key, Val > & list )
friend

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

Definition at line 1038 of file hashTable_tpl.h.

1038 {
1039 bool deja = false;
1040 stream << "[";
1041
1043 ptr = ptr->list.next, deja = true) {
1044 if (deja) stream << " , ";
1045
1046 stream << ptr->key() << "=>" << ptr->val();
1047 }
1048
1049 stream << "]";
1050
1051 return stream;
1052 }

Member Data Documentation

◆ _deb_list_

template<typename Key, typename Val>
HashTableBucket< Key, Val >* gum::HashTableList< Key, Val >::_deb_list_ {nullptr}
private

A pointer on the first element of the chained list.

Definition at line 503 of file hashTable.h.

503{nullptr};

Referenced by HashTableList(), ~HashTableList(), _copy_(), at(), at(), bucket(), bucket(), clear(), erase(), exists(), insert(), operator<<, operator=(), operator[](), and operator[]().

◆ _end_list_

template<typename Key, typename Val>
HashTableBucket< Key, Val >* gum::HashTableList< Key, Val >::_end_list_ {nullptr}
private

A pointer on the last element of the chained list.

Definition at line 506 of file hashTable.h.

506{nullptr};

Referenced by _copy_(), clear(), erase(), insert(), and operator=().

◆ _nb_elements_

template<typename Key, typename Val>
Size gum::HashTableList< Key, Val >::_nb_elements_ {Size(0)}
private

The number of elements in the chained list.

Definition at line 509 of file hashTable.h.

509{Size(0)};

Referenced by _copy_(), at(), at(), clear(), empty(), erase(), insert(), and operator=().


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