Come mai l'eliminazione casuale da uno std :: vector è più veloce di uno std :: list?

Question

Come mai che la cancellazione casuale da uno std :: vector è più veloce di uno std :: list? Quello che sto facendo per accelerarlo è lo scambio l'elemento casuale con l'ultimo e quindi l'eliminazione dell'ultimo. Avrei pensato che l'elenco sarebbe più veloce in quanto l'eliminazione casuale è ciò che è stato costruito per.

for(int i = 500; i < 600; i++){
    swap(vector1[i], vector1[vector1.size()-1]);
    vector1.pop_back();
}

for(int i = 0; i < 100; i++){
        list1.pop_front();
}

Risultati (in secondi):
di swap Vec cancellare: 0.00000909461232367903
Lista normale eliminare: 0,00011785102105932310

Answer 1

Quello che stai facendo non è la cancellazione a caso però. Si sta cancellando dalla fine, che è quello che i vettori sono costruiti per (tra le altre cose).

E quando lo scambio, si sta facendo una sola operazione di indicizzazione casuale, che è anche quello vettori sono bravi a.

Answer 2

La differenza tra std::list e std::vector non è solo verso il basso per le prestazioni. Essi hanno anche una semantica diversa iteratore di invalidazione. Se si cancella un elemento da una <=>, tutti gli iteratori che puntano ad altri elementi nell'elenco rimangono valide. Non così con <=>, in cui la cancellazione di un elemento invalida tutti gli iteratori che puntano dopo tale elemento. (In alcune implementazioni, essi possono ancora servire come iteratori validi, ma secondo lo standard ora sono inutilizzabili, e un'implementazione controllo dovrebbe valere se si tenta di utilizzarli.)

Quindi, la vostra scelta di contenitore è anche a che fare con ciò che la semantica si richiedono.

Answer 3

Non è casuale. Prova vector1.erase (vector.begin () + rand ()% vector.size ()); invece.

Answer 4

La lista erase causerà per eliminare l'elemento della lista cancellata, questo richiamerà una chiamata al delete dell'operatore. Il vettore cancellazione provoca solo uno swap e poi un decremento intero -. Questo è molto più veloce

Answer 5

In realtà se si vuole ulteriormente la velocità-up si dovrebbe elementi di indice nel vettore tramite iteratori . Essi sono noti per avere prestazioni migliori per alcune architetture.