Schneller Copy Konstruktor für einen Stack

[pumuckl]

uhsuhz schrieb:

Funktionniert das auch noch mit Standarttypen? also int, double, ...??

Jup. Standardtypen haben auch eine Art impliziten "copy-ctor", den du z.B. bei anzahl_elemente in der init-Liste des Stack benutzt. das data(t) in Stack<int>::Element::Element(int const& t) unterscheidet sich davon z.B. garnicht. Der einizge andere Aufruf des Copy-Ctors von T ist im pop(), und ein** int result(top->data); **(der '.' war ein Fehler in meinem Code oben) ist eine völlig normale Initialisierung eines int.

[uhsuhz]

ich glaube du hättest den copy-ctor noch müssen in die klasse reinbringen, oder?

also so:

template<class T>
class MyStack
{
private:
	class Element
	{
	public:
		T data;
		Element *next;
		Element(const T& t) :data(t),next(0) {} //C-tor
	};
	class EmptyStackExcetption : public std::exception
	{
		virtual const char* what() throw() {return "Stack is empty";}
	};
	Element *top;
	int anzahl_elemente;
public:
	MyStack();
	MyStack(const MyStack& other);
	~MyStack();
	void push(const T& v);
	T pop();
	int get_anzahl();
	bool is_empty();
	void clear();
};

und dann:

template<class T>MyStack<T>::MyStack(const MyStack &other)
:top(NULL), anzahl_elemente(0)
{
	if(!other.top) //leerer Stack, nichts zu kopieren
		return;
	this->top = new Element(other.top->data); //wenn hier was fliegt räumt C++ selber auf
	Element *rigth = other.top;
	Element *left = top;
	while(rigth->next)
	{
		try
		{
			left->next = new Element(rigth->next->data); //sollte hier was fliegen...
			rigth = rigth->next;
			left = left->next;  //müssen wir selber aufräumen
		}
		catch(...)
		{
			clear();
			throw;
		}
	}
}

hab jetzt auch verstanden, warum in der STL bei den containern left und rigth benutzt wird^^
so werde jetzt noch den operator=, ==, != reinbringen. weiß jemand was genau < bringt bei stacks? ob ein stack größer ist als der andere, oder ???
jedenfalls habe ich mir die header von dem stack angeschaut, und da habe ich auch nicht mehtr funktionen gefunden , als diese hier(mit ==, !=, <, >=, <=, >,

außerdem habe ich den rükgabetyp von push fortgemacht gibt keinen sinn mehr... ist jetzt void push(const T& v)

[pumuckl]

sry, selbstverständlich muss die deklaration des copy-ctor in den stack, hatte ich vergessen mit einzutragen.

op= ist recht einfach gemacht, wenn du eine (genauso einfache) swap-methode implementierst:

template <class T>
void Stack<T>::swap(Stack& other)
{
  using std::swap;
  swap(top, other.top);  //einfach die top-Zeiger der Stacks vertauschen
  swap(anzahl_elemente, other.anzahl_elemente);
}

template <class T>
Stack& Stack<T>::operator=(Stack const& rhs)
{
  Stack tmp(rhs);
  swap(tmp);
}

um op== zu benutzen muss T auch einen op== haben, aber das zu verlangen ist durchaus legitim (wenn T den nicht hat, darf man eben op== nicht benutzen, das ist dann dank SFINAE* kein Fehler)
implementiert wird der indem man sich (wieder mit left, right) die Liste entlanghangelt und die data-attribute der elemente vergleicht

op!= ist einfach mit op== implementiert

Was das mit den arithmetischen vergleichen auf sich hat - keine Ahnung. Schau mal in der Doku zu den stack-klassen die dir vorliegen (z.B. cplusplus.com für std::stack)

_____________________________________________
* Substitution Failure Is Not An Error - google hilft bei Interesse weiter

[uhsuhz]

den operator= und swap hab ich schon fertig, benutzte immer die C-tor+swap methode für operator=

template<class T>void MyStack<T>::swap(MyStack &stck)
{
	int itemp = this->anzahl_elemente;
	this->anzahl_elemente = stck.anzahl_elemente;
	stck.anzahl_elemente = itemp;
	Element *etemp = this->top;
	this->top = stck.top;
	stck.top = etemp;
}

template<class T>MyStack<T>& MyStack<T>::operator=(const MyStack& other)
{
	MyStack<T> temp = other;
	this->swap(temp);
	return *this;
}

welche header muss ich einbinden um std::swap zu benutzen?

io das mit dem != operator war mir klar, bin ja nicht so doof alles neu zu schreiben, geht ja viel einfacher wenn ich den fertigen == operator schon hab, das gleiche mit > und <= , < und >=

[ghorst]

uhsuhz schrieb:

welche header muss ich einbinden um std::swap zu benutzen?

<algorithm>

[uhsuhz]

danke wieder was dazugelernt^^

[camper]

Den copy-ctor können wir eleganter schreiben, da alle notwendigen Operationen bereits in anderen Funktionen realisiert werden.

template<class T>MyStack<T>::MyStack(const MyStack &other)
:top(NULL), anzahl_elemente(0)
{
    MyStack temp; // !!!
    for ( Element* p = other.top; p != NULL; p = p->next )
        temp.push( p->data );
    swap( temp );
}

sieht fast aus wie op= ? So ein Zufall
Bzgl. pop bin ich mir etwas unsicher:

template<class T> T Stack<T>::pop()
{
         if (! top) throw EmptyStackException();
         T result(top.data);
    Element* temp = top;
    top = top->next;
    delete (temp);
    --anzahl_elemente;
    return result;
}

Abgesehen von ersten Zeile, kann diese Funktion an 2 Stellen mit einer Exception fehlschlagen. An der ersten Stelle verbleibt das Element im Stack, bei der zweiten Stelle ist es bereits entfernt worden. Das ist nicht optimal, weil sich der benutzende Code nicht auf ein bestimmtes Verhalten einstellen kann.

[uhsuhz]

camper schrieb:

Den copy-ctor können wir eleganter schreiben, da alle notwendigen Operationen bereits in anderen Funktionen realisiert werden.

template<class T>MyStack<T>::MyStack(const MyStack &other)
:top(NULL), anzahl_elemente(0)
{
    MyStack temp; // !!!
    for ( Element* p = other.top; p != NULL; p = p->next )
        temp.push( p->data );
    swap( temp );
}

sieht fast aus wie op= ? So ein Zufall

ne kann nicht funktionnieren, dann liegen die daten den verkehrten weg im Stack, darum muss man ja eine etwas längere funktion schriebn und nicht einfach eine pushmethode benutzen... Damit das funktionnieren könnte müsste man hinten anfangen und nach vorne fahren, klappt aber nicht mit nem stack...

[hehehe]

Mit Linux wäre das nicht passiert.

[uhsuhz]

hä was soll das denn heißen??

naja egal, @camper, den code kann ich aber locker bei der Queue benutzen^^

[camper]

uhsuhz schrieb:

camper schrieb:

Den copy-ctor können wir eleganter schreiben, da alle notwendigen Operationen bereits in anderen Funktionen realisiert werden.

template<class T>MyStack<T>::MyStack(const MyStack &other)
:top(NULL), anzahl_elemente(0)
{
    MyStack temp; // !!!
    for ( Element* p = other.top; p != NULL; p = p->next )
        temp.push( p->data );
    swap( temp );
}

sieht fast aus wie op= ? So ein Zufall

ne kann nicht funktionnieren, dann liegen die daten den verkehrten weg im Stack, darum muss man ja eine etwas längere funktion schriebn und nicht einfach eine pushmethode benutzen...

stimmt wohl, hab ich nicht aufgepasst. Aber das try+catch brauchen wir wirklich nicht.

template<class T>MyStack<T>::MyStack(const MyStack &other)
:top(NULL), anzahl_elemente(other.anzahl_elemente)
{
    MyStack temp;
    for ( Element *p = other.top, **q = &temp.top; p != NULL; p = p->next )
    {
        *q = new Element( p->data );
        q = &q->next;
    }
    std::swap( top, temp.top );
}
}

[uhsuhz]

ich habs mal so gelassen, ich schau mir das später mal an...

[pumuckl]

camper schrieb:

Bzgl. pop bin ich mir etwas unsicher:

template<class T> T Stack<T>::pop()
{
         if (! top) throw EmptyStackException();
         T result(top.data);
    Element* temp = top;
    top = top->next;
    delete (temp);
    --anzahl_elemente;
    return result;
}

Abgesehen von ersten Zeile, kann diese Funktion an 2 Stellen mit einer Exception fehlschlagen. An der ersten Stelle verbleibt das Element im Stack, bei der zweiten Stelle ist es bereits entfernt worden. Das ist nicht optimal, weil sich der benutzende Code nicht auf ein bestimmtes Verhalten einstellen kann.

Hm, zwei Stellen? Ich nehem mal an, beim Copy-Ctor und beim return?
Folgendes sollte dann aber einheitlich sein, so dass ein pop() auf jeden Fall das oberste Element entfernt:

template<class T> T Stack<T>::pop()
{
    if (! top) throw EmptyStackException();
    std::auto_ptr<Element> temp(top);
    top = top->next;
    --anzahl_elemente;
    return temp->data;
}