const et comparaison de chaines via qsort

Le
candide
Bonjour

Soit à coder une fonction de comparaison de chaînes à utiliser comme
callback par la fonction standard qsort().

La faq de fclc et de clc proposent cette implémentation :


/* */
/* compare strings via pointers */
int pstrcmp(const void *p1, const void *p2)
{
return strcmp(*(char *const *) p1, *(char *const *) p2);
}
/* */

Le site de ed (http://www.bien-programmer.fr/qsort.htm) propose encore
quelque chose de différent :

/* */
/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
/* definir des pointeurs type's et initialise's
avec les parametres */
char const *const *pa = a;
char const *const *pb = b;

/* evaluer et retourner l'etat de l'evaluation (tri croissant) */
return strcmp (*pa, *pb);
}
/* */


Moi, j'aurais plutôt dit :

/* */
/* compare strings via pointers */

int pstrcmp(const void *p1, const void *p2)

{

return strcmp(*(char const **) p1, *(char const **) p2);
}
/* */
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
-ed-
Le #21097781
On 30 jan, 14:01, candide
Soit à coder une fonction de comparaison de chaînes à utiliser comm e
callback par la fonction standard qsort().

La faq de fclc et de clc proposent cette implémentation :



Le site de ed (http://www.bien-programmer.fr/qsort.htm) propose encore
quelque chose de différent :



Moi, j'aurais plutôt dit :



Les trois méthodes fonctionnent...

#include #include #include /* ---------------------------------------------------*/
/* compare strings via pointers */
int pstrcmp_fclc (const void *p1, const void *p2)
{
return strcmp (*(char *const *) p1, *(char *const *) p2);
}

/* ---------------------------------------------------*/

/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
/* definir des pointeurs type's et initialise's
avec les parametres */
char const *const *pa = a;
char const *const *pb = b;

/* evaluer et retourner l'etat de l'evaluation (tri croissant) */
return strcmp (*pa, *pb);
}

/* compare strings via pointers */
int pstrcmp_candide (const void *p1, const void *p2)
{

return strcmp (*(char const **) p1, *(char const **) p2);
}

/* ---------------------------------------------------*/
static void print (char const *as[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf ("%s ", as[i]);
}
putchar ('n');
}

int main (void)
{
{
char const *as[] = { "a", "z", "e", "r", "t", "y", "u", "i",
"o", "p" };
qsort (as, sizeof as / sizeof *as, sizeof *as, pstrcmp_fclc);
print (as, sizeof as / sizeof *as);
}

{
char const *as[] = { "a", "z", "e", "r", "t", "y", "u", "i",
"o", "p" };
qsort (as, sizeof as / sizeof *as, sizeof *as, compare);
print (as, sizeof as / sizeof *as);
}

{
char const *as[] = { "a", "z", "e", "r", "t", "y", "u", "i",
"o", "p" };
qsort (as, sizeof as / sizeof *as, sizeof *as, pstrcmp_candide);
print (as, sizeof as / sizeof *as);
}

return 0;
}

a e i o p r t u y z
a e i o p r t u y z
a e i o p r t u y z

Process returned 0 (0x0) execution time : 0.024 s
Press any key to continue.
Antoine Leca
Le #21104201
candide écrivit :
Soit à coder une fonction de comparaison de chaînes à utiliser comme
callback par la fonction standard qsort().

La faq de fclc et de clc proposent cette implémentation :
int pstrcmp(const void *p1, const void *p2) {
return strcmp(*(char *const *) p1, *(char *const *) p2); }

Le site de ed (http://www.bien-programmer.fr/qsort.htm) propose encore
quelque chose de différent :
static int compare (void const *a, void const *b) {
/* definir des pointeurs type's et initialise's
avec les parametres */
char const *const *pa = a;
char const *const *pb = b;
/* evaluer et retourner l'etat de l'evaluation (tri croissant) */
return strcmp (*pa, *pb); }



Ce deuxième code est formellement plus restrictif : il oblige les
chaînes triées à être des chaînes à lecture seule (char const *), et
donc à passer des pointeurs vers de telles chaînes (char const * *);
techniquement le comportement peut être indéfini si les chaînes
originales n'ont pas cette propriété, comme par exemple des chaînes
littérales. À moins que ce ne soit nécessaire pour l'application
envisagée (une hypothétique machine où les chaînes const pourraient
bénéficier d'une implémentation plus rapide, via inline, de strcmp que
l'implémentation générique), je serais d'avis de supprimer cette
restriction, d'autant plus que les compilateurs sont généralement
incapables de faire l'analyse suffisante (à travers l'appel indirect et
le type intermédiaire en void*) pour signaler la différence.


Moi, j'aurais plutôt dit :
int pstrcmp(const void *p1, const void *p2) {
return strcmp(*(char const **) p1, *(char const **) p2);
}



Ta version est équivalente à celle d'Emmanuel, on peut donc y appliquer
le même commentaire sur la restriction à mon sens inutile.

Par ailleurs, le fait de court-circuiter le qualificatif const des
paramètres p1 et p2 dans le transtypage, sans commentaire pour
l'expliquer, me paraît une faute de style : c'est vrai qu'ici cela n'a
pas d'influence puisque le pointeur est immédiatement déréférencé par
l'opérateur *, donc n'est jamais modifié et par tant le code est
«correct» ; mais le mélange entre ce qualificateur et celui appliqué aux
objets triés (ici des chaînes const), avec un qualificateur enlevé et un
qualificateur ajouté, n'apparaît pas clairement et peut donc facilement
induire des erreurs de compréhension sur l'effet de ce code.


On peut utilement comparer avec deux autres versions possibles :

D'un côté
int pstrcmp(void const *a, void const *b)
{
char * const *pa = a;
char * const *pb = b;
return strcmp(*pa, *pb);
}

C'est le même code que la première version (celle de la FAQ), avec le
formalisme de la version d'Emmanuel, en passant par les initialisations
avec conversions implicites des paramètres. Un compilateur normal
devrait donner exactement le même code que pour la première version,
même avec une implémentation inline de strcmp qui distingue (de manière
magique) entre des chaînes const ou pas const (rappelez vous que le
const dans le prototype de strcmp n'a rien à voir, il sert seulement à
informer que l'implémentation de strcmp ne modifiera pas les arguments).

D'un autre côté, si on applique la même transformation au dernier code :
int pstrcmp(void const *a, void const *b)
{
char const * *pa = a;
char const * *pb = b;
return strcmp(*pa, *pb);
}
Et là, certains compilateurs vont se plaindre (parce que
l'initialisation fait disparaître l'information du qualificatif des
arguments, donc potentiellement le pointeur pa n'est plus équivalent).
Évidemment une analyse globale va faire ressortir que ce n'est pas un
problème, et c'est pour cela que le code de Candide, qui est équivalent
mais fond en une seule expression les deux opérations ici séparées de
conversion (de void* à const char**) puis de déréférence, peut ne pas
générer les mêmes avertissements.


Antoine
candide
Le #21107321
Antoine Leca a écrit :

Ce deuxième code est formellement plus restrictif : il oblige les
chaînes triées à être des chaînes à lecture seule (char const *), et
donc à passer des pointeurs vers de telles chaînes (char const * *);
techniquement le comportement peut être indéfini si les chaînes
originales n'ont pas cette propriété, comme par exemple des chaînes
littérales.



Indéfini au sens de la Norme ? Tu pourrais donner un exemple d'un tel
code stp car je vois pas trop.


[...] (rappelez vous que le
const dans le prototype de strcmp n'a rien à voir, il sert seulement à
informer que l'implémentation de strcmp ne modifiera pas les arguments).




Oui, on peut dire que je m'étais planté à cause de ça, j'ai placé mon
const en fonction des paramètres de strcmp (et aussi en me disant que
mes chaînes pouvaient être en lecture seule) ce qui en fait n'a rien à
voir. Finalement, je viens de comprendre la version de la faq, le const
est juste là pour dire que dans la fonction de comparaison ne modifie
pas le contenu du tableau d'objets à trier, ce qui est bien naturel.

Finalement, il faut rien que plusieurs années pour _vraiment_ comprendre
la fonction qsort()... Pas grave, l'espérance de vie augmente ;)




Merci de ta réponse.
Antoine Leca
Le #21110491
candide écrivit :
Antoine Leca a écrit :

Ce deuxième code est formellement plus restrictif : il oblige les
chaînes triées à être des chaînes à lecture seule (char const *), et
donc à passer des pointeurs vers de telles chaînes (char const * *);
techniquement le comportement peut être indéfini si les chaînes
originales n'ont pas cette propriété, comme par exemple des chaînes
littérales.



Indéfini au sens de la Norme ?



Oui, /undefined behaviour/ si tu préfères (moi pas ;-)).


Tu pourrais donner un exemple d'un tel code stp car je vois pas trop.



Bin non, parce que je me suis emmêlé les pinceaux :-)

En fait c'est la conversion dans l'autre sens, de const toto à toto, qui
peut induire un comportement indéfini ; dans ce sens-là il n'y a pas de
souci.


Merci d'avoir soulevé l'imprécision.

Antoine
Publicité
Poster une réponse
Anonyme