list<x>::iterator bis knapp vors Ende laufen lassen.

[314159265358979]

Nexus schrieb:

Ob splice() allein immer ein guter Grund ist... Und welche Implementierungen haben O(n)?

splice reicht eigentlich schon als Grund, denn die Größe einer list braucht man nie. Da ist der zusätzliche int Verschwendung :p
Die SGI Lib oder wie die heißt hat eine O(n) Implementierung.

[otze]

314159265358979 schrieb:

splice reicht eigentlich schon als Grund

Wer spliced dnen eine Liste? Also so in der Praxis. Wer benutzt überhaupt Listen?

[Nexus]

otze schrieb:

Wer spliced dnen eine Liste? Also so in der Praxis.

Ist schon selten. Aber andererseits liegt Pi auch nicht ganz falsch, size() kommt auch nicht allzu häufig vor.

otze schrieb:

Wer benutzt überhaupt Listen?

Unter anderem Leute, denen schnelle Einfügungen/Löschungen in der Mitte oder dauernd gültige Iteratoren wichtig sind.

[Ethon]

otze schrieb:

Ethon schrieb:

Und das mit Abstand ineffizienteste, da list<T>::size linearen Aufwand bedeutet und du den Wert nicht cachest.

nein. a) Es ist bei aktuellen Implementationen unwahrscheinlich, dass size() O(n) ist. b) der Compiler kann das ganz gut optimieren und es besteht kein Grund, das cachen selbst zu übernehmen.

Die Diskussion war vor kurzem, libstdc++ implementiert size jedenfalls mit linearen Aufwand, also hat man das Problem schon mal mit dem G++ und Clang. Ob MS/Intel das anders machen weiß ich nicht, aber in der Begründung bei der libstdc++ steht dass es besser ist den User selbst mitzählen zu lassen als splice so zu drosseln. Eine Begründung die imho Sinn macht.

b) der Compiler kann das ganz gut optimieren und es besteht kein Grund, das cachen selbst zu übernehmen.

Bezweifle dass der Compiler das wegoptimieren kann. Und das 'cachen' würde sich ja von der Tipparbeit auf ein:

for(std::size_t i = 0, count = list.size() - 1; i != count; ++i)

beschränken, würde sich nicht lohnen dafür eine Komplexität von O(n²) zu riskieren.

[hustbaer]

314159265358979 schrieb:

Nexus schrieb:

Ob splice() allein immer ein guter Grund ist... Und welche Implementierungen haben O(n)?

splice reicht eigentlich schon als Grund, denn die Größe einer list braucht man nie. Da ist der zusätzliche int Verschwendung :p

Klar, du mit deiner jahrzehntelangen Erfahrung in der Software-Entwicklung kannst das natürlich super einschätzen.

Lern erstmal wie man Programme mit mehr als 10 Zeilen entwirft und fertigstellt.

[314159265358979]

[otze]

Ethon schrieb:

beschränken, würde sich nicht lohnen dafür eine Komplexität von O(n²) zu riskieren.

Mein Gegenargument ist: Code ist 95% Gewohnheit. Die Gewohnheit sollte man nur brechen, wenn es wirklich notwendig ist.

wenn ich an 1000 Stellen des Programms

for (std::size_t i = 0; i != c.size();++i){

stehen hab, dann macht mich eine Zeile:

for(std::size_t i = 0, count = list.size() - 1; i != count; ++i)

total nervös. Jedes mal, wenn ich sie lesen würde, würde ich wahrscheinlich etwas länger über dem Code verharren. Wenn 2 Dinge gleich sind, sollten sie gleich aussehen, ansonsten habe ich den Eidnruck, einem Fehler aufgesessen zu sein.

[Nexus]

otze schrieb:

wenn ich an 1000 Stellen des Programms

for (std::size_t i = 0; i != c.size();++i){

stehen hab

...dann hast du eine schlechte Gewohnheit. Diese Iterationsweise ist nicht die übliche für Container, sondern ein Spezialfall, den man vielleicht ab und zu bei Random-Access-Containern braucht. Aber du iterierst sicher nicht so über std::list .

[otze]

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.

[LordJaxom]

otze schrieb:

Wer spliced dnen eine Liste? Also so in der Praxis. Wer benutzt überhaupt Listen?

Ich

Anwendungsfall: LRU-Cache.

[314159265358979]

Oder jemand, der Mergesort implementieren möchte.

[hustbaer]

Jemand der Merge-Sort implementieren möchte ist mit Zeiger-Arrays besser bedient.

[314159265358979]

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.

[Ethon]

Quicksort ist nicht pauschal besser als Mergesort

[314159265358979]

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.