aGrUM  0.13.2

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

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 1200 of file hashTable_tpl.h.

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

1201  {
1202  bool deja = false;
1203  stream << "[";
1204 
1205  for (HashTableBucket< Key, Val >* ptr = list.__deb_list; ptr;
1206  ptr = ptr->list.next, deja = true) {
1207  if (deja) stream << " , ";
1208 
1209  stream << ptr->key() << "=>" << ptr->val();
1210  }
1211 
1212  stream << "]";
1213 
1214  return stream;
1215  }
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 1218 of file hashTable_tpl.h.

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

1219  {
1220  bool deja = false;
1221  stream << "[";
1222 
1223  for (HashTableBucket< Key, Val >* ptr = list.__deb_list; ptr;
1224  ptr = ptr->list.next, deja = true) {
1225  if (deja) stream << " , ";
1226 
1227  stream << ptr->key() << "=>" << ptr->val();
1228  }
1229 
1230  stream << "]";
1231 
1232  return stream;
1233  }
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 1236 of file hashTable_tpl.h.

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

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::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 1256 of file hashTable_tpl.h.

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

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