Wie kommt es zufällig Löschung von einem std :: vector ist schneller als eine std :: list?

Question

Wie kommt es, dass zufällige Löschung von einem std :: vector ist schneller als eine std :: list? Was ich tue, es zu beschleunigen, ist das Zufallselement mit dem letzten Austausch und dann die letzten löschen. Ich hätte gedacht, dass die Liste schneller sein würde, da zufällige Löschung ist, was es für gebaut wurde.

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();
}

Ergebnisse (in Sekunden):
Vec Swap löschen: ,00000909461232367903
Auflisten normalen löschen: 0,00011785102105932310

Answer 1

Was Sie tun, ist nicht zufällig Löschung though. Sie sind von dem Ende zu löschen, die was Vektoren für die (unter anderem) gebaut ist.

Und wenn Swapping, sind Sie einen einzelnen Zufallsindexierungsvorgang zu tun, das ist auch , welche Vektoren ist gut.

Answer 2

Der Unterschied zwischen std::list und std::vector ist nicht nur nach unten, um die Leistung. Sie haben auch verschiedene Iterator Ungültigkeits Semantik. Wenn Sie ein Element aus einem std::list löschen, alle Iteratoren auf andere Elemente in der Liste zeigt weiterhin gültig. Nicht so bei std::vector, wo ein Element Löschen entkräftet alle Iteratoren nach diesem Element zeigen. (In einigen Implementierungen können sie immer noch als gültig Iteratoren dienen, sondern nach der Norm sind sie jetzt unbrauchbar, und eine Kontrolle der Durchführung sollte geltend machen, wenn Sie versuchen, sie zu verwenden.)

So Ihre Wahl der Behälter ist auch mit dem zu tun, was Semantik Sie benötigen.

Answer 3

Das ist nicht zufällig. Versuchen Sie vector1.erase (vector.begin () + rand ()% vector.size ()); statt.

Answer 4

Die Liste erase bewirkt, dass die gelöschten Listenelement löschen, wird dies einen Aufruf an die delete Operator aufzurufen. Der Vektor Lösch verursacht nur eine Swap und dann eine ganze Zahl Dekrement -. Dies viel schneller ist

Answer 5

Eigentlich, wenn Sie weitere Geschwindigkeits-ups wollen Sie sollten Indexelemente in den Vektor über Iteratoren . Sie sind dafür bekannt eine bessere Leistung für einige Architekturen haben.