Qual è la differenza tra set e hashset in C++ STL?

Question

Quando dovrei sceglierne uno rispetto all'altro? Ci sono dei suggerimenti che consiglieresti di usare i contenitori STL giusti?

Answer 1

hash_set è un'estensione che non fa parte dello standard C++. Le ricerche devono essere O (1) anziché O (log n) per set, quindi sarà più veloce nella maggior parte dei casi.

Un'altra differenza si vedrà quando si scorre attraverso i contenitori. set consegnerà il contenuto in ordine, mentre hash_set sarà essenzialmente casuale (Grazie Lou Franco).

Modifica: l'aggiornamento C++ 11 allo standard C++ ha introdotto unordered_set che dovrebbe essere preferito anziché hash_set. Le prestazioni saranno simili e garantite dallo standard. Il "non ordinato" nel nome sottolinea che l'iterazione produrrà risultati in nessun ordine particolare.

Answer 2

Un hash_set sarebbe implementato da una tabella hash, che ha per lo più operazioni O (1), mentre un set è implementato da un albero di qualche tipo (AVL, rosso nero, ecc.) Che hanno O (log n) operazioni, ma sono in ordine.

Modifica: avevo scritto che gli alberi sono O (n). Questo è completamente sbagliato.

Answer 3

stl::set viene implementato come un albero di ricerca binario. hashset è implementato come tabella hash.

Il problema principale qui è che molte persone usano stl::set pensando che sia una tabella hash con la ricerca di O (1), che non è, e non ha. Ha davvero O (log (n)) per le ricerche. Altri poi che leggono sugli alberi binari vs tabelle hash per avere un'idea migliore dei datastructures.

Answer 4

Un'altra cosa da tenere a mente è che con hash_set è necessario fornire la funzione hash, mentre un set richiede solo una funzione di confronto ('<') che è più facile da definire (e predefinita per i tipi nativi).

Answer 5

Credo che nessuno abbia ancora risposto all'altra parte della domanda.

Il motivo per utilizzare hash_set o unordered_set è solitamente il tempo di ricerca O (1). Di solito dico perché ogni tanto, a seconda dell'implementazione, un hash può dover essere copiato su un più grande array di hash, o un hash bucket può finire per contenere migliaia di voci.

La ragione per utilizzare un set è se spesso è necessario il membro più grande o più piccolo di un set. Un hash non ha ordine quindi non esiste un modo rapido per trovare l'oggetto più piccolo. Un albero ha ordine, quindi il più grande o il più piccolo è molto veloce. O (log n) per un albero semplice, O (1) se contiene puntatori alle estremità.