Template & pointeurs

Version imprimable

11/07/2008, 15h32
Apocalipsia`

Template & pointeurs
Bonjour a tous !

Bon, j'ai un petit soucis de compréhension je pense... J'ai lu toutes les aides et tuto possible mais je n'ai pas trouvé ma réponse.

Pour un projet perso, je suis en train de recoder une liste chainée générique. Mon problème est le suivant :

J'utilise une structure :
Code:

1 2 3 4 5 6 7 8 template <typename T> struct listC { listC * prev; T v; listC * next; };
J'ai une fonction "find" qui permet de me placer sur un élément passé en paramètre :

Code:

eListErr find (T &t);

(eListErr est un enum d'erreur...) La fonction find appel l'opérateur != qui doit etre surchargé pour le type T.

Jusque là tout va bien ! Ca marche très bien avec des int, des float, et touti quanti... Evidement, ca ne fonctionne pas pour les char * mais ca c'est normal... Le problème, c'est que je ne peux pas spécialiser mes template pour chaque classe que je vais utiliser... Or, dans mon cas, j'utilise une classe "Node" (qui représentent les noeuds d'un graph lui meme template aussi mais ca c'est pas un problème) J'instancie donc comme suit (je vous passe les templates du node pour plus de clareté...) :

Code:

TempList<Node *> *nodeList = new TempList<Node *>

Tout va bien... Sauf quand je fais un find... evidement, comme mon T est "Node *", il compare les adresses... Du coup ca fait pas ce qu'il faut... (l'opérateur != est évidement surchargé pour Node...)

L'astuce c'est que je ne veux pas lui mettre T=Node parce que j'ai plusieurs listes de noeuds et voudrais éviter les redondances... et si je met "T *v" dans la structure de base, c'est la meme chose... Je vais devoir faire l'allocation en interne et donc réallouer chaque noeud autant de fois qu'ils apparaissent dans une liste... S'il n'y a pas de solution, je ferais comme ca, tant pis pour la mémoire...

Merci d'avance si vous avez des idées !

Apo`
11/07/2008, 15h48
JolyLoic

Tu peux ajouter un élément template à ta liste (ou à ta fonction find) qui indique comment les objets sont comparés.

Autre solution, moins flexible, tu fais une spécialisation partielle de ta liste pour les T* qui compare sur les T.
11/07/2008, 15h52
Apocalipsia`

Et bhe justement, pour moi la surcharge de l'opérateur != c'est plus simple que de passer une fonction en paramètre... Mais si je peux pas j'y viendrais surement.

J'ai déja pensé a une spécialisation partielle, ca ne fonctionne pas pour simple raison que comme mon T est "Node *", de toute facon il n'appel pas la méthod "find(T *t)" puisque pour lui ca serait un "Node **" qu'il faut... (Ou alors je m'y suis mal pris...)

Merci pour la réponse rapide en tout cas ! J'attend d'autres avis, si certains ont des idées, sinon je ferais passer une fonction de comparaison... Tant pis pour l'opérateur != :)

Apo`
11/07/2008, 16h08
JolyLoic

Citation:

Envoyé par Apocalipsia`

J'ai déja pensé a une spécialisation partielle, ca ne fonctionne pas pour simple raison que comme mon T est "Node *", de toute facon il n'appel pas la méthod "find(T *t)" puisque pour lui ca serait un "Node **" qu'il faut... (Ou alors je m'y suis mal pris...)

J'en ai l'impression. On peut avoir un extrait du code correspondant.

Voici le code de ma liste chainée :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#ifndef TEMPLIST_H
#define TEMPLIST_H
 
typedef enum eListErr
{
  LIST_ERR_NO_ERROR,
  LIST_ERR_MEMORY_ALLOCATION_ERROR,
  LIST_ERR_EMPTY_LIST_ERROR,
  LIST_ERR_NOT_FOUND,
  LIST_ERR_INDEX_OUT_OF_BOUND
 
};
 
template <typename T>
struct listC
{
  listC * prev;
  T v;
  listC * next;
};
 
template <typename T>
class TempList
{
public:
  // Constructor
  TempList();
  ~TempList();
 
  TempList(const TempList<T> &l);
 
  TempList &operator = (const TempList<T> &l);
 
  eListErr insert(T t);
  eListErr insert(unsigned long index, T t);
  eListErr del(bool freeValue);
  eListErr del(unsigned long index, bool freeValue);
  eListErr delAll(bool freeValue);
  eListErr change(T t, bool freeValue);
 
  eListErr find(T t);
  eListErr find(T *t);
  eListErr access(int index);
  T operator [] (int index);
 
  T getValue();
 
  inline unsigned int size() {return m_size;}
  inline bool isEmpty() {return !m_first;}
 
private:
  listC<T> * m_first;
  listC<T> * m_current;
  listC<T> * m_last;
  unsigned int m_size;
};
 
#include "tempList.tpp"
 
#endif

Et le code de find :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template <typename T>
eListErr TempList<T>::find(T t)
{
  if (isEmpty()) return LIST_ERR_EMPTY_LIST_ERROR;
 
  listC<T> * temp = m_first;
 
  printf("temp->v :%i\nt :%i\n", temp->v, t);
 
  while (temp != m_last && temp->v != t) 
  {
    printf("temp->v :%i\nt :%i\n", temp->v, t);
    temp = temp->next;
  }
  if (temp == m_last && temp->v != t) return LIST_ERR_NOT_FOUND;
 
  return LIST_ERR_NO_ERROR;
}
 
template <typename T>
eListErr TempList<T>::find(T *t)
{
  if (isEmpty()) return LIST_ERR_EMPTY_LIST_ERROR;
 
  listC<T> * temp = m_first;
 
  printf("temp->v :%i\nt :%i\n", temp->v, t);
 
  while (temp != m_last && *temp->v != *t) 
  {
    printf("temp->v :%i\nt :%i\n", temp->v, t);
    temp = temp->next;
  }
  if (temp == m_last && *temp->v != *t) return LIST_ERR_NOT_FOUND;
 
  return LIST_ERR_NO_ERROR;
}

Je pense que je n'ai pas bien saisi comment fonctionne la spécialisation en fait... :/ Un éclaircissement ? :)

Apo`

11/07/2008, 17h04
koala01

Salut,

Personnellement, je ne ferais pas renvoyer un code d'erreur à une fonction nommée find :aie:

En effet find signifie ... trouve :P
Dés lors, on est en droit de s'attendre à ce qu'une fonction find(quelque chose) nous renvoie... l'élément trouvé :|

Par contre, il n'est pas exclu d'envisager qu'une telle fonction... lance une exception si... l'élément n'est pas trouvé ;)

J'aurais presque tendance à dire que ta fonction serait bien mieux nommée "exists", pour indiquer à l'utilisateur qu'elle vérifie l'existence de l'élément... mais on pourrait alors estimer qu'un simple booléen (oui, l'élément existe, non il n'existe pas) serait amplement suffisant ;)

Maintenant, j'admet que ce n'est "qu'un détail" et que cela n'apporte pas la moitié d'une solution, mais j'estimais utile d'attirer ton attention sur l'importance de la "sémantique" que l'on donne aux noms de fonctions ;)
11/07/2008, 17h21
Apocalipsia`

Tout commentaire est bon a prendre !!! Et je t'en remerci !

Je l'ai appeler find, parce qu'en fait elle se positionne sur l'élément... (s'il éxiste), donc Exist n'est pas cohérent, et j'ai surcharger le [] pour renvoyer un élément...

J'ajoute que pour moi, la plupart du temp, lorsqu'une méthode renvoie une valeur, elle est nommé "get...()", je n'ai pas trouvé mieux que "find", ca aurait pu etre "setCurrentOn" ou quelque chose du genre mais bon...

Disons que l'interet de cette méthode est que l'on peut facilement la trier puisque l'insertion se fait apres la valeur en cour.

Meme s'il ne résoud pas mon problème, merci pour ce commentaire ^^

Apo`
11/07/2008, 18h53
koala01

A vrai dire, meme si tu la nommais "setCurrentTo", voir, pourquoi pas, tout simplement "select" (ce qui serait sémantiquement parfait), je ne renverrais pas l'erreur dans le type de retour... je préférerais lancer une exception, de manière à lui permettre de remonter jusqu'à ce qu'elle soit en mesure d'être gérée ;)

Car, même nomée SetCurrentTo (ou quelque soit son nom, d'ailleurs), on "peut s'attendre" à ce que la méthode qui va sélectionner l'élément courent renvoie - au choix - un itérateur (idéalement :D), un pointeur ou une référence vers l'élément sélectionné ;)

[EDIT]PS: tu auras remarqué que je ne suis pas partisan des retours en forme de valeur d'erreur... ou du moins, pas dans le cas présent ;)

Effectivement, là tu n'as pas spécialisé, tu as juste défini une surcharge.

L'idée est une syntaxe du style (aux typos près) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 // Définition du template de base template <class T> class list { void add (T t); }; // Spécialisation totale pour les Noeuds* template<> class list<Noeud*> { // On peut y mettre tout ce qu'on veut, mais en général, on // fourni au moins la même interface que le template primaire void add (Noeud*n); }; // Spécialisation partielle pour les données de type pointeur // plus générique qu'une spécialisation totale template<class T> class list<T*> { // Idem pour ce qui concerne le contenu void add(T* t); };
Mais je ne suis pas certain que ce soit la meilleure solution. Avoir un comparateur variable instance par instance me semble plus générique que cette solution où toutes les listes d'un même type vont devoir avoir la même notion de ce qu'est une comparaison.

15/07/2008, 09h27
Apocalipsia`

Merci pour vos réponses !

@koala01 : Perso je suis pas fan des exceptions, d'ou ce choix ^^ Chacun son truc :) (Mais j'approuve le nom "select" !!!! Merci :D)

@JolyLoic : Oki, merchi, donc c'est bien ce que j'avais compris de la spécialisation... On est obligé de redéfinir entierement la class... On peut pas spécialiser uniquement une méthode :/ Tant pis... Je vais faire un copier coller de ma class et j'aurais du code en double ^^ Merci beaucoup en tout cas ! :)

Apo`
15/07/2008, 12h01
Alp

On ne peut pas spécialiser partiellement une méthode, je crois.
15/07/2008, 13h35
Apocalipsia`

Visiblement... :/

Enfin, en duplicant mon code et en modifiant juste la méthode select pour les pointeurs, ca marche bien, mais bon... doubler du code je trouve ca moyen, mais au moins ca marche ^^

Merci a tous ! :)

Apo`
15/07/2008, 16h42
loufoque

Je ne comprends vraiment pas l'intérêt de faire un conteneur de pointeurs, surtout quand il s'agit d'un conteneur à base de nœuds.
15/07/2008, 16h48
koala01
Citation:

Envoyé par Apocalipsia`

@koala01 : Perso je suis pas fan des exceptions, d'ou ce choix ^^ Chacun son truc :) (Mais j'approuve le nom "select" !!!! Merci :D)

Je continue dans la digression, mais, personnellement, je ne vois pas pourquoi:
- Une exception peut être un objet tout à fait indépendant du type de retour attendu
- Comme elle peut être un objet, il t'es possible d'utiliser toutes les méthodes de POO à leur sujet
- Une exception lancée est susceptible de contenir des informations de contexte bien plus importantes qu'une simple valeur de retour, quelle que soit l'origine de cette valeur significative.
- Une exception permet de réserver la valeur de retour en vue de renvoyer quelque chose de plus utile que le simple fait de savoir si "ca a marché" ou non... et éventuellement pourquoi
- Une exception est normalement prévue pour permettre de signaler un événement... exceptionnel (AKA: quelque chose qui n'aurait pas du se produire si toutes les conditions avaient été respectées, ou qui se produit parce que l'on a atteint les limites du système).
- Une exception est prévue pour remonter dans la pile d'appel, en gardant le contexte du problème survenu, jusqu'à ce que l'on soit en mesure d'apporter une réponse à ce problème, sans avoir à s'inquiéter de la nécessité de récupérer à chaque fois le retour de la fonction et de devoir gérer tous les cas potentiels d'erreur alors... que l'on n'est peut-être (sans doute :question:) pas ou plus en mesure d'en gérer la plupart.
Maintenant, je reconnais que la gestion des exceptions peut faire un peu peur aux gens qui n'y sont pas habitués, mais je peux t'assurer qu'elles sont de nature à te faciliter grandement tes développements futurs.

Ce n'est donc qu'un conseil, et je te laisse libre d'en faire ce que tu veux, mais, si j'étais toi, je m'y intéresserait d'un peu plus près et j'accepterais d'au moins me donner l'occasion de changer d'avis
15/07/2008, 16h52
Alp

Citation:

Envoyé par loufoque

Je ne comprends vraiment pas l'intérêt de faire un conteneur de pointeurs, surtout quand il s'agit d'un conteneur à base de nœuds.

Boost.Ptr_Container ?
15/07/2008, 17h01
Apocalipsia`

@koala01 :

Je n'ai jamais dit que les exceptions n'étaient pas utiles... J'en ai par ailleur déja fait l'expérience et je confirme que c'est pratique, par contre, je maintient que je ne suis pas fan pour des simples questions de lisibilité (qui est surement une habitude en fait...) Je trouve que des blocs "try {} catch {}" partout ca rend le code illisible, et j'ajoute que comprendre les classes d'exception c'est souvent galère (ok j'en ai fait surtout en java, sachant que je suis pro C++, ca m'a un peu bloqué.... Mais bon)

Bref pour résumer : comme tu le dis, c'est une (mauvaise) habitude, je m'y mettrais surement, pour le moment c'est un projet perso qui n'a aucune envergure particuliere et pour me faire plaisir... On verra si je me fais plaisir sur les exceptions quand ca marchera ;)

Apo`
15/07/2008, 17h22
Médinoc

Si on se met à parler des exceptions, bien que ce soit hors-sujet, je dirais qu'à mon goût elles ne sont, la plupart du temps, pas "assez facultatives": Pour moi, elles devraient être réservées aux erreurs exceptionnelles, et non pas aux "échecs" auxquels on s'attend.

Le niveau de "facultatif" que j'attends généralement est celui des collections .Net : La différence entre valeur = map[clé] et map.TryGet(clé, out valeur). Cette facilité exposée par les collections ne l'est pas par les fichiers, et c'est assez horripilant quand, en exécutant un programme dans le debugger, on doit sauter les quatre premières FileNotFoundException parce que les fonctions de sérialisation XML n'ont pas trouvé des assemblys non-obligatoires, alors qu'elles peuvent faire sans.
15/07/2008, 17h27
Apocalipsia`

Tres juste Médinoc ! Bien d'accord avec cette version ^^ (ce qui ne m'aide pas a me lancer dans les exceptions :P)

Et pour revenir au sujet initial, finalement, j'ai dupliqué mon code et j'ai spécialisé ma classe pour les pointeurs... Ca marche tres bien mais du coup, pour UNE méthode différente, j'ai deux fois le code, je trouve ca dommage mais bon... Visiblement, pas d'autre solution ^^

Apo`
15/07/2008, 17h28
Médinoc

C'est généralement le genre de cas où tu peux envisager de séparer ta classe en deux: Une classe mère contenant toutes les fonctions sans spécialisation, et deux classes filles...
15/07/2008, 18h04
JolyLoic

Citation:

Envoyé par Apocalipsia`

Je trouve que des blocs "try {} catch {}" partout ca rend le code illisible, et j'ajoute que comprendre les classes d'exception c'est souvent galère (ok j'en ai fait surtout en java, sachant que je suis pro C++, ca m'a un peu bloqué.... Mais bon)

En Java, les blocs try sont nécessaires pour faire de la libération déterministe de ressource, par try/finally. Il y en a donc beaucoup.

En C++, cette même fonctionnalité est remplie plus élégamment pas les destructeurs et le RAII, et donc on se retrouve au final à avoir beaucoup moins de blocs try. Si ce n'est pas le cas, c'est en général que le code est mal écrit.

Pour le cas qui nous concerne, je ne sais pas si une exception est la bonne façon d'introduire une erreur. Intuitivement, et sans avoir trop réfléchi au sujet, j'aurais plutôt utilisé une valeur sentinelle.
16/07/2008, 09h33
Apocalipsia`

En ce qui concerne les exceptions, je ne me repeterais pas. J'ajouterais juste : "De plus je n'en ai pas assez fait en C++ pour les gérer correctement pour le moment, comme je voudrais finir vite ce projet (qui sera long) je ne m'y lance pas pour le moment :)"

Apo`
16/07/2008, 23h49
loufoque

Une liste chaînée, c'est déjà des pointeurs. La structure ne requiert nullement que le type et la taille des objets soient homogènes.
Bien entendu, faire marcher ça avec l'héritage etc. peut demander quelques astuces. (avec des listes intrusives, c'est assez trivial)
17/07/2008, 09h46
Apocalipsia`

Le problème n'est pas l'homogénéité... Le problème c'est la place que ca prend en mémoire... Si tu stocks des classes complexes et gourmandes dans plusieurs listes en meme temps, en ne stockant pas les pointeurs mais les objets tu vas doubler rapidement ton utilisation mémoire...

Apo`
18/07/2008, 04h19
loufoque

Si le nombre de listes dans lesquelles tu veux mettre ton élément est statique (ce qui est généralement le cas), il suffit de mettre autant de pointeurs vers le maillon suivant dans ton objet que nécessaire.
Bien entendu, ce genre de chose n'est réalisable qu'avec des listes intrusives.
18/07/2008, 09h04
Apocalipsia`

Tout a fait ! Mais ce n'est pas forcément le cas. Si tu as une liste de liste par exemple... :)

Apo`