C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Trier un vecteur d'iterateur à l'envers          C++Talk.NET Forum Index -> C++ (French) View previous topic :: View next topic   Author Message Michaël Delva Guest Posted: Wed Mar 03, 2004 1:10 am    Post subject: Trier un vecteur d'iterateur à l'envers Salut à tous, continuant sur mes tâtonnements concernant les algos de la STL (c'est pas faute de chercher et de m'user les yeux sur Le Language C++ par Stroustrup), je n'arrive pas trier un vecteur d'iterateurs en ordre inverse, donc de end() à begin()... Comment vous faites ça? Merci d'avance!! Back to top Jean-Sebastien Mouret Guest Posted: Wed Mar 03, 2004 1:46 am    Post subject: Re: Trier un vecteur d'iterateur à l'envers "Michaël Delva" <zoubidaman (AT) hotmail (DOT) com> writes: Quote: Salut à tous, continuant sur mes tâtonnements concernant les algos de la STL (c'est pas faute de chercher et de m'user les yeux sur Le Language C++ par Stroustrup), je n'arrive pas trier un vecteur d'iterateurs en ordre inverse, donc de end() à begin()... Comment vous faites ça? en admettant que tu aies un operateur < sur tes iterateurs (T): std::sort(v.begin(), v.end(), not2(std::less mais je pense sincerement qu'un simple: std::reverse(v.begin(), v.end()); devrait suffire car tu ne dois surement pas avoir d'opérateur < tu peux aussi parcourir ton vecteur en sens inverse avec un reverse_iterator et ses potes rbegin() et rend(). -- [email]js (AT) mouret (DOT) org[/email] "creating the future" (c) framfab Back to top Fabien LE LEZ Guest Posted: Wed Mar 03, 2004 1:48 am    Post subject: Re: Trier un vecteur d'iterateur à l'envers On 03 Mar 2004 01:10:05 GMT, "Michaël Delva" <zoubidaman (AT) hotmail (DOT) com> wrote: Quote: je n'arrive pas trier un vecteur d'iterateurs en ordre inverse, donc de end() à begin()... Comment vous faites ça? Je fais pas Ou du moins, si j'ai bien compris ton problème, je ne l'ai jamais fait. Voici donc comment j'ai compris ta question : - tu as un std::X<MaClasse> (où X == vector, deque ou list), qui est le conteneur "de base". - tu as un std::vector <std::list, que tu cherches à trier suivant la position de chaque iterateur dans le conteneur de base. A priori donc, il te faut un prédicat "EstPosterieurA" pour "std::sort (it, it, predicat)". Histoire de simplifier les écritures : typedef std::X<MaClasse> Conteneur; typedef Conteneur::iterator Iterateur; /* Note : ça peut aussi être const_iterator */ typedef std::vector<Iterateur> VectIter; Pour X==vector, je pense que ceci doit marcher : template<class T> bool EstPosterieurA (VectIter::const_iterator i1, VectIter::const_iterator i2) { return &*i1 > &*i2; } Pas trop sûr toutefois :-/ Pour X==deque, il doit y avoir un truc, mais je connais assez mal ce conteneur :-( Pour X==list, je crois que la seule façon de savoir si un itérateur est postérieur à un autre est de parcourir toute la liste à partir de l'itérateur qui t'intéresse, et de regarder si on tombe d'abord sur l'autre itérateur ou sur end(). Autre solution : parcourir la liste, et, pour chaque itérateur, compter le nombre d'occurences dans le VectIter. On peut alors créer un nouveau VectIter en se basant sur ces informations. -- ;-) Back to top Michaël Delva Guest Posted: Wed Mar 03, 2004 1:53 am    Post subject: Re: Trier un vecteur d'iterateur à l'envers Quote: tu peux aussi parcourir ton vecteur en sens inverse avec un reverse_iterator et ses potes rbegin() et rend(). Parfait avec les reverse_iterator... Je les avais oublié ceux-là... Merci beaucoup!! Back to top Fabien LE LEZ Guest Posted: Wed Mar 03, 2004 1:53 am    Post subject: Re: Trier un vecteur d'iterateur à l'envers On Wed, 03 Mar 2004 02:48:17 +0100, Fabien LE LEZ <gramster (AT) gramster (DOT) com> wrote: Quote: Voici donc comment j'ai compris ta question : Note : vu l'heure, j'ai peut-être écrit un tissu de conneries. Bien faire attention à ma signature donc. -- ;-) Back to top Michaël Delva Guest Posted: Wed Mar 03, 2004 2:17 am    Post subject: Re: Trier un vecteur d'iterateur à l'envers Fabien LE LEZ <gramster (AT) gramster (DOT) com> wrote in news:rrda40d7f9ukpsql8dnuomo8n931cg3cav (AT) 4ax (DOT) com: Quote: Je fais pas ;-) Quote: Ou du moins, si j'ai bien compris ton problème, je ne l'ai jamais fait. Voici donc comment j'ai compris ta question : - tu as un std::X<MaClasse> (où X == vector, deque ou list), qui est le conteneur "de base". - tu as un std::vector <std::list, que tu cherches à trier suivant la position de chaque iterateur dans le conteneur de base. Tu as bien compris... En fait j'ai un std::vector<SJ_Sequence> toutes_possessions; que je parcoure par itérateur, et si l'itérateur ne répond pas à certaines exigences, je l'enregistre dans un vecteur de cet itérateur, pour le supprimer en fin de parcours... J'en arrive donc à ça (version réduite): //----------------------------------------------------------------------- typedef std::vector<SJ_Sequence>::iterator C_ITE; std::vector<C_ITE> suppr_iterateurs; for (C_ITE ite = toutes_possessions.begin(); ite != toutes_possessions.end(); ++ite) { bool fin_poss = false, ds_periode = false, ds_strategie = false; //Premier test concluant: fin_poss = true; //Deuxième test concluant: ds_periode = true //Si l'une des deux conditions est fausse, on stocke l'itérateur if (!fin_poss || !ds_periode) suppr_iterateurs.push_back(ite); } //On supprime les itérateurs qui ne sont pas adéquats for (std::vector<C_ITE>::reverse_iterator ite = suppr_iterateurs.rbegin(); ite != suppr_iterateurs.rend(); ++ite) toutes_possessions.erase(*ite); //----------------------------------------------------------------------- Maintenant, j'ai une question subsidiaire: comment je peux faire la suppression directement dans la première boucle? Même avec une boucle inversée ça marche pas... * Si je fais avec reverse_iterator, ça marche pas, normal avec le erase... * Si je fais: for (C_ITE ite = toutes_possessions.end(); ite == toutes_possessions.begin(); --ite) Il commence le parcours depuis le .end(), donc après le dernier élément, ce qui ne va pas non plus... * J'avais donc cherché du côté de ça: C_ITE ite = toutes_possessions.end(); --ite; for (ite = toutes_possessions.end(); ite == toutes_possessions.begin(); --ite) Mais ça plante si le vecteur est vide, et donc il y a trop de vérifications à faire dans le code pour que ça me semble être une solution correcte... Peut-être aussi que je me casse la tête pour rien et que ce que je fais est déjà la meilleure méthode?? Back to top Franck Branjonneau Guest Posted: Wed Mar 03, 2004 10:42 am    Post subject: Re: Trier un vecteur d'iterateur à l'envers "Michaël Delva" <zoubidaman (AT) hotmail (DOT) com> écrivait: Quote: news:rrda40d7f9ukpsql8dnuomo8n931cg3cav (AT) 4ax (DOT) com: Maintenant, j'ai une question subsidiaire: comment je peux faire la suppression directement dans la première boucle? Même avec une boucle inversée ça marche pas... std::vector<>::erase(std::vector<>::iterator) retourne un itérateur désignant l'élément suivant celui qu'il vient de détruire ou std::vector<>::end(). -- Franck Branjonneau <fasbjx (AT) free (DOT) fr> Back to top Samuel Krempp Guest Posted: Wed Mar 03, 2004 11:51 am    Post subject: Re: Trier un vecteur d'iterateur à l'envers le Wednesday 03 March 2004 02:53, [email]zoubidaman (AT) hotmail (DOT) com[/email] écrivit : Quote: Parfait avec les reverse_iterator... Je les avais oublié ceux-là... Merci beaucoup!! et ben, tu aurais dû mieux rédiger ta question départ car ce n'est pas du tout ce qu'on pouvait penser que tu voulais, il n'y a aucun rapport avec un *tri* d'itérateurs. -- Sam Back to top Michaël Delva Guest Posted: Wed Mar 03, 2004 12:23 pm    Post subject: Re: Trier un vecteur d'iterateur à l'envers Samuel Krempp <krempp (AT) crans (DOT) truc.en.trop.ens-cachan.fr> wrote in news:4045c6bb$0$29938$626a14ce (AT) news (DOT) free.fr: Quote: le Wednesday 03 March 2004 02:53, [email]zoubidaman (AT) hotmail (DOT) com[/email] écrivit : Parfait avec les reverse_iterator... Je les avais oublié ceux-là... Merci beaucoup!! et ben, tu aurais dû mieux rédiger ta question départ car ce n'est pas du tout ce qu'on pouvait penser que tu voulais, il n'y a aucun rapport avec un *tri* d'itérateurs. Ben trier à "l'envers", c'est bien aller de end() à begin(), non? Ce que font les reverse_iterator? Back to top Samuel Krempp Guest Posted: Thu Mar 04, 2004 12:14 pm    Post subject: Re: Trier un vecteur d'iterateur à l'envers le Wednesday 03 March 2004 13:23, [email]zoubidaman (AT) hotmail (DOT) com[/email] écrivit : Quote: Ben trier à "l'envers", c'est bien aller de end() à begin(), non? Ce que font les reverse_iterator? non, trier c'est pas "aller", comme les verbes le laissent penser c'est une action bien différente. toi tout ce que tu voulais c'est itérer en allant du dernier au premier, et ce n'est pas le concept du tri. En l'occurence, si tu mets les itérateurs begin() et end() dans un tableau (c'était ça si j'ai bien suivi, non ?) il faut ensuite inverser l'ordre des éléments. Alors là trier aurait le résultat voulu, mais ce n'est même pas la méthode adaptée pour "retourner" un tableau, qui se fait mieux et plus simplement. Et à la base, aller de end() à begin() se fait sans mettre des itérateurs dans un vecteur, donc c'est simplement ça qu'il aurait fallu demander : ce que tu voulais vraiment faire au final. C'est pas pour être désagréable que je dis ça, c'est pas ta faute si tu as pensé que mettre dans un vecteur et trier était la solution à ton problème. Mais je voulais juste te faire remarquer que tu obtiendras plus de réponses en formulant tes questions en fonction de ton but plus que de ce que tu penses être la solution. Et tu mettras moins de lecteurs sur des fausses pistes. -- Sam Back to top Michaël Delva Guest Posted: Thu Mar 04, 2004 3:06 pm    Post subject: Re: Trier un vecteur d'iterateur à l'envers Samuel Krempp <krempp (AT) crans (DOT) truc.en.trop.ens-cachan.fr> wrote in news:40471da7$0$2441$626a14ce (AT) news (DOT) free.fr: Quote: le Wednesday 03 March 2004 13:23, [email]zoubidaman (AT) hotmail (DOT) com[/email] écrivit : Ben trier à "l'envers", c'est bien aller de end() à begin(), non? Ce que font les reverse_iterator? non, trier c'est pas "aller", comme les verbes le laissent penser c'est une action bien différente. toi tout ce que tu voulais c'est itérer en allant du dernier au premier, et ce n'est pas le concept du tri. En l'occurence, si tu mets les itérateurs begin() et end() dans un tableau (c'était ça si j'ai bien suivi, non ?) il faut ensuite inverser l'ordre des éléments. Alors là trier aurait le résultat voulu, mais ce n'est même pas la méthode adaptée pour "retourner" un tableau, qui se fait mieux et plus simplement. Et à la base, aller de end() à begin() se fait sans mettre des itérateurs dans un vecteur, donc c'est simplement ça qu'il aurait fallu demander : ce que tu voulais vraiment faire au final. C'est pas pour être désagréable que je dis ça, c'est pas ta faute si tu as pensé que mettre dans un vecteur et trier était la solution à ton problème. Mais je voulais juste te faire remarquer que tu obtiendras plus de réponses en formulant tes questions en fonction de ton but plus que de ce que tu penses être la solution. Et tu mettras moins de lecteurs sur des fausses pistes. OK, j'essaierai de mieux formuler ma question les prochaines fois. En espérant ne pas être limité, comme c'est souvent le cas, par le vocabulaire spécifique au C++, ce qui, je te l'accorde volontiers, n'a pas été le cas cette fois ;-) Back to top kanze@gabi-soft.fr Guest Posted: Fri Mar 05, 2004 7:52 am    Post subject: Re: Trier un vecteur d'iterateur à l'envers "Michaël Delva" <zoubidaman (AT) hotmail (DOT) com> wrote Quote: Samuel Krempp <krempp (AT) crans (DOT) truc.en.trop.ens-cachan.fr> wrote in news:40471da7$0$2441$626a14ce (AT) news (DOT) free.fr: [...] Quote: Et à la base, aller de end() à begin() se fait sans mettre des itérateurs dans un vecteur, donc c'est simplement ça qu'il aurait fallu demander : ce que tu voulais vraiment faire au final. C'est pas pour être désagréable que je dis ça, c'est pas ta faute si tu as pensé que mettre dans un vecteur et trier était la solution à ton problème. Mais je voulais juste te faire remarquer que tu obtiendras plus de réponses en formulant tes questions en fonction de ton but plus que de ce que tu penses être la solution. Et tu mettras moins de lecteurs sur des fausses pistes. OK, j'essaierai de mieux formuler ma question les prochaines fois. En espérant ne pas être limité, comme c'est souvent le cas, par le vocabulaire spécifique au C++, ce qui, je te l'accorde volontiers, n'a pas été le cas cette fois Sauf que dans ce cas-ci, il ne s'agit pas d'un vocabulaire propre à C++, mais d'un vocabulaire général de l'algorithmique. D'après tes commentaires dans un autre fil de discussion (que tu ne savais pas ce que c'est qu'un tableau de hachage), j'ai l'impression que tu as dû passer à côté de l'algorithmique dans ta formation. Si tu as un diplôme en informatique, je dirais qu'il faudrait sérieusement poser des questions sur la qualité de l'école. Sinon, je peux te dire par expérience (je suis autodidacte moi-même, sans bac et sans jamais avoir suivi un cours d'informatique), c'est facile de passer à côté, parce que précisement, il ne se rapporte pas directement à des outils dont on se sert. Dans mon cas, j'ai trouvé le livre « Algorithms + Data Structure = Program », de Wirth (ISBN 0-13-022418-9) extrèmement clair et facile à comprendre, malgré quelque faiblesses, surtout au niveau de la typographie. On conseille aussi souvent « Algorithms in C », de Sedgewick ; je l'ai trouvé moins facile à aborder, mais c'est une question de goût. (J'ai aussi un livre d'un certain Aaron Tanenbaum que j'ai trouvé très bien. Malheureusement, je n'arrive pas à en trouver les référence chez Amazon, ce qui me fait penser qu'il n'est peut-être plus disponible.) La référence dans le domaine, c'est sans doute le Knuth («@The Art of Computer Programming »), mais c'est ça, une référence. AMHA, ce n'est pas un livre pour commencer avec le sujet. -- James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16 Back to top Gabriel Dos Reis Guest Posted: Sun Mar 07, 2004 5:04 pm    Post subject: Re: Trier un vecteur d'iterateur à l'envers "Michaël Delva" <zoubidaman (AT) hotmail (DOT) com> writes: Quote: Samuel Krempp <krempp (AT) crans (DOT) truc.en.trop.ens-cachan.fr> wrote in news:4045c6bb$0$29938$626a14ce (AT) news (DOT) free.fr: le Wednesday 03 March 2004 02:53, [email]zoubidaman (AT) hotmail (DOT) com[/email] écrivit : Parfait avec les reverse_iterator... Je les avais oublié ceux-là... Merci beaucoup!! et ben, tu aurais dû mieux rédiger ta question départ car ce n'est pas du tout ce qu'on pouvait penser que tu voulais, il n'y a aucun rapport avec un *tri* d'itérateurs. Ben trier à "l'envers", c'est bien aller de end() à begin(), non? Ce que font les reverse_iterator? J'aurais cru à une douce méchante blague si c'était quelqu'un d'autre qui avait écrit ça... Non, reverse_iterator ne trie pas un les itérateurs. Il se content just de contrarier les iérateurs : quand l'un dit ++, l'autre dit --. Un reverse_iterator va dans le sens inverse de l'itérateur à partir duquel il est construit. -- 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.