Quale contenitore STL usare?

Question

quale contenitore STL devo usare se:

1. dati viene inserito e rimosso regolarmente.
2. I dati sono accessibili regolarmente a caso.

per esempio: set di dati (4,10,15) se voglio trovare il numero più vicino al 9, allora dovrebbe tornare mi 10.

1. io sono solo la memorizzazione di un numero intero.
2. Ha bisogno di essere ordinati
3. può andare a 100k dataset

Ho pensato di utilizzare vettore, ma l'inserimento e la rimozione di vettore è costoso.

vector<int> 

Se dovessi usare la lista, dovrei accedere a O (n) elementi prima di raggiungere i dati.

list<int> 

Stavo pensando di utilizzare impostato come sarà un bene se è ordinato, ma im non molto sicuro circa le efficienze per l'utilizzo SET

quindi spero che qualcuno possa dare una buona soluzione!

Answer 1

Credo che si dovrebbe controllare questo SO messaggio: In which scenario do I use a particular STL container? per piccoli formati vettore si adatta maggior parte degli scenari indipendentemente da ciò che si intende fare.

Tuttavia, il grafico è una guida, il fatto che il contenitore venga visitato regolarmente non influisce sulla scelta del contenitore, il fatto che si stia memorizzando int non è importante a meno che non si preoccupi delle dimensioni del contenitore, nel qual caso il sovraccarico dei puntatori di un contenitore di elenchi o di una mappa che ti interessa?

L'ordinamento viene eseguito automaticamente tramite la mappa ma l'ordinamento di un vettore e l'elenco possono essere molto veloci se la dimensione del contenitore è sufficientemente piccola da stare in memoria.

L'inserimento dei dati è ottimizzato per elenchi e mappe ovunque nel contenitore, per le mappe si ottiene il vantaggio che si ordinerà da solo, ma di nuovo se la dimensione è abbastanza piccola quindi la costruzione di un nuovo vettore con la nuova voce potrebbe essere molto veloce ancora .

Si potrebbe anche voler considerare le mappe di hash, sarebbe ancora meglio per profilare il codice, cercando di indovinare in secondo luogo ciò che è ottimale dipende dal tuo utilizzo e hai davvero bisogno di misurare e profilo.

Si potrebbe anche solo decidere che uno STL <map> è un equilibrio sufficiente un'ammenda o una <set> e utilizzare quei contenitori in quanto automaticamente ordinamento inserimento e la cancellazione e look up è veloce, ma c'è l'overhead di mantenere i puntatori in ciascuna voce che aumenta la dimensione della memoria utilizzata rispetto al vettore, se non ti interessa, allora potresti prendere in considerazione questi contenitori.

Tuttavia, se è importante testare e profilare e confrontare le prestazioni di ciascun contenitore, sarete sorpresi dal modo in cui il codice verrà eseguito rispetto alle vostre ipotesi.

Answer 2

La risposta alla tua domanda dipende completamente dalle dimensioni del tuo set di dati, dal momento che un elenco cresce fino a dimensioni enormi, il tempo necessario per eseguire l'attraversamento lineare per raggiungere l'elemento che devi rimuovere/inserire molto più di il tempo impiegato da un vettore per eseguire una rimozione/inserimento. Quindi se il tuo set di dati è piccolo, vai con le liste, se è enorme, vai con il vettore.

Answer 3

Se ha bisogno di essere risolto, usare un albero binario di ricerca

Answer 4

Un set è sufficientemente efficiente da inserire/rimuovere/accedere ed è sempre ordinato. L'unica cosa da considerare è che le voci negli insiemi sono const (quindi l'ordine non è rotto), quindi per cambiare, dovresti rimuovere, aggiornare e inserire

Answer 5

Se il requisito è solo prestazioni, la scelta dovrebbe essere fondamentalmente sempre un std::vector.

Evita le numerose allocazioni di memoria delle strutture di dati basate su nodi (alberi e liste) e sfrutta la località spaziale per attraversamenti molto più efficienti.

Ovviamente, inserzioni/rimozioni al centro del vettore richiedono elementi da spostare, ma anche questo è raramente sufficiente a rendere il vettore più lento rispetto ad altre strutture di dati.

Le uniche vere ragioni che vedo per l'utilizzo di altre strutture di dati sono questi:

• std::map/std::set: questi sono grandi per convenienza. Bello e facile da usare, quindi se non è richiesta una prestazione ottimale, li uso quando ho bisogno di un contenitore ordinato o di una mappa chiave/valore. (per le migliori prestazioni, un vettore ordinato può essere preferibile)
• tutti gli altri contenitori: può essere utile per la correttezza garantisce l'offerta di fronte a modifiche: il vettore spesso rialloca e sposta il suo contenuto, che invalida sia i puntatori sia iteratori nel vettore. Le altre strutture dati offrono maggiori garanzie (per uno deque, i puntatori sono garantiti per rimanere validi dopo l'inserimento/rimozione alle estremità, ma gli iteratori possono comunque essere invalidati. Per list, set e map, sono garantiti sia i puntatori che gli iteratori valido durante l'inserimento/rimozione)

Naturalmente, queste sono solo regole pratiche.

L'unica regola universalmente vera in cui è coinvolta la prestazione è "confrontarla da soli". Posso dirvi come un vector effettua tipicamente in molti scenari comuni, ma io non posso dirvi come si svolge nel il codice, con tua compilatore e vostra libreria standard. Quindi se ti preoccupi delle prestazioni, misuralo. Prova le diverse alternative e vedi quale è più veloce.