realloc ? - Page 1

Pour l'IUT, on doit faire un programme où l'espace mémoire utilisé varie au cours du programme. On fait ça en C++.
Donc, la méthode brute serait de faire un realloc : lorsqu'on a besoin d'agrandir l'espace utilisé, on alloue un bloc de taille plus grande que l'actuel, dans lequel on recopie le contenu du bloc actuel, puis on libère le bloc actuel et on utilise le nouveau bloc comme bloc actuel.

Mais je pense que ce serait mieux si au lieu de ça, à chaque fois que j'ai besoin d'agrandir mon bloc, j'alloue un nouveau bloc d'une taille moyenne, assez petite, et je l'utilise comme s'il était contigu au précédent. Mais pour gérer ça, pour l'instant la seule solution à laquelle j'ai pensé est de faire une liste chainée de blocs de mémoire, et en fonction de l'endroit auquel je veux accéder du grand bloc virtuel constitué par tous ces blocs, je sélectionne le bloc que je veux dans ma liste chainée. Il y a plus simple ?

1. C++ => Utilise stl::vector.
2. "on alloue un bloc de taille plus grande que l'actuel, dans lequel on recopie le contenu du bloc actuel, puis on libère le bloc actuel et on utilise le nouveau bloc comme bloc actuel." Faux une implantation normale de realloc regarde d'abord si elle ne peut pas etendre ton premier malloc sans a avoir a recopier. Si tu fais peu d'allocation memoire c'est souvent le cas.
3. "plus simple". Ca depend. C'est quoi les operations sur ton bloc ?

1. Non, il faut qu'on code ça nous même je pense.
2. Oui, tu as raison, mais je ne sais pas comment faire ça en C++.
3. Je l'utilise comme un tableau.

PpHd
: Faux une implantation normale

Je dirais plutôt "une bonne implantation" (glibc par exemple). Le cas "normal" est plutôt de tout copier à chaque fois malheureusement. Regarde les realloc des *BSD...

Pour sélectionner le bloc que tu veux dans la liste chaînée, t'es obligé de la parcourir ? Pas très efficace.

Pourquoi une liste chaînée ? Un simple tableau ne suffit pas ?
Tu l'agrandis avec la méthode 1

PpHd
: regarde d'abord si elle ne peut pas etendre ton premier malloc sans a avoir a recopier. Si tu fais peu d'allocation memoire c'est souvent le cas.

C'est pas toujours le cas avec une MMU ?

Sasume
: 2. Oui, tu as raison, mais je ne sais pas comment faire ça en C++.

#include <cstdlib>
using std::malloc;
using std::realloc;
using std::free;

Mouais, mais là je ne fais rien.
Je pense qu'ils veulent qu'on fasse nous-même cette gestion de mémoire.

./4: Moi j'appelle ca une MAUVAISE implantation. Meme AMS fait mieux.
./5: Non, c'est pas si simple.

Sinon tu peux faire un systeme de realloc progressif.

current += n
if (current > max)
 {
   max = min (2* current, current + 1000000)
   r = realloc (current, max),
 }

vi, il vaut mieux faire un truc "progressif" (sinon pour des gros fichiers tu vas te retrouver à passer la plupart du temps de l'algo à faire tes realloc() )

Soit dit en passant que même si l'implémentation est pourrie (recopie systématique), avec un tel truc progressif le surcoût de réallocation n'augmente pas avec la taille du fichier, donc la différence sera minime. Le seul inconvénient étant l'occupation mémoire (ton buffer aura des chances d'être 2x trop gros), mais tu peux aussi faire "max = current + (current>>2) + 1000;" si tu veux vraiment économiser au maximum la mémoire (à noter que dans ce cas là, le temps passé à réallouer sera 4x plus gros : mais il y a des chances qu'il reste très largement négligeable)

Si tu n'as pas le droits aux containers et sans utiliser realloc, tu créé un nouvel espace et tu utilises l'algo copy

template
T *resize(T *array, size_t old_size, size_t new_size)
{
T *temp = new T[new_size];
delete [] array;
return std::copy(array, array + old_size, temp);
}

Mais bon ...

delete [] array;
return std::copy(array, array + old_size, temp);

J'ai comme un doute


Et sinon, std::copy est équivalent à memcpy, non?

ouep pour le memcpy
et teste pour le reste

Je ne dis pas que "en pratique" ça ne marchera pas, mais je dis qu'il y aura de (nombreuses) plateformes et configurations pour lesquelles ça ne marchera pas... Tu n'as en principe pas le droit d'utiliser "array" après l'avoir libéré, même si c juste la ligne d'après ^^

Je ne dis pas que "en pratique" ça ne marchera pas, mais je dis qu'il y aura de (nombreuses) plateformes et configurations pour lesquelles ça ne marchera pas... Tu n'as en principe pas le droit d'utiliser "array" après l'avoir libéré, même si c juste la ligne d'après ^^

sur TI ça ne marcherait pas, par exemple ^^

Si, je crois que ça peut marcher si "array" a un trou (au lieu d'un bloc alloué) à sa gauche...

[cross] oki pollux

1. Non, il faut qu'on code ça nous même je pense.

Ben faudrait leur demander, parce que les STL sont quand meme un truc standard de C++.
Perso, je dirais que l'un des gros apports du c++ par rapport au c, c'est la possibilité d'utiliser std::string et compagnie. (l'autre étant évidemment les classes)

Je sais pas, mais utiliser *alloc dans un programme en c++, c'est la dernière chose que je ferais.

Je pense que leur but n'est pas de programmer en C++ pour l'instant, mais de bien comprendre les concepts d'allocation mémoire. Mais c'est vrai que ça porterait moins à confusion si ces choses-là étaient faites en C pur

Bah, généralement, c'est ce qu'on fait ... nous en tout cas (même si ca sucks grave !)

$ pollux, je vois pas pkoi ca marcherais uniquement si le bloc précédent es libre, tu peux expliquer ?

Mais en fait, je ne sais pas trop ce qu'ils veulent de nous.
En cours, ils n'ont pas introduit les primitives *alloc du C, donc je suppose qu'ils veulent qu'on fasse sans.
On n'a vu que new et delete, donc il faut qu'on fasse avec.
Mais d'habitude ils nous prennent complètement pas la main pour ce genre de boulot et là pas du tout, donc je doute qu'il faille faire des trucs très recherchés (sinon ils nous auraient encore pris par la main), donc peut-être qu'ils pensent à ce qu'on utilise des new pour obtenir des blocs de plus en plus gros et qu'on recopie l'ancien bloc dedans...
Je leur demanderai plus tard, parce que je ne comprends pas jusqu'où ils veulent qu'on aille.
Ça m'étonnerait vraiment beaucoup qu'ils veuillent qu'on fasse la méthode 2 que j'ai décrite au post de départ parce qu'ils nous auraient tout détaillé étape par étape si ça avait été le cas.

En plus, le bloc de mémoire, on est censés l'utiliser pour faire une liste chainée, alors qu'en cours, ils n'ont montré qu'une représentation avec une allocation par cellule, pas avec un gros tableau. Et dans le sujet, ils disent qu'on a vu une représentation avec un tableau.
Donc je ne comprends vraiment pas de quoi ils parlent.
Je ne sais pas s'ils veulent qu'on utilise la méthode bête et brute de tout décaler dans le tableau à chaque fois qu'on insère/supprime un élément ou bien qu'on utilise une méthode plus sophistiquée, mais là encore, ça m'étonnerait parce qu'ils nous auraient pris par la main si ça avait été le cas...

$ pollux, je vois pas pkoi ca marcherais uniquement si le bloc précédent es libre, tu peux expliquer ?

un bloc plein est précédé par un word indiquant sa taille (ce qui permet d'aller au bloc suivant)
quand le bloc est effacé, le word qui indiquait sa taille est mis à 0.
sa taille est reportée dans le word suivant, et juste après y a l'adresse du bloc libre suivant (ça explique pourquoi un handle fait au moins 6o)

ah j'oubliais, si le bloc précédent est vide, le tios aggrandit le bloc vide qui précède afin d'en faire un plus grand (d'où la remarque de pollux)

nEUrOO
:Bah, généralement, c'est ce qu'on fait ... nous en tout cas (même si ca sucks grave !)

Je crois que tu as gagné le droit d'aller engueuler ton prof, parce que c'est complètement fumé
On vous a dit aussi de ne surtout pas vérifier si le buffer était assez grand avant de faire un strcpy() ?

$ pollux, je vois pas pkoi ca marcherais uniquement si le bloc précédent es libre, tu peux expliquer ?

Dès la libération du bloc, le TIOS stoque des informations sur la longueur du "trou" ainsi créé dans le heap. Ma remarque sur le cas où il n'y a pas création d'un nouveau trou n'était là que pour dire que ça dépend de plein de facteurs "aléatoires" et que donc c'est d'autant plus casse-gueule... (suppositions invalides sur le comportement "normal" de la fonction)

Inutile de préciser que le comportement du TIOS respecte parfaitement les standards sur ce point.


Sasume> si tu réalloues ton tableau en multipliant sa taille par une constante (plutôt que d'ajouter une constante), le fait d'utiliser new/copy/delete n'est pas problématique et ne devrait pas faire ramer (comme je l'ai dit dans ./9). Par contre, ça va très très vite ramer si tu réalloues à chaque nouveau caractères (temps proportionnel au carré du nb d'éléments )

Pollux
:

nEUrOO
: Bah, généralement, c'est ce qu'on fait ... nous en tout cas (même si ca sucks grave !)

Je crois que tu as gagné le droit d'aller engueuler ton prof, parce que c'est complètement fumé
On vous a dit aussi de ne surtout pas vérifier si le buffer était assez grand avant de faire un strcpy() ?

D'apprendre le C pour les structures de données avant de passer au C++ ...

Mais, et alors ? C'est vachement important de bien comprendre le concept de durée de vie d'une variable/d'un espace de stockage, surtout en C++ ! (qui n'est pas garbage-collecté, hein) Non seulement c'est possible d'utiliser une gestion bas niveau de la mémoire en C++ (delete ptr), mais en plus même si tu utilises une gestion de plus haut niveau, le même problème se pose encore : si tu as un map<int,int>::iterator i, alors tu peux pas te permettre de faire "vect.delete(i); return *i;" non plus

Si on vous apprend vraiment à faire ça, votre prof est complètement à côté de ses pompes...

On apprend pas a faire ca ... on apprend pas le C++ d'où mon "sucks"

c'est pas un pb de c++, c'est un pb de programmation. Quel que soit le langage, retourner une référence (au sens français, pas au sens c++) à un objet détruit est un bug. Qu'il se manifeste ou pas n'est pas la question.

Sasume>fait une liste chainé.

Je n'ai pas le temps de bien lire les reponses déjà postées, donc ça a déjà peut etre été proposé, mais le plus simple à mon avis c'est de faire une classe avec un tableau dynamique dedans d'une taille multiple de N.
Tu te fais une methode *push_back* qui vérifie si tu as encore de la place. => A chaque fois que tu dépasse, tu réalloues N octets suplementaires.
Comme ça tu ne réalloues pas trop souvent.