C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  std::map : à quel moment les iterateur sont invalidés ?          C++Talk.NET Forum Index -> C++ (French) View previous topic :: View next topic   Author Message Nicolas Castagne Guest Posted: Fri Apr 15, 2005 9:04 am    Post subject: std::map : à quel moment les iterateur sont invalidés ? Bonjour à tous, dans mon appli, j'ai besoin à la fois de : 1 - accéder rapidement à des entités (classe Entite) par nom (string - le nom est unique) 2 - récupérer le nom de ces entités lorsque je manipule une Entitie Le 1- tend à ce qu'une std::map soit utilisée, par exemple : map<const string , Entite*, ltstr> nameSpace; Le 2- tend à ce que le nom soit stoqué dans les objets Entite, par exemple : class Entite { string name; ... } Mais dans ce cas, il y a la duplication de donnée. Mon programme est ammené à manipuler un grand nombre d'entité, et par suite un grand nombre de noms. Les noms peuvent être longs. Je cherche donc à optimiser ces deux actions, sans dupliquer l'info. Une solution consisterait à stoquer dans Entite un iterator sur la map : class Entite { map<string, Entite *>::iterator name; ... } Dans la STL de SGI, cela semble possible, puique la doc de stl::map précise : Quote: Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. (from : http://www.sgi.com/tech/stl/Map.html ) J'ai essayé avec la map de std... mais ca semble ne pas fonctionner. Aucune des docs que j'ai lu qui présentent std::map ne présente d'information quant aux conditions dans lesquelles un iterator sur une std::map devient invalide. Qu'est-ce qu'en est-il exactement ? Y a t il une différence sur l'invalidation des itérator pour les map entre la stl de SGI et std ? Plus généralement, quel solution de conception 'typique' proposeriez vous pour traiter ce problème, à savoir : optimiser à la fois l'accès par nom à une entité et l'accès au nom d'une entité donnée, sans dupliquer les données ? Merci d'avance !!! Nicolas Back to top adebaene@club-internet.fr Guest Posted: Fri Apr 15, 2005 11:55 am    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? Nicolas Castagne wrote: Quote: Bonjour à tous, dans mon appli, j'ai besoin à la fois de : 1 - accéder rapidement à des entités (classe Entite) par nom (string - le nom est unique) 2 - récupérer le nom de ces entités lorsque je manipule une Entitie Le 1- tend à ce qu'une std::map soit utilisée, par exemple : map<const string , Entite*, ltstr> nameSpace; Ou plutôt std::map<std::string, Entite> (le const est inutile sur la clé, et à moins d'avoir une bonne raison de faire autrement, autant stocker directement les objets dans le conteneur, ca évite de devoir te coltiner la gestion de la mémoire à la main). Quote: Dans la STL de SGI, cela semble possible, puique la doc de stl::map précise : Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. (from : http://www.sgi.com/tech/stl/Map.html ) C'est une garantie donnée par la norme, et que toute implémentation doit respecter. Sur quelle implémentation as tu observé un comportement différent? Arnaud Back to top Nicolas Castagne Guest Posted: Fri Apr 15, 2005 12:07 pm    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? Salut tous, salut Arnaud, [email]adebaene (AT) club-internet (DOT) fr[/email] a écrit : Quote: C'est une garantie donnée par la norme, et que toute implémentation doit respecter. Sur quelle implémentation as tu observé un comportement différent? Sur std de gcc, Linux, RedHat Enterprise. Rien que du très commun. Es-tu sur que la norme relative aux conteneurs de la librairie standard std garantisse la non-invalidation des iterator des map en cas d'ajout et de suppression ? Parce que la STL de SGI le garantit, mais ce n'est pas une 'norme'... A priori, sauf erreur, rien n'indique que std respectent les choix fait pour la STL. Aurais-tu un pointeur sur la 'norme' à laquelle tu fais référence ? Sinon, bien sur, il est possible que ma série de tests soit bugguée. Je vais verifier ça. Nico Sinon... Quote: Nicolas Castagne wrote: ... Ou plutôt std::map oué c'était une erreur Quote: Dans la STL de SGI, cela semble possible, puique la doc de stl::map précise : Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. (from : http://www.sgi.com/tech/stl/Map.html ) C'est une garantie donnée par la norme, et que toute implémentation doit respecter. Sur quelle implémentation as tu observé un comportement différent? Arnaud Back to top Nicolas Castagne Guest Posted: Fri Apr 15, 2005 4:54 pm    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? J'ai refait mes tests, puis inclu ça dans le programme, et tout semble se passer correctement. Merci, donc ! (au cas où, je suis toujours preneur d'info sur les liens entre les specifs des conteneurs de la std et celles de la stl !) Nico Nicolas Castagne a écrit : Quote: Salut tous, salut Arnaud, [email]adebaene (AT) club-internet (DOT) fr[/email] a écrit : C'est une garantie donnée par la norme, et que toute implémentation doit respecter. Sur quelle implémentation as tu observé un comportement différent? Sur std de gcc, Linux, RedHat Enterprise. Rien que du très commun. Es-tu sur que la norme relative aux conteneurs de la librairie standard std garantisse la non-invalidation des iterator des map en cas d'ajout et de suppression ? Parce que la STL de SGI le garantit, mais ce n'est pas une 'norme'... A priori, sauf erreur, rien n'indique que std respectent les choix fait pour la STL. Aurais-tu un pointeur sur la 'norme' à laquelle tu fais référence ? Sinon, bien sur, il est possible que ma série de tests soit bugguée. Je vais verifier ça. Nico Sinon... Nicolas Castagne wrote: ... Ou plutôt std::map oué c'était une erreur :) Dans la STL de SGI, cela semble possible, puique la doc de stl::map précise : Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. (from : http://www.sgi.com/tech/stl/Map.html ) C'est une garantie donnée par la norme, et que toute implémentation doit respecter. Sur quelle implémentation as tu observé un comportement différent? Arnaud Back to top Arnaud Debaene Guest Posted: Fri Apr 15, 2005 6:21 pm    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? Nicolas Castagne wrote: Quote: Aurais-tu un pointeur sur la 'norme' à laquelle tu fais référence ? La norme ISO elle-même : 23.1.2/8 : [A propos des conteneurs associatifs] : The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements. Un bon bouqin de référence sur le sujet est le Josuttis Arnaud Back to top James Kanze Guest Posted: Sat Apr 16, 2005 10:09 am    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? Nicolas Castagne wrote: Quote: dans mon appli, j'ai besoin à la fois de : 1 - accéder rapidement à des entités (classe Entite) par nom (string - le nom est unique) 2 - récupérer le nom de ces entités lorsque je manipule une Entitie Le 1- tend à ce qu'une std::map soit utilisée, par exemple : map<const string , Entite*, ltstr> nameSpace; Le 2- tend à ce que le nom soit stoqué dans les objets Entite, par exemple : class Entite { string name; ... } Mais dans ce cas, il y a la duplication de donnée. Mon programme est ammené à manipuler un grand nombre d'entité, et par suite un grand nombre de noms. Les noms peuvent être longs. Je cherche donc à optimiser ces deux actions, sans dupliquer l'info. La solution « consacrée », c'est d'utiliser un std::set< Entite, EntityNameComparer >, avec le code dans EntityNameComparer qui va bien. Cette solution est préconcisée par plusieurs experts, même dans le cas où on veut pouvoir modifier les autres champs des éléments (ce qui implique un const_cast, parce que std::set ne va te donner que des références const aux éléments). Si je mets le mot « consacrée » en guillemets, c'est que je ne suis pas complètement convaincu moi-même. Formellement, la façon correcte de modifier un élément d'un set, c'est de l'extraire, le modifier, puis de le réinsérer. Dans toutes les applications que j'ai eu jusqu'ici, c'était aussi une façon acceptable, y compris de point de vue des performances. (C'était même souvent la seule solution valable, parce que mes modifications portaient sur la clé.) Un autre alternatif serait std::map< std::string const*, Entite*, ComparePointedTo >, avec des pointeurs. Et évidemment, tu t'arranges pour que la clé pointe à la chaîne dans Entite. Ça marche, mais ça introduit un problème de gestion de la durée de vie. En revanche, si les objets de type Entite ont de toute façon leur propre durée de vie, c'est une solution simple et efficace. Quote: Plus généralement, quel solution de conception 'typique' proposeriez vous pour traiter ce problème, à savoir : optimiser à la fois l'accès par nom à une entité et l'accès au nom d'une entité donnée, sans dupliquer les données ? La plupart du temps, la duplication de la chaîne ne m'a pas posé de problème. Donc, std::map< std::string, Entite > avec aussi la chaîne dans Entite. (Mais même quand la duplication en soi n'est pas un problème, ça peut poser des problèmes de cohérence -- il n'y a rien formellement qui empèche une différence entre la chaîne clé et la chaîne dans Entite.) -- James Kanze mailto: [email]james.kanze (AT) free (DOT) fr[/email] Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34 Back to top Ahmed MOHAMED ALI Guest Posted: Mon Apr 18, 2005 6:02 am    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? Bonjour, Quote: Je cherche donc à optimiser ces deux actions, sans dupliquer l'info. Une solution consisterait à stoquer dans Entite un iterator sur la map : class Entite { map<string, Entite *>::iterator name; ... } Quote: J'ai refait mes tests, puis inclu ça dans le programme, et tout semble se passer correctement. Merci, donc ! Bien que fonctionnelle, je voudrai juste attirer ton attention sur le fait que cette solution introduit un couplage entre le type stocké et le type de conteneur. En effet, lorsque le type Entite n'est pas stocké dans un conteneur ou qu' il est stocké dans un conteneur d'un autre type, std::vector par exemple, il y'aura une dépendance inutile avec map.Et que signifiera alors "map<string, Entite *>::iterator name". Est-ce que cette optimisation est primordiale par rapport à une meilleure conception ? Si oui et si le type Entite sera toujours lié à un conteneur std::map, ne faut-il pas reconsidérer la conception ? Cordialement, Ahmed "Nicolas Castagne" <castagne (AT) imag (DOT) fr> wrote Quote: J'ai refait mes tests, puis inclu ça dans le programme, et tout semble se passer correctement. Merci, donc ! (au cas où, je suis toujours preneur d'info sur les liens entre les specifs des conteneurs de la std et celles de la stl !) Nico Nicolas Castagne a écrit : Salut tous, salut Arnaud, [email]adebaene (AT) club-internet (DOT) fr[/email] a écrit : C'est une garantie donnée par la norme, et que toute implémentation doit respecter. Sur quelle implémentation as tu observé un comportement différent? Sur std de gcc, Linux, RedHat Enterprise. Rien que du très commun. Es-tu sur que la norme relative aux conteneurs de la librairie standard std garantisse la non-invalidation des iterator des map en cas d'ajout et de suppression ? Parce que la STL de SGI le garantit, mais ce n'est pas une 'norme'... A priori, sauf erreur, rien n'indique que std respectent les choix fait pour la STL. Aurais-tu un pointeur sur la 'norme' à laquelle tu fais référence ? Sinon, bien sur, il est possible que ma série de tests soit bugguée. Je vais verifier ça. Nico Sinon... Nicolas Castagne wrote: ... Ou plutôt std::map oué c'était une erreur :) Dans la STL de SGI, cela semble possible, puique la doc de stl::map précise : Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. (from : http://www.sgi.com/tech/stl/Map.html ) C'est une garantie donnée par la norme, et que toute implémentation doit respecter. Sur quelle implémentation as tu observé un comportement différent? Arnaud Back to top Pierre THIERRY Guest Posted: Thu May 12, 2005 12:08 pm    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? Le Fri, 15 Apr 2005 14:07:55 +0200, Nicolas Castagne a écrit : Quote: Parce que la STL de SGI le garantit, mais ce n'est pas une 'norme'... A priori, sauf erreur, rien n'indique que std respectent les choix fait pour la STL. Nota bene: std n'est pas une implémentation particulière de la STL, c'est juste son espace de nom. Et ceci qu'on compile avec GCC, Sun CC ou VC++. Quant à la STL de SGI, c'est précisément celle-ci qui est livré avec la plupart des Linux, et c'est en tout cas celle qui est livrée avec GCC. Donc normalement, si tu compiles de C++ avec GCC, c'est bien àla STL de SGI que tu fais appel. Est-ce que tu avais un code qui démontrait l'invalidation de l'itérateur ? Curieusement, Nowhere man PS: est-ce que c'est aussi l'implémentation SGI de la STL qui est livrée avec les autres compilos ? -- [email]nowhere.man (AT) levallois (DOT) eu.org[/email] OpenPGP 0xD9D50D8A Back to top Gabriel Dos Reis Guest Posted: Thu May 12, 2005 2:11 pm    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? Pierre THIERRY <nowhere.man (AT) levallois (DOT) eu.org> writes: Quote: Le Fri, 15 Apr 2005 14:07:55 +0200, Nicolas Castagne a écrit : Parce que la STL de SGI le garantit, mais ce n'est pas une 'norme'... A priori, sauf erreur, rien n'indique que std respectent les choix fait pour la STL. C'est exact. La portion de la bibliothèque standard est un sous-ensemble de la STL de SGI. De fait, si j'en crois les paroles de celui qui en a facilité son introduction dans la norme, il en a coupé quelque chose comme les 2/3. L'implémentation de GNU, même si elle était basée au départ sur celle de SGI, s'en est substantiellement déviée pour se rapprocher de la norme. Quote: Nota bene: std n'est pas une implémentation particulière de la STL, c'est juste son espace de nom. Et ceci qu'on compile avec GCC, Sun CC ou VC++. Quant à la STL de SGI, c'est précisément celle-ci qui est livré avec la plupart des Linux, et c'est en tout cas celle qui est livrée avec GCC. Donc normalement, si tu compiles de C++ avec GCC, c'est bien àla STL de SGI que tu fais appel. Ce qui n'est pas vrai. -- Gaby Back to top Gabriel Dos Reis Guest Posted: Thu May 12, 2005 2:54 pm    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? Nicolas Castagne <castagne (AT) imag (DOT) fr> writes: Quote: Es-tu sur que la norme relative aux conteneurs de la librairie standard std garantisse la non-invalidation des iterator des map en cas d'ajout et de suppression ? Oui. Quote: Parce que la STL de SGI le garantit, mais ce n'est pas une 'norme'... A priori, sauf erreur, rien n'indique que std respectent les choix fait pour la STL. Oui mais non. Quote: Aurais-tu un pointeur sur la 'norme' à laquelle tu fais référence ? §23.1.2/3 -- Gaby Back to top Gabriel Dos Reis Guest Posted: Thu May 12, 2005 3:01 pm    Post subject: Re: std::map : à quel moment les iterateur sont invalidés ? Nicolas Castagne <castagne (AT) imag (DOT) fr> writes: Quote: Bonjour à tous, dans mon appli, j'ai besoin à la fois de : 1 - accéder rapidement à des entités (classe Entite) par nom (string - le nom est unique) 2 - récupérer le nom de ces entités lorsque je manipule une Entitie Le 1- tend à ce qu'une std::map soit utilisée, par exemple : map<const string , Entite*, ltstr> nameSpace; Le 2- tend à ce que le nom soit stoqué dans les objets Entite, par exemple : class Entite { string name; ... } Mais dans ce cas, il y a la duplication de donnée. Mon programme est ammené à manipuler un grand nombre d'entité, et par suite un grand nombre de noms. Les noms peuvent être longs. C'est un problème bien connu. Si la définition de <set> avait été utile, tu pourrais juste écrire std::set<Entite, EntiteCompareByName> nameSpace; mais visiblement personnes n'a envie que ce soit utile. Quote: Je cherche donc à optimiser ces deux actions, sans dupliquer l'info. Une solution consisterait à stoquer dans Entite un iterator sur la map : class Entite { map<string, Entite *>::iterator name; ... } Et le pointeur (valeur du mapping) viendrait d'où ? Quote: Dans la STL de SGI, cela semble possible, puique la doc de stl::map précise : Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. (from : http://www.sgi.com/tech/stl/Map.html ) J'ai essayé avec la map de std... mais ca semble ne pas fonctionner. Exactement, qu'est-ce qui ne fonctionne pas ? Quote: Aucune des docs que j'ai lu qui présentent std::map ne présente d'information quant aux conditions dans lesquelles un iterator sur une std::map devient invalide. Ah bon ? Quote: Qu'est-ce qu'en est-il exactement ? Tu invalides uniquement ce qye tu as effacé -- il n'y a pas de miracle. -- Gaby 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.