3. Template Listenklasse

Template Listenklasse

  • C

    Hallo,
    Bevor ich zu deiner Frage komme, eine Frage meinerseits: Ist die Liste ein Element? Oder hat die Liste ein/mehrere Element(e)?. Falls du diese Frage mit ist beantworten solltest, lies das. ;).

    Ansonsten zum Problem: Mach das Element-Objekt generisch, sprich:

    template <class Type> 
struct node {
   Type value; // enthält das Objekt.
   // Rest wie gehabt.
};

    Die Liste ist dann mit diesen Typen implementiert. So long.

    template <class Type>
class List
{
   node<Type> head, current;
   // ...
};

    Gruß Caipi

    0
  • R

    Hab ne Weile gebraucht bis ich mich wieder melde, aber der Terminkalender hats nicht anders ergeben.

    Dank der Tipps bin ich mit dem Headerfile so weit

    #ifndef NULL
	#define NULL 0
#endif

#ifndef LIST_ELEM_INCLUDED
	#define LIST_ELEM_INCLUDED

	/* Elementklasse, die die Knoten in der Liste bilden */

	template <class OBJ>
	class ELEM
	{
		friend class LIST;

		public:
			ELEM();							/* leeres Element */

		protected:
			ELEM* pNext;					/* Zeiger auf den Nachfolger */
			ELEM* pPrev;					/* Zeiger auf den Vorgaenger */
			OBJ* pItem;						/* Zeiger auf den Inhalt */
	};

#endif

#ifndef RLIST_INCLUDED
	#define RLIST_INCLUDED

	/* Listenklasse, die die Funktionen der Liste bereit stellt
		Sie erbt die Elemente der ELEM Klasse */

	template <class OBJ>
	class LIST
	{
		public:
			LIST();					/* Anlegen einer Liste */
			~LIST();				/* Destruktor */

			int InsertBehind(OBJ* pItem);	/* hinter dem aktuellen Element einfuegen */
			int InsertBefore(OBJ* pItem);	/* vor dem aktuellen Element einfuegen */
			int InsertHead(OBJ* pItem);			/* am Kopf einfuegen */
			int InsertTail(OBJ* pItem);			/* am Ende einfuegen */
			int Insert(OBJ* pItem, int (*cmpf)(const OBJ* object1, const OBJ* object2));		/* sortiertes Einfuegen */
			int Change(OBJ* pItem);				/* veraendert den Inhalt eines Elements */
			int Remove();			/* loescht das aktuelle Element */
			int RemoveHead();			/* loescht das erste Element */
			int RemoveTail();			/* loescht das letzte Element */

			OBJ* GetFirst();					/* gibt erstes Objekt zurueck */
			OBJ* GetTail();						/* gibt letztes Objekt zurueck */
			OBJ* GetPrev();						/* gibt vorhergehendes Objekt zurueck */
			OBJ* GetNext();						/* gibt naechstes Objekt zurueck */
			OBJ* GetIndexed(int index);			/* gibt bestimmtes Objekt zurueck */
			OBJ* GetSelected();					/* gibt aktuelles Objekt zurueck */

			OBJ* Find(OBJ* pItem);				/* findet ein Objekt in der Liste */

		private:
			ELEM<OBJ>* pCurrent;						/* aktuelles Element */
			ELEM<OBJ>* head;						/* Kopfelement */
	};

#endif

    und habe auch das entsprechende Modul durch probieren so weit, das es keinen Copilerfehler mehr gab (posten will ich es jetzt nicht unbedingt, da die Größe ja "unverantwortlich wäre"). Dann habe ich allerdings ein kleines Prog zum testen geschrieben und schon gehen die Schwirigkeiten wieder los.

    Schon wenn ich nur

    #include <iostream>
#include "list_neu.hpp"

using namespace std;

int main()
{
	int a=1,b=2,c=3,d=4,e=5,f=6;
	int *pointer;

	LIST<int> zahlenliste;

	return 0;
}

    schreibe bekomme ich die Meldung:
    undefined reference to LIST<int>::LIST[in-charge]()' /tmp/ccZVKc8e.o(.text+0x5d):haupt.cpp: undefined reference toLIST<int>::~LIST [in-charge]()'

    Hier noch die entsprechenden Modulzeilen:

    template <class OBJ>
ELEM<OBJ>::ELEM()
{
	this->pNext = NULL;		/* noch kein Nachfolger */
	this->pPrev = NULL;		/* noch kein Vorgaenger */
	this->pItem = NULL;		/* noch kein Objekt */
}

/***************************************** CLASS LIST **************************************/

/* Standartkonstruktor
   erzeugt das Kopffeld der Liste*/

template <class OBJ>
LIST<OBJ>::LIST()
{
	head = new ELEM<OBJ>;			/* neues Kopfelement erzeugen */
	pCurrent = head;				/* ist das momentan aktuelle Element */
	pCurrent->pNext = head;
	pCurrent->pPrev = head;
}

/* Destruktor baut das Kopfelement wieder ab, wenn Liste komplett leer */
template <class OBJ>
LIST<OBJ>::~LIST()
{
	if(pCurrent == head)
		delete [] head;				/* Listenkopf loeschen */
	else
		cout << "Liste nicht geloescht. Ursache: nicht leer!";
}

    Der Fehler tritt zwar auch bei den anderen Funktionen auf, aber ich hoffe durch die Lösung dieses Probs kann ich das andere wieder erschließen.

    Leider fehlt mir noch ein wenig die Erfahrung mit Templates und erst recht bei der Vererbung, ... von diesen.
    Ich hoffe ihr könnt mir weiter auf die Sprünge helfen.

    0
  • C

    Erstmal etwas technisches zur Listenklasse: wo veränderst du eigentlich die Position des "aktuellen Elements"?

    Dann zu deinem Problem: Der Compiler muß den Quelltext deiner Templateklasse kennen, WENN er das Anwenderprogramm compiliert - d.h. du mußt alle Funktionen in die Headerdatei schreiben, damit sie richtig zugeordnet werden können.
    (in dem Moment, wo du die list.cpp compilierst, kennt der Compiler zwar den nötigen Quelltext - aber er hat keine Ahnung, ob er ausführbaren Code für eine LIST<int>, LIST<double> oder LISTstd:string bereitstellen soll)

    0
  • R

    CStoll schrieb:

    Erstmal etwas technisches zur Listenklasse: wo veränderst du eigentlich die Position des "aktuellen Elements"?

    Das mache ich jeweils in den Funktionen wie InsertBehind(), GetFirst() usw...

    CStoll schrieb:

    Dann zu deinem Problem: Der Compiler muß den Quelltext deiner Templateklasse kennen, WENN er das Anwenderprogramm compiliert - d.h. du mußt alle Funktionen in die Headerdatei schreiben, damit sie richtig zugeordnet werden können.
    (in dem Moment, wo du die list.cpp compilierst, kennt der Compiler zwar den nötigen Quelltext - aber er hat keine Ahnung, ob er ausführbaren Code für eine LIST<int>, LIST<double> oder LISTstd:string bereitstellen soll)

    Sorry, das versteh ich noch nicht ganz, die Funktionen stehen doch im Headerfile, der Klasse. Aber das hast Du sicher nicht gemeint...
    Ich glaube auch nicht das Du meinst ich muss Funktionen wie

    List<int>::LIST();
List<long>::LIST();
...

    ins Headerfile schreiben, dann wäre das Template ja umsonst. 😕

    0
  • C

    Richard schrieb:

    CStoll schrieb:

    Dann zu deinem Problem: Der Compiler muß den Quelltext deiner Templateklasse kennen, WENN er das Anwenderprogramm compiliert - d.h. du mußt alle Funktionen in die Headerdatei schreiben, damit sie richtig zugeordnet werden können.
    (in dem Moment, wo du die list.cpp compilierst, kennt der Compiler zwar den nötigen Quelltext - aber er hat keine Ahnung, ob er ausführbaren Code für eine LIST<int>, LIST<double> oder LISTstd:string bereitstellen soll)

    Sorry, das versteh ich noch nicht ganz, die Funktionen stehen doch im Headerfile, der Klasse.

    Zur Zeit stehen nur die Deklarationen der Methoden im Header. Die Implementation jedoch nicht.

    Aber das hast Du sicher nicht gemeint...

    Doch, genau das hat CStoll gemeint... (Sofern ich diese Frage richtig interpretiert habe).

    Ich glaube auch nicht das Du meinst ich muss Funktionen wie

    List<int>::LIST();
List<long>::LIST();
...

    ins Headerfile schreiben, dann wäre das Template ja umsonst. 😕

    Wie kommst du denn zu dieser grausigen Feststellung?

    Wie bereits gesagt müssen bei Template-Klassen die Implementationen der Methoden der Klasse (zur compile-Zeit) in der gleichen Datei stehen wie die Deklaration der Klasse und deren Benutzung. (Hoffentlich war dieser Satz verständlich).
    Falls nicht:
    Wenn du folgende Template-Klasse foo<T> hast, die im modul main.cpp verwendet werden soll, muss zur Compile-Zeit die Deklaration von foo<T> (also foo.hpp) sowie deren Implementation (foo.cpp) in main.cpp zur Verfügung stehen. Dies kannst du mit dem Präprozessor erreichen, so das du nicht von Hand alles in main.cpp einfügen musst (;)). Die Gründe hat dir CStoll ja bereits genannt.

    Beispiel:

    // foo.hpp - Klassendeklaration
template <class T>
class foo { ... };

// foo.cpp - Definition der Methoden.
template <class T>
foo<T>::foo() { ... }
...

// main.cpp - Benutzung von foo<int>

// Zur Compile-Zeit müssen sowohl foo.hpp als auch foo.cpp in dieser
// Datei vorhanden sein. Dies erreichst bsp. durch
#include "foo.hpp"
#include "foo.cpp"

int main() { ... }

    Allerdings ist es hier imho schöner folgendes zu schreiben:

    // foo.hpp - Deklarationen
template <class T>
class foo { ...};

#include "foo.cpp" // Implementationen per Präprozessor am Ende einfügen.

// main.cpp
#include "foo.hpp" // jetzt reicht hier ein einfaches foo.hpp, da dieses ja bereits foo.cpp enthält.

int main() { ... }

    /edit: Es gibt zwar "neuerdings" ein Schlüsselwort (export), welches es gestatten Soll die Deklarationen von Template-Klassen und deren Implementationen zu trennen, dieses wird aber afaik nur vom comeau-Compiler unterstützt...

    Gruß Caipi.

    0
  • C

    Richard schrieb:

    CStoll schrieb:

    Erstmal etwas technisches zur Listenklasse: wo veränderst du eigentlich die Position des "aktuellen Elements"?

    Das mache ich jeweils in den Funktionen wie InsertBehind(), GetFirst() usw...

    Und wie würde ich in deiner Impelementation z.B. sagen "füge dieses Element an Position 7 der Liste ein" oder "vertausche die Elemente 5 und 9 dieser Liste"?

    CStoll schrieb:

    Dann zu deinem Problem: Der Compiler muß den Quelltext deiner Templateklasse kennen, WENN er das Anwenderprogramm compiliert - d.h. du mußt alle Funktionen in die Headerdatei schreiben, damit sie richtig zugeordnet werden können.
    (in dem Moment, wo du die list.cpp compilierst, kennt der Compiler zwar den nötigen Quelltext - aber er hat keine Ahnung, ob er ausführbaren Code für eine LIST<int>, LIST<double> oder LISTstd:string bereitstellen soll)

    Sorry, das versteh ich noch nicht ganz, die Funktionen stehen doch im Headerfile, der Klasse. Aber das hast Du sicher nicht gemeint...

    Im Header-File steht nur die Deklaration der Funktionen, die Dateien "list.cpp" (mit den zugehörigen Definitionen) und "main.cpp" (mit dem Hauptprogramm) werden allerdings getrennt compiliert. Und damit steht der Compiler vor einem mittelschweren Problem: Wenn er die "list.cpp" compilieren will, hat er keine Ahnung, mit was für Listen er später arbeiten soll, also kann er auch keinen Objektcode dafür erstellen. Wenn er später die "main.cpp" bearbeitet, weiß er, daß er eine LIST<int> erstellen soll, hat aber keine Ahnung, wie (die Definitionen dazu sind in der "list.cpp", die gerade irgendwo anders beschäftigt ist).
    Deswegen mußt du für Templates die Definitionen (sprich: dein Quellcode) und Instantiierungen (sprich: die Variablendeklaration im Hauptprogramm) an einem Punkt haben, um etwas sinnvolles herauszubekommen - wie das geht, hat Caipi schon erklärt.

    0
  • R

    Ich danke euch beiden erstmal ganz herzlich für die Tipps, hab das jetzt kapiert.

    Allerdings hat sich noch ein (hoffentlich letztes) problem ergeben.

    Um auf die privaten Daten der Basisklasse zugreifen zu können, muss ich die abgeleitete Klasse doch als friend deklarieren?! So habe ich ja bisher auch in der ELEM gemacht. Allerdings meint der Kompiler nun, ich würde damit LIST als ein anderes Symbol neu definieren und das ich auf die privaten Datenmember der Basisklasse nicht zugreifen darf. Kommentiere ich diese friend Geschichte aus, dann hab ich nur noch den 'private Fehler' und die Redefinition ist erstmal weg.
    Nun weiß ich nicht, wie ich LIST als Firend deklarieren muss, dass alles funzt und ich hoffe ihr (oder auch andere ;)) wissen eine Lösung.

    Danke

    0
  • C

    Liegt wohl daran, daß LIST eine Template-Klasse ist - das mußt du dem Compiler mitteilen:

    template<typename OBJ> class LIST;//forward-Deklaration

template<typename OBJ> class ELEM
{
  friend class LIST<OBJ>;
  //...
}

    Und für den Zugriff aus abgeleiteten Klassen heraus gibt es noch das Schlüsselwort "protected" 😉 - wobei ich mich frage, was bei deiner Konstruktion wovon abgeleitet sein soll.

    0
  • R

    Danke probier ich dann gleich mal aus.

    Das protected kenn ich, hatte ich zuerst auch, kam aber komischerweise der gleiche Fehler, warum auch immer. Ich hoffe das wird die friend Deklaration nun beheben, denn ich habe doch noch ein "wenig Ableitung" drin und deshalb ist sie notwenig. 😉

    0
  • C

    "ein wenig Ableitung" - also die Bezeichnung habe ich auch noch nicht gehört 😃

    Also rein vom logischen Standpunkt brauchst du gar keine Ableitung - eine Liste ist kein Listenelement, sondern hat höchstens einzelne Elemente (und das ergibt Komposition).

    0
Anmelden zum Antworten