spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

1) Weil man Iteratoren keine Ordnung haben. Es ist nicht definiert, dass ein Iterator grösser oder kleiner ist als ein anderer. Darum machst du nur den Vergleich, ob der Iterator end entspricht.

2) Kommt drauf an. Mit den Klammern kannst du nachher auf das dereferenzierten Objekt zugreifen, währen die Variante ohne Klammern eher zuerst eine Funktion aufruft und dann dereferenziert.



3)
Das ist der Punkt bei linearen Listen. Du hast da eine verknüpfung von Objekt zu Objekt und kannst daher nicht wahlfrei auf ein Objekt zugreifen. Wenn du ein bestimmtes Objekt willst, dann musst du an den Anfang der Liste gehen und dann um diese bestimmte Anzahl an Elementen weitergehen. Dafür gibt es std::advance:
http://www.cplusplus.com/reference/std/iterator/advance/



Noch ein paar Bemerkungen:

• Rück deinen Code anständig ein. Es ist extrem mühsam den so zu lesen!
• cIndianer::löschen hast du einen Kommentar drin. Das auskommentierte geht nicht, weil du in der Liste int's hast, welche du nicht freigeben musst, weil diese automatisch freigegeben werden
• Gewöhn dir an die Bezeichner in Englisch zu benennen. Wenn dus doch mit Deutsch machst, dann wenigstens ohne Umlaute!
  

1. da die objekte nicht wie bei einem vector/array direkt hintereinander. es kann sein, dass das zweite element im speicher vor dem ersten liegt. daher funktioniert it < it2 nicht.
2. in deinem fall eigentlich gar nichts. wieso? es gibt einen unterschied zwischen *it-> und (*it)-> weil... edit: vergessen und auch netmehr nötig. siehe drakons post

3. du kannst nur über den iterator auf die elemente zugreifen. da sie wie gesagt nciht direkt hintereinander im speicher liegen.

dein problem ist, dass du deletest wo du es gar nicht musst. versuchs mal mit erase und lies das kapitel nochmal

edit: blah zu langsam. hab mir die CT bilder meiner hand angeschaut

Hallo zusammen, ich habe ein kleines Verständnisproblem bei der Verwendung/Unterscheidung zwischen den verketteten Listen und Vektoren und dachte mir, das passt hier gut dazu

Es geht um die Funktionen insert und erase. Diese gibt es ja für Vektoren und für Listen. Im Buch steht, dass diese sehr langsam sind und genau das verstehe ich nicht so ganz. Bei Vektoren ist es noch einleuchtend, da diese ja zusammenhängend im Speicher liegen und somit alle Elemente hinter der entsprechenden Position verschoben werden müssen.

Aber was dauert hier bei Listen lange? So wie ich es verstanden habe, wird jedes neue Element einer Liste irgendwo im Speicher angelegt und entsprechend über je einen Pointer miteinander verbunden. Wenn also ein neues Element eingefügt oder gelöscht wird, müsste doch nur ein einziger Pointer geändert werden?
Also statt: A->B->C wird eben A->D->B->C Wobei aber B und C immer noch an der gleichen Stelle im Speicher liegen.

Habe ich da etwas falsch verstanden, oder was kann dabei so lange dauern?

Hallo Cheveyo,

und Willkommen im Forum.

Also im Vergleich zu Vektoren sind Listen, was das Einfügen / Entfernen / Bewegen bzw. Ordnen von Daten angeht, effizienter. Das hast du schon richtig erkannt.
Ich weiß gerade nicht genau auf welche Textstelle im Buch du dich beziehst, aber generell gilt, dass sowohl Listen, als auch Vektoren nicht umbedingt besonders schnell sind. Für verschiedene Anwendungsgebiete jedoch eignen sich je nach dem Liste oder Vektor eher.

EDIT:

Hab gerade mal die - so vermute ich - betreffende Textstelle rausgesucht. (Seite 295, zweiter Absatz)

Heiko Kalista weist darauf hin, dass man nicht bedenkenlos oder gar verschwenderisch mit den insert() Aufrufen umgehen sollte. Aber, wie er ja sagt, benötigt man die auch eher selten. Also nur benutzen, falls umbedingt nötig.


Gruß
SaRu_

Nun, ein Faktor bei Listen ist, dass erst bis zur entsprechenden Stelle gesucht werden muss. Also muss man jedes Element suchen und kann dann an der Position das neue Element einfügen. Am Ende und am Anfang einfügen geht jedoch recht fix.
Sie sollten aber trotz allem schneller als Arrays sein, was das einfügen von Positionen angeht.

Hallo SaRu und danke für die Antwort

Das dürfte die Stelle sein (ist bei mir allerdings Seite 286 ). Was ich immer noch nicht ganz verstehe ist folgendes: Kalista schreibt, dass ein insert eben langsam ist und wenn es geht vermieden werden soll, was man in der Regel auch kann, indem man neue Elemente per push_back() oder push_front() eben ans Ende oder am Anfang der Liste anhängt, was wohl (wesentlich ?) schneller ist (Zitat: "In der Regel kann man diese einfach per push_back() oder push_front() einfügen, insert() würde dagegen kaum in Frage kommen.").

Aber wo ist jetz der Unterschied, welcher das ganze schneller macht?
Ich habe eine Liste mit den Elementen A->B->C. Nun will ich ein neues Element D an die Liste anhängen.

Fall 1)
Ich hänge es per push_front() an den Anfang: D wird irgendwo im Speicher an eine freie Stelle geschrieben und ein Pointer zu Element A wird in D gespeichert. A,B,C bleiben unverändert wo sie sind: D->A->B->C

Fall 2)
Ich hänge es per push_back() ans Ende: D wird irgendwo im Speicher an eine freie Stelle geschrieben. Der "End-Pointer" in C wird geändert in die Adresse von D. A,B,C bleiben dabei wo sie sind: A->B->C->D

Fall 3)
Ich schiebe D zwischen A und B in die Liste: D wird irgendwo im Speicher an eine freie Stelle geschrieben und ein Pointer zu Element B wird in D gespeichert. Der Pointer in A wird von der Adresse von B in die Adresse von D geändert. A,B,C bleiben wo sie sind: A->D->B->C

Wenn ich Heiko Kalista jetzt richtig verstanden habe, sind die ersten beiden zu bevorzugen, da sie schneller sind als die 3. Möglichkeit. Allerdings sehe ich den Unterschied nur darin, dass bei 3) eine weitere Variable geändert werden muss (Pointer in A), was eigentlich nicht lange dauern kann.

Edit: Ah, da kam der Beitrag von MCP dazwischen
Das ist dann der Unterschied, an den ich nicht gedacht habe. Bei Listen kann ich also nicht einfach sagen: an 10. Stelle einfügen, sondern muss die Liste erst vom ersten Element durchlaufen, bis zum 10. und hier dann den Pointer ändern, richtig? Das klingt dann natürlich logisch

Danke für die Erklärung!

Zitat von »Cheveyo«

Fall 3)
Ich schiebe D zwischen A und B in die Liste: D wird irgendwo im Speicher an eine freie Stelle geschrieben und ein Pointer zu Element B wird in D gespeichert. Der Pointer in A wird von der Adresse von B in die Adresse von D geändert. A,B,C bleiben wo sie sind: A->D->B->C

Wenn ich Heiko Kalista jetzt richtig verstanden habe, sind die ersten beiden zu bevorzugen, da sie schneller sind als die 3. Möglichkeit. Allerdings sehe ich den Unterschied nur darin, dass bei 3) eine weitere Variable geändert werden muss (Pointer in A), was eigentlich ni

Siehe mein Post: Der Zeiger muss sich erst über die Liste hangeln um bis zu der Stelle zu kommen, an der D eingefügt werden soll. Bei einer kleinen Liste macht es kaum einen Unterschied, aber wenn Du Hunderte oder gar Tausende Objekte in Deiner Liste hast, dann kann es ein Performance Problem geben (Bottleneck).
Hab ich eine Liste mit A->B->C->D->E->F->H->J und möchte nach F ein G einfügen, dann muss ich bei A anfangen über B, C, D, E und F gehen um zu sehen das ich die Pointer von F und H verändern muss.

Edith sagt: Haste ja schon gesehen, dann ist ja gut.

Zitat von »MCP«

Siehe mein Post: Der Zeiger muss sich erst über die Liste hangeln um bis zu der Stelle zu kommen, an der D eingefügt werden soll. Bei einer kleinen Liste macht es kaum einen Unterschied, aber wenn Du Hunderte oder gar Tausende Objekte in Deiner Liste hast, dann kann es ein Performance Problem geben (Bottleneck).
Hab ich eine Liste mit A->B->C->D->E->F->H->J und möchte nach F ein G einfügen, dann muss ich bei A anfangen über B, C, D, E und F gehen um zu sehen das ich die Pointer von F und H verändern muss.

Kannst du mir bitte mal eine Implementation von einem list::insert zeigen, die das so seltsam macht? Gerne auch eine selbstgeschriebene Variante.
Bei mir läuft insert immer in O(1). Auszug aus einer list-impl, die mal zur Übung geschrieben wurde:


Edit: Oder gehts wirklich nur darum, dass man an der n-ten Stelle einfügen will, und keinen iterator hat? Dann hat das aber kaum was mit insert an sich zu tun, das suchen steckt dann ja ganz woanders.