2008-10-19 5 views
7

ho una lista collegata che voglio ordinare parte di, ad esempio:sorta parziale di std :: list

std::sort(someIterator, otherIterator, predicate); 

std :: sort richiede iteratori ad accesso casuale per cui questo approccio non funziona. C'è una specializzazione std :: list :: sort, ma che può solo ordinare l'intera lista. Non penso di avere abbastanza accesso ai membri della lista per scrivere qualcosa da solo.

C'è un modo per farlo senza cambiare, diciamo, vettore?

+0

e qual è il motivo principale per cui si utilizza la lista anziché il vettore? Nonostante il fatto che std :: vector debba eseguire mosse su avg. mezzi elementi (ad esempio quando si elimina), è super veloce grazie alla cache. std :: vector beats std :: elenca anche in frequenti eliminazioni e inserimenti su rand. pos. Devi avere un numero molto grande di elementi da trarre profitto usando la lista. – relaxxx

+0

Onestamente non ricordo, da quando sono passato tre anni e mezzo da quando ho chiesto di essere abbastanza sicuro che in qualche modo si fosse rifattorizzato e ho lasciato quel lavoro comunque. Il punto della domanda non era tanto l'efficienza (anche se c'è una buona probabilità che ci fossero dati sufficienti che non avrei voluto duplicare tutto al volo) ma più solo curiosità; mi sembrava strano che non sembrassi in grado di fare questo tipo parziale e che ci debba essere un modo per ottenerlo. – Peter

+0

oh: D mio male ... ho trovato questa domanda attraverso la ricerca non attraverso la "pagina delle domande attive" e non ho capito che :) In realtà ho pensato che questa fosse una domanda attiva. – relaxxx

risposta

12

Come svuotare la parte dell'elenco che si desidera ordinare, in un elenco indipendente, quindi utilizzare l'ordinamento di elenco specializzato, quindi collegarlo nuovamente all'elenco originale?

+2

Questa è una buona idea. È facile dimenticare la potenza del metodo splice(). – bk1e

+0

+1 Questo è il modo più semplice per farlo. – Nawaz

2

Sì, ma sarà necessario utilizzare uno merge sort.