Devo usare std :: set o std :: unordered_set per un set di puntatori?

Ho una serie di puntatori. Nel primo passaggio, inserisco i puntatori di dati e, nella seconda fase, eseguo l'iterazione sull'intero insieme e faccio qualcosa con gli elementi. L'ordine non è importante, ho solo bisogno di evitare i duplicati, che funziona bene con il confronto dei puntatori.Devo usare std :: set o std :: unordered_set per un set di puntatori?

La mia domanda è, se potrebbe essere vantaggioso utilizzare un set non ordinato per lo stesso scopo. L'inserimento è più veloce per un set non ordinato?

fonte

2016-02-19 Fabian

"L'ordine non è importante" - una volta deciso, usa 'unordered_set'. L'unico svantaggio di contenitori ordinati è ... l'ordine. –

Di quanti elementi stiamo parlando? E fai un lavoro intensivo di calcolo su ogni oggetto o è più come sommare/moltiplicare tutti gli elementi? – MikeMB

I contenitori ordinati hanno un altro importante vantaggio è che può garantire che il tempo per ogni operazione sia O (lg n) mentre quelli non ordinati richiedono O (n) nel caso peggiore. Quindi se vuoi fare promesse sulla complicità, usa std :: set. – James

Come ha commentato Ami Tavory, se non è necessario l'ordine, di solito è meglio andare per contenitori non ordinati. La ragione è che se l'ordine in qualche modo migliora le prestazioni, i contenitori non ordinati sarebbero comunque liberi di usarlo, e quindi ottenere comunque la stessa o migliore complessità.

Uno svantaggio di raccolte non ordinate è che in genere richiedono una funzione hash per il tipo di chiave. Se è troppo difficile o costoso crearne uno, allora i contenitori che non usano gli hash potrebbero essere migliori.

In libreria standard C++ s ', la complessità media inserimento per std::set è O (log (N)), mentre per std::unordered_set è O (1). A parte questo, ci sono probabilmente meno errori di cache in media quando si utilizza std::unordered_set.

Alla fine della giornata, però, questa è solo teoria. Dovresti provare qualcosa che suoni abbastanza bene e profilarlo per vedere se lo è davvero.

fonte

2016-02-19 12:32:36

Per i puntatori, che è la domanda, c'è una specializzazione di '' std :: hash'' nella libreria standard, quindi niente di cui preoccuparsi. –

Un'altra cosa da considerare, è che il comportamento del confronto di puntatori non correlati (che non punta allo stesso array o nello stesso oggetto) non è definito. Quindi, in senso stretto, non è sicuro archiviare i puntatori in 'std :: set' –

Dato che si menziona la complessità: la ricerca nel caso peggiore non è rilevante per la domanda originale, ma O (N) per unordered_set può essere un motivo per scegliere un set ordinato invece. Un altro argomento * per * l'inadempienza a non ordinato è l'espressione di intenti: il lettore vede che non ti interessa l'ordine. – peterchen

Devo usare std :: set o std :: unordered_set per un set di puntatori?

risposta

Problemi correlati