aGrUM  0.14.1

A efficient and flexible implementation of hash tables. More...

+ Collaboration diagram for Hash Tables:

Detailed Description

A efficient and flexible implementation of hash tables.

This file provides class HashTable. This class is both efficient and flexible: efficient because the access to elements is usually computed using a small amount of processor instructions, and flexible because several methods allow to fine tune the behavior of each hash table. For instance, a hashtable can allow or forbid different elements to have the same key. This behavior can be modified at any time during the execution of the program. Functions for hashing keys are defined in file HashFunc.h. Here again, these functions are quite flexible as they can be overloaded by the user to support new kind of keys. In addition to HashTable, the current file provides classes HashTableIteratorSafe and HashTableConstIteratorSafe (a.k.a. HashTable<>::iterator_safe and HashTable<>::const_iterator_safe) that 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 the "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 );
Warning
agrum/core/set_tpl.h To speed-up accessors in sets, we rely on the fact (which holds currently) that hashTable's iterators end are never modified by insertions or deletions of elements in hash tables. If this property were to be changed, set_tpl.h should be updated accordingly.
agrum/core/bijection_tpl.h Same as set_tpl.h but, in addition, bijections assume that once a pair (key,val) has been created in the hashtable, its location in memory will never change, even if the hashtable is resized.
agrum/core/sequence_tpl.h Same as bijection_tpl.h.
agrum/core/priorityQueue_tpl.h Same as bijection_tpl.h.
agrum/core/heap_tpl.h Same as bijection_tpl.h.

Classes

class  gum::HashTableConst
 Parameters specifying the default behavior of the hashtables. More...
 
class  gum::HashTableBucket< Key, Val >
 A recipient for a pair of key value in a gum::HashTableList. More...
 
class  gum::HashTableList< Key, Val, Alloc >
 A chained list used by gum::HashTable. More...
 
class  gum::HashTable< Key, Val, Alloc >
 The class for generic Hash Tables. More...
 
class  gum::HashTableIteratorStaticEnd
 A class used to create the static iterator used by HashTables. More...
 
class  gum::HashTableConstIteratorSafe< Key, Val >
 Safe Const Iterators for hashtables. More...
 
class  gum::HashTableIteratorSafe< Key, Val >
 Safe Iterators for hashtables. More...
 
class  gum::HashTableConstIterator< Key, Val >
 Unsafe Const Iterators for hashtablesHashTableConstIterator provides a fast but unsafe way to parse HashTables. More...
 
class  gum::HashTableIterator< Key, Val >
 Unsafe Iterators for hashtablesHashTableIterator provides a fast but unsafe way to parse HashTables. More...
 

Functions

template<typename Key , typename Val , typename Alloc >
std::ostream & gum::operator<< (std::ostream &s, const HashTableList< Key, Val, Alloc > &list)
 Prints the content of a gum::HashTableList in the stream. More...
 
template<typename Key , typename Val , typename Alloc >
std::ostream & gum::operator<< (std::ostream &s, const HashTableList< Key *, Val, Alloc > &list)
 Prints the content of a gum::HashTableList with pointers key in the stream. More...
 
template<typename Key , typename Val , typename Alloc >
std::ostream & gum::operator<< (std::ostream &s, const HashTable< Key, Val, Alloc > &table)
 Prints the content of a gum::HashTable in the stream. More...
 
template<typename Key , typename Val , typename Alloc >
std::ostream & gum::operator<< (std::ostream &s, const HashTable< Key *, Val, Alloc > &table)
 Prints the content of a gum::HashTable with pointers key in the stream. More...
 

Function Documentation

◆ operator<<() [1/4]

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

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

Definition at line 1203 of file hashTable_tpl.h.

References gum::HashTableList< Key, Val, Alloc >::__deb_list.

1204  {
1205  bool deja = false;
1206  stream << "[";
1207 
1208  for (HashTableBucket< Key, Val >* ptr = list.__deb_list; ptr;
1209  ptr = ptr->list.next, deja = true) {
1210  if (deja) stream << " , ";
1211 
1212  stream << ptr->key() << "=>" << ptr->val();
1213  }
1214 
1215  stream << "]";
1216 
1217  return stream;
1218  }

◆ operator<<() [2/4]

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

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

Definition at line 1221 of file hashTable_tpl.h.

References gum::HashTableList< Key, Val, Alloc >::__deb_list.

1222  {
1223  bool deja = false;
1224  stream << "[";
1225 
1226  for (HashTableBucket< Key, Val >* ptr = list.__deb_list; ptr;
1227  ptr = ptr->list.next, deja = true) {
1228  if (deja) stream << " , ";
1229 
1230  stream << ptr->key() << "=>" << ptr->val();
1231  }
1232 
1233  stream << "]";
1234 
1235  return stream;
1236  }

◆ operator<<() [3/4]

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

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

Definition at line 1239 of file hashTable_tpl.h.

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

1240  {
1241  bool deja = false;
1242  stream << "{";
1243 
1244  for (Size i = Size(0); i < table.__size; ++i)
1245  for (auto ptr = table.__nodes[i].__deb_list; ptr; ptr = ptr->next) {
1246  if (deja) stream << " , ";
1247 
1248  stream << ptr->key() << "=>" << ptr->val();
1249 
1250  deja = true;
1251  }
1252 
1253  stream << "}";
1254 
1255  return stream;
1256  }
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45

◆ operator<<() [4/4]

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

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

Definition at line 1259 of file hashTable_tpl.h.

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

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