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

Swordfish

volkard schrieb:

Endlich jemand, der genu Leerzeichen schreibt.
Da fehlen aber noch welche!

volkard schrieb:

Warum Postinkrement?

Willst ihn absichtlich verwirren?

Skym0sh0

ne das zweite leerzeichen (also das zwischen -- und war unabsichtlich. es eh egal...

und ob post- oder prä- in/de-krement ist auch egal fürs beispiel, das soll der TE selsbt entscheiden

Du musst nur den Iterator mit richtig viel Gefühl vorwärts schupsen, damit er nicht gleich gegen das Ende knallt. Erfordert etwas Übung.

Ethon

// Geht, ist aber nicht sehr elegant
    unsigned ctr(0);
    for(list<Border>::iterator it=lPolygon.begin();ctr<lPolygon.size()-1;++it,++ctr)
    {
    }

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

otze

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.

314159265358979

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.

Gibt genug Implementierungen, bei denen size() O(n) läuft, und das mit gutem Grund. Da nehme ich lieber die Variante mit dem end-Iterator.

Nexus

bts2 schrieb:

Wie kann man einen Iterator auf eine Liste über den gesamten Bereich mit
Ausnahme des letzten Elements laufen lassen?

for (list<Border>::iterator itr = lPolygon.begin(), end = std::prev(lPolygon.end()); itr != end; ++itr)

Wobei hier auch --lPolygon.end() gehen sollte. Setzt natürlich voraus, dass mindestens ein Element drin ist und die end() -Kopie dekrementiert werden kann. Übrigens bricht das Forum die Zeilen automatisch um, du brauchst es also nicht selbst zu tun

314159265358979 schrieb:

Gibt genug Implementierungen, bei denen size() O(n) läuft, und das mit gutem Grund.

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

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.

list&lt;x&gt;::iterator bis knapp vors Ende laufen lassen.

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