Templates in verketteten Listen. Dritter und letzer Versuch..es muss doch irgendwie gehen!

[lgn]

Hallo,

leider hänge ich immernoch bei dem Problem mit den Templates in verketteten
Listen fest. Deswegen noch ein letzter Versuch zu fragen ob nicht jemand eine
Lösung oder Idee zu diesem Problem hat.

Ich habe eine objekt-orientierte verkettete Liste geschrieben. Der Kopf-, End-
und Datenknoten erben von der abstrakten Klasse Node.

Da ich eine Vielzahl von unterschiedlichen Objekten in Listen speichern möchte,
möchte ich die verk. Liste mit Template-Objekten arbeiten lassen.
Das geht auch, bis zu diesem Punkt:

class Node
{
public:
  ..
  template <class T>
  Node * add(DataNode<T> *t){}
  ..
}

Da die Funktion eine Template-Funktion ist, kann ich diese nicht als virtuell
deklarieren. Implementieren geht nicht, weil die Klasse abstrakt ist.
Implementiere ich sie leer, wie im obrigen Beispiel, wird immer add von Node
aufgerufen und es passiert (logischerweise) nichts. Und spezifiziere ich diese
Methode (add(DataNode<Typ1> *t)) muss ich diese in abgeleiteten Klassen für alle
Typen überschreiben und führe damit Templates ad absurdum.

Das Problem nochmal vereinfacht: Es wird immer ein Node-Zeiger zurückgeliefert,
es soll aber die entsprechende add-Methode des Objekt ausgeführt werden.

Gibt es irgenteine Möglichkeit eine verkettete Liste mit Templates so oder
ähnlich zu realisieren?

Hat die STL vielleicht etwas zu bieten, womit sowas ginge?

[GPC]

lgn schrieb:

Da ich eine Vielzahl von unterschiedlichen Objekten in Listen speichern möchte,
möchte ich die verk. Liste mit Template-Objekten arbeiten lassen.

Bloss zum Verständniss, willst du eine inhomogene Liste, also eine die mehrere Objekte unterschiedlichen Typs enthält, oder eine homogene, also eine die nur Objekte des selben Typs enthält? Vllt. kann man dir ja dann helfen

[lgn]

Danke, das ging wirklich schnell

Also die Listen sollen homogen sein. Also eine Liste mit Typ1 und eine andere mit
einem anderen Typen.

[ness]

Ich glaube dein ansatz ist falsch. Alle nodes sind gleich. Nix kopf- und fußnode. Also eher:

template<class T>
class list
{
private:
    struct node
    {
        T data;
        node* next,prev;
    };
    node* head;
public:
    //...
};

[lgn]

Vielen Dank. Ich werde das so probieren.

Ich hab allerdings ein Verständnisproblem bei dem Beispiel.
Wie erzeuge ich überhaupt neue Knoten? (es werden ja struct-Variablen und nicht
deren Klassen-Objekte miteinander verknüpft)

Anmerkung:

so wie ich das sehe brauche ich auch zwei add-Methoden, eine void und eine, die
einen Zeiger auf eine Node-Struktur zurückliefert.

Mit der void-methode wird dann hinzugefügt (Liste->add(Typ1 *t)), die andere ist
intern, bekommt einen Zeiger übergeben und liefert einen Zeiger für Node next
zurück (um die Objekte zu delegieren und an der richtigen Stelle anzufügen).

Ist das so in etwa richtig?

[otze]

ich gb dir jetzt nur einige beispielzeilen code von denen du sehr schnell schließen kannst wie die liste funktioniert:

node* newNode=new node;
head->next=newNode;
newNode->prev=head;

und das ergebnis davon ist folgende liste(pfeile geben richtungen an in denen man sich bewegen kann):

head---->newNode
    <----

[ness]

Ich glaube mal, er weiß, wie eine liste funktioniert. Die idee ist, den Kram zu kapseln:

template<class T>
class list
{
private:
    struct node
    {
        T data;
        node* next,prev;
        node(const T& d,node* n,node* p)
            :data(d),next(n),prev(p)
        {
        };
    };
    node* head;
public:
    typedef node* iterator;    

    iterator push_back(const T& t)
    {
        node* l=head;
        while(l->next)
            l=l->next;
        l->next=new node(t,0,l);
        return l->next;
    };

    iterator push_front(const T& t)
    {
        head->prev=new node(t,head,0);
        head=head->prev;
        return head;
    };

    iterator insert(const T& t,iterator i)
    {
        i->next=new node(t,i->next,i);
        return i->next;
    };
    //...
};

Keine Ahnung ob das hetzt alles perfekt ist, ...

[Vorden]

ness schrieb:

Ich glaube mal, er weiß, wie eine liste funktioniert. Die idee ist, den Kram zu kapseln:

template<class T>
class list
{
private:
    struct node
    {
        T data;
        node* next,prev;
        node(const T& d,node* n,node* p)
            :data(d),next(n),prev(p)
        {
        };
    };
    node* head;
public:
    typedef node* iterator;    

    iterator push_back(const T& t)
    {
        node* l=head;
        while(l->next)
            l=l->next;
        l->next=new node(t,0,l);
        return l->next;
    };

    iterator push_front(const T& t)
    {
        head->prev=new node(t,head,0);
        head=head->prev;
        return head;
    };
    
    iterator insert(const T& t,iterator i)
    {
        i->next=new node(t,i->next,i);
        return i->next;
    };
    //...
};

Keine Ahnung ob das hetzt alles perfekt ist, ...

Du verwendest bei nem struct nen Konstruktor??
structs führen keine Methoden mit sich ( jedenfalls meines Wissens nach)

[akari]

Hallo

Du verwendest bei nem struct nen Konstruktor??
structs führen keine Methoden mit sich ( jedenfalls meines Wissens nach)

Doch. In C++ ist der einzigste Unterschied zwischen struct und class, das die Member von class per Default private sind, bei struct public.

bis bald
akari

[Vorden]

Ich dachte immer, dass structs keine Methoden enthalten können...
Bei structs is doch dann eh immer alles public, wenn ich mich recht entsinne

[akari]

Hallo

also noch einmal : in C++ kannst du mit structs alles machen, was du auch mit clas machen kannst, auch private verwenden. Nur die Standardsichtbarkeit der Meber ist unterschiedlich.

bis bald
akari

[ness]

Ich denke mal volkard wollte eher darauf hinaus, dass structs keine methoden enthalten sollten, da sie (ehemals) nur zur datenhaltung gedacht waren. Ich finde aber halt

f = new foo(a,b);

schöner als

f = new foo;
f.a = a;
f.b = b;

keine ahnung ob sowas wie f = new foo({a,b}) geht (impliziter copy-ctor?).

[Caipi]

ness schrieb:

Ich denke mal volkard

volkard? Sicher? ;).

Btw:

iterator insert(const T& t,iterator i)
    {
        i->next=new node(t,i->next,i);
        return i->next;
    };
    //...
};

Hier bekommt new node->next einen Zeiger auf sich selbst... (Außerdem bekommt das dynamische Objekt hinter new node keinen Zeiger auf new node als previous...)

Außerdem:

...
    struct node
    {
        T data;
        node* next,prev;
        node(const T& d,node* n,node* p)
            :data(d),next(n),prev(p)
        {
        };
    };
...

legst du in dieser Struktur nur einen Pointer next an. prev ist ein normales Objekt vom Typ node ;).

Caipi

[lgn]

Vielen Dank für die ausführlichen Beispiele.