Templateklasse & Iterator

soad

Hi,

ich muss einen eigenen Container als Templateklasse schreiben plus dazugehörigem Iterator, jedoch ohne Verwendung der STL. Weiters gibt es eine Basisklasse mit einem Attribut, sowie zwei davon abgeleitete Klassen, die jeweils ein weiteres Attribut besitzen. Zwei Instanzen des Containers sollen anschließend mit Elementen der einen bzw. anderen (abgeleiteten) Klasse gefüllt werden.

Jetzt hab ich versucht den Container als verkettete Liste zu implementieren:

struct ListenElement				
{
	int data[2];				
	ListenElement * next;	

};

template<class Typ> class TSet
{
	public:
		TSet(void) { m_root = NULL; };
		void add(Typ x) 
		{	
			if(m_root == NULL) 
			{
				m_root = new ListenElement;	
				m_root->data[0] = x->getSeatNr(); 
				m_root->data[1] = x->getLength(); // ?????	
				m_root->next=NULL;	
			}
			else							
			{
				m_ptr = m_root;					
				while (m_ptr->next != NULL)
				{
					m_ptr = m_ptr->next;
				}
				m_ptr->next = new ListenElement;	
				m_ptr = m_ptr->next;			

			m_ptr->data[0] = x->getSeatNr();
			m_ptr->data[1] = x->getLength();
			m_ptr->next = NULL;
			}
		}

	private:
		ListenElement *m_root;
		ListenElement *m_ptr;

};

Jetzt hab ich in der add-Methode schon das Problem, dass wenn ich die Daten in das data[] schreiben will, ich unterscheiden müsste, welchen Klassentyp der Paramter x hat, weil sie die abgeleiteten Klassen ja in einem Attribut unterscheiden.

Wie mache ich das? Wie könnte ich in der add-Methode überprüfen, ob ein Element mit der selben Adresse schon vorhanden ist? Ist mein jetziger Listenansatz überhaupt vernünftig (es soll ja dann auch ein Iterator geschrieben werden mit begin, end, in-, dekrement und Dereferenzierung)? Wie schaut so ein eigener Iterator eigentlich aus? Hab mir zwar den Artikel von CStoll durchgelesen, check das aber nicht ganz ...

So, ich weiß, das waren jetzt einmal ein Haufen Fragen, aber ich wäre auch sehr dankbar, wenn ihr mir den einen oder anderen Tipp geben könntet!!

mfg,
soad

Xin

soad schrieb:

Hi,

Jetzt hab ich in der add-Methode schon das Problem, dass wenn ich die Daten in das data[] schreiben will, ich unterscheiden müsste, welchen Klassentyp der Paramter x hat, weil sie die abgeleiteten Klassen ja in einem Attribut unterscheiden.

Wie mache ich das?

Du überlegst, welcher Part in den Container gehört und welcher Part nicht.
Die Initialisierung von Listenelementen gehört nicht in eine Liste.

Umgekehrt ist es nicht Job des Datensatzes, für die Verkettung zu sorgen, dafür hast Du schließlich den Container.

Deine Liste<Datensatz> sollte also Listenelement<Datensatz> verwalten.
Und Deinen Datensatz konstruierst Du im Datensatz - unabhängig vom Container.

Wenn Dir die Trennung von Listenelement<Datensatz> und Datensatz nicht gefällt, kannst Du auch vererben. Damit sparst einen Zeiger und den Aufwand Listenelemente zu erzeugen.

template <class T> class ListenElement
{
  ListenElement<T> * Next;
};

template <class T> class Liste
{
  ListenElement<T> * First;

  ...
};

class Datensatz : public Listenelement<Datensatz>
{
  public:
    int Daten[2];

    Datensatz( int a, int b ) { Daten[0] = a; Daten[1] = b; }
};

class DatensatzA : public Datensatz
{
  public:
    int NochEinElement;

    DatensatzA( int a, int b, int c ) : Datensatz( a, b ), NochEinElement( c ) {}
};

int main( void )
{
  Liste<Datensatz> Liste;

  Liste += new DatensatzA( 1, 2, 3 );
  Liste += new Datensatz( 4, 5 );

  return 0;
}

PS: Was den Iterator angeht - auch das ist sein eigenes Template.
Ein Container besteht nicht zwangsläufig aus nur einem Template.

template <class T> ListenIterator
{
  ListenElement<T> Current;
}

CStoll

Wenn du Polymorphie (Übergabe verschiedener Typen zur Laufzeit) nutzen willst, benötigst du schon Zeiger, die du in deinen Container packst (damit erübrigt sich auch die Frage, wieviel Platz du im Container benötigst - ein Zeiger ist immer gleich groß):

TSet<Base*> cont;
cont.add(new Derived1);
cont.add(new Derived2(4711,0x0815));

Zu deiner Klasse: die 'struct Listenelement' sollte auch ein Template sein - und benötigt nur einen 'T value;' und einen Nachfolger-Zeiger (eventuell noch einen Vorgänger-Zeiger. Und die Membervariable m_ptr brauchst du nicht ständig zu speichern - da reicht eine lokale Hilfsvariable. Stattdessen benötigst du noch einen Zeiger auf das letzte Element deiner Liste

@Iteratoren:
Ein Iterator dient dazu, mit einer Pointer-artigen Syntax durch einen Container zu wandern. Deine Iterator-Klasse benötigt:

einen Zeiger auf ein Listenelement als privaten Member (m_akt).
operator++() (Inkrement)
setzt m_akt auf m_akt->next und gibt sich selber zurück
operator--() (Dekrement) - macht nur Sinn, wenn Listenelement einen Vorgänger-Zeiger hat
setzt m_akt auf m_akt->prev und gibt sich selber zurück
operator++(int) und operator--(int) (Postfix-Versionen von op++ und op--)

iterator operator++(int)
{
  iterator t=*this;
  ++*this;
  return t;
}

operator* und operator-> (Dereferenzierung)
geben m_akt.value bzw. dessen Adresse zurück
operator== und operator!= (Vergleich)
vergleichen die m_akt-Werte der verglichenen Iteratoren

(ich denke mal, ich hab' nichts vergessen)
TSet::begin() gibt einen Iterator auf m_root zurück, end() einen mit NULL initialisierten Iterator (bzw. ein Dummy-Element, das hinter dem letzten Element liegt, wenn du Dekrement-Operatoren unterstützen willst)

soad

Danke euch beiden erstmal !

Ich habe jetzt versucht - soweit ich es verstanden habe - eure Vorschläge einzubauen. Hab jetzt eine doppelt verkettete Liste; die Funktionen isStored, add und remove funktionieren eigentlich schon.

Aber mit dem Iterator habe ich so mein Schwierigkeiten. Ich hab ihn jetzt mal ansatzweise in zwei Versionen als verschachtelte Klasse(ist so gefordert) implementiert (s.u.), aber das ist irgendwie beides Blödsinn :(.

Danke CStoll jedenfalls für die super Beschreibung, da ist echt alles dabei, was ich brauche !! Ich checks nur leider noch nicht ganz :). Hab ich das richtig verstanden bei begin und end gebe ich einen Iterator zurück, ansonsten ein ListenElement? Hier die 1. Version:

template<class T> class Iterator
		{
			public:
				Iterator<T>* begin(void)
				{
					Iterator<T> *iterator;
					iterator->m_act = TSet::m_begin;
					return *iterator; 
				}

				Iterator<T>* end(void)
				{
					return NULL; 
				}

			private: 
				ListenElement<T> *m_act;
		};

Der Klasse TSet gebe ich jetzt noch ein zusätzlichen public Memberzeiger *iterator, stimmt das eh so?!
Ist es sinnvoll den Iterator auch schon in den Klassenfunktionen zu verwenden, oder ist der eher als "Zugriff von Außen" gedacht?
Die 2. Version + dem Rest:

template<class T> class ListenElement				
{
	public:
		T value;				
		ListenElement<T> *next;
		ListenElement<T> *prev;
};

template<class T> class TSet
{
	public:
		TSet(void) : m_begin(NULL), m_end(NULL) {}

		template<class T> class Iterator               // 2. VERSION
		{
			public:
				ListenElement<T> begin(void)
				{
					m_act = TSet::m_begin;
					return m_act;
				}

				ListenElement<T> end(void)
				{
					return TSet::m_end;
				}

			private: 
				ListenElement<T> *m_act;
		}; 

		Iterator<T> *iterator;

		bool isStored(T x)
		{
			ListenElement<T> *ptr;
			ptr = m_begin;					

			while (ptr != NULL)
			{
				if(ptr->value == x)
					return true;	
				else
					ptr = ptr->next;;
			}
			return false;
		}

		void add(T x) 
		{	
			if(m_begin == NULL) 
			{
				m_begin = new ListenElement<T>;	
				m_end = new ListenElement<T>;
				m_begin->value = x;
				m_begin->prev = NULL;
				m_end = m_begin;
				m_end->next = NULL;
			}
			else							
			{
				ListenElement<T> *ptr;
				ptr = m_begin;					

				while (ptr != m_end)
				{
					if(ptr->value != x)
						ptr = ptr->next;
					else
						throw "Element bereits vorhanden! Element kann nicht eingefuegt werden!";
				}
				ptr->next = new ListenElement<T>;				
				ptr->next->value = x;
				ptr->next->prev = ptr;
				m_end = ptr->next;
				m_end->next = NULL;
			}
		}

		void remove(T x)
		{
			if(m_begin != NULL) 
			{
				ListenElement<T> *ptr;
				ptr = m_begin;					

				while (ptr != NULL)
				{
					if(ptr->value == x)
					{
						if(ptr == m_begin)
						{
							if(ptr->next != NULL)
							{
								m_begin = ptr->next;
								m_begin->prev = NULL;
							}
							break;
						}
						else if(ptr == m_end)
						{
							m_end = ptr->prev;
							m_end->next = NULL;
							break;
						}
						else
						{
							ptr->prev->next = ptr->next;
							ptr->next->prev = ptr->prev;
							break;
						}
					}
					else
					{
						ptr = ptr->next;
						if(ptr == NULL)
							throw "Element nicht vorhanden! Element kann nicht geloescht werden!";
					}
				}
				delete ptr;
			}
			else							
			{
				throw "Container ist leer! Element kann nicht geloescht werden!";
			}
		}

	private:
		ListenElement<T> *m_begin;
		ListenElement<T> *m_end;

};

Passt jetzt eigentlich der Rest so?

sg,
soad

Xin

soad schrieb:

Aber mit dem Iterator habe ich so mein Schwierigkeiten. Ich hab ihn jetzt mal ansatzweise in zwei Versionen als verschachtelte Klasse(ist so gefordert) implementiert (s.u.), aber das ist irgendwie beides Blödsinn :(.

So würde ich das nicht sagen, aber Du vergißt zu iterieren.

soad schrieb:

Hab ich das richtig verstanden bei begin und end gebe ich einen Iterator zurück, ansonsten ein ListenElement?

Ein Iterator ist ein Objekt, das weiß was durchgegangen wird und wo man grade dran ist.
Du hast also nicht nur einen Iterator, sondern soviele, wie eben grade durch die Listen iterieren.

Nun holst Du Dir vom Iterator Dein Objekt ab mit dem Arbeiten möchtest. Anschließend sagst Du Deinem Iterator, dass Du das nächste Objekt haben möchtest usw.

Der Ablauf einer (von beliebig vielen Iterationen) ist also:
1.) Container um Iterator bitten, wird von Container erzeugt und übergeben.
2.) Iterator befragen - Iterator gibt Referenz auf ein Element wieder
3.) Solange nach nächstem Element fragen, bis der Iterator im Container keinen weiteren mehr findet.
4.) Letzes Element verarbeitet, dann Iterator entsorgen.

CStoll

Übrigens sollten begin() und end() keine Methoden des Iterators sein, sondern der TSet-Klasse

PS: Was spricht eigentlich dagegen, std::set<> zu verwenden?

soad

Danke euch wieder einmal :)!

Die STL darf ich leider nicht verwenden. Ich hab den Iterator jetzt um einige Operatoren erweitert, ganz sicher bin ich mir aber nicht, insbesondere beim * und -> Operator, da mach ich eigentlich dasselbe .

Weiters ist mir nicht ganz klar, ob ich den Iterator als Zeiger instanzieren, also z.B. TSet<Foo*>::Iterator *it oder wäre folgendes Beispiel richtig?

TSet<CCar*> car;
TSet<CCar*>::Iterator it;
it = car.begin();

while(it != car.end())
{
    cout << (*it)->getLength() << endl;
    ++it;
}

Hier jetzt mein Container ohne Methoden + Iterator.

template<class T> class TSet
{
	public:
		TSet(void) : m_begin(NULL), m_end(NULL) {}

		class Iterator
		{
			friend class TSet;
			public:
				bool operator==(const Iterator &it) const
				{
					return (m_act == it.m_act);
				}

				bool operator!=(const Iterator &it) const
				{
					return (m_act != it.m_act);
				}

				Iterator& operator++()
				{
					this->m_act = this->m_act->next;
					return *this;
				}

				Iterator& operator++(int)
				{
					Iterator *temp = this;
					this->m_act = this->m_act->next;
					return *temp;
				}

				T& operator*()
				{
					return (this->m_act->value);
				}

				T operator->()
				{
					return (this->m_act->value);
				}

			private: 
				ListenElement<T> *m_act;
		}; 

		Iterator begin(void)
		{
			Iterator iterator;
			iterator.m_act = m_begin;
			return iterator; 
		}

		Iterator end(void)
		{
			Iterator iterator;
			iterator.m_act = NULL;
			return iterator; 
		}

	private:
		ListenElement<T> *m_begin;
		ListenElement<T> *m_end;

};

mfg,
soad

soad

Nur noch eine letzte Frage: Stimmen der -> und der *- operator so?

T operator*()
{
	return *(this->m_act->value);
}

T& operator->()
{
	return (this->m_act->value);
}

mfg,
soad

soad

Eine Frage ist jetzt doch noch aufgetreten :):
Ich habe eine abstrakte Klasse Automobile und davon abgeleitet eine Klasse Car und eine Klasse Truck (wie im ersten Post beschrieben), wenn ich jetzt meinen Container TSet mit Elementen BEIDER Klassen füllen möchte bekomme ich, folgenden Fehler:

error C2243: 'Typumwandlung': Konvertierung von 'CCar *' zu 'IAutomobile *const ' ist bereits vorhanden, aber es kann nicht darauf zugegriffen werden.

TSet<IAutomobile*> t;
CCar *car1 = new CCar(5, 10);
CTruck *truck1 = new CTruck(3, 10);
t.add(car1);
t.add(truck1);

Sollte das nicht eigentlich gehen bzw. was bedeutet die Fehlermeldung ?!

CStoll

Ich würde mal darauf tippen, daß du CCar und CTruck nicht public abgeleitet hast ( class CCar:IAutomobil ist private Ableitung - und nicht zugänglich für Polymorphie-Aufgaben).

soad

Stimmt, danke ! Wieder so ein dummer Fehler ...

Templateklasse &amp; Iterator

Templateklasse & Iterator