Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1035 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  STL - multimap - ou le mystère de l'iterator perdu (non résolu)

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

STL - multimap - ou le mystère de l'iterator perdu (non résolu)

n°1167534
ahmlot-khm​en
age = 5 ans
Posté le 02-08-2005 à 09:26:55  profilanswer
 

Bonjour,
 
J'aurai besoin d'un petit coup de main sur l'utilisation des multimap.
 
Supposons que je dispose d'une multimap<string , vector<int> >, et j'aimerais effacer de manière assez optimale toutes les paires dont le vector<int> est vide. Je rappelle notamment (car je ne le savais pas alors ça peut être utile :) ) qu'un erase(iterator) invalide tous les iterator (donc une boucle for avec iterator sans revenir à begin après chaque erase est, il me semble, impossible).
 
Je sais qu'une multimap ne s'utilise normalement qu'avec les clés mais j'ai quand même besoin de cet algo.
 
Merci d'avance.
 
a.k.
 
PS : si la réponse est complexe, j'aimerais, svp,  une simple explication sur le fonctionnement de l'algo.
(edit)PPS : après avoir lu la charte, je tiens à signaler que ceci n'est pas un exercice de cours, ni quoi que ce soit et que j'ai déjà chercher sur Google (deux ou trois heures) sans obtenir de résultat probant.(/edit)


Message édité par ahmlot-khmen le 02-08-2005 à 16:05:52
mood
Publicité
Posté le 02-08-2005 à 09:26:55  profilanswer
 

n°1167548
theshockwa​ve
I work at a firm named Koslow
Posté le 02-08-2005 à 09:39:19  profilanswer
 

#include <algorithm>
 
std::remove_if
 
non ?

n°1167559
ahmlot-khm​en
age = 5 ans
Posté le 02-08-2005 à 09:47:27  profilanswer
 

Citation :

#include <algorithm>
 
std::remove_if
 
non ?


 
Le problème de remove_if est qu'il permet de tester sur la paire < string, vector<int> > et qu'il me faut un test uniquement porté sur le vector<int>. (A moins que le remove_if permette de ne tester que la seconde valeur de la pair, mais je n'y suis pas arrivé  :cry: ).
 
Une autre suggestion ?

n°1167590
theshockwa​ve
I work at a firm named Koslow
Posté le 02-08-2005 à 10:23:54  profilanswer
 

Code :
  1. std::pair<string, vector<int> > p;
  2. p.second.push_back(12345);


Message édité par theshockwave le 02-08-2005 à 10:24:08
n°1167607
ahmlot-khm​en
age = 5 ans
Posté le 02-08-2005 à 10:37:24  profilanswer
 

Je ne comprends pas ta réponse.  :pt1cable:  
 
Par contre, voici où je m'étais arrêté dans ma solution de ce problème :

Code :
  1. multimap<string, vector<int> > pMaMultimap;
  2. pMaMultimap.erase(remove_if(pMaMultimap.begin(), pMaMultimap.end(),
  3. bind2nd(equal_to< vector<int> >(), vector<int>())), pMaMultimap.end())


 
Mais le prédicat n'est pas bon, il ne fait pas les comparaisons sur la seconde valeur comme je l'aimerais.

n°1167618
theshockwa​ve
I work at a firm named Koslow
Posté le 02-08-2005 à 10:50:14  profilanswer
 

:heink:
 
pourquoi tu veux écraser le retour du remove_if ?
 
sinon, je crois que je suis allé un peu vite, j'ai effectivement du mal à voir comment utiliser un remove_if sur une map (ou multimap), étant donné que le premier élément de la paire retournée est constant (pas d'affectation possible, quoi :/ )
 
tu peux toujours faire ta propre méthode, en revanche :
 

Code :
  1. bool cond(const std::pair<const std::string, std::vector<int> > &e) {
  2. return !e.second.size();
  3. }
  4. int main() {
  5. std::multimap<std::string, std::vector<int> > mm;
  6. std::multimap<std::string, std::vector<int> >::iterator it;
  7. while((it = std::find_if(mm.begin(), mm.end(), cond)) != mm.end())
  8.  mm.erase(it);
  9. return 0;
  10. }

n°1167650
ahmlot-khm​en
age = 5 ans
Posté le 02-08-2005 à 11:07:15  profilanswer
 

Citation :

pourquoi tu veux écraser le retour du remove_if ?


 
Ce truc remonte de l'année dernière, où un prof me l'avait donnée. Réponse sur http://www.sgi.com/tech/stl/remove_if.html, dans la Note [1].
 

Citation :

tu peux toujours faire ta propre méthode, en revanche :  [...]


 
Plutôt bien ton algo, mais un truc du type :
 

Code :
  1. while((it = std::find_if( it , mm.end(), cond)) != mm.end())
  2.     mm.erase(it);


 
plutôt que :
 

Code :
  1. while((it = std::find_if(mm.begin(), mm.end(), cond)) != mm.end())
  2.      mm.erase(it);


 
me conviendrait mieux (ça éviterait de re-chercher sur des pairs ne vérifiant pas la condition), mais l'itérateur est perdu à chaque erase. Une solution ?

n°1167680
theshockwa​ve
I work at a firm named Koslow
Posté le 02-08-2005 à 11:23:32  profilanswer
 

Citation :

Réponse sur http://www.sgi.com/tech/stl/remove_if.html, dans la Note [1].


Je note [:dawa]
 

Citation :

Une solution ?


 
Nope, pas de mon côté, en tout cas

n°1167687
ahmlot-khm​en
age = 5 ans
Posté le 02-08-2005 à 11:28:22  profilanswer
 

:jap: Merci beaucoup de ton aide, j'ai déjà une bonne solution :jap:
 
Il ne me reste plus qu'à trouver comment ne pas perdre cet itérateur ... si d'autres personnes ont une astuce ?

n°1167696
Taz
bisounours-codeur
Posté le 02-08-2005 à 11:34:11  profilanswer
 

return !e.second.size();
 
perdu, c'est pas encore ça ... not e.empty()

mood
Publicité
Posté le 02-08-2005 à 11:34:11  profilanswer
 

n°1167701
theshockwa​ve
I work at a firm named Koslow
Posté le 02-08-2005 à 11:39:00  profilanswer
 

ah, oui, tiens [:petrus75]

n°1167708
ahmlot-khm​en
age = 5 ans
Posté le 02-08-2005 à 11:48:05  profilanswer
 

Le but est de trouver les éléments e.second vides, cond doit donc retourner true si e.second est vide.
Dans le cas où ça l'est, e.second.size() vaut 0 (== false) donc !e.second.size() vaut true, ce qui est le booléen recherché (non ?).
 
Mais effectivement e.second.empty() fait la même chose (plus vite ?).
 
Une solution pour la perte d'itérateur lors du erase ?

n°1167722
theshockwa​ve
I work at a firm named Koslow
Posté le 02-08-2005 à 11:56:33  profilanswer
 

ahmlot-khmen a écrit :

Mais effectivement e.second.empty() fait la même chose (plus vite ?).


 
J'imagine qu'on ne peut pas garantir que ce sera fait plus vite (ca dépend de l'implémentation) mais en tout cas, ca n'a aucune chance d'être plus lent que de comparer la taille à 0 :jap:

n°1167898
theshockwa​ve
I work at a firm named Koslow
Posté le 02-08-2005 à 14:45:06  profilanswer
 

Code :
  1. struct KeysFunctor {
  2. std::list<std::string> keys;
  3. void operator()(const std::pair<const std::string, std::vector<int> > &e) {
  4.  if(e.second.empty())
  5.   keys.push_back(e.first);
  6. }
  7. };
  8. int main() {
  9. std::multimap<std::string, std::vector<int> > mm;
  10. KeysFunctor keysFunct;
  11. std::for_each(mm.begin(), mm.end(), keysFunct);
  12. for(std::list<std::string>::const_iterator it = keysFunct.keys.begin(); it != keysFunct.keys.end(); ++it)
  13.  mm.erase(*it);
  14. return 0;
  15. }


 
Je ne sais pas trop si ca colle à ce que tu veux, à vrai dire, vu que je ne sais pas s'il est plus coûteux de faire un erase sur une clé que sur un iterateur (de même, j'imagine que ca dépendra toujours de l'implémentation de la STL ...)

n°1167962
ahmlot-khm​en
age = 5 ans
Posté le 02-08-2005 à 15:20:50  profilanswer
 

Je n'ai pas tester ton code, mais je pense qu'il ne marche pas dans le cas où par exemple j'aurais deux pair :
 une < "toto", <>  >  
 une < "toto" , <1, 2, 3> >  
(placés de n'importe quelle manière dans ma multimap), amha le erase doit effacer aléatoirement le bon ou le mauvais.

n°1167980
theshockwa​ve
I work at a firm named Koslow
Posté le 02-08-2005 à 15:30:50  profilanswer
 

il me semble me souvenir qu'il y avait eu un problème de suppression de plusieurs éléments dans une map récemment (pas multimap, donc, mais ca passait par des itérateurs, donc ca doit aussi pouvoir s'appliquer pour toi), sur ce même forum. Tu peux peut-être essayer d'y jeter un oeil
 
Edit : Typo


Message édité par theshockwave le 02-08-2005 à 15:31:10
n°1168021
ahmlot-khm​en
age = 5 ans
Posté le 02-08-2005 à 15:52:27  profilanswer
 

cherchi, pas trouvi, quand meme merci :)

n°1168023
theshockwa​ve
I work at a firm named Koslow
Posté le 02-08-2005 à 15:53:47  profilanswer
 

j'essayerai de le rechercher ce soir, j'ai pas trop le temps de faire ca maintenant ( le C# m'occuppe trop :/ )

n°1168072
Taz
bisounours-codeur
Posté le 02-08-2005 à 16:35:18  profilanswer
 

empty() est plus rapide en général (sauf pour vector à priori) car size() peut être O(n). Et puis sémantiquement, c'est mieux

n°1170721
ahmlot-khm​en
age = 5 ans
Posté le 05-08-2005 à 14:46:51  profilanswer
 

En plus de la perte d'iterator pendant l'effaçage de la multimap (au fait theShOcKwAvE si jamais tu pouvais retrouver le sujet, ça m'intéresserait) j'aimerais également savoir comment, lorsqu'on parcours une multimap, savoir que l'on est sur le dernier élément.
 

Code :
  1. using namespace std;
  2. #include <string>
  3. #include <vector>
  4. #include <map>
  5. multimap<string, vector<int> > maM;
  6. // [on remplit la multimap]
  7. for (multimap<string, vector<int> >::iterator it = maM.begin() ; it != maM.end() ; ++it)
  8. {
  9.     if (/* condition pour détecter le dernier élément */)
  10.     {
  11.         // actions ...
  12.     }
  13. }


 
Et ne me dites pas rend() qui ne fonctionne qu'avec un reverse_iterator.
 
Pour l'instant, j'ai triché :) en transformant mon for en while, et en incrémentant avant mon test qui vérifie du coup l'égalité avec end.
 
Pas de manière plus élégante ? (et qui permettrait de garder la boucle for
 
a.k.

n°1170726
Taz
bisounours-codeur
Posté le 05-08-2005 à 14:54:29  profilanswer
 

ben le dernier c'est si cur + 1 == end()
 
ça serait très maladroit de mettre un tel test dans ta boucle. mieux vaut faire une boucle sur n-1 éléments et mettre le traitement du dernier en dehors

n°1170737
ahmlot-khm​en
age = 5 ans
Posté le 05-08-2005 à 15:20:37  profilanswer
 

Citation :

cur + 1 == end()


ça malheureusement avec une multimap, il ne veut pas (pas les bons iterateurs)
 

Citation :

mieux vaut faire une boucle sur n-1 éléments et mettre le traitement du dernier en dehors


je n'aime pas trop m'occuper des "exceptions" hors de la boucle, je trouve ça plus propre de tout faire dans une boucle (question de goût peut-être ...)

n°1170748
Taz
bisounours-codeur
Posté le 05-08-2005 à 15:28:17  profilanswer
 

je suis sur que si tu cherches un peu tu trouverais comment exprimé x + 1 autrement ...
 
c'est dégueux de gérer tous les cas limites dans la boucle, et surtout c'est très pénalisant en performance. ça pue complet la boucle
 
pour tous les éléments :
  si c'est le dernier :
     faire ça
  sinon :
     faire si
 
c'est très mauvais, même en lisibilité. tu mélanges des traitement différents ...

n°1170772
Taz
bisounours-codeur
Posté le 05-08-2005 à 15:49:03  profilanswer
 

Code :
  1. template<typename InputIterator>
  2.   void tous_sauf_dernier(InputIterator begin, InputIterator end)
  3.   {
  4.     if (begin == end)
  5.       return;
  6.     InputIterator last(end);
  7.     --last;
  8.     while (begin != last) {
  9.       std::cout << begin->first << ", ";
  10.       ++begin;
  11.     }
  12.     std::cout << '\n'
  13.       << "Last is : << " << last->first << '\n';
  14.   }

mood
Publicité
Posté le   profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  STL - multimap - ou le mystère de l'iterator perdu (non résolu)

 

Sujets relatifs
[JavaScript] Concaténer des chaines pour faire un nom de var. [Résolu][php] [RESOLU] probleme de tableau
[php] [RESOLU] lancer un fichier excel avec un headerpb de requête [RESOLU]
[résolu] Générer aléatoirement des donnéesSQL sous SPIP je suis perdu!
[résolu][pyGTK]question de débutant - fixer les dimentions d'un TextVi[PHP][Resolu] Sortir du php proprement
[resolu]Warning qui s'affiche malgré un traitement de l' erreur[Résolu] Dephi - Webbrowser
Plus de sujets relatifs à : STL - multimap - ou le mystère de l'iterator perdu (non résolu)


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR