Schneller Copy Konstruktor für einen Stack

uhsuhz

Kennt jemand einen schnellen Copy Konstruktor für nen Stack

zur zeit habe ich:

#pragma once

template<class T>
class Stack
{
private:
	class Element
	{
	public:
		Element *next;
		T data;
	};
	Element *top;
	int anzahl_elemente;
public:
	Stack();
	~Stack();
	int push(T v);
	int pop(T& v);
	int get_anzahl();
	int is_empty();
	void clear();
};

template<class T>Stack<T>::Stack()
:top(NULL), anzahl_elemente(0)
{
}

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

template<class T>int Stack<T>::push(T v)
{
	Element *temp = new Element;
	if(!temp)
		return 0;
	temp->data = v;
	temp->next = top;
	top = temp;
	anzahl_elemente++;
	return 1;
}

template<class T>int Stack<T>::pop(T &v)
{
	Element *temp = top;
	if(!temp)
		return 0;
	v = temp->data;
	top = temp->next;
	delete (temp);
	anzahl_elemente--;
	return 1;
}

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

template<class T>int Stack<T>::is_empty()
{
	return (get_anzahl == 0);
}

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

funktionniert alles prima, hab bis jetzt noch keine mängel entdeckt, allerdings habe ichn keine ahnung wie ich einen Ctor programmieren soll...

das problem liegt darin, dass ich ja nicht auf das unterste element zugreifen kann, ich habe nur top und next. ich könnte natürlich zuerst alles in ein temporären stack kopieren und von da in den richtigen per push und pop, aber ich glaube das ist ziemlich langsam oder?

gibt es keine elegantere Lösung dafür?
ich weiß, in der STL wird der Stack als Deque element genuztz, deshalb wird es da leichter sein, aber ich habe noch keine Deque container programmiert, von daher würde ich gerne einen Stack c_tor selber basteln

Ich hoffe das war klar^^

danke im Voraus

Shade Of Mine

Stack(Stack const& other) {
  anzahl_elemente = other.anzahl_elemente;
  Element* p = other.top;
  top = new Element(p->value);
  copy=top;
  p=p->next;
  while(p) {
    copy->next = new Element(p->value);
    copy=copy->next;
    p=p->next;
  }
}

aber es ist spaet, ich hab das nur hingenudelt wie man so schoen sagt :p

pumuckl

Deine Implementierung hat noch die eine oder andere Unzulänglichkeit, z.B.
- du verlangst, dass T einen default-Ctor hat (der keine Exception werfen darf)
- du verlangst, dass T einen exceptionsicheren op= hat (sonst kann push() speicherlecks verursachen)
- die if-Abfrage in push ist sinnfrei, new wirft bei Misserfolg eine Exception, statt den Zeiger auf 0 zu setzen
- clear() und der Dtor haben duplizierten Code. Ruf doch einfach im Dtor clear() auf
- is_empty liefert einen int, sollte aber eher bool liefern

Ich versuch mal entsprechend Änderungen vorzuschagen:

#pragma once

template<class T>
class Stack
{
private:
	class Element
	{
	public:
	  T data;
	  Element *next;
           Element(T const& t) : data(t), next(0) {} //Ctor
	};
         class EmptyStackException : public std::exception {
           virtual const char* what() throw() {return "Stack is empty.";}
         }

	Element *top;
	int anzahl_elemente;
public:
	Stack();
	~Stack();
	int push(T const& v);  //referenz reicht!
	T pop();               //falls T kein op= hat gehts mit Referenz nicht
	int get_anzahl();
	bool is_empty();
	void clear();
};

template<class T>Stack<T>::Stack()
:top(NULL), anzahl_elemente(0)
{
}

template<class T>Stack<T>::~Stack() //throw()
{
  clear();    //code-duplizierung vermeiden.
}

template<class T>int Stack<T>::push(T const& v)
{
	Element *temp = new Element(v); //wenn der copy-Ctor von T schmeißt, wird der Speicher automatisch befreit -> kein Speicherleck
	temp->next = top;
	top = temp;
	++anzahl_elemente;
	return 1;
}

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;
}

template<class T> int Stack<T>::get_anzahl()
{
	return anzahl_elemente; //wolltest keine rekurion, oder?
}

template<class T> bool Stack<T>::is_empty()
{
	return (get_anzahl() == 0);
}

template<class T>void Stack<T>::clear()  //throw() , da keine unnötigen Aufrufe von T-Ctoren
{
  Element* tmp = top;
  while (top)
  {
    top = top->next;  //-> top steht am Ende auf 0;
    delete tmp;
    tmp = top;
  } 
}

//jetzt der gewuenschte copy-Ctor:
template<class T> Stack(Stack const& rhs) : top(0), anzahl_elemente(0)
{
  if (!rhs.top) return; //leerer stack, nichts zu kopieren

  top = new Element(rhs.top->data); //wenn hier was fliegt, räumt C++ selber auf
  Element* right = rhs.top;
  Element* left = top;
  while (right->next)
  {
    try
    {
      left->next = new Element(right->next->data); //sollte hier was fliegen...
      right = right->next;
      left = left->next;
    }
    catch(...)
    {
      clear();    //... müssen wir selber aufräumen!
      throw;
    }
  }
}

Wenn ich nicht irgendwas übersehen hab verlangt diese Implementierung lediglich, dass T einen Copy-Ctor besitzt. Wenn der ne Exception wirft ists nicht schlimm, der Stack wirft die dann einfach weiter, ohne Speicherlecks etc. zu hitnerlassen. Es wird kein op= vorausgesetzt, kein default-Ctor.

uhsuhz

ups, das mit dem get_anzahl und is_empty hab ich wohl nicht aufgepasst, natürlich war es so gemeint wie du jetzt geschrieben hast, rekursion war nicht geplant^^

leuchtet mir alles ein, was du geschrieben hast
werde den code jetzt mal entsprechend umändern

Danke für die Hilfe, ist sehr nett.

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

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?

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...

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;
}