C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Implementation end/rend pour list et map Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ (French) View previous topic :: View next topic   Author Message Marc Boyer Guest Posted: Fri Jul 23, 2004 11:56 am    Post subject: Implementation end/rend pour list et map Bonjour, dans le cadre d'unn projet en C, j'en suis ammené à m'interroger sur l'implémentation des itérateurs end/rend dans list et map. En effet, dans ces deux conteneurs, une impleméntation triviale d'un itérateur est de faire un pointeur sur un élément interne (cellule pour list et noeud pour map), avec une surcharge de * et ->. Mais, comment coder end (et rend), en restant homogène ? J'ai plusieurs idées en tête, mais la plus réaliste est aussi la plus moche :-( 1) Ajouter des éléments end/rend Ajouter dans la liste et dans l'arbre des éléments "en plus", des cellules/noeuds marqueurs de fin. Mais autant c'est faisable pour la liste (avec des tests genre it->next->next != NULL au lieu de it->next != NULL), autant dans l'arbre, ça complique tous les codes. 2) Itérateur comme tuple (pointeur element, pointeur conteneur) Mettre dans un itérateur un pointeur sur le conteneur lui même, ainsi, on peu imaginer que (NULL, p1) est le résultat de p1->end(). A priori, je me dirige vers 2), surtout pour l'arbre de map, mais j'ai peut-être raté un truc. J'ai tenté de jetter un coup d'oeuil sur les sources de la stl de gcc, et les itérateurs semblent n'etre qu'un pointeur. Le list semble codé avec un element en rab, en tête (?), end() étant l'adresse de ce pointeur, et begin étant end()->next (en gros). Pour l'arbre, ça semble être la racine, mais j'ai pas compris comment ils font si par hasard on fait un erase() de cette racine... Marc Boyer -- La contractualisation de la recherche, c'est me donner de l'argent pour faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce que je sais faire, je le fais sans moyens... Back to top drkm Guest Posted: Fri Jul 23, 2004 12:40 pm    Post subject: Re: Implementation end/rend pour list et map Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: Quote: dans le cadre d'unn projet en C, j'en suis ammené à m'interroger sur l'implémentation des itérateurs end/rend dans list et map. En effet, dans ces deux conteneurs, une impleméntation triviale d'un itérateur est de faire un pointeur sur un élément interne (cellule pour list et noeud pour map), avec une surcharge de * et ->. Lorsque tu dis « faire un pointeur ... », j'imagine que tu veux dire « définir une structure contenant un pointeur ... ». Il faut également surcharger les opérateurs de comparaison, d'incrémentation et de décrémentation. Quote: Mais, comment coder end (et rend), en restant homogène ? Qu'entends-tu par « homogène » ? Ce qui me vient directement à l'esprit serait d'initialiser le pointeur membre de l'itérateur à une valeur sentinelle, comme 0. Je ne sais pas s'il s'agit d'une implémentation permise, mais je ne vois pas a priori de contre-indication, ni d'avantage à avoir une autre valeur. Quote: J'ai plusieurs idées en tête, mais la plus réaliste est aussi la plus moche Laquelle trouves-tu la plus réaliste (et la plus moche, donc) ? Quote: 1) Ajouter des éléments end/rend Ajouter dans la liste et dans l'arbre des éléments "en plus", des cellules/noeuds marqueurs de fin. Mais autant c'est faisable pour la liste (avec des tests genre it->next->next != NULL au lieu de it->next != NULL), autant dans l'arbre, ça complique tous les codes. Je ne vois pas l'intérêt. Quote: 2) Itérateur comme tuple (pointeur element, pointeur conteneur) Mettre dans un itérateur un pointeur sur le conteneur lui même, ainsi, on peu imaginer que (NULL, p1) est le résultat de p1->end(). Il y a des avantages à avoir des itérateurs contenant une référence vers le conteneur dont ils sont issus. Mais je pense que le modèle des itérateurs de la STL ne permet pas de les exploiter. Quote: A priori, je me dirige vers 2), surtout pour l'arbre de map, mais j'ai peut-être raté un truc. J'ai tenté de jetter un coup d'oeuil sur les sources de la stl de gcc, et les itérateurs semblent n'etre qu'un pointeur. Huh ? Autant je comprendrais avec std::vector (et il me semble qu'il s'agissait effectivement d'une implémentation courante), autant je n'arrive pas à voir comment utiliser un simple pointeur comme itérateur de std::list ou std::map. Quote: Le list semble codé avec un element en rab, en tête (?), end() étant l'adresse de ce pointeur, et begin étant end()->next (en gros). Pour l'arbre, ça semble être la racine, L'itérateur renvoyé par end() désigne donc un noeud existant, mais bidon ? On a donc une certaine identité entre chaque itérateur retourné par end(), depuis une même liste ou map ... Quote: mais j'ai pas compris comment ils font si par hasard on fait un erase() de cette racine... Tu parles bien de o.erase( o.end() ) ?!? --drkm, en recherche d'un stage : http://www.fgeorges.org/ipl/stage.html Back to top Marc Boyer Guest Posted: Fri Jul 23, 2004 12:49 pm    Post subject: Re: Implementation end/rend pour list et map drkm wrote: Quote: Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: En effet, dans ces deux conteneurs, une impleméntation triviale d'un itérateur est de faire un pointeur sur un élément interne (cellule pour list et noeud pour map), avec une surcharge de * et ->. Lorsque tu dis « faire un pointeur ... », j'imagine que tu veux dire « définir une structure contenant un pointeur ... ». Il faut également surcharger les opérateurs de comparaison, d'incrémentation et de décrémentation. Tout a fait. Quote: Mais, comment coder end (et rend), en restant homogène ? Qu'entends-tu par « homogène » ? Pas un horible cast de la mort pour mettre un pointeur sur conteneur dans une variable destinée à recevoir un pointeur sur noeud interne. Quote: Ce qui me vient directement à l'esprit serait d'initialiser le pointeur membre de l'itérateur à une valeur sentinelle, comme 0. Je ne sais pas s'il s'agit d'une implémentation permise, mais je ne vois pas a priori de contre-indication, ni d'avantage à avoir une autre valeur. C'était aussi mon idée, facile à implémenter, faite, sauf que, comment faire end()-1 et retrouver begin()+(size()-1) ? Quote: 1) Ajouter des éléments end/rend Ajouter dans la liste et dans l'arbre des éléments "en plus", des cellules/noeuds marqueurs de fin. Mais autant c'est faisable pour la liste (avec des tests genre it->next->next != NULL au lieu de it->next != NULL), autant dans l'arbre, ça complique tous les codes. Je ne vois pas l'intérêt. De end(), on passe facilement à end()-1 Quote: J'ai tenté de jetter un coup d'oeuil sur les sources de la stl de gcc, et les itérateurs semblent n'etre qu'un pointeur. Huh ? Autant je comprendrais avec std::vector (et il me semble qu'il s'agissait effectivement d'une implémentation courante), autant je n'arrive pas à voir comment utiliser un simple pointeur comme itérateur de std::list ou std::map. Pointeur sur un noeud interne. Globalement, une list<T>, c'est un list_node<T>* avec class list_node<T> { T data; list_node<T> *prev, *next; } Quote: L'itérateur renvoyé par end() désigne donc un noeud existant, mais bidon ? Oui. Quote: On a donc une certaine identité entre chaque itérateur retourné par end(), depuis une même liste ou map ... Ben, heureusement non ? Quote: mais j'ai pas compris comment ils font si par hasard on fait un erase() de cette racine... Tu parles bien de o.erase( o.end() ) ?!? Non, dans un arbre équilibré, normalement, la racine c'est pas o.end() mais plutôt o.begin()+ o.size()/2. Quote: --drkm, en recherche d'un stage : http://www.fgeorges.org/ipl/stage.html Désolé, je ne suis pas bruxellois... Marc Boyer -- La contractualisation de la recherche, c'est me donner de l'argent pour faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce que je sais faire, je le fais sans moyens... Back to top drkm Guest Posted: Fri Jul 23, 2004 1:57 pm    Post subject: Re: Implementation end/rend pour list et map Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: Quote: drkm wrote: Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: En effet, dans ces deux conteneurs, une impleméntation triviale d'un itérateur est de faire un pointeur sur un élément interne (cellule pour list et noeud pour map), avec une surcharge de * et ->. Lorsque tu dis « faire un pointeur ... », j'imagine que tu veux dire « définir une structure contenant un pointeur ... ». Il faut également surcharger les opérateurs de comparaison, d'incrémentation et de décrémentation. Tout a fait. Mais, comment coder end (et rend), en restant homogène ? Qu'entends-tu par « homogène » ? Pas un horible cast de la mort pour mettre un pointeur sur conteneur dans une variable destinée à recevoir un pointeur sur noeud interne. Je ne comprend toujours pas. Pourquoi veux-tu dans ce cas effectuer un cast depuis un pointeur sur conteneur ? Quote: Ce qui me vient directement à l'esprit serait d'initialiser le pointeur membre de l'itérateur à une valeur sentinelle, comme 0. Je ne sais pas s'il s'agit d'une implémentation permise, mais je ne vois pas a priori de contre-indication, ni d'avantage à avoir une autre valeur. C'était aussi mon idée, facile à implémenter, faite, sauf que, comment faire end()-1 et retrouver begin()+(size()-1) ? std::list<>::end() - 1 ?!? Quote: 1) Ajouter des éléments end/rend Ajouter dans la liste et dans l'arbre des éléments "en plus", des cellules/noeuds marqueurs de fin. Mais autant c'est faisable pour la liste (avec des tests genre it->next->next != NULL au lieu de it->next != NULL), autant dans l'arbre, ça complique tous les codes. Je ne vois pas l'intérêt. De end(), on passe facilement à end()-1 Mais je ne vois pas l'intérêt dans le cas de std::list<> et std::map<>. Quote: J'ai tenté de jetter un coup d'oeuil sur les sources de la stl de gcc, et les itérateurs semblent n'etre qu'un pointeur. Huh ? Autant je comprendrais avec std::vector (et il me semble qu'il s'agissait effectivement d'une implémentation courante), autant je n'arrive pas à voir comment utiliser un simple pointeur comme itérateur de std::list ou std::map. Pointeur sur un noeud interne. Globalement, une list<T>, c'est un list_node<T>* avec class list_node<T> { T data; list_node<T> *prev, *next; } Je ne vois toujours pas comment il est possible d'utiliser un simple pointeur, de quelque type que ce soit, comme itérateur dans le cas d'une std::list<>. Quote: L'itérateur renvoyé par end() désigne donc un noeud existant, mais bidon ? Oui. On a donc une certaine identité entre chaque itérateur retourné par end(), depuis une même liste ou map ... Ben, heureusement non ? Il me semblait que la seule contrainte de cet itérateur est d'être comparé à un itérateur de ce conteneur. Un itérateur de fin qui stockerait par exemple 0 comme valeur sentinelle me semblerait acceptable (il suffit que le suivant du dernier noeud de la liste vale lui-même 0). Mais, sans doute, je ne pense pas à certaines contraintes ou garanties sur les itérateurs. Quote: mais j'ai pas compris comment ils font si par hasard on fait un erase() de cette racine... Tu parles bien de o.erase( o.end() ) ?!? Non, dans un arbre équilibré, normalement, la racine c'est pas o.end() mais plutôt o.begin()+ o.size()/2. Lorsque tu disais que std::map<>::end() pointait vers la racine de l'arbre, je pensais que tu parlais d'une racine bidon, comme on en trouve dans certaines implémentations d'arbres où l'on est certain d'avoir toujours un noeud, mais ce noeud ne fait pas partie de l'arbre lui-même. Il me semble qu'un implémentation où end() retourne un itérateur vers un élément valide ne serait pas conforme. Mais peut-être que je me trompe. Quote: --drkm, en recherche d'un stage : http://www.fgeorges.org/ipl/stage.html Désolé, je ne suis pas bruxellois... C'est pas grave, une fois ... --drkm, en recherche d'un stage : http://www.fgeorges.org/ipl/stage.html Back to top Marc Boyer Guest Posted: Fri Jul 23, 2004 2:14 pm    Post subject: Re: Implementation end/rend pour list et map In article <wkbri63jx5.fsf (AT) fgeorges (DOT) org>, drkm wrote: Quote: Pas un horible cast de la mort pour mettre un pointeur sur conteneur dans une variable destinée à recevoir un pointeur sur noeud interne. Je ne comprend toujours pas. Pourquoi veux-tu dans ce cas effectuer un cast depuis un pointeur sur conteneur ? A partir de end(), il faut pouvoir retrouver le conteneur, donc, pointer sur quelque chose. Hors, on ne peut pas pointer sur un element puisque les iterateurs ne doivent pas etre invalidé par la destruction d'un élément désigné par un autre itérateur. Sur quoi pointer donc ? Quote: Ce qui me vient directement à l'esprit serait d'initialiser le pointeur membre de l'itérateur à une valeur sentinelle, comme 0. Je ne sais pas s'il s'agit d'une implémentation permise, mais je ne vois pas a priori de contre-indication, ni d'avantage à avoir une autre valeur. C'était aussi mon idée, facile à implémenter, faite, sauf que, comment faire end()-1 et retrouver begin()+(size()-1) ? std::list<>::end() - 1 ?!? Me semble bien qu'on peut décrémenter l'intérateur end, non ? #include <list> int main(){ std::list<int> li; std::list<int>::iterator it; li.push_back(0); it= li.end(); it--; assert( it == li.begin() ); return 0; } Ou ça marche juste parce que mon compilateur est gentil avec moi ? Quote: 1) Ajouter des éléments end/rend Ajouter dans la liste et dans l'arbre des éléments "en plus", des cellules/noeuds marqueurs de fin. Mais autant c'est faisable pour la liste (avec des tests genre it->next->next != NULL au lieu de it->next != NULL), autant dans l'arbre, ça complique tous les codes. Je ne vois pas l'intérêt. De end(), on passe facilement à end()-1 Mais je ne vois pas l'intérêt dans le cas de std::list<> et std::map<>. Ben, c'est *une* solution. Quote: Pointeur sur un noeud interne. Globalement, une list<T>, c'est un list_node<T>* avec class list_node<T> { T data; list_node<T> *prev, *next; } Je ne vois toujours pas comment il est possible d'utiliser un simple pointeur, de quelque type que ce soit, comme itérateur dans le cas d'une std::list<>. Quand je dis "simple pointeur", c'est que l'unique variable membre est un poiteur, auquel on rajoute toutes les fonctions qui vont autour (*, ->, l'arithmétique...) Quote: Il me semblait que la seule contrainte de cet itérateur est d'être comparé à un itérateur de ce conteneur. Un itérateur de fin qui stockerait par exemple 0 comme valeur sentinelle me semblerait acceptable (il suffit que le suivant du dernier noeud de la liste vale lui-même 0). Mais, sans doute, je ne pense pas à certaines contraintes ou garanties sur les itérateurs. Ben, faire it= li.end(); it--; Mais est-ce valide ? Je croyais que oui mais je me plante peut-être. Marc Boyer -- La contractualisation de la recherche, c'est me donner de l'argent pour faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce que je sais faire, je le fais sans moyens... Back to top Jean-Marc Bourguet Guest Posted: Fri Jul 23, 2004 2:21 pm    Post subject: Re: Implementation end/rend pour list et map Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: Quote: J'ai tenté de jetter un coup d'oeuil sur les sources de la stl de gcc, et les itérateurs semblent n'etre qu'un pointeur. Le list semble codé avec un element en rab, en tête (?), end() étant l'adresse de ce pointeur, et begin étant end()->next (en gros). Pour l'arbre, ça semble être la racine, mais j'ai pas compris comment ils font si par hasard on fait un erase() de cette racine... Ce ne serait pas un element en plus egalement qui serait donc garanti de rester toujours la racine? A+ -- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org Back to top drkm Guest Posted: Fri Jul 23, 2004 4:05 pm    Post subject: Re: Implementation end/rend pour list et map Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: Quote: In article <wkbri63jx5.fsf (AT) fgeorges (DOT) org>, drkm wrote: Pas un horible cast de la mort pour mettre un pointeur sur conteneur dans une variable destinée à recevoir un pointeur sur noeud interne. Je ne comprend toujours pas. Pourquoi veux-tu dans ce cas effectuer un cast depuis un pointeur sur conteneur ? A partir de end(), il faut pouvoir retrouver le conteneur, Pourquoi ? Quote: donc, pointer sur quelque chose. Hors, on ne peut pas pointer sur un element puisque les iterateurs ne doivent pas etre invalidé par la destruction d'un élément désigné par un autre itérateur. Sur quoi pointer donc ? Ce qui me vient directement à l'esprit serait d'initialiser le pointeur membre de l'itérateur à une valeur sentinelle, comme 0. Je ne sais pas s'il s'agit d'une implémentation permise, mais je ne vois pas a priori de contre-indication, ni d'avantage à avoir une autre valeur. C'était aussi mon idée, facile à implémenter, faite, sauf que, comment faire end()-1 et retrouver begin()+(size()-1) ? std::list<>::end() - 1 ?!? Me semble bien qu'on peut décrémenter l'intérateur end, non ? Ce qui n'est pas la même chose. Mais il est vrai que je pensais que la décrémentation n'était pas non plus permise. Il me semblait avoir lu que les itérateurs de std::list<> devaient être « at least forward iterators ». Je n'arrive cependant pas à remettre la main dessus. J'ai par contre en effet trouvé des « -- a.end() » dans 23.1.1/12. Je n'arrive cependant pas à déterminer s'il s'agit d'une illustration conceptuelle ou une réelle contrainte. Par illustration conceptuelle, j'entend « même si cela n'est pas garanti, on fait ici appel à votre bon sens, à titre indicatif ». Mais cela m'étonnerait. Quote: #include <list int main(){ std::list std::list<int>::iterator it; li.push_back(0); it= li.end(); it--; assert( it == li.begin() ); return 0; } Ou ça marche juste parce que mon compilateur est gentil avec moi ? Parce qu'il est gentil avec toi. Il t'a déclaré assert() ;-) Pour la décrémentation de end(), j'aurais dit que ce n'était pas correct. Mais après avoir jeté un coup d'oeil rapide à la norme, je ne suis plus sûr. J'essaierai de chercher plus profondément, si personne ne poste de référence. Quote: 1) Ajouter des éléments end/rend Ajouter dans la liste et dans l'arbre des éléments "en plus", des cellules/noeuds marqueurs de fin. Mais autant c'est faisable pour la liste (avec des tests genre it->next->next != NULL au lieu de it->next != NULL), autant dans l'arbre, ça complique tous les codes. Je ne vois pas l'intérêt. De end(), on passe facilement à end()-1 Mais je ne vois pas l'intérêt dans le cas de std::list<> et std::map<>. Ben, c'est *une* solution. J'ai jeté également un coup d'oeil rapide à la libstdc++ de GNU. Il semble qu'il s'agisse d'une implémentation classique d'une liste doublement chaînée avec noeud de tête bidon. Dans une liste vide, ce noeud bidon a ses deux pointeurs pointant vers lui-même. Sinon, son suivant est le premier élément, et son précédent le dernier (et il est le suivant du dernier et le précédent du premier). Je pense que l'utilisation d'un tel noeud permet justement de devoir considérer moins de cas limites (moins de tests pour voir si on est à la fin ou au début). Et cela règle de manière élégante la décrémentation de end(), si elle est permise. Quote: Pointeur sur un noeud interne. Globalement, une list<T>, c'est un list_node<T>* avec class list_node<T> { T data; list_node<T> *prev, *next; } Je ne vois toujours pas comment il est possible d'utiliser un simple pointeur, de quelque type que ce soit, comme itérateur dans le cas d'une std::list<>. Quand je dis "simple pointeur", c'est que l'unique variable membre est un poiteur, auquel on rajoute toutes les fonctions qui vont autour (*, ->, l'arithmétique...) Ok. Je pensais que tu parlais de quelque chose comme : template < T , A = allocator< T > > class list { public: typedef T * iterator ; typedef T const * const_iterator ; // ... } ; Il me semble que c'est ce que réalisaient plusieurs implémentations pour std::vector<>. Je pense d'ailleurs que c'est une implémentation conforme (à moins que, quelques effets subtils au niveau du système de typage et des templates ?). Quote: Il me semblait que la seule contrainte de cet itérateur est d'être comparé à un itérateur de ce conteneur. Un itérateur de fin qui stockerait par exemple 0 comme valeur sentinelle me semblerait acceptable (il suffit que le suivant du dernier noeud de la liste vale lui-même 0). Mais, sans doute, je ne pense pas à certaines contraintes ou garanties sur les itérateurs. Ben, faire it= li.end(); it--; Mais est-ce valide ? Je croyais que oui mais je me plante peut-être. Je croyais que non mais je me plante peut-être. --drkm, en recherche d'un stage : http://www.fgeorges.org/ipl/stage.html Back to top drkm Guest Posted: Sun Jul 25, 2004 2:51 pm    Post subject: Re: Implementation end/rend pour list et map drkm <usenet.fclcxx (AT) fgeorges (DOT) org> writes: Quote: Il me semblait avoir lu que les itérateurs de std::list<> devaient être « at least forward iterators ». Je n'arrive cependant pas à remettre la main dessus. J'ai confondu avec 23.1.1/5 : iterator and const_iterator types for sequences must be at least of the forward iterator category. 23.2.2/1 précise : list is a kind of sequence that supports bidirectional iterators C'était pourtant pas compliqué ;-) --drkm, en recherche d'un stage : http://www.fgeorges.org/ipl/stage.html Back to top Marc Boyer Guest Posted: Tue Jul 27, 2004 7:10 am    Post subject: Re: Implementation end/rend pour list et map drkm wrote: Quote: Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: std::list<>::end() - 1 ?!? Me semble bien qu'on peut décrémenter l'intérateur end, non ? Ce qui n'est pas la même chose. Oui, j'avais oublié. Je me demande pourquoi il y a une différence d'ailleurs, mais c'est pas fondamental comme question. Quote: int main(){ std::list<int> li; std::list<int>::iterator it; li.push_back(0); it= li.end(); it--; assert( it == li.begin() ); return 0; } Ou ça marche juste parce que mon compilateur est gentil avec moi ? Parce qu'il est gentil avec toi. Il t'a déclaré assert() ;-) Pour la décrémentation de end(), j'aurais dit que ce n'était pas correct. Mais après avoir jeté un coup d'oeil rapide à la norme, je ne suis plus sûr. J'essaierai de chercher plus profondément, si personne ne poste de référence. Bon, j'ai vu que depuis tu a posté une ref. Quote: J'ai jeté également un coup d'oeil rapide à la libstdc++ de GNU. Il semble qu'il s'agisse d'une implémentation classique d'une liste doublement chaînée avec noeud de tête bidon. Dans une liste vide, ce noeud bidon a ses deux pointeurs pointant vers lui-même. Sinon, son suivant est le premier élément, et son précédent le dernier (et il est le suivant du dernier et le précédent du premier). Je pense que l'utilisation d'un tel noeud permet justement de devoir considérer moins de cas limites (moins de tests pour voir si on est à la fin ou au début). Oui, c'est assez simple pour la liste. Pour l'arbre qui est derrière map, c'est nettement moins évident. Quote: Et cela règle de manière élégante la décrémentation de end(), si elle est permise. Tout a fait. Quote: Ben, faire it= li.end(); it--; Mais est-ce valide ? Je croyais que oui mais je me plante peut-être. Je croyais que non mais je me plante peut-être. Donc, en fait, c'est valide. Bon, la question de l'implémentation des itérateurs et de end() pour list est close. Mais pour map, ma réflexion avance mais j'hésite toujours à mettre un pointeur sur le conteneur dans l'itérateur. Marc Boyer -- La contractualisation de la recherche, c'est me donner de l'argent pour faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce que je sais faire, je le fais sans moyens... Back to top Marc Boyer Guest Posted: Tue Jul 27, 2004 7:30 am    Post subject: Re: Implementation end/rend pour list et map Jean-Marc Bourguet wrote: Quote: Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: J'ai tenté de jetter un coup d'oeuil sur les sources de la stl de gcc, et les itérateurs semblent n'etre qu'un pointeur. Le list semble codé avec un element en rab, en tête (?), end() étant l'adresse de ce pointeur, et begin étant end()->next (en gros). Pour l'arbre, ça semble être la racine, mais j'ai pas compris comment ils font si par hasard on fait un erase() de cette racine... Ce ne serait pas un element en plus egalement qui serait donc garanti de rester toujours la racine? Sauf que, pour des questions d'équilibre, un élément racine peut perdre sa caractéristique de racine. Alors apres, on peut faire une Meta-racine, sans element pertinent dedant, au dessus de la racine. Mais si on dit alors que end() est un pointeur sur cette racine, le passage de end() à end()-1 ou de end()-1 à end() passe en complexité log(n). C'est pas le bout du monde, mais dans le code de la stl g++ ils écrivent avoir codé begin() en temps constant, et je vois pas trop l'intérêt d'avoir begin en temps constant si le passage de end()-1 a end() est en log(n). En fait, avec dans l'itérateur un pointeur sur l'élément *et* un pointeur sur le conteneur, on peut avoir le passage de end() a son prédécesseur (et inversement) en temps constant. Mais on double la taille d'un itérateur. Est-ce grave docteur ? ;-) Marc Boyer -- La contractualisation de la recherche, c'est me donner de l'argent pour faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce que je sais faire, je le fais sans moyens... Back to top Jean-Marc Bourguet Guest Posted: Tue Jul 27, 2004 9:02 am    Post subject: Re: Implementation end/rend pour list et map Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: Quote: En fait, avec dans l'itérateur un pointeur sur l'élément *et* un pointeur sur le conteneur, on peut avoir le passage de end() a son prédécesseur (et inversement) en temps constant. Mais on double la taille d'un itérateur. Est-ce grave docteur ? Je suis partisan des iterateurs connaissant leur conteneur, meme quand c'est possible de faire autrement. (Mais je suis aussi partisan des iterateurs sachant quand ils sont invalides plutot que faisant n'importe quoi...) A+ -- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org Back to top Marc Boyer Guest Posted: Tue Jul 27, 2004 9:29 am    Post subject: Re: Implementation end/rend pour list et map In article <pxbzn5l4ybt.fsf (AT) news (DOT) bourguet.org>, Jean-Marc Bourguet wrote: Quote: Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: En fait, avec dans l'itérateur un pointeur sur l'élément *et* un pointeur sur le conteneur, on peut avoir le passage de end() a son prédécesseur (et inversement) en temps constant. Mais on double la taille d'un itérateur. Est-ce grave docteur ? ;-) Je suis partisan des iterateurs connaissant leur conteneur, meme quand c'est possible de faire autrement. Heuh, pourquoi ? Dans ce cas, je gagne en performance sur une opération, mais ça fait un itérateur plus gros (2 pointeurs). Quote: (Mais je suis aussi partisan des iterateurs sachant quand ils sont invalides plutot que faisant n'importe quoi...) C'est à dire ? Qu'ils aient le même résultat de déréférencer le pointeur nul ? Marc Boyer -- La contractualisation de la recherche, c'est me donner de l'argent pour faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce que je sais faire, je le fais sans moyens... Back to top Jean-Marc Bourguet Guest Posted: Tue Jul 27, 2004 9:42 am    Post subject: Re: Implementation end/rend pour list et map Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: Quote: In article <pxbzn5l4ybt.fsf (AT) news (DOT) bourguet.org>, Jean-Marc Bourguet wrote: Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: En fait, avec dans l'itérateur un pointeur sur l'élément *et* un pointeur sur le conteneur, on peut avoir le passage de end() a son prédécesseur (et inversement) en temps constant. Mais on double la taille d'un itérateur. Est-ce grave docteur ? ;-) Je suis partisan des iterateurs connaissant leur conteneur, meme quand c'est possible de faire autrement. Heuh, pourquoi ? Dans ce cas, je gagne en performance sur une opération, mais ça fait un itérateur plus gros (2 pointeurs). Et permettant de faire des verifications. Quote: (Mais je suis aussi partisan des iterateurs sachant quand ils sont invalides plutot que faisant n'importe quoi...) C'est à dire ? Qu'ils aient le même résultat de déréférencer le pointeur nul ? Cad qu'on peut leur demander s'ils sont invalides (et ils font en fait quelque chose de sense pour ++ permettant d'iterer sur tout et effacer une partie assez naturellement). A+ -- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org Back to top Marc Boyer Guest Posted: Tue Jul 27, 2004 10:11 am    Post subject: Re: Implementation end/rend pour list et map Jean-Marc Bourguet wrote: Quote: Heuh, pourquoi ? Dans ce cas, je gagne en performance sur une opération, mais ça fait un itérateur plus gros (2 pointeurs). Et permettant de faire des verifications. A quelles vérifications penses-tu ? Quote: (Mais je suis aussi partisan des iterateurs sachant quand ils sont invalides plutot que faisant n'importe quoi...) C'est à dire ? Qu'ils aient le même résultat de déréférencer le pointeur nul ? Cad qu'on peut leur demander s'ils sont invalides (et ils font en fait quelque chose de sense pour ++ permettant d'iterer sur tout et effacer une partie assez naturellement). Je comprends pas trop ta remarque. Tu aimerais que end()+1 == end() ? Marc Boyer -- La contractualisation de la recherche, c'est me donner de l'argent pour faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce que je sais faire, je le fais sans moyens... Back to top Jean-Marc Bourguet Guest Posted: Tue Jul 27, 2004 11:31 am    Post subject: Re: Implementation end/rend pour list et map Marc Boyer <Marc.Boyer (AT) enseeiht (DOT) yahoo.fr.invalid> writes: Quote: Jean-Marc Bourguet wrote: Heuh, pourquoi ? Dans ce cas, je gagne en performance sur une opération, mais ça fait un itérateur plus gros (2 pointeurs). Et permettant de faire des verifications. A quelles vérifications penses-tu ? (Mais je suis aussi partisan des iterateurs sachant quand ils sont invalides plutot que faisant n'importe quoi...) C'est à dire ? Qu'ils aient le même résultat de déréférencer le pointeur nul ? Cad qu'on peut leur demander s'ils sont invalides (et ils font en fait quelque chose de sense pour ++ permettant d'iterer sur tout et effacer une partie assez naturellement). Je comprends pas trop ta remarque. Tu aimerais que end()+1 == end() ? Non, ce n'est pas sense. Faire ++ sur un iterateur invalide parce qu'un element a ete efface fait pointer l'iterateur sur le prochain element valide de la collection. A+ -- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org 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 Goto page 1, 2  Next Page 1 of 2   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.