Diciamo che ho 30000 oggetti nel mio vettore/elenco. Che aggiungo uno per uno.
Ho bisogno di loro ordinati.
È più rapido ordinare tutto in una volta (come std :: sort) oppure mantenere il vettore/elenco ordinato mentre aggiungo gli oggetti uno per uno?mantieni il vettore/lista std ordinati durante l'inserimento, o ordina tutti i
vector/list NON verrà modificato in seguito.
Quando si mantiene ordinata la lista vettoriale mentre si inseriscono gli elementi uno alla volta, si esegue fondamentalmente un ordinamento di inserimento, che in teoria esegue O (n^2) nel peggiore dei casi. Anche il caso medio è quadratico, il che rende l'inserimento non pratico per l'ordinamento di grandi matrici.
Con l'input di ~ 30000, sarà meglio prendere tutti gli input e quindi ordinarlo con un algoritmo di ordinamento più veloce.
EDIT: Come @Veritas ha sottolineato, possiamo utilizzare un algoritmo più veloce per cercare la posizione per l'elemento (come la ricerca binaria). Quindi l'intero processo richiederà tempo O (nlg (n)). Anche se, può anche essere sottolineato che qui l'inserimento degli elementi è anche un fattore da prendere in considerazione. Il caso peggiore per l'inserimento di elementi richiede O (n^2) che è ancora il tempo di esecuzione complessivo se vogliamo mantenere ordinato l'array.
L'ordinamento dopo l'input è ancora di gran lunga il metodo migliore piuttosto che mantenerlo ordinato dopo ogni iterazione.
Il l'intera procedura per mantenere ordinato l'array durante l'inserimento è l'ordinamento di inserimento. Quindi il suo modo di input è l'inserimento sort in sé. Quando il contenitore è già ordinato, beh, questo è un caso molto specifico. – Beowulf
@Veritas Ti stai dimenticando che su un vettore, l'inserimento [arbitrario] richiede O (n) tempo. O (n) tempo per elemento con n elementi totali lo rende n^2. Trovare dove inserire l'elemento non ha nulla a che fare con la sua natura quadratica. Vedi http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-summary.html#vector – wrhall
@wrhall Ho eliminato i miei commenti precedenti perché non ho letto correttamente la domanda. Ho pensato che occasionalmente inseriva elementi, risultando in un inserimento di tempo O (n). – Veritas
Mantenendo il vector ordinato durante l'inserimento si otterrebbe una prestazione quadratica poiché in media si dovrà spostare di circa metà del vettore per ogni articolo inserito. L'ordinamento una volta alla fine sarebbe n log(n), piuttosto veloce.
A seconda delle esigenze è anche possibile che set o map sia più appropriato.
Né. Usa 'std :: set'. Modifica: a meno che non si desideri inserire tutti gli oggetti, quindi ordinarli e quindi non modificare mai più il contenitore. In tal caso, basta usare un vettore e ordinarlo una volta. – Thomas
@Nick: sì, 'set' è _always_ ordinato. Forse stai pensando a 'unordered_set'? –
'std :: vector' e' std :: sort' probabilmente saranno molte volte più veloci di 'std :: set'. Entrambi sono 'O (N log N)' ma il vettore usa meno memoria ed è contiguo in memoria. – MSalters