PDA

Visualizza la versione completa : [C++] Template di hash table


lovesemiramide
28-07-2013, 10:34
Premetto che so che esiste la classe unorder_map (http://www.cplusplus.com/reference/unordered_map/unordered_map/) ma io voglio implementare una mia hash table.

Ad ogni modo ho subito trovato un problema: non so come poter implementare una funzione hash valida per tutti i tipi. Avevo pensato di considerare gli indirizzi delle chiavi, ma cambiando variabile anche con stesso valore non mi restituirebbe la corretta chiave.

Qualcuno ha qualche spunto da darmi?

MItaly
28-07-2013, 14:38
Io seguirei le orme di std::unordered_map: essa accetta tra i parametri template il tipo di un functore usato per calcolare gli hash; di default, viene usato std::hash<T>, che fornisce una funzione di hash di default per tutti i tipi primitivi e diversi tipi derivati della libreria standard (vedi qui (http://www.cplusplus.com/reference/functional/hash/)). Quanto ai tipi definiti dall'utente, č possibile specificare esplicitamente il tipo del functore da usare per calcolarne l'hash, ma in genere se il programmatore vuole che il suo tipo sia usato in una hashtable dovrebbe creare una specializzazione di std::hash<T> per il suo tipo (http://stackoverflow.com/a/8157967/214671), in modo che poi si possa usare std::hash<T> senza fare null'altro di particolare.

lovesemiramide
28-07-2013, 15:59
Ok, proverņ.
Grazie mille. :D

Loading