Generische Programmierung mit Templates und STL Containern

duracell

Hi!

Ich versuche gerade, einen generischen BinaryTree (Heap) in C++ zu implementieren und stosse da auf einige Schwierigkeiten. Der Heap soll eine Menge von HeapNodes (wegen konstantem Zugriff) in einer Map verwalten.

Der generische Typ "HeapNode" ist folgendermaßen definiert:

C

template <class K, class D>
class HeapNode
{
    public:
    HeapNode(K key, D data);
    ...
};


#include heapnode.c

soweit so gut, der Typ HeapNode funktioniert wie erwartet. Bei der Implementierung des Heaps beginnen allerdings die Probleme:

Ich würde den "Heap" gerne so implementieren, dass die ihm als Datenstruktur zu Grunde liegende Map die Schlüssel vom Typ K, sowie die dazugehörigen Werte als generischen Typen HeapNode<K, D> speichert:

C

template <class K, class D>
class Heap
{
    public:
    Heap(map<K, HeapNode<K, D>> nodes);


    protected:
    map<K, HeapNode<K, D>> nodes;
};


#include heap.c

Alles anzeigen

Hier schreit aber der Compiler (g++ 2.8). Scheinbar stört ihn der generische Typ innerhalb des Wertetyps von map. Das gleiche passiert übrigens auch bei Verwendung von vector, z.B: vector<HeapNode<K, D>>. Sind hier nur "konkrete" Datentypen innherhalb von STL Containern erlaubt?

...was ich also benötige ist eine Einschränkung des Wertetypen der map auf Objekte vom Typ HeapNode mit key K und value V.

Hat jemand einen Plan? Danke!
lg, martin

Plantschkuh!

Ein mehr oder weniger vollständiges (aber möglichst kleines) Programmfragment sowie die genaue Fehlermeldung wären hilfreich...
Folgender Code:

Code

#include <map>


template <class K, class D>
class HeapNode
{
    public:
    HeapNode(K key, D data);
};


template <class K, class D>
class Heap
{
    public:
    Heap(std::map<K, HeapNode<K, D> > nodes);


    protected:
    std::map<K, HeapNode<K, D> > nodes;
};

Alles anzeigen

wird von meinem g++ 3.3 anstandslos akzeptiert. Mein Tip wär, daß deinen Compiler der Token >> stört; das ist der left-shift-operator. Will man zwei > hintereinander, so muß man sie durch ein Space trennen. (Mein g++ erkennt das schon und gibt nur eine Warnung aus.)

(Source-Files in Headern #includieren ist übrigens böhse.)

tivolo

Zitat von Plantschkuh!

Mein Tip wär, daß deinen Compiler der Token >> stört; das ist der left-shift-operator. Will man zwei > hintereinander, so muß man sie durch ein Space trennen.

das wär auch mein tip gewesen.

Zitat von Plantschkuh!

(Source-Files in Headern #includieren ist übrigens böhse.)

generell und in diesem fall: ja. kann aber durchaus auch sinn machen.

-tiv

sauzachn

g++ 2.8 ist sowieso sehr veraltet. Grad im Umgang mit Templates lohnt sich einer aus der 3er Serie oder natürlich der 4er, der noch dazu bei exzessiver Verwendung von Templates (boost etc.) viel schneller ist.

hal

Zitat von sauzachn

Grad im Umgang mit Templates lohnt sich einer aus der 3er Serie oder natürlich der 4er, der noch dazu bei exzessiver Verwendung von Templates (boost etc.) viel schneller ist.

>1GB RAM sind auch sehr zu empfehlen.

duracell

ich dank euch für die ratschläge! funktioniert bestens!

@Plantschkuh:
ich weiss, das inkludieren des c-files im header-file ist im allgemeinen eine üble sache. ich habe allerdings gelesen, dass templates nicht automatisch exportiert werden. export template<class T> wurde zwar in den standard aufgenommen, wird aber von den aktuellen compilern (informationsstand 2004) noch nicht unterstützt. ich habe auf g++ 3.3 (letzte stable von debian sarge) upgedated und da wirds ebenfalls noch nicht unterstützt.

um den template-typ zu inkludieren, muss also sowohl jeweiliges .h- als auch .c-file inkludiert werden. ich wollte mir das auf diese weise ersparen (natürlich dabei das c-file gegen mehrfaches inkludieren geschützt). weiss jemand eine bessere praxis, bzw. weiss jemand, ob die verwendung von "export template" bereits unterstütz wird? mir gefällt die lösung auch nicht!

greets, martin

hal

Zitat von duracell

ich habe auf g++ 3.3 (letzte stable von debian sarge) upgedated und da wirds ebenfalls noch nicht unterstützt.

Also so weit ich das seh weigern sich die gcc-Entwickler, das Feature einzubauen.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=8434

Fup

Ich verstehe nicht ganz, wozu du die Implementierung inkludierst, die Schnittstelle reicht doch? Wenn nicht, kannst du dir ja die Klassen vordefinieren und Makro-Hacks verwenden.

tivolo

Zitat von Fup

Ich verstehe nicht ganz, wozu du die Implementierung inkludierst, die Schnittstelle reicht doch? Wenn nicht, kannst du dir ja die Klassen vordefinieren und Makro-Hacks verwenden.

sobald methoden verwendet werden, die nicht inline sind und somit im .c/.cpp file stehen, kommt es bei fast allen compilern zu linker errors. das ist lästig, weil sich definition/implementation bei templates dadurch nicht mehr schön trennen lassen. im C++-standard ist ein entsprechendes 'export' keyword definiert, um die implementation von template-klassen für den linker "sichtbar" zu machen. allerdings ist die zukunft des 'export' keywords ziemlich undefiniert. der einzige compiler, der das momentan unterstützt, ist der Comeau C++ compiler (http://www.comeaucomputing.com/tryitout/).

interessanter read:
http://www.gotw.ca/publications/mill23.htm
http://www.gotw.ca/publications/mill24.htm

eine andere möglichkeit wäre natürlich noch, 'explicit instantiation' zu verwenden, was angesichts der generalität deiner klasse jedoch nicht wirklich praktikabel ist.

-tiv

Jetzt mitmachen!