Taille tableau dynamique

Version imprimable

01/10/2016, 22h57
Amnael

Taille tableau dynamique
Salutation,

désolé pour la question basique mais cela fait tellement longtemps que je n'ai pas touché au C que je ne sais plus trop comment m'y prendre. Je me suis un peu trop habitué au size et length de java :D

Je possède une structure
Code:

1 2 3 4 5 typedef struct frequence_element{ int element; int frequence; }frequence_element;
J'ai à coté une fonction qui va me renvoyer un tableau de cette structure

Le prototype est donc

Code:

frequence_element* init()

Après l'appel de ma fonction comment pourrais-je retrouver la taille de mon tableau de frequence élément ?

En fait, lorsque j'alloue mon tableau, je lui alloue une taille donné; mais en réalité cela ne représente que le nombre total et non le nombre effectif de ma taille du tableau.

J'aimerais donc pouvoir récupérer cette taille réelle pour éviter d'aller lire des tours de boucles inutiles..

Code:

frequence_element* tab=malloc(taille*sizeof(frequence_element));//déclaré dans init() taille représente le max que je connais dans le main et non le nb effectif de valeur réelle

Merci pour votre aide !
01/10/2016, 23h21
Pyramidev

Bonjour,

Voici ce que dit la FAQ du langage C :
« Il n'existe pas en C de fonction permettant de connaître la taille d'un tableau alloué dynamiquement, il faut donc impérativement conserver la taille de chaque tableau alloué. Une implémentation particulière peut cependant fournir une fonction permettant d'obtenir cette information (la fonction _msize sous Windows par exemple). »

Lien : http://c.developpez.com/faq/?page=L-...leau-dynamique
01/10/2016, 23h29
Amnael

Ah zut, bon au moins ça explique pourquoi je ne m'en rappelais pas :P

C'est pas très grave au pire, je peux toujours créer une seconde structure artificielle qui va stocker mon tableau + sa taille.
Sa revient à contourner le problème, mais je vois pas très bien comment faire autrement.

Merci.
02/10/2016, 01h09
foetus

Citation:

Envoyé par Amnael

une seconde structure artificielle qui va stocker mon tableau + sa taille.

Et oui ;) et en plus il te manque peut-être une capacité: parce que si tu fais un tableau vraiment dynamique (éventuellement avec realloc) il faut stocker le nombre d’éléments (sa taille ou nombre d'éléments) et son nombre maximal d'éléments (sa capacité)

Exemple d'implémentation considérant ce qui a été écrit plus haut, avec un flexible array member :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <stdlib.h> #define ATYPE char typedef struct { size_t capacity, size; ATYPE data[]; } array_t; array_t *array_alloc(size_t reserve) { array_t *a = malloc(sizeof(array_t) + reserve * sizeof(ATYPE)); if (a) { a->capacity = reserve; a->size = 0; } return a; }
Citation:

Envoyé par Amnael

C'est pas très grave au pire, je peux toujours créer une seconde structure artificielle qui va stocker mon tableau + sa taille.
Sa revient à contourner le problème, mais je vois pas très bien comment faire autrement.

Tu sais, c'est aussi ce que fait Java. ;)

Citation:

Envoyé par Amnael

C'est pas très grave au pire, je peux toujours créer une seconde structure artificielle qui va stocker mon tableau + sa taille.

Bonjour

Ce n'est pas une structure artificielle, c'est une vraie structure permettant de répondre proprement à un problème. C'est d'ailleurs ce que je fais tout le temps chaque fois que je veux gérer un truc "grossissant"

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
typedef struct {
    truc* data;
    truc* new;
    size_t nb_elem;
    size_t sz_alloc;
} t_dynamictab;
 
t_dynamictab tableau;
tableau.data=NULL;
tableau.nb_elem=0;
tableau.sz_alloc=0;
 
while (recuperation_info())
{
    // Si on a atteitn la limite allouée (ce qui arrive à la toute première itération puisque tout est à 0)
    if (tableau.nb_elem == tableau.sz_alloc)
    {
        // On agrandit la taille
        tableau.sz_alloc+=SIZE;
 
        // On réalloue de la mémoire (si la zone à réallouer est à "NULL", la réallocation se comporte comme une allocation)
        tableau.new=realloc(tableau.data, tableau.sz_alloc * sizeof(truc));
 
        // On vérifie le résultat de la réallocation
        if (tableau.new == NULL)
        {
              // Pb d'allocation à gérer - Généralement libérer la mémoire déjà allouée et sortir de l'algo
              ....
        }
 
        // La réallocaton a réussi - On récupère la zone allouée
        tableau.data=tableau.new;
    }
 
    // Ici on est certain d'avoir assez de place pour stocker l'info récupérée
    tableau.data[tableau.nb_elem]=info;
 
    // On a un élément de plus
    tableau.nb_info++;
}

Citation:

Envoyé par Amnael

Sa revient à contourner le problème,

Non, ça revient à répondre au problème

Citation:

Envoyé par Amnael

mais je vois pas très bien comment faire autrement..

Ben peut-être parce qu'il n'y a pas d'autre solution...

02/10/2016, 13h59
Amnael

Toujours aussi fan de tes réponses depuis math forum Sve@r ;)

La question est donc résolu, merci à tous.

Pour rebondir sur un point tout de même...comment peut-on savoir qu'une solution qu'on met en place règle un problème et ne fait pas que le masquer ?

Dans tous les cas finalement je vois que ça vaudrait le coup que je me fasse une petite librairie C pour régler ces problèmes de tableaux dynamique, quitte à justement implémenter manuellement certaines fonctions existant en java pour retourner les tailles justement.

Existe t-il en C le concept de généricité (pas sûr d'employer le bon terme là). J'entends par là réaliser une fonction ou une structure qui ne prendrait pas un type précis en paramètres (int, char etc etc); mais un type plus large, qui serait déterminé par la suite par les opération appliqué.

Exemple typique d'Ocaml où on a des types définis par 'a 'b etc etc qui peuvent ensuite prendre n'importe quel type.
02/10/2016, 14h23
Matt_Houston
Il faut recourir au préprocesseur pour faire de la programmation générique en C, et je te préviens de suite : c'est ni vraiment type-safe, ni vraiment sexy.

Ce que tu peux faire en premier lieu, par exemple, c'est écrire le code avec un nom de type générique (comme je l'ai fait dans mon exemple plus haut), placer le code dans array_generic.h et array_generic.impl (une sorte de .c générique) puis le spécialiser dans un couple .h / .c dédié :
Code:

1 2 3 #define ATYPE int #include "array_generic.h" #undef ATYPE
Code:

1 2 3 4 #define ATYPE int #include "array_generic.h" #include "array_generic.impl" #undef ATYPE
Il est possible ensuite de perfectionner le truc en adaptant les identifiants (de types et fonctions) au type paramètre ou même de générer du code en fonction du type paramètre. Jette un oeil à la concaténation au sein des macros et à la macro _Generic.
02/10/2016, 16h26
picodev

Bonjour,

Citation:

Envoyé par Amnael

[...]
Pour rebondir sur un point tout de même...comment peut-on savoir qu'une solution qu'on met en place règle un problème et ne fait pas que le masquer ?

Parce qu'il y a problèmes et problèmes. Il y a les problèmes qu'on résout simplement comme «je dois écrire une fonction qui me donne les nombres de fibonacci», là il y a plusieurs solutions plus ou moins efficaces. Il y a aussi les problèmes qui surviennent et qu'on essaye de résoudre ou de contourner comme par exemple «ma fonction fibo explose la pile», on la résout en changeant d'algo ou on la contourne en augmentant la taille de la pile. Il y a aussi les problèmes qu'on a pu su voir venir, «arg, je dois manipuler de très grands nombres avec ma fonction fibo», là on revoit la conception et au choix on utilise une bibliothèque d'arithmétique en précision arbitraire ou on réinvente la roue. Il y a les gros problèmes qu'on contourne par manque de temps, d'expériences ou de rigueur comme «je ne comprends pas pourquoi ça plante avec un tableau de taille 10 mais ça ne plante plus si je mets une taille à 10000».
Et finalement il y a les problèmes qui n'en sont pas comme «en java je peux avoir directement des tableaux croissant dynamiquement et j'ai un moyen de connaître leur taille, c'est un problème de ne pas pouvoir le faire en C». Ce n'est carrément pas un problème, c'est juste une différence de fonctionnalité.

Pour info, la solution classique de Svear est plus performante si au lieu d'une croissance linéaire de la capacité on implémente une croissance exponentielle (comme le fait java d'ailleurs). Cela permet de garder les mêmes compléxités temporelles pour les primitives de base.

Citation:

Envoyé par Amnael

Dans tous les cas finalement je vois que ça vaudrait le coup que je me fasse une petite librairie C pour régler ces problèmes de tableaux dynamique, quitte à justement implémenter manuellement certaines fonctions existant en java pour retourner les tailles justement.

De telles bibliothèques tierces existent déjà. Il y a comme la libapr d'Apache, la Glib de GNU, la gnulib au niveau source …

Citation:

Envoyé par Amnael

Existe t-il en C le concept de généricité (pas sûr d'employer le bon terme là). J'entends par là réaliser une fonction ou une structure qui ne prendrait pas un type précis en paramètres (int, char etc etc); mais un type plus large, qui serait déterminé par la suite par les opération appliqué.

Exemple typique d'Ocaml où on a des types définis par 'a 'b etc etc qui peuvent ensuite prendre n'importe quel type.

Oui et non. Le langage ne fournit pas un mécanisme simple pour ça. Mais tu peux utiliser les mécanismes existant pour le faire quand même, mais comme ce n'était pas prévu «au départ» ça fait toujours un peu usine à gaz et/ou un tonne de code pour ce qui serait plus simplement implémenté dans un autre langage.

Par exemple pour avoir une sorte de mécanisme d'héritage tu peux le faire avec des structs, tu peux faire ce qui ressemble à des classes aussi → regarde du côté de GObject, la base pour la GLib,GIO, GDK,GTK+.

Pour ce qui est le polymorphisme tu peux te tourner vers _Generic (C11), elle est utilisée pour implémenter tgmath (type générique math). Le compilateur clang fournit une infrastructure propriétaire pour ça aussi.

Mais au final, le plus important quand tu fais du C c'est aussi de se mettre à l'esprit C (ok bien qu'ayant évolué depuis 40 ans reste relativement bas niveau par rapport à ce qu'on a pu voir apparaître par la suite).
02/10/2016, 16h37
foetus

Citation:

Envoyé par Amnael

Existe t-il en C le concept de généricité (pas sûr d'employer le bon terme là). J'entends par là réaliser une fonction ou une structure qui ne prendrait pas un type précis en paramètres (int, char etc etc); mais un type plus large, qui serait déterminé par la suite par les opération appliqué.

Attention il faut savoir ce qu'on fait :mrgreen: :mrgreen: avec un type void*.

Et avec les P.O.D. (int, char, short, ...) tu ne crées pas de pointeur mais tu mets la valeur directement puisque sizeof(void*) c'est soit 32 soit 64 ~~octets~~ bits.

Édit: Merci Médinoc :kiss: Parce que 32 octets cela en fait pour une super précision
03/10/2016, 11h52
Médinoc

Citation:

Envoyé par foetus

Attention il faut savoir ce qu'on fait :mrgreen: :mrgreen: avec un type void*.

Et avec les P.O.D. (int, char, short, ...) tu ne crées pas de pointeur mais tu mets la valeur directement puisque sizeof(void*) c'est soit 32 soit 64 octets.

Tu veux dire 32 ou 64 bits, et si tu veux trifouiller avec ça tu as plutôt intérêt à passer par des intptr_t (d'ailleurs, le standard manque cruellement de longptr_t ou longlongptr_t...).

Au point où on en est, autant passer par des variants (ou sous Windows, par des tableaux et des variants COM, qui ont déjà fait ça pour toi).
03/10/2016, 12h50
foetus
En regardant sur Internet, que ce soit intptr_t ou les variants COM, on introduit une dépendance :whistle:

Une probable meilleure solution portable:
Code:

1 2 3 4 union generic_type { int integer; void* pointer; }
03/10/2016, 14h12
Médinoc

Que veux-tu dire par là? Que intptr_t n'est pas C90? Pourtant Microsoft le supporte...
03/10/2016, 14h58
foetus

Citation:

Envoyé par Médinoc

Que veux-tu dire par là? Que intptr_t n'est pas C90? Pourtant Microsoft le supporte...

:mrgreen: C'est C99 et effectivement Visual 2010 le supporte (mais je n'ai pas testé réellement)

Je donne une possibilité 100% portable et donc tu comprends tout de suite le truc en lisant :mrgreen:
On peut peut-être remplacer le int par un long pour ne pas perdre en mémoire et avoir éventuellement un entier sur 64bits en 64bits.

Parce que le nouveaux types (intptr_t, uintptr_t, ptrdiff_t ... size_t c'est différent) c'est mignon mais même en lisant la documentation tu ne sais pas trop comment les utiliser (tu piges le truc mais pas à 100%) :koi:

Parce que "intptr_t: integer type capable of holding a pointer " :mrgreen: alors que moi je parlais de mettre un P.O.D. dans un pointer void*
03/10/2016, 15h09
Matt_Houston
Citation:

Envoyé par foetus

je parlais de mettre un P.O.D. dans un pointer void*
Code:

1 2 3 4 5 6 7 8 void bar(void *args) { printf("%f\n", (float)args); } void foo() { float a = 42.f; bar((void *)a); }
Comme ceci ? Comportement indéterminé AMHA.
03/10/2016, 15h23
picodev

C'est carrément interdit par la norme :
6.5.4 Cast operators section 4 : «A pointer type shall not be converted to any floating type. A floating type shall not be converted to any pointer type.»

Caster un pointeur vers autre chose qu'un entier ou un pointeur est explicitement cité comme un UB par la norme dans l'annexe J2 «A pointer is converted to other than an integer or pointer type ».

Comme par défaut la norme n'indique pas qu'il puisse/doive exister un type entier capable de supporter une adresse (on caste un pointeur sur void vers un entier puis on recaste cet entier vers un pointeur sur void, cette opération donnant le même pointeur) elle définit un type optionnel qui s'il existe possède cette propriété. La norme prévoit aussi le cas où tous les pointeurs n'auraient pas la même taille …

Norme C11 → http://www.compsci.hunter.cuny.edu/~...11standard.pdf
03/10/2016, 15h30
foetus
Citation:

Envoyé par Matt_Houston

Comme ceci ? Comportement indéterminé AMHA.

Non comme cela : :mrgreen:
Code:

1 2 3 void* my_generic_array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int indice = my_generic_array[5];
Parce que, mine de rien (et picodev a répondu à cette question), la conversion flottant <-> void* cela ne doit pas fonctionner :koi: :koi: parce cela déborde de 32 bits (après rapide vérification float 4octets, double 8, long double 10)
03/10/2016, 15h37
picodev
Citation:
Envoyé par foetus

Non comme cela : :mrgreen:

Code:

1 2 3 void* my_generic_array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int indice = my_generic_array[5];
Mauvaise idée … pourra éventuellement fonctionner mais uniquement avec des entiers (et pas tous, aucune garantie) et des pointeurs. La mauvais idée étant d'utiliser void * comme un conteneur de valeurs ne représentant pas des adresses valides.

Il ne faut faire aucune hypothèses sur la taille des types. Même un long double peut ne pas avoir la même taille d'une plateforme à l'autre ni la même précision.
03/10/2016, 15h50
foetus
C'est pour cela que 6 posts plus haut, je propose un union :mrgreen: :mrgreen: ;)
Code:

1 2 3 4 union generic_type { int integer; // or long void* pointer; }
03/10/2016, 16h04
picodev

Ce qui est parfait si pointer contient bel et bien un pointeur sur une valeur et non une valeur numérique qui n'est pas un pointeur valide.