ein paar fragen zu listen
-
auch wenn ich mich im folgenden auf c++ beziehe soll es eine allgemeine frage sein.
ich programmiere mir gerade eine eigene listenklasse in c++ und mir sind da viele "probleme" aufgefallen, die "normale/einfache" listen nicht vollständig realisieren - vielleicht weiß ich es aber nur nicht besser und man kann alles auch mit std::list machen.
meine frage an euch:
was für listenklassen verwendet ihr denn so? und wie könnte man eine liste, die folgendes realisieren soll, am besten programmieren?
die liste soll...
- keine dynamischen, also mit new innerhalb der liste erzeugten knotenpunkte besitzen, sondern knotenpunkte als eigene(externe) klassen/strukturen besitzen, so das der programmiere selbst entscheiden kann ob er die knoten auf dem stack erzeugt oder dynamisch mit new auf dem heap. (-> dann erspart man sich das ständige new und delete, wenn man eine gekapselte listenklasse hat, die die knoten intern selber erzeugt und löscht)
- mehrere (unbegrenzt bzw. speicherabhängig) iteratoren zu selben zeit ermöglichen um auf alle knotenpunkte der liste zugreifen zu können und um sich in der liste hin- und herbewegen zu können.
- mehrere knoten pro datenpaket erlauben. also ein "datenknoten" soll mittels mehrerer "listenknoten" in meheren listen gleichzeitig benutzt werden können. das ist eigentlich relativ einfach und funktioniert auch meistens automatisch.
alles andere spielt keine rolle. also z.b. wenn die liste auch noch mitzählen kann wieviel knoten sie hat, dann hab ich natürlich nichts dagegen. aber sowas kostet, soweit ich das bis jetzt beurteilen kann, zuviel verwaltungsrechenzeit, da jeder knoten in der liste registriert werden muss, denn wenn mit einer anderen liste oder einem fremden iterator der knoten gelöscht wird, dann müssen ja alle anderen listen eine nachricht erhalten, das der knoten entfernt wurde damit sie ihren knotenzähler um eins verringert können... das wird dann ziemlich komplex, da man listen in der eigentlichen listenklasse braucht
ich habe einen ansatz der mit einer CList-klasse einer CListNode-klasse und einer CListIterator-klasse arbeitet, die alle friends untereinader sind und die sich alle gegenseitig registrieren, wenn sie beziehungen zueinander haben. das problem ist nun, daß dieser ansatz relativ komplex und rechenintensiv ist und auch noch ein paar logische "schönheitsfehler" hat. wenn z.b. ein iterator auf einen knoten zeigt und dieser knoten mittel einem anderen iterator gelöscht wird, was soll dann mit dem anderen iterator passieren? soll der dann einfach auf nichts zeigen oder auf den nächsten knoten?
-
Ein großteil Deiner Probs ist gelöst, wenn Du eine Liste mit Zeigern verwendest. Was Du willst (mehrere Iteratoren etc) kannst Du problemlos mit (fast) jeder beliebigen Listen-Implementation machen.
Dass mit dem Löschen, wenn zwei Iteratoren auf den gleichen Knoten zeigen, wirst Du so einfach nicht hinbekommen. Außer jedes Iterator-Instanz würde auch alle anderen Iteratoren kennen und denen das mitteilen.
Die Frag ist aber, ob das was bringt. Denn: was machen die Iteratoren, wenn Ihnen das mitgeteilt wird? Du bräuchtest ein definiertes Verhalten. Und Du müsstest überall, wo du die Iteratoren verwendet werden jedesmal prüfen, ob das Teil noch auf den Knoten zeigt, den Du willst. imho ist das eher ein Designproblem, das sich anderweitig, d.h. in der Programmlogik, sauberer lösen lässt.