La compilation de fonctions ou de structure template est un peu particulière : comme le code dépend d'un type passé en paramètre, aucun code objet n'est généré tant que ce paramètre n'est pas fixé. Ainsi, en adoptant le découpage habituel en un fichier .h contenant les déclarations et un fichier .cpp contenant les définitions ne fonctionne pas correctement. Il faut que le code complet d'un template (déclaration et définition) soit accessible lors de l'instanciation (moment où les paramètres template sont fixés).
Il y a globalement deux méthodes :
-
mettre la définition de la classe dans la déclaration, comme ce qui est fait en Java,
-
conserver la séparation en deux fichiers, mais sans compiler le fichier contenant les définitions, et en incluant ce fichier a la fin du fichier contenant les déclarations
Dans ce TD, la première méthode est utilisée.
Sommets du graphe
#ifndef Sommet_h #define Sommet_h template<typename T> class Sommet { public : Sommet(int n) : numero(n) { } Sommet(Sommet<T> const & sommet) : numero(sommet.numero) { } Sommet<T> const & operator=(Sommet<T> const & sommet) { if(this!=&sommet) { numero = sommet.numero; label = sommet.label; } return *this; } T getLabel() const { return label; } void setLabel(T newLabel) { label = newLabel; } int getNumero() const { return numero; } private : int numero; T label; }; #endif // Sommet_h
Arêtes du graphe
#ifndef Arete_h #define Arete_h #include <utility> #include "Sommet.h" template<typename Poids> class Arete { public : Arete(int s1, int s2, int n) : numero(n), extremites(s1, s2) { } Arete(Arete<Poids> const & arete) : numero(arete.numero), extremites(arete.extremites) { } Arete<Poids> const & operator=(Arete<Poids> const & arete) { if(this!=&arete) { numero = arete.numero; extremites = arete.extremites; poids = arete.poids; } return *this; } Poids getPoids() const { return poids; } void setPoids(Poids p) { poids = p; } std::pair<int, int> getExtremites() const { return extremites; } int getNumero() const { return numero; } private : int numero; std::pair<int, int> extremites; Poids poids; }; #endif // Arete_h
Graphe
#ifndef Graphe_h #define Graphe_h #include <vector> #include "Sommet.h" #include "Arete.h" template<typename PoidsArete, typename LabelSommet> class Graphe { public : Graphe() : sommets(), aretes() { } Graphe(Graphe<PoidsArete, LabelSommet> const & graphe) : sommets(graphe.sommets), aretes(graphes.aretes) { } int ajouteSommet(LabelSommet label) { sommets.push_back( Sommet<LabelSommet>(sommets.size()) ); sommets[sommets.size()-1].setLabel(label); return sommets.size()-1; } int ajouteArete(Sommet<LabelSommet> const & s1, Sommet<LabelSommet> const & s2, PoidsArete p) { aretes.push_back(Arete<PoidsArete>(s1.getNumero(), s2.getNumero(), aretes.size())); aretes[aretes.size()-1].setPoids(p); } int getNbSommets() const { return sommets.size(); } int getNbAretes() { return aretes.size(); } Sommet<LabelSommet> getSommet(int n) const { // Le sommet de numero n est en n-ième position return sommets[n]; } Arete<PoidsArete> getArete(int n) const { // Idem. return aretes[n]; } int degre(Sommet<LabelSommet> s) const { int result=0; for(int i=0; i<aretes.size(); ++i) { std::pair<int, int > extremites = getExtremites(aretes[i]); if(extremites.first==s.getNumero() || extremites.second== s.getNumero()) { ++result; } } return result; } private : std::vector<Sommet<LabelSommet> > sommets; std::vector<Arete<PoidsArete> > aretes; }; #endif // Graphe_hpp
Tramway
#include <iostream> #include <string> #include "Sommet.h" #include "Arete.h" #include "Graphe.h" int main() { Graphe<float, std::string> g; // Création de réseau du tram (terminus et croisments int sommets[9]; sommets[0] = g.ajouteSommet("Hautepierre Maillon"); sommets[1] = g.ajouteSommet("Rotonde"); sommets[2] = g.ajouteSommet("Elsau"); sommets[3] = g.ajouteSommet("Illkirch Lixenbuhl"); sommets[4] = g.ajouteSommet("Homme de fer"); sommets[5] = g.ajouteSommet("Etoile Polygone"); sommets[6] = g.ajouteSommet("République"); sommets[7] = g.ajouteSommet("Hoehnheim Gare"); sommets[8] = g.ajouteSommet("Esplanade"); int aretes[8]; aretes[0] = g.ajouteArete(g.getSommet(0), g.getSommet(1), 12.34); aretes[1] = g.ajouteArete(g.getSommet(4), g.getSommet(1), 23.45); aretes[2] = g.ajouteArete(g.getSommet(4), g.getSommet(2), 34.56); aretes[3] = g.ajouteArete(g.getSommet(4), g.getSommet(6), 45.67); aretes[4] = g.ajouteArete(g.getSommet(4), g.getSommet(5), 56.78); aretes[5] = g.ajouteArete(g.getSommet(4), g.getSommet(3), 67.89); aretes[6] = g.ajouteArete(g.getSommet(6), g.getSommet(7), 78.90); aretes[7] = g.ajouteArete(g.getSommet(6), g.getSommet(8), 89.01); return 0; }