C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  STL et allocation memoire          C++Talk.NET Forum Index -> C++ (French) View previous topic :: View next topic   Author Message Gabriel Dos Reis Guest Posted: Wed Jun 09, 2004 6:28 pm    Post subject: Re: STL et allocation memoire drkm <usenet.fclcxx (AT) fgeorges (DOT) org> writes: Quote: Falk Tannhäuser <falk.tannhauser (AT) crf (DOT) canon.fr> writes: drkm wrote: Pour un std::vector, c'est le même principe, sauf qu'il maintient un tableau qui peut être plus grand que le nombre d'éléments que tu lui as ajouté. Mais les derniers éléments du tableau ne te sont pas accessibles. Lorsque tu veux ajouter un élément et qu'il n'y a plus de place, il crée un nouveau tableau, plus grand [*], y recopie tous les éléments, y ajoute le dernier, et supprime le premier tableau. [*] Tiens, j'avais lu quelque part que des tests semblaient favoriser un facteur racine de deux, qui semblait le plus approprié pour un vecteur aussi général que std::vector. Quelqu'un a-t-il plus d'infos là dessus ? C'était pas plutôt le "nombre d'or" (1 + sqrt(5.0)) / 2 soit environ 1.618 ? Je serais incapable de l'affirmer. Mais je pense qu'il s'agissait bien de la racine carrée de deux. Il s'agit bien du nombre d'or, (1 + sqrt(2))/2. Quote: Je me demande si ce n'était pas dans une partie de la doc de la GNU libstdc++, Cela m'étonnerait. -- Gaby Back to top Gabriel Dos Reis Guest Posted: Wed Jun 09, 2004 6:29 pm    Post subject: Re: STL et allocation memoire drkm <usenet.fclcxx (AT) fgeorges (DOT) org> writes: Quote: Il fallait lire « myTail », évidemment . Mon dieu ! :-) -- Gaby Back to top Gabriel Dos Reis Guest Posted: Wed Jun 09, 2004 7:06 pm    Post subject: Re: STL et allocation memoire Gabriel Dos Reis <gdr (AT) cs (DOT) tamu.edu> writes: Quote: | > C'était pas plutôt le "nombre d'or" (1 + sqrt(5.0)) / 2 soit environ 1.618 ? | | Je serais incapable de l'affirmer. Mais je pense qu'il s'agissait | bien de la racine carrée de deux. Il s'agit bien du nombre d'or, (1 + sqrt(2))/2. ^ rhaaaaa, 5. -- Gaby Back to top heinquoi Guest Posted: Wed Jun 09, 2004 9:50 pm    Post subject: STL et allocation memoire bjr, les conteneurs de la stl sont -ils definie dans le tas, sinon peut-on le faire ? j'ai fait quelques essais, et cela semble possible, du moins avec map. Pourtant, je croyait que pour utiliser new, la taille de l'objet devait etre connu, histoire de pouvoir reserver l'espace memoire. or les listes chainés et autres hormis les vector ne sont pas de taille fixe.A moins qu'il n'y ait une reallocations memoire dans le tas,pour chaque donnée suplementaires le web n'ayant pas répondu a ma question ( j'ai pt'etre pas trouvé) , infirmé ou affirmé mon hypothese, il y aurait il un 'gourou' de la STL ... La question semblera evidente à bcp, et je remercie ceux qui y répondrons cordialement H Back to top Fabien LE LEZ Guest Posted: Wed Jun 09, 2004 10:43 pm    Post subject: Re: STL et allocation memoire On Wed, 9 Jun 2004 23:50:44 +0200, "heinquoi" <nospam*heinquoi1 (AT) libertysurf (DOT) fr> wrote: Quote: Pourtant, je croyait que pour utiliser new, la taille de l'objet devait etre connu, histoire de pouvoir reserver l'espace memoire. or les listes chainés et autres hormis les vector ne sont pas de taille fixe. vector<> non plus n'est pas de taille fixe. La méthode est simple : on alloue assez de mémoire pour N éléments ; si l'utilisateur essaie d'insérer un (N+1)-ième élément, on augmente N (généralement, on le multiplie par un nombre allant de 1,4 à 2), on alloue un plus gros bloc, et on déplace les objets. Pour list<>, c'est encore plus simple : chaque élément de la liste est composé d'un objet (l'objet contenu, argument de list<>), d'un pointeur vers l'élément précédent, et d'un pointeur vers l'élément suivant. Par conséquent, une insertion consiste à allouer un nouvel élément, et de mettre à jour les pointeurs des éléments précédent et suivant. deque<> fonctionne à peu près comme vector, à ceci près qu'au lieu d'allouer un plus grand espace quand il n'y a plus de place, on alloue un nouveau bloc, ce qui évite de déplacer les éléments présents. D'après ce que j'ai compris, la cuisine interne de map<> n'est pas très éloignée de celle de list<>, à ceci près que l'ordre des éléments n'a rien à voir avec l'ordre d'insertion. -- FLL, Epagneul Breton Back to top drkm Guest Posted: Thu Jun 10, 2004 12:48 am    Post subject: Re: STL et allocation memoire "heinquoi" <nospam*heinquoi1 (AT) libertysurf (DOT) fr> writes: Quote: les conteneurs de la stl sont -ils definie dans le tas, sinon peut-on le faire ? Je ne comprend pas la question ... Mais tu peux allouer ces conteneurs sur le tas comme sur la pile. Quote: j'ai fait quelques essais, et cela semble possible, du moins avec map. Pourtant, je croyait que pour utiliser new, la taille de l'objet devait etre connu, histoire de pouvoir reserver l'espace memoire. Elle l'est. Quote: or les listes chainés et autres hormis les vector ne sont pas de taille fixe. Il faut distinguer ici deux « tailles ». La taille de l'objet collection et celle de la collection entière. Prenons une liste. Typiquement, elle maintient un pointeur sur la tête et un autre sur la queue. Elle peut maintenir une taille, aussi. Disons qu'elle ressemble à ceci : template< typename T > class Liste { Noeud< T > * myHead ; Noeud< T > * myQueue ; int myLength ; ... } ; Lorsque tu ajoutes un élément à la liste, au moyen d'une fonction membre, elle ajoute un noeud. Elle fait à ce moment une allocation mémoire pour ce nouveau noeud. Mais cette mémoire allouée ne fait pas partie de l'objet Liste lui-même. Il s'agit d'un objet Noeud<T> que la liste crée quelque part dans la mémoire. Lorsque tu crées ta liste, la taille en est connue. Car la taille de l'objet Liste est calculée sur base des deux pointeurs et de l'entier. Les noeuds eux-mêmes sont des objets distincts. Pour un std::vector, c'est le même principe, sauf qu'il maintient un tableau qui peut être plus grand que le nombre d'éléments que tu lui as ajouté. Mais les derniers éléments du tableau ne te sont pas accessibles. Lorsque tu veux ajouter un élément et qu'il n'y a plus de place, il crée un nouveau tableau, plus grand [*], y recopie tous les éléments, y ajoute le dernier, et supprime le premier tableau. [*] Tiens, j'avais lu quelque part que des tests semblaient favoriser un facteur racine de deux, qui semblait le plus approprié pour un vecteur aussi général que std::vector. Quelqu'un a-t-il plus d'infos là dessus ? Et les autres conteneurs ? Ben, laissés en exercice ... --drkm Back to top Bertrand Motuelle Guest Posted: Thu Jun 10, 2004 7:39 am    Post subject: Re: STL et allocation memoire drkm <usenet.fclcxx (AT) fgeorges (DOT) org> wrote Quote: [*] Tiens, j'avais lu quelque part que des tests semblaient favoriser un facteur racine de deux, qui semblait le plus approprié pour un vecteur aussi général que std::vector. Quelqu'un a-t-il plus d'infos là dessus ? Recherche le guru of the week #43 (Reference Counting - Part I). Je t'aurais bien envoyé l'url mais le site www.gotw.ca n'est pas très en forme ce matin... (en tout cas le facteur 1.5 vient d'un article d'Andrew Koenig parut dans JOOP il me semble). Bertrand. Back to top Falk Tannhäuser Guest Posted: Thu Jun 10, 2004 8:44 am    Post subject: Re: STL et allocation memoire drkm wrote: Quote: Pour un std::vector, c'est le même principe, sauf qu'il maintient un tableau qui peut être plus grand que le nombre d'éléments que tu lui as ajouté. Mais les derniers éléments du tableau ne te sont pas accessibles. Lorsque tu veux ajouter un élément et qu'il n'y a plus de place, il crée un nouveau tableau, plus grand [*], y recopie tous les éléments, y ajoute le dernier, et supprime le premier tableau. [*] Tiens, j'avais lu quelque part que des tests semblaient favoriser un facteur racine de deux, qui semblait le plus approprié pour un vecteur aussi général que std::vector. Quelqu'un a-t-il plus d'infos là dessus ? C'était pas plutôt le "nombre d'or" (1 + sqrt(5.0)) / 2 soit environ 1.618 ? Il y a quelque mois il y avait une discussion à ce sujet sur comp.lang.c++.moderated - je me ne souviens plus exactement de l'argumentation avancée, mais c'est lié au fait que ce nombre est la limite du rapport de deux membres consécutifs de la suite de Fibonacci. Falk Back to top drkm Guest Posted: Thu Jun 10, 2004 12:11 pm    Post subject: Re: STL et allocation memoire Falk Tannhäuser <falk.tannhauser (AT) crf (DOT) canon.fr> writes: Quote: drkm wrote: Pour un std::vector, c'est le même principe, sauf qu'il maintient un tableau qui peut être plus grand que le nombre d'éléments que tu lui as ajouté. Mais les derniers éléments du tableau ne te sont pas accessibles. Lorsque tu veux ajouter un élément et qu'il n'y a plus de place, il crée un nouveau tableau, plus grand [*], y recopie tous les éléments, y ajoute le dernier, et supprime le premier tableau. [*] Tiens, j'avais lu quelque part que des tests semblaient favoriser un facteur racine de deux, qui semblait le plus approprié pour un vecteur aussi général que std::vector. Quelqu'un a-t-il plus d'infos là dessus ? C'était pas plutôt le "nombre d'or" (1 + sqrt(5.0)) / 2 soit environ 1.618 ? Je serais incapable de l'affirmer. Mais je pense qu'il s'agissait bien de la racine carrée de deux. Je me demande si ce n'était pas dans une partie de la doc de la GNU libstdc++, mais je n'arrive pas à remettre la main dessus. Quote: Il y a quelque mois il y avait une discussion à ce sujet sur comp.lang.c++.moderated - je me ne souviens plus exactement de l'argumentation avancée, mais c'est lié au fait que ce nombre est la limite du rapport de deux membres consécutifs de la suite de Fibonacci. Il reste à déterminer la relation entre le rapport entre deux membres consécutifs de F et le rapport entre la taille avant et après réallocation de l'espace de stockage d'un std::vector . --drkm Back to top drkm Guest Posted: Thu Jun 10, 2004 12:18 pm    Post subject: Re: STL et allocation memoire drkm <usenet.fclcxx (AT) fgeorges (DOT) org> writes: Quote: template< typename T class Liste { Noeud< T > * myHead ; Noeud< T > * myQueue ; ^^^^^^^ int myLength ; ... } ; Il fallait lire « myTail », évidemment . --drkm Back to top Falk Tannhäuser Guest Posted: Thu Jun 10, 2004 1:38 pm    Post subject: Re: STL et allocation memoire drkm wrote: Quote: Falk Tannhäuser <falk.tannhauser (AT) crf (DOT) canon.fr> writes: C'était pas plutôt le "nombre d'or" (1 + sqrt(5.0)) / 2 soit environ 1.618 ? Je serais incapable de l'affirmer. Mais je pense qu'il s'agissait bien de la racine carrée de deux. Je me demande si ce n'était pas dans une partie de la doc de la GNU libstdc++, mais je n'arrive pas à remettre la main dessus. Il y a quelque mois il y avait une discussion à ce sujet sur comp.lang.c++.moderated - je me ne souviens plus exactement de l'argumentation avancée, mais c'est lié au fait que ce nombre est la limite du rapport de deux membres consécutifs de la suite de Fibonacci. Il reste à déterminer la relation entre le rapport entre deux membres consécutifs de F et le rapport entre la taille avant et après réallocation de l'espace de stockage d'un std::vector . Voir le fil de discussion commençant dans le groupe comp.lang.c++.moderated le 05/11/2003 par le message de Scott Meyers <http://groups.google.com/groups?q=g:thl3942413381d&dq=&hl=de&lr=&ie=UTF-8&selm=MPG.1a11d4f0a43bc0549896ff%40news.hevanet.com> et en particulier les réponses d'Andrew Koenig, John Potter et Risto Lankinen. En gros, avec un facteur de croissance supérieur, on ne peut jamais placer le bloc nouvellement alloué dans la zone des blocs préalablement libérés. Dans la pratique, on préfère toutefois un facteur de croissance inférieur, par exemple 1.5 -mais ça marche certainement aussi avec sqrt(2.0) :-) Falk Back to top drkm Guest Posted: Thu Jun 10, 2004 2:35 pm    Post subject: Re: STL et allocation memoire Gabriel Dos Reis <gdr (AT) cs (DOT) tamu.edu> writes: Quote: drkm <usenet.fclcxx (AT) fgeorges (DOT) org> writes: | Je serais incapable de l'affirmer. Mais je pense qu'il s'agissait | bien de la racine carrée de deux. Il s'agit bien du nombre d'or, (1 + sqrt(2))/2. | Je me demande si ce n'était pas | dans une partie de la doc de la GNU libstdc++, Cela m'étonnerait. En effet, je viens de voir qu'elle utilise un facteur 2 (du moins, en cherchant vite-fait dans les sources). --drkm Back to top Nicolas Repiquet Guest Posted: Mon Jun 14, 2004 7:38 pm    Post subject: Re: STL et allocation memoire "heinquoi" <nospam*heinquoi1 (AT) libertysurf (DOT) fr> wrote Quote: bjr, les conteneurs de la stl sont -ils definie dans le tas, sinon peut-on le faire ? j'ai fait quelques essais, et cela semble possible, du moins avec map. Pourtant, je croyait que pour utiliser new, la taille de l'objet devait etre connu, histoire de pouvoir reserver l'espace memoire. or les listes chainés et autres hormis les vector ne sont pas de taille fixe.A moins qu'il n'y ait une reallocations memoire dans le tas,pour chaque donnée suplementaires le web n'ayant pas répondu a ma question ( j'ai pt'etre pas trouvé) , infirmé ou affirmé mon hypothese, il y aurait il un 'gourou' de la STL ... La question semblera evidente à bcp, et je remercie ceux qui y répondrons cordialement H La structure du conteneur est allouée sur le tas si l'objet est créé ( new ) ou sur la pile si la variable est automatique. L'endroit où est alloué le contenu de ton container dépend de l'Allocator utilisé. Par défault, l'Allocator fourni utilise le tas. J'espère que j'ai pas dit de bêtises ! -- Nicolas Repiquet Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ (French) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.