Version imprimable
D'accord dragonjoker59 mais ce que je veux dire par là, c'est que lors de la compilation, les directives de préprocesseur des .cpp seront aussi parcourues, donc je ne vois pas pourquoi le temps de compilation serait différent entre le fait de mettre les includes dans les .h ou dans les .cpp...
Le vrai code (les unités de compilation) est dans les cpp.
Dans les headers (les h) tu as juste du code qui va être copié/collé dans tes cpp , via #include.
Donc, si tu as des N #include dans un .h, tous les cpp qui vont include ce fichier vont appliquer l'include. Si tu as K fichiers cpp, alors tu as T = N x K includes qui vont se passer à la compilation.
Une #include corresponds à un copier coller de fichier, soit:
1. ouvrir le fichier
2. lire le contenu
2.1. lire les commandes de preprocessing et les appliquer (potentiellement allant a 1. recursivement)
3. copier le code final (après preprocessing) dans le code du cpp
Hors optimizations faites par les compilateurs, tu vas donc avoir T fois ces operations.
Notemment, 1. est très couteux, 2. est contextuel et peut donc donner différents résultats selon les définitions en cours (#define).
Et en plus, seulement une fois tous les includes resolus, là on peut compiler l'ensemble.
Donc c'est couteux en temps. Dans l'idéal, limite les #include dans le .h à ce qui est absolument nécessaire, lorsque tu dois avoir la DEFINITION des types utilisés dans le header. Si tu n'as besoin que de leurs noms, leurs DECLARATION, alors fait des "forward declare", dis juste que leurs noms existes - typiquement si tu ne manipules que des pointeurs et des références vers ces types dans le header.
En fait il faut comprendre tout le processus de compilation pour que cela paraisse évident.
bonjour
veux-tu reinventer la roue a propos de la representation d'un graphe.il n'y a pas sur le plan des recherches mathematiques theoriques d'autres representation efficiente que matrice d'incidence noeud/noeud ou(exclusif) matrice d'adjacence arcs/noeuds .
Elles contiennent si je puis dire la "quintessence,la moelle " pour decrire d'une maniere complete un graphe et meme un peu plus .
Entre autres suivant que l'on a choisi l'une de ces 2 representations on peut deduire ,à partir d'une liste des aretes ou arcs les informations suivantes :
1/graphe non oriente
- liste des noeuds voisins d'un noeud
- liste des arcs voisins d'un noeud
2/graphe oriente (arete oriente)
- liste des noeuds voisins incidents et sortants d'un noeud
- liste des arcs voisins incidents et sortants d'un noeud
De plus ces "structures" d'informations complementaires sont -indispensables- dans la quasi majorites des algo de graphes classiques (plus court chemin et ses variantes, coupe ,postier chinois, sac à dos .... ).
Maintenant il ne faut pas confondre l'implementation de ces representations dans un language bien specifique (c++,fortran,java ou cobol ...) et les 2 representations citees ci-dessus.
Je connais des implementations de graphe en fortran(ou il n'y a que des tableaux),en c++ avec des dictionnaires etc....
Implementation
---------------
Un premier point est remarquable dans l'implementation :
-la representation par une matrice d'incidence n'a pas la faveur des auteurs de code à cause qu'elle peut etre "sparse" (comporter des elements vide -graphe peu dense en nombre d'aretes) et gaspiller la memoire.
-aussi la matrice d'adjacence a-t-elle la faveur dans toutes les implementations quelque soit les languages utilises.
Un deuxieme point qui parait anodin mais de la plus haute importance en realite est que l'information "noeud" est deja contenu dans l'information "arete" mais l'inverse n'est pas vrai (un graphe ou tous les noeuds seraient "pendants ou dead nodes " ne repond pas à la definition d'un graphe).Ceci pour soulager ton martyr à propos de la redondance qui n'existe pas si ty reflechis un peu plus en profondeur.
Un troisieme point doit attirer l'attention est que les donnees d'un graphe sont disponibles ou peuvent etre toujours mises sous la forme d'une liste d'aretes jointes à d'autres informations.
Armes de ces remarques on peut concevoir :
-un dictionnaire graphe (un dictionnaire ou table de hashage à cle unique) contenant la liste des membres de la classe Arcs (cle=serait "startnode+endnode",numero d'arc=indice).
L'utilite du dictionnaire vient à propos pour eviter les erreurs dans les donnees ainsi que son indice qui servira heureusement à numeroter les arcs.
-toujours un 2eme dictionnaire(ou est deporte la fameuse adjacence arc-noeud) s'avere approprie pour la classe "Node" (cle="startnod",numero noeud =indice).Les membres de cette classe sont crees au fur et à mesure de l'insertion des aretes.
L'utilite du dictionnaire est qu'il permet de n'inserer que les noeuds des nouveaux arcs mais qui ne figurent pas encore dans le dictionnaire noeud (pas de "dead nodes ou bouts morts" suite à une duplication erronee).
Les autres structures complementaires citees en 1/ et 2/ sont egalement à implementer dans les classes de base.Ces structures sont construites egalement au fur à mesure de l'insertion des aretes et noeuds
La encore ne craignons pas d'abuser des dictionnaires pour les noeuds voisins et les arcs voisins d'un noeuds.
Entre autre utilite de la structure dictionnaire est qu'elle permet d'eviter le fameux test de connexite d'un graphe.
-Il faudrait implementer le tri evidement qui est utile dans la fonction de base des classes.
Classe Graphe
-------------
Autre question bien à propos c'est d'implementer la classe Graphe car il s'agit d'une question pratique bien à propos:
-distinguer un graphe oriente d'un graphe non-oriente
-appartenance d'un sous-graphe à un graphe (foret).
-un algo doit posseder en donnee d'entree une instance graphe (avec tous ses baguages cite ci-dessus) et se limiter à implementer uniquement ses propres structures et sa logique.
Algos structures et methodes communes
---------------------------------------
-table de marquage pour exploration ou tables de recherche avec des structures identiques (liste de noeuds ou arcs predecesseurs dans une exploration)peuvent etre communes à plusieurs algos ainsi que leur methodes (à mettre en pool =>methodes helper d'algo).
Algos structures specifiques
------------------------------
-les autres structures et mthodes specifiques à chaque algo sont à circoncire à l'algo en question.
Pour l'anecdote quand j'ai vu les structures utilisees dans la BCL et dans les fameux graphes de codeplex cela m'a rappele 2 anciens programmes en fortran (annee 70) qui utilisait une structure graphe et comment le probleme de "redondance" avait ete resolu remarquablement à l'epoque par une routine dont le seul role est de verifier au cours de la lecture de chaque arc pour la paire "starnode" et "endnode" que le "nom" de chaque node ne figure dans une table des noms de noeuds et auquel cas elle devait l'ajouter et renvoyer un numero de noeud .
Ce numero etait necessaire pour construitre les autres tables (noeuds voisins,arcs voisins) car les "noms" servait juste de mnemoniques pour l'impression et la comprehension humaine des choses par les utilisateurs en fait )
En esperant que mes humbles remarques auront contribues à eclaircir un peu mieux les choses....
bon code....grapheur...mais il ne faut lacher le morceau et avoir bonne prise...
La raison est simple. Un fichier .cpp définit une unité de traduction et est donc compilé une seule fois. Un fichier .h est compilé une fois par unité de traduction qui l'inclut, donc un nombre arbitraire de fois.Citation:
Envoyé par betsprite
Donc, ajouter un include dans un cpp entraîne potentiellement une et une seule compilation supplémentaire de ce fichier d'en-tête; ajouter un include dans un .h entraîne un nombre arbitraires de compilations supplémentaires.