list<x>::iterator bis knapp vors Ende laufen lassen.
-
Nexus schrieb:
ein Spezialfall, den man vielleicht ab und zu bei Random-Access-Containern braucht.
Benutzt du mal was anderes als dichte Container oder Bäume(über die du dann eher selten iterieren wirst)? Der Spezialfall ist doch recht häufig der Fall der einen in der Praxis begegnet. Und im Grunde ist das der Einzige anständige weg, wenn man über mehrere Container parallel iterieren will. Für den Rest gibt's foreach.
Aber du iterierst sicher nicht so über
std::list.Ne, das war auch kein Iterationsargument. Sondern ein Argument dagegen, dass size() für Listen sich fundamental anders verhalten soll als das size(), von vektoren welches visuell im Code gleich aussieht. würde es size_slow() heißen (doer irgendwie anders), dann wäre das alles kein Problem, aber so wird der Code halt schwerer verständlich.
-
otze schrieb:
Wer spliced dnen eine Liste? Also so in der Praxis. Wer benutzt überhaupt Listen?
Ich
Anwendungsfall: LRU-Cache.
-
Oder jemand, der Mergesort implementieren möchte.
-
Jemand der Merge-Sort implementieren möchte ist mit Zeiger-Arrays besser bedient.
-
Bei einem Zeiger-Array kann ich gleich einen besseren Sortieralgortihmus, z.B. Quicksort verwenden.
Mergesort würde ich nur dann implementieren, wenn ich nur Bidi-Access habe. Ob das erstellen von einem Zeiger-Array da performanter ist, wage ich zu bezweifeln.
-
Quicksort ist nicht pauschal besser als Mergesort
-
Quicksort hat kleinere Konstanten, trotz gleiche Komplexitätsklasse. Natürlich kann er in Ausnahmefällen schlechter geeignet sein. Auch spielt die Wahl des Pivot Elements eine Rolle. Bei einem Schlechten Pivot Element ist Mergesort besser, da er auch im Worst Case O(N log(N)) hat, Quicksort hingegen O(N^2). Normalerweise wählt man aber das Pivot Element, indem man 3 zufällige Elemente aus der Sequenz wählt und das wertmäßig mittlere davon als Pivot, meistens ist das dann gut gewählt.
