Question sur les pointeurs génériques

Version imprimable

16/05/2006, 23h29
mikedavem

Question sur les pointeurs génériques

Bonsoir tout le monde ,

J'ai juste une question sur les pointeurs génériques.
En fait j'aimerais faire une fonction de tri générique par la méthode Tri à bulle . Donc je ne connais pas ce que je vais trier.

J'ai vu dans la FAQ qu'il fallait passer en paramètre le type de variable à traiter donc dans mon cas il faut absolument que je passe le type d'objet à trier . Mais y'a t il un autre moyen de le faire , par exemple en passant la longueur de l'objet ?

Merci pour vos réponses
16/05/2006, 23h35
Emmanuel Delahaye
Citation:

Envoyé par mikedavem

J'ai juste une question sur les pointeurs génériques.
En fait j'aimerais faire une fonction de tri générique par la méthode Tri à bulle . Donc je ne connais pas ce que je vais trier.

J'ai vu dans la FAQ qu'il fallait passer en paramètre le type de variable à traiter donc dans mon cas il faut absolument que je passe le type d'objet à trier . Mais y'a t il un autre moyen de le faire , par exemple en passant la longueur de l'objet ?

Pour faire des traitements de données génériques, il faut passer
- L'adresse
- La taille de l'élément
- Le nombre d'éléments (si c'est un tableau)
Regarde l'interface de la fonction standard qsort(), tu vas comprendre.

C'est un sujet interessant. Poste ton code...

Ok ,

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
 
#include <stdio.h>
#include <stdlib.h>
 
   void** Tri_generique(void *tabTri, int nbobjet, int longobjet, int(*compare)(void *, void *)) {
 
   int i,j,permut=0;
   void** tabrang = malloc(nobjet*longobjet);
   void *temp;
 
   if (tabrang) {
      // Initialisation du tableau en insérant les pointeurs de tabTri
      for(i=0;i<nbobjet;i++) tabrang[i] = &(tabTri[i]);
 
      // Tri à bulle
      for(i=0;(i<nbobjet) && (permut == 0);i++) {
         permut = 1;
         for(j=1;j<(nbobjet-i);j++) {
            if(compare(tabrang[j],tabrang[j-1]) == -1) {
               temp = tabrang[j-1];
               tabrang[j-1] = tabrang[j];
               tabrang[j] = temp;
               permut = 0;
                         }
                   }
             }
             return (tabrang);
       }
       else return NULL;
}

Bon j'ai une erreur "deferencing 'void *' pointer sur tabrang[i] = &(tabTri[i]) , ce qui peut paraître normale car je ne renseigne aucun type de variable... On fait comment dans ce cas là ? car je ne suis censé ne pas le connaître .

En attendant je vais regarder l'interface de qsort comme tu me l'as indiqué.

Merci pour ta réponse

Citation:

Envoyé par mikedavem

Bon j'ai une erreur "deferencing 'void *' pointer sur tabrang[i] = &(tabTri[i]) , ce qui peut paraître normale car je ne renseigne aucun type de variable... On fait comment dans ce cas là ? car je ne suis censé ne pas le connaître .

Tu aurais dû faire un copié/collé, car il y a des erreurs de saisie...

Le type void** ne fait pas du tout ce que tu crois, et n'est pas générique. Seul void* est générique. De toutes façon, ta stratégie n'est pas bonne. Une fonction de tri de fait pas la copie triée d'un tableau mais agit directement sur le tableau original (qui doit évidemment être modifiable).

Pour ce qui est des calculs internes, il faut créer un ou des pointeurs char * internes et faire les calculs d'adresse à la main à l'aides des informations passée en paramètre (taille de l'élément, notamment). Quand aux copies (swap), elles se font à coup de memcpy(), l'élement temporaire étant évidemment alloué dynamiquement (1 seule fois, bien sûr). Il n'y a rien à retourner.

Tu devrais donner un exemple complet, notamment de la fonction de comparaison, ou au moins expliquer sa valeur de retour...

Tu aurais dû commencer par mettre au point l'algo de tri, car il est faux.

Voici une version corrigée de l'algo...
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 61 62 63 64 65 66 #include <stdio.h> #include <stdlib.h> #include <string.h> #define DBG 0 static intswap (int *a, int *b) { int t = *a; *a = *b; *b = t; } void Tri_int(int *tabTri, size_t nbobjet, int(*compare)(void const *, void const *)) { // Tri à bulle size_t i; int *pa = tabTri; for (i = 0; i < nbobjet; i++) { size_t j; for (j = 1;j < nbobjet - i; j++) { if (compare(pa + (j - 0), pa + (j - 1)) < 0) { intswap(pa + (j - 0), pa + (j - 1)); } } } } static int compare (void const *a, void const *b) { int const *pa = a; int const *pb = b; #if DBG printf ("*pa=%3d *pb=%3d\n", *pa, *pb); #endif return *pa - *pb; } static display (int *a, size_t n) { size_t i; for (i = 0; i < n; i++) { printf ("%3d", a[i]); } printf ("\n"); } int main (void) { int a[] = { 4, 2, 6, -1, 5, 4, 6, 2, 5, 7, 3 }; Tri_int(a, sizeof a / sizeof * a, compare) ; display(a, sizeof a / sizeof * a); return 0; }
La partie comparaison est générique. Je te laisse rendre la chose complètement générique (j'ai une solution qui fonctionne). L'algo a été prépéré pour la généricité. Il ne reste plus qu'à modifier le type de pa en char * et d'integrer la taille de l'objet dans les calculs d'adresse.

Il y a une petite astuce pour optimiser le swap génerique... (mais j'en ai déjà parlé)

17/05/2006, 09h07
mikedavem

Excuse pour les fautes , le copier coller ne marchait pas chez moi sous linux .. Je mettrais le code complet dès ce soir .

En fait j'ai pris un bout de prog que j'ai fait cette année . Il fallait trier un tableau de structure de skieurs (champ nom , prenom , age , vitesse ..) . Le trier directement est trop long donc il fallait passer par un tableau intermédiaire d'indice. On pouvait passer par n'importe quelle méthode de tri (Bon là j'ai pris une méthode tri à bulle) .

Bon je mettrais le code dès ce soir de toute façon.

Merci encore pour ton aide
17/05/2006, 09h10
Emmanuel Delahaye

Citation:

Envoyé par mikedavem

En fait j'ai pris un bout de prog que j'ai fait cette année . Il fallait trier un tableau de structure de skieurs (champ nom , prenom , age , vitesse ..) . Le trier directement est trop long donc il fallait passer par un tableau intermédiaire d'indice. On pouvait passer par n'importe quelle méthode de tri (Bon là j'ai pris une méthode tri à bulle) .

Avec qsort(), tu tries n'importe quoi..
17/05/2006, 19h13
mikedavem

ben disons que j'aimerais passer par un tableau de pointeurs sur ce fameux tableau de structures pour éviter de bouger les éléments à chaque fois lors d'un tri. (en imaginant que ma structure comporte un champ image qui est un tableau à 3 dimensions par exemple)...

On bougera simplement les pointeurs ...

Donc il n'y a pas de moyen d'affecter à tabrang (tableau de pointeurs) l'adresse du pointeur de tabTri (tableau de structures) ?
17/05/2006, 19h20
Emmanuel Delahaye

Citation:

Envoyé par mikedavem

ben disons que j'aimerais passer par un tableau de pointeurs sur ce fameux tableau de structures pour éviter de bouger les éléments à chaque fois lors d'un tri.

Bonne idée.

Tu crées le tableau de pointeurs
Tu le tries
Tu t'en sers pour accéder aux données. qsort() permet le tri. Tu voulais tout intégrer, c'est ça ?

Il faut peut être travailler avec un niveau d'abstraction supplémentaire et des fonctions de manipulation des données (approche 'objet') de façon à ne pas embéter l'utilisateur avec les détails gores.

Pour concevoir ce genre d'engin, on part de l'utilisation et on évalue les besoins en terme de fonctions, d'interfaces et comportements. Ensuite, il ne reste plus qu'à coder.
...
17/05/2006, 20h38
mikedavem

1 pièce(s) jointe(s)

Exactement , je me sers du tableau de pointeurs trié pour réafficher dans l'ordre selon le critère choisi (Nom ou vitesse etc..) . Il faut juste que j'arrive à mettre les adresses de mon tableau passé en paramètre dans mon tableau de pointeur que j'ai créé . Hors la j'ai un bel "deferencing void pointer" . Il faut que j'arrive à contourner mon pb . (je précise que sans les void* et avec les types de structure connues ca marche bien sûr)

Bah je suis encore un newbie mais bon ca va rentrer :lol:

Je passe le code des fois que quelq'un sache comment contourner ca (le copier coller ne marche pas chez moi depuis la nouvelle version du forum .. je ne sais pas pouquoi .. faut que je cherche ).. Je cherche de mon côté de toute façon

Merci
17/05/2006, 21h52
mikedavem

Bon à bien regarder , y'a qq parties qui ne vont pas .. Je m'embrouille je pense ,

Je vais approfondir le sujet et revenir sur le post qd j'aurai un peu plus réfléchi .

Merci des réponses en tout cas

Bonjour tout le monde ,

bon finalement j'y suis arrivé . Je mets le code au cas ou ca intéresserait qqn.
La fonction renvoie donc un tableau de pointeurs sur n'importe quel tableau de structure ou autre passé en paramètre. Y'a peut être encore des maladresses dans l'écriture du code ..

++

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
#include <stdio.h>
#include <stdlib.h>
#include "tri_generique.h"
 
void ** TriGenerique(void *tabTri, unsigned int nbElements, unsigned int tailleElement, int(*compare)(const void *, const void *)) {
 
   int i,j,permut=0;
   void ** tabrang = malloc(nbElements*sizeof(int));
   int *temp;
 
   if (tabrang) {
      // Initialisation du tableau tabrang avec les adresses de d             
   for (i=0;i<nbElements;i++) tabrang[i] = tabTri+(tailleElement*i);
      // Boucle de tri
      for(i=0;(i<nbElements) && (permut == 0);i++){
         permut = 1;
         for(j=1;j<(nbElements-i);j++){
            if (compare(tabrang[j],tabrang[j-1]) < 0) {
           temp = tabrang[j-1];
           tabrang[j-1] = tabrang[j];
           tabrang[j] = temp;
           permut = 0;
        }
     }
      }
 
      return(tabrang);
   }
   else return NULL;
}

et une de mes fonctions compare

Code:

1
2
3
4
5
6
7
8
 
// Fonction compare avec le numéro de dossard du skieur
   int compare_numDossard_skieur (const void *a1, const void *a2) {
   SKIEUR *p1 = (SKIEUR *)a1;
   SKIEUR *p2 = (SKIEUR *)a2;
 
   return ((p1->numDossard < p2->numDossard) ? -1 : +1); 
}

Citation:

Envoyé par mikedavem

En fait, c'est un indexeur trié. Il suffisait de créer l'index comme tu l'as fait, et ensuite d'appeler qsort() pour trier les pointeurs en fonction des données pointées...

Ca fait moins de copies que de toucher le tableau original et on peut avoir simultanément plusieurs index triés...

OK, c'est un bon exercice... Je vais jeter un oeil à ce code...

Ne fonctionne pas avec un tableau de doubles.

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
61
62
63
64
65
66
67
68
69
 
#include <stdio.h>
#include <stdlib.h>
//#include "tri_generique.h"
 
void ** TriGenerique(void *tabTri, unsigned int nbElements, unsigned int tailleElement, int(*compare)(const void *, const void *)) {
 
   int i, j, permut = 0;
   void ** tabrang = malloc(nbElements * sizeof(int));
   int *temp;
 
   if (tabrang)
   {
      // Initialisation du tableau tabrang avec les adresses de d
      for (i = 0;i < nbElements;i++)
         tabrang[i] = tabTri + (tailleElement * i);
      // Boucle de tri
      for (i = 0;(i < nbElements) && (permut == 0);i++)
      {
         permut = 1;
         for (j = 1;j < (nbElements - i);j++)
         {
            if (compare(tabrang[j], tabrang[j - 1]) < 0)
            {
               temp = tabrang[j - 1];
               tabrang[j - 1] = tabrang[j];
               tabrang[j] = temp;
               permut = 0;
            }
         }
      }
 
      return (tabrang);
   }
   else
      return NULL;
}
 
 
static int cmp (const void *a, const void *b)
{
   double *pa = a;
   double *pb = b;
 
   return *pa - *pb;
}
 
int main()
{
   static const double a[] =
      {
         2.3, 4.1, 1.5, 3.2, 1.9
      };
 
   void ** pp = TriGenerique(a, sizeof a / sizeof * a, sizeof * a, cmp);
   if (pp != NULL)
   {
      size_t i;
 
      for (i = 0; i < sizeof a / sizeof *a; i++)
      {
         double *p = pp[i];
         printf ("%.1f\n", *p);
      }
      free (pp), pp = NULL;
   }
 
   return 0;
}

Code:

1
2
3
4
5
6
7
8
 
2.3
1.5
1.9
4.1
3.2
 
Press ENTER to continue.

Mais vu le paquet de warning, je ne suis pas surpris...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
Compiling: main.c
main.c:5: warning: no previous prototype for 'TriGenerique'
main.c: In function `TriGenerique':
main.c:14: warning: comparison between signed and unsigned
main.c:15: warning: pointer of type `void *' used in arithmetic
main.c:17: warning: comparison between signed and unsigned
main.c:20: warning: comparison between signed and unsigned
main.c: In function `cmp':
main.c:41: warning: initialization discards qualifiers from pointer target type
main.c:42: warning: initialization discards qualifiers from pointer target type
main.c: In function `main_':
main.c:54: warning: passing arg 1 of `TriGenerique' discards qualifiers from pointer target type
Linking console executable: C:\dev\forums\OP\01.exe
Process terminated with status 0 (0 minutes, 0 seconds)
0 errors, 8 warnings

Je me suis penché sur ton code . J'ai modifié de façon à enlever les warning . Ca marche comme ca ...

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
 
#include <stdio.h> 
#include <stdlib.h> 
//#include "tri_generique.h"  
 
void ** TriGenerique(void *tabTri, unsigned int nbElements, unsigned int tailleElement, int(*compare)(const void *, const void *)) {     
   int i, j, permut = 0;    
   void ** tabrang = malloc(nbElements * sizeof(int));    
   int *temp;     
   if (tabrang)    {       // Initialisation du tableau tabrang avec les adresses de d       
      for (i = 0;i < nbElements;i++)          
         tabrang[i] = tabTri + (tailleElement * i);       
      // Boucle de tri       
      for (i = 0;(i < nbElements) && (permut == 0);i++)       {          
         permut = 1;          
         for (j = 1;j < (nbElements - i);j++)          {             
            if (compare(tabrang[j], tabrang[j - 1]) < 0)             {                
               temp = tabrang[j - 1];               
               tabrang[j - 1] = tabrang[j];                
               tabrang[j] = temp;                
               permut = 0;             
            }          
        }       
     }        
     return (tabrang);    
   }    
   else       
      return NULL; 
}   
 
static int cmp (const void *a, const void *b) {   
   return ((*(double*)a < *(double*)b ) ? -1 : +1); 
}   
 
int main() {    
   static const double a[] = { 2.3, 4.1, 1.5, 3.2, 1.9 };     
   double ** pp = (double **)TriGenerique((void*)a, sizeof a / sizeof * a, sizeof * a, cmp);    
   if (pp != NULL)    {       
      size_t i;        
      for (i = 0; i < sizeof a / sizeof *a; i++)       {          
         double *p = pp[i];          
         printf ("%.1f\n", *p);       
      }       
      free (pp), pp = NULL;    
   }     
   return 0; 
}

Citation:

Envoyé par mikedavem

Je me suis penché sur ton code . J'ai modifié de façon à enlever les warning . Ca marche comme ca ...

OK, j'avais une erreur dans ma fonction de comparaison. (Il faudrait mieux la documenter, car elle ne fonctionne pas comme celle de qsort() qui est la référence en la matière...)

Pour le reste, on ne résout pas les problèmes de warnings à coup de typecast, mais en mettant les bons types. La fonction de modifie pas le tableau (elle accepte donc de créer un index sur un tableau invariant), Ca doit apparaitre clairement :

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
61
62
63
64
65
66
67
68
 
#include <stdio.h>
#include <stdlib.h>
//#include "tri_generique.h"
 
static
void const **TriGenerique(void const *tabTri
                     , size_t nbElements
                     , size_t tailleElement
                     , int(*compare)(const void *, const void *))
{
   void const **tabrang = malloc(nbElements * sizeof* tabrang);
   if (tabrang != NULL)
   {       // Initialisation du tableau tabrang avec les adresses de d
      char const *pBytes = tabTri;
      size_t i;
      int permut = 0;
      for (i = 0;i < nbElements;i++)
      {
         tabrang[i] = pBytes + (tailleElement * i);
      }
      // Boucle de tri
      for (i = 0;(i < nbElements) && (permut == 0);i++)
      {
         size_t j;
         permut = 1;
         for (j = 1;j < (nbElements - i);j++)
         {
            if (compare(tabrang[j], tabrang[j - 1]) < 0)
            {
               void const *temp = tabrang[j - 1];
               tabrang[j - 1] = tabrang[j];
               tabrang[j] = temp;
               permut = 0;
            }
         }
      }
   }
   return tabrang;
}
 
static int cmp (const void *a, const void *b)
{
   double const *pa = a;
   double const *pb = b;
 
   return *pa < *pb ? -1 : 1;
}
 
int main()
{
   static const double a[] =
      {
         2.3, 4.1, 1.5, 3.2, 1.9
      };
   void const ** pp = TriGenerique(a, sizeof a / sizeof * a, sizeof * a, cmp);
   if (pp != NULL)
   {
      size_t i;
      for (i = 0; i < sizeof a / sizeof *a; i++)
      {
         double const *p = pp[i];
         printf ("%.1f\n", *p);
      }
      free (pp), pp = NULL;
   }
   return 0;
}

Pose des questions si tu ne comprends pas.

22/05/2006, 23h40
mikedavem

Ok merci pour tes réponses .

J'ai compris le truc pour ne pas caster comme un gorret .
Cependant j'ai juste une dernière question à te poser ? Est on obligé de mettre à chaque fois des const dans ce code . Est ce qu'on est obligé de les mettre dans ce cas là?

++
23/05/2006, 08h35
Emmanuel Delahaye

Citation:

Envoyé par mikedavem

Cependant j'ai juste une dernière question à te poser ? Est on obligé de mettre à chaque fois des const dans ce code . Est ce qu'on est obligé de les mettre dans ce cas là?

C'est pas au hasard. C'est une question de conception et de conformité aux specs.

Le principe, c'est const par défaut. Si il n'y a pas const, c'est que la fonction modifie les données. Elle n'acceptera donc pas de données invariantes (comme une chaine de caractères, oar exemple). Si tu compiles (ou vérifies) ton code avec gcc, active l'option -Wwrite-strings tu vas comprendre.
24/05/2006, 11h56
mikedavem

Ok , Merci pour tes réponses.