Wie realisiere ich den end() iterator?

Hallo!

Bisher war es immer so das mein end-Iterator auf das letzte Element "gezeigt" hat.
Jetzt will ich aber, das er quasi auf ein (nicht vorhandenes) Element nach dem letzten Element zeigt, damit man mit dem End-iterator while und for-Schleifen bauen kann (wie bei der STL).

Meine Idee war das hier:

inline  Iterator<T> End  ()
{ 
Node<T> *temp = new Node<T>(last);  
Iterator<T> itTemp(temp);  return(itTemp); 
};

Es wird ein neuer Knoten erstellt und an die Liste rangehangen. Allerdings bleibt der last pointer vom echten letzten Listenelement auf 0. Ansonsten
könnte man ja auch nur immer einen end Iterator haben, da mit jeden neu Erstellten der Vorherige ungültig wird.
Dann wird ein Iterator erstellt und ihm wird der neue Knoten zugewiesen.

Problem:
So werde ich niemals auf Gleichheit kommen, begin == end wird sich niemals erfüllen, da man zwar mit ++ und -- navigieren kann, allerdings nie über den Listenanfang / das Listenende hinaus.
Somit erreicht begin mit seinem Knoten nie den Knoten von end.

Ich bin da gerade ein wenig ratlos

otze

erstmal:

inline  Iterator<T> End  ()
{
    Node<T> *temp = new Node<T>(last);  
    Iterator<T> itTemp(temp);  return(itTemp);
};

Ich bin mir nicht sicher, aber sollte das nicht ein dickes resource leak geben?(oder kommt danach noch irgendwo ein delete?)

zu deiner frage: du arbeitest mit einer liste, wenn du willst, kannst du also einen speziellen end-node ans Ende der liste hängen.

Ponto

1. Da dein letztes Element auf 0 zeigt, koennte dein End Iterator dies auch machen.
2. Du koenntest in deine Liste einen speziellen End Knoten einfuegen. Wenn dann neue Elemente in die Liste eingefuegt werden, kommen sie zwischen das letzte Element und den End Knoten.

Nein, es gibt kein Speicherleck, dass hätte ich schon deleted

Die Idee mit dem end-knoten ist eine Überlegung wert, morgen wage ich mich mal daran, falls es nicht klappt melde ich mich nochmal

groovemaster

Sry, aber die Idee mit dem dynamischen temp ist Müll. Und dann wundern sich Leute, warum Performance Tests so unerwartete Ergebnisse liefern ( siehe hier). Warum nicht einfach

inline Iterator<T> End()
{
    Iterator<T> temp(&last);
    return temp;
};

?

Weil end dann nicht über das Ende hinauszeigt sondern auf das letzte Element?

So, ich denke ich hab es. Eure Lösung mit dem extra Endknoten war gut, jetzt wird einmal per new ein end-note erstellt und zwischen dem last node und end node werden die neuen Einträge angehangen.

Jetzt funktionieren auch die != und == abfragen

groovemaster

end() schrieb:

Weil end dann nicht über das Ende hinauszeigt sondern auf das letzte Element?

Na und, das macht dein Code doch genauso. Wenn du hinter das letzte Element zeigen willst, reicht

inline Iterator<T> End()
{
    Iterator<T> temp(NULL);
    return temp;
};

vollkommen aus. Du musst dann nur dafür sorgen, dass beim iterieren (operator ++) der Iterator nach dem letzten Element auf null gesetzt wird. Und das alles ganz ohne irgendwelchen dynamischen Speicher Overhead.

Ponto

groovemaster schrieb:

end() schrieb:

Weil end dann nicht über das Ende hinauszeigt sondern auf das letzte Element?

Na und, das macht dein Code doch genauso. Wenn du hinter das letzte Element zeigen willst, reicht
inline Iterator<T> End()
{
    Iterator<T> temp(NULL);
    return temp;
};
vollkommen aus. Du musst dann nur dafür sorgen, dass beim iterieren (operator ++) der Iterator nach dem letzten Element auf null gesetzt wird. Und das alles ganz ohne irgendwelchen dynamischen Speicher Overhead.

Falls es sich hier um eine doppelt verkettete Liste handelt, wird so die implementierung von operator-- komplizierter, da sie von end() nicht einfach zurückgehen kann. Dann bekommt man den Overhead einer if Abfrage pro Dekrement.

Falls man für end() ein Listenelement verwendet, muss dieses gar nicht dynamisch alloziert werden, sondern kann schon Element der Klasse sein. Man kann dieses Element auch als Anfang der Liste benutzen, so dass nur einmal die Payload verschwendet wird. Durch Vererbung kann man die auch los werden.

groovemaster

Ponto schrieb:

Falls man für end() ein Listenelement verwendet, muss dieses gar nicht dynamisch alloziert werden

Das ist ja mein Reden. Mein Code war ja mehr oder weniger auch nur Pseudo. Du hast natürlich Recht, dass es Probleme bei zB verketteten Listen gibt, wenn man einfach nur einen Nullzeiger nimmt. Das NULL stand eigentlich eher für ein Null-Element, welches hinter dem letzten Element angesiedelt ist.

So hab ich das doch schon lange erledigt, direkt nach den ersten Vorschlägen

der end Node ist jetzt ein Node Objekt, d.h. er wird 1x per new angelegt.