19
Quando dovrei sceglierne uno rispetto all'altro? Ci sono dei suggerimenti che consiglieresti di usare i contenitori STL giusti?Qual è la differenza tra set e hashset in C++ STL?
A
risposta
28
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.
+0
Inoltre, impostare è ordinato. –
1
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.
+0
O (log n) per alberi – Andrey
+0
alberi rosso-neri sono O (n)? –
+0
Oh gesù, non posso credere di aver scritto O (n). Questa è probabilmente la cosa più stupida che ho fatto tutto il giorno. –
13
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.
+0
Perché è stato downvoted? - un albero rosso-nero è un tipo di albero di ricerca binario, e la specifica non dice che deve essere rosso-nero - è sufficiente impostare i parametri O grande per le operazioni. –
+1
Che cos'è 'stl :: set'? –
+0
@LouFranco: Probabilmente perché discute [possibili (probabilmente!)] Implementazioni piuttosto che comportamento/semantica con mandato standard. –
3
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).
+2
Esistono anche funzioni hash per i tipi nativi. –
1
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à.
Non c'è 'hashset' in STL. Ci sarà 'unordered_set' in C++ (si spera) il prossimo anno. – avakar
Parlando di questo http://www.sgi.com/tech/stl/hash_set.html – kal
@mkal: Questo non fa parte dell'STL standard. 'hash_set' è un'estensione. – kennytm