creation d'un tableau de taille augmentant a chaque iteration d'une boucle

Question

Salut,
J'ai besoin de creer un tableau de taille variable... dt la taille n'est pas connue d'avance (d'ou le pb avec malloc).
En fait, j'ai une boucle qui calcule des distances entre des chaines de caracteres, et chaque fois qu'on tombe sur une distance inferieure a un seuil, je veux stocker le resultat ds un tableau de resultats... mais je ne peux pas creer un tableau de taille fixe car il risque de bouffer trop de memoire pour pas grand chose et avec malloc je suis oblige de connaitre le nombre de resultats a l'avance pour alloer la memeoire...
Si qq1 a une idee, ca m'aiderai bien ;)
A+
Rom1 (#2 puisqu' y a deja un #1)

cs_djl · Answer

utilise une liste ou alloue ton tableau a une taille maximale  pouvant etre atteinte et resize (realloc) apres la boucle

cs_rom12 · Answer

comment je fais avec une liste?

cs_djl · Answer

en gros

typedef struct _list
{
       int value;

       struct _list *next;
       struct _list *cur;
       struct _list *prev;

} List;

List liste;

liste.prev = NULL;
liste.cur = &liste;

for( ... )
{
     liste.cur->value = ...

     liste.cur->next = malloc( sizeof *liste );
     liste.cur->next->prev = liste.cur;
     liste.cur = liste.cur->next;
}

mais c'est a verifier

cs_rom12 · Answer

merci, je v essayer de suite.

jpthomasset · Answer

Salut,

Jette aussi un oeil sur le template vector dans la STL...

A+,
JP.

cs_djl · Answer

deja une rectif

liste.cur->next = malloc( sizeof liste ); au lieu de 
liste.cur->next = malloc( sizeof *liste );

leprov · Answer

et si tu es en C (et que dc tu n'as pas les vectors), tu peux les réecrire grossièrement pou le type pour lequel tu as besoin de faire ca (voila en gros ce qu'il faut faire)

struct vector
{
       int taille;
       int capacite;
       type * tableau [];
}

ensuite tu fais tes fonctions qui soient telles que tu puisse ajouter un élement au tableau, ce qui va augmenter la taille du tableau, et si besoin la capacité. pour augmenter la capacité, déclare un tableau de capacité + 8 (en c++ pour les vectors les granules mémoires sont de 8, je suppose dc ke cest intelligement choisi), recopie l'ancien tableau, ds ce nouveau tableau, free l'autre, et réalloue ton pointeur sur ce nouveau tableau. ensuite fait les fonctions de bases dont tu auras besoin, genre accesseur etc.... ca sera pas forcement tres tres propre ds l'ecriture, mais ca sera simple d'utilisation, et si ton tableau doit devenir tres gros au final, ca bouffera moins de memoire qu'une liste. et les performances seront probablement meilleures.

magic_Nono · Answer

avec realloc, comme l'ont dit les autres, je n'en ai po trouvé d'équivalent si on utilise les new....

exemple de liste gérées ainsi : BListeDir & BListeIndir
et les stl, bien sur

++
Magic Nono: l'informagicien! 8-)

cs_djl · Answer

l'equivalent reallloc en c++ c'est std::vector

en c++, pour les listes, utilise std::vector ou std::list

cs_djl · Answer

leprov > il me semble que les vector sont implementer sous formes de cellules liées, justement pour ne pas avoir a faire ssytemetiquement des recopie de buffer (ca peut etre le probleme de realloc)

leprov · Answer

bah t'évite les recopie de buffer dans ce cas, d'accord, mais tu perd du temps a tous les accès a reparcourir a partir d'un élement (courant ou dernier ou premier, va savoir).....ca serais un compromis.
donc on a une taille et une capacité avec des ganules memoires de 8 pour ne faire des realloc que tous les 8 ajouts d'élément, c'est a ca que sert la capacité, et a ca que sevent les granules. enfin du moins il me semble, je peux aussi me tromper....(je sais pas si ce que j'ai dis est tres clait pr tt le monde, j'espere...).

cs_djl · Answer

ta raison faut verifier ca en profondeur

juste que dans ce cas la 

for(  /* 2500000 iteration */ ) v.push_back( ... );

tu imagines le nombre de copies ?

au niveaux des acces, pas la peine de caché que vector est bien plus long qu'un tableau

leprov · Answer

bah ca fait 2 500 000/8 copies, et si tu veux accéder au dernier élément du tableau il faudrait que tu parcours tte ta liste, alors que ds le cas d'un tableau c'est uniquement un décalage d'adresses. c'est vrai que les 2 idées se défendent, mais explique moi l'utilité de la capacité si on a une liste......et pr les strings ca serait des listes aussi? non, moi il me semble bien que c'est des tableaux

magic_Nono · Answer

ouep, G failli répondre que GT po convaincu au niveau perf.... & facilité....

Magic Nono: l'informagicien! 8-)

cs_djl · Answer

pas forcement comme une liste, je verifie

leprov · Answer

et ds le cas que tu propose, t'imagine le temps de libération de la mémoire? c'est encore une fois le tableau le plus rapide des deux....

leprov · Answer

et pense aux iterators. lorsque la capacité est modifiée, tous les iterators déja existants sont invalidés....pourquoi? parce que la tableau a changé de "position" en mémoire.....si tu avais une liste, les itérators ne seraient pas invalidés

cs_djl · Answer

ouai j'imagine

en fait ta raison, c'est bien  un buffer ou les données son contigues, le buffer à une capacité max  et size inferieur, et seul les elements < size sont construit,  quand on push_back ca appel le constructeur du suivant

cs_djl · Answer

le probleme c'est que c'est pas facile à lire comme hierarchie de classe

cs_djl · Answer

ca n'empeche que le schmilblick rend les accés trop long, d'ailleur c'est spécifié
"Use STL to build containers when number of objects is unknown; use static array or buffer when number is known"

leprov · Answer

chui pas tt a fait d'accord. accès longs? tant que ca? si tu connais la taille de ton tableau t'as la fonction reserve() qui alloue a ton tableau la taille voulue, apres les accès sont pas vraiment plus longs. a priori ton acces va etre un truc genre en inline : 
return *tableau [i]; pour ton accès en lecture, et pour l'écriture, ca va etre la meme chose avec juste une vérif que capacity > size, et pis c'est tt.
donc a priori, tu va perdre quelques rares cycles machines pour tester ca, et c'est tout. donc a partir de la il faut savoir si tu vise la performance, ou si tu vise le confort.....

cs_djl · Answer

a chaque debordement de capacité reallocation du double, ca peux devenir genant en terme d'espace occupé

cs_djl · Answer

justement, c'est que je dis, le but premier de vector c'est la facilité d'uttilisation, l'aspect fonctionnel et la securité, tout est codé de facon tres optimisé mais on aura jamais les  performances d'un buffer en acces

leprov · Answer

réallocation du double? en principe c'est juste recopie dans un tableau pouvant contenir 8 éléments de plus que celui actuel il me semble. a vérifier, certes, mais il me semble. tente de faire un vector rempli de par exemple 5000 elements et fait un truc genre 
cout << V.size() <<  ' ' << V.capacity();
(je peux pas tester, a pas compilo sous la main....)

et c'est vrai qu'on aura pas les perf d'un tableau réel, mais en meme temps, passe un tableau multidimensionnel en parametres d'une fonction.....et regarde la différence avec un vector......meme un tableau unidimensionnel c'est la mort a passer en parametres.

cs_djl · Answer

ben si, tu le passe par reference

pour capacity et size je verifi

leprov · Answer

ouais c'est pas la question de le passer.
void fonction (int tableau [])
{
   cout << tableau [5];
}

int main (void)
{
    int tableau [5];
    fonction (tableau[]);
    return 0;
}

fantastique ca marche.........

et pour les tableaux multidimensionnels, c'est tres gai, tu peux passer que des tableaux dont la deuxieme dimension est de taille constante, donc ta fonction n'est applicable qu'a un tableau, si tu dois faire le meme traitement avec 3 tableaux dont la seconde dimension est de taille différente pour chaque tableau, t'as gagné le droit de réecrire trois fonctions, ou de feinter avec un truc de merde.........pas de pbs avec les vectors...

leprov · Answer

et ca parce que le compilo sera pas d'accord si tu passe un tableau bidimensionnel sans lui passer la taille de la seconde dimension (ex : le parametre int tableau [][] ne passe pas alors que int tableau [][3] passe a la compilation)

cs_djl · Answer

je suis d'accord, je repete, quand la taille est connue ou fixe, pas vector

pour les impresions ca donne ca, ce qui verifie qu'il reallouebien le double à chaque fois

1 1
2 2
3 4
4 4
5 8
6 8
7 8
8 8
9 16
10 16
11 16
12 16
13 16
14 16
15 16
16 16
17 32
18 32
19 32
20 32
21 32
22 32
23 32
24 32
25 32
26 32
27 32
28 32
29 32
30 32
31 32
32 32
33 64
34 64
35 64
36 64
37 64

je suis d'accord avec tout ce que tu dis, pas la peine de transformer ce topic en un debat steril ;)

int func( (&tab)[][MAX] ) c'est mieux

cs_djl · Answer

j'utilise moi meme std::vector des que j'en ai l'occasion, ca simplifie enorment le code

leprov · Answer

effectivement pr les realloc, merci pr cette verif. 
et pr les tableaux.............des ke jen ai un a passer en param, j'evite de les utiliser et je passe aux vectors paske c'est la mort, ou alors a la rigueur
int func (int tableau [][MAX], int tailleX, int tailleY), mais ta solution est pas terrible, tu as pas la taille de ton tableau...sur ce, il est vrai qu'un debat "tableau VS vector : ready, fight!" sera pas super utile, avec ce qui a été dit les gens pourront se faire leur propre opinion s'ils passent ici.......
pour les reallocation, il me semblait pourtant avoir deja fait le test avec gcc, et qu'on avait des granules memoires de 8, je verifierais plus tard pour voir si c'est implémenté differement ou si je me suis tapé une hallu, et je reposterais pr dire (dici deux ou trois jours, pas avant)

cs_djl · Answer

pour info j'ai tester avec gcc version 3.2 (mingw special 20020817-1)

leprov · Answer

oki......metonne tt ca. bon bah javais du me taper un hallu....merci djl pr ces precisions

cs_djl · Answer

c'est moi qui te remerci, jusqu'ici je croyais qu'un vector c'etait une liste o_O

Creation d'un tableau de taille augmentant a chaque iteration d'une boucle

33 réponses

Votre réponse

Discussions similaires