Qual è un buon metodo per * temporaneamente * ordinare un vettore?

Ho un std :: vector che ho bisogno di ordinare per algoritmi selezionati per certe operazioni, ma per mantenere il suo stato originale (ad esempio, gli oggetti ordinati da quando sono stati inseriti) per il resto del tempo.Qual è un buon metodo per * temporaneamente * ordinare un vettore?

Ovviamente posso usare std :: copy per creare un vettore temporaneo e ordinarlo, ma mi chiedo se c'è un modo migliore, possibilmente con il timestamp degli elementi inseriti.

Acclamazioni

fonte

2010-02-22 deworde

Perché? L'ordinamento è 'O (N log N)', per non parlare del fattore costante; copiare è direttamente 'N * sizeof (T)' scrive la memoria assumendo gli elementi POD. Inoltre potresti facilmente escludere il tempo di copia dall'analisi comparativa. – kennytm

Supponendo che gli elementi POD, la copia è tempo costante (suggerimento: pensare * memcpy *), e abbastanza veloce a quello. –

La copia non è un tempo costante, @Stingray. E 'acceso). –

si potrebbe creare uno std :: vector che contiene tutti gli indici del primo vettore. Puoi quindi ordinare il vettore dell'indice come preferisci. Questo dovrebbe essere veloce e, soprattutto, non significa che devi copiare il primo vettore (che è probabilmente più costoso!).

fonte

2010-02-22 17:33:05 monoceres

+1 per le dita più veloci, stava postando più o meno la stessa risposta. –

Avrei usato una serie di puntatori malloc'a vecchio stile e ho chiamato qsort ma anche questo funziona. – Joshua

@Joshua: la maggior parte delle volte funziona meglio - qsort di solito è un po 'più lento di std :: sort. –

Ogni vettore specificato verrà ordinato al massimo in un modo e in qualsiasi momento.

ci sono due alternative:

Copiare un vettore temporanea e tipo che come desiderato. A meno che il vettore non sia molto grande e tu abbia uno spazio limitato, questo è quasi sicuramente il modo migliore. Anche se sei preoccupato per le prestazioni, il costo di una copia sarà inferiore al costo di ordinamento, e se il costo della copia è significativo, l'ordinamento sarà molto più lento della copia.

In alternativa, è possibile mantenere in qualche modo (il timestamp che hai menzionato?) Di essere in grado di ordinare il vettore di nuovo all'ordine originale. Questo sarà lento, dato che vorresti farlo solo se il vettore fosse molto grande, ma se non puoi creare un vettore temporaneo questo è l'unico modo per farlo.

fonte

2010-02-22 17:33:12

La copia può essere costosa se non è un vettore di puntatori, dipende anche da come il copisturbo è impiantato. –

@Binary Worrier: Penso che il punto di David sia che l'operazione di ordinamento sul vettore fa un mucchio di copie quando muove gli elementi intorno. Se l'ordinamento è O (n log n) l'aggiunta di un'operazione di copia O (n) inizialmente non modifica la complessità temporale complessiva. –

Se la copia è costosa, l'ordinamento è più importante. Come prevedi di ottenere un vettore ordinato senza copiare ogni elemento nel suo nuovo posto? (In realtà, il costruttore di copie potrebbe essere molto più costoso dell'operatore di assegnamento, nel qual caso la cosa corretta da fare è di riparare il costruttore di copie.) Non sto pensando a casi in cui il costruttore di copie dovrebbe essere molto più costoso.) –

Qualsiasi elemento si stia ordinando, è possibile inserirlo in una struttura con più campi di ordinamento.

struct someThing 
{ 
    int sortOrder1; 
    int sortOrder2; 
    ... 
    int sortOrderN; 
    //payload data object here 
} //note: this code may have some sytax errors (I haven't actually tried compiling this ;), but hope the idea is clear

(o forse aggiungere le ordinamento alla struttura di base stessa?)

Poi, quando è necessario in grado di calcolare i diversi ordinamenti, e ri-ordinare la vostra lista a seconda di quale tipo di ordine è necessario .

fonte

2010-02-22 17:33:57 FrustratedWithFormsDesigner

Se non ti dispiace un po 'di Boost puoi usare la libreria MultiIndex. Vedi this answer da me dove troverai del codice di esempio.

Fondamentalmente, consente di mantenere più "viste" degli stessi dati, ciascuna con un ordine diverso. Nel tuo caso sarai in grado di mantenere una vista "sequenza", in cui i dati sono in ordine di inserimento (come un vettore) e una vista "ordinata" in cui i dati sono ordinati secondo un criterio (come una mappa) .

fonte

2010-02-22 17:42:22 Manuel

Suggerisco di memorizzare puntatori intelligenti, sui dati originali, in ogni vector. std::vector consente di fornire diversi metodi per l'ordinamento. Inoltre, con puntatori intelligenti, verranno automaticamente distrutti quando tutti i riferimenti all'elemento vengono rimossi.

fonte

2010-02-22 18:12:46

Qual è un buon metodo per * temporaneamente * ordinare un vettore?

risposta

Problemi correlati