Avatar von Nalathni
  • Nalathni

mehr als 1000 Beiträge seit 09.09.2004

Re: Diese Listen haben Vor- und Nachteile.

aber hier ging es um die Frage, ab wann eine std::list schneller wird, wenn man haeufig Elemente einfuegt und loescht.

Es kommt aber auch darauf an, wie man einfügt und löscht. Zwar ist der eigentliche Einfüge- und Löschvorgang bei std::list ziemlich schnell. Wenn die Position aber via Index angegeben wird, kann man dennoch viel Zeit verlieren, weil sich ja erst zu dem gewünschten Element vorgetastet werden muss, bevor das Einfügen oder Löschen stattfinden kann.

Wenn man bereits einen Iterator zur Hand hat, geht es sehr viel schneller. Aber oftmals hat man den eben nicht. Vor allem bei sortierten Listen ist bei std::vector die gewünschte Position dank binärer Suche normalerweise viel schneller gefunden, weil sich diese nicht effizient mit verketteten Listen durchführen lässt. Die Liste muss schon extrem groß sein, dass der Geschwindigkeitsgewinn beim Einfügen oder Löschen den Indexzugriff (oder die Suche nach dem Element) kompensieren kann. Insofern kann std::vector auch beim wahlweisen Einfügen oder Löschen performanter sein, selbst wenn der Container sehr groß ist.

Aber es gibt natürlich Sonderfälle. Wenn etwa das erste Element eines Containers gelöscht werden soll, und kein zufälliges, oder wenn ein neues Element am Anfang eingefügt werden soll, gewinnt std::list, es sei denn natürlich der Container ist entsprechend klein.

Wenn man sehr oft Modifikationen am Anfang der Liste durchführen muss (und selten in der Mitte oder am Ende), muss man sich aber natürlich die Frage gefallen lassen, warum man die Reihenfolge der Elemente nicht umkehrt. Das wäre im Prinzip ja ein Fall für einen Stack, und dafür eignet sich natürlich ein std::vector ganz hervorragend - oder gleich std::stack.

Bewerten
- +