Stack mit Klassen füllen

Also ich habe einen Stack geschrieben, der sämtliche Datentypen unterstützen soll.
So weit so gut klappt ja auch alles wunderbar, und bei den standartdatentypen wird der gebrauchter Speicher während den push-aufrufen größer und während den pop-aufrufen kleiner. Wenn ich aber jetzt ne klasse als element nehme, wird der speicher auch richtig allokiert aber bei der pop-methode wird nur ein Teil des Speichers wieder freigemacht, so dass der Speicher erst frei wird wenn ich das programm beende.

Hier mal der Code:

#ifndef STACK_H
#define STACK_H

template<class T>
class Stack
    {
    private:
        struct element
            {
            element* nxt;
            T value;
            };
        element* top;
        int anz_elem;
    public:
        Stack();
        ~Stack();
        int push(T v);
        int pop(T& v);
        int get_anzahl();
        int isempty();
    };

template<class T>
Stack<T>::Stack()
    {
    top = 0;
    anz_elem = 0;
    }

template<class T>
Stack<T>::~Stack()
    {
    T dummy;
    while(pop(dummy))
        ;
    }

template<class T>
int Stack<T>::push(T v)
    {
    element *x = new element;
    if(!x)
        return 0;
    x->value = v;
    x->nxt = top;
    top = x;
    anz_elem++;
    return 1;
    }

template<class T>
int Stack<T>::pop(T &v)
    {
    element *x = top;
    if(!x)    
        return 0;
    v = x->value;
    top = x->nxt;
    delete(x);
    anz_elem--;
    return 1;
    }

template<class T>
int Stack<T>::get_anzahl()
    {
    return (anz_elem);
    }

template<class T>
int Stack<T>::isempty()
    {
    return(anz_elem == 0);
    }
#endif

In der main steht dann folgender Code:

class punkt
    {
    public:
        int i;
        int j;
        int q;
        int r;
        int z;
    };

int main()
    {
    Stack<punkt>* stck = new Stack<punkt>;
    punkt p;
    cout << "Put: " << endl;
    for(p.i = 0; p.i < 10000000; p.i++)
        {
        stck->push(p);
        cout << p.i << " ";
        }
    cout << endl << "Get: " << endl;
    while(stck->pop(p))
        cout << p.i << " ";
    if(stck->isempty())
        cout << "Empty";
    delete (stck); 
    cin >> p.i;
    }

So ich hoffe dass ihr mir helfen könnt^^ denn bei längerer laufzeit wäre dieser Speicher tödlich für das System...

Hier mal das bild vom gebrauchten Speicher:

[img=http://img61.imageshack.us/img61/1008/sanstitreji0.png]

hmm fehler in der linkangabe

hier ist der richtige link:

http://img61.imageshack.us/img61/1008/sanstitreji0.png

struct element
            {
            element* nxt;
            T value;
            };

Du hast hier keinen destructor definiert der den destructur für element aufruft und damit sieht der compiler deinen zeiger nur als integer und löscht den.

template<class T>
int Stack<T>::pop(T &v)
    {
    element *x = top;
    if(!x)    
        return 0;
    v = x->value;
    top = x->nxt;
    delete(x->next); <- irgendwie so muss dein aufruf aussehen
    anz_elem--;
    return 1;
    }

Quellcode

Leider kann ichdir nicht genua helfen... jedoch ist mir in deiner pop-methode etwas aufgefallen:

Wenn dunur ein element hast...
rutscht top auf seinen eigenen Nachfolger, der aber auf 0 zeigt...

top
|v|n|->0

x=top
|v|n|->0

Hier soltle ein Fehler sein
top=x->nxt
x
|v|n|->0

x->nxt (=top)
0

top wird also Null oder wie sehe ich das ?

EDIT:
Probier doch mal alle deine im Stack zu speichernde Klasse enthaltenen Variablen i,q,r,... als zeiger zu setzen und sie dann zu löschen. Kannst ja noch einen Konstruktur für die Klasse Punkt bauen.

@Quellcode

das habe ich jetzt nicht ganz verstanden mit dem fehler in der pop-methode^^
vielleicht könntest du dass mal etwas genauer erklären.

Quellcode

habe mitbekommen, dass die pop-Methode richtig ist... bin's nochmal Stück für Stück durchgegangen... Wo aber dein Fehler liegt weiß ich nicht... kann nur versuchen logisch daran zu gehen:

Du reservierst Speicherplatz, aber gibst ihn nicht wieder komplett frei. Irgendwo fehlt ein delete warscheinlich. Oder aber der Speicherplatz für die Integer wird nicht wieder freigegeben (wenn er überhaupt reserviert wird).

uhsuhz

ich weiß auch nicht wo das problem ist, aber der speicher wird allokiert, man sieht es ja im gebrauchten speicher, auf dem bild...

Quellcode

probier mal

delete [] stack;

uhsuhz

ia nee der stack funktionniert ja auch komplett, die löschung aber die gespeicherten klassen werden nicht ganz freigegeben, ich glaub der erste post:

Du hast hier keinen destructor definiert der den destructur für element aufruft und damit sieht der compiler deinen zeiger nur als integer und löscht den.

hat den fehler entdeckt nur sein code kann nicht klappen da ich sonst das erste element ganz lösche und somit die liste futsch ist...

uhsuhz

So hab jetzt mal was umgeändert, der speicher wird jetzt auch zur laufzeit freigemacht, ich bin mir aber nicht sicher ob es ganz richitg funktionniert... es scheint zwar so, aber ob es wirklich so ist...

template<class T>
class CStack
    {
    private:
        struct element
            {
            element* nxt;
            T* value;
            };
        element* top;
        int anz_elem;
    public:
        CStack();
        ~CStack();
        int push(T *v);
        int pop(T *v);
        int get_anzahl();
        int isempty();
    };

und dann in der main:

int main()
    {
    CStack<punkt>* cstck = new CStack<punkt>;
    punkt *p = new punkt;
    cout << sizeof(punkt);
    cout << "Put: " << endl;
    for(p->i = 0; p->i < 10000000; p->i++)
        {
        cstck->push(p);
        cout << p->i << " ";
        }
    cout << endl << "Get: " << endl;
    while(cstck->pop(p))
        cout << p->i << " ";
    delete(p);
    delete cstck;
    cin >> p->i;
    }

Erhard Henkes

Vielleicht für Dich zum Vergleich interessant:
http://www.henkessoft.de/C++/C++ Fortgeschrittene/C++_Fortgeschrittene.htm#2.6._Template-Stack-Klasse
auch Kap. 2.7

uhsuhz

Danke für den link, nur funktionniert der auch mit arrays, würde mal gerne einen sehen der mit verweisen funktionniert.

Danke aber trotzdem