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

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

Marsh Posté le 02-08-2005 à 09:26:55    

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
Reply

Marsh Posté le 02-08-2005 à 09:26:55   

Reply

Marsh Posté le 02-08-2005 à 09:39:19    

#include <algorithm>
 
std::remove_if
 
non ?

Reply

Marsh Posté le 02-08-2005 à 09:47:27    

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 ?

Reply

Marsh Posté le 02-08-2005 à 10:23:54    

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
Reply

Marsh Posté le 02-08-2005 à 10:37:24    

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;
  3. pMaMultimap.erase(remove_if(pMaMultimap.begin(), pMaMultimap.end(),
  4. 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.

Reply

Marsh Posté le 02-08-2005 à 10:50:14    

: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. }
  5. int main() {
  6. std::multimap<std::string, std::vector<int> > mm;
  7. std::multimap<std::string, std::vector<int> >::iterator it;
  8. while((it = std::find_if(mm.begin(), mm.end(), cond)) != mm.end())
  9.  mm.erase(it);
  10. return 0;
  11. }

Reply

Marsh Posté le 02-08-2005 à 11:07:15    

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 ?

Reply

Marsh Posté le 02-08-2005 à 11:23:32    

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

Reply

Marsh Posté le 02-08-2005 à 11:28:22    

: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 ?

Reply

Marsh Posté le 02-08-2005 à 11:34:11    

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

Reply

Marsh Posté le 02-08-2005 à 11:34:11   

Reply

Marsh Posté le 02-08-2005 à 11:39:00    

ah, oui, tiens [:petrus75]

Reply

Marsh Posté le 02-08-2005 à 11:48:05    

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 ?

Reply

Marsh Posté le 02-08-2005 à 11:56:33    

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:

Reply

Marsh Posté le 02-08-2005 à 14:45:06    

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. };
  9. int main() {
  10. std::multimap<std::string, std::vector<int> > mm;
  12. KeysFunctor keysFunct;
  13. std::for_each(mm.begin(), mm.end(), keysFunct);
  15. for(std::list<std::string>::const_iterator it = keysFunct.keys.begin(); it != keysFunct.keys.end(); ++it)
  16.  mm.erase(*it);
  17. return 0;
  18. }


 
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 ...)

Reply

Marsh Posté le 02-08-2005 à 15:20:50    

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.

Reply

Marsh Posté le 02-08-2005 à 15:30:50    

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
Reply

Marsh Posté le 02-08-2005 à 15:52:27    

cherchi, pas trouvi, quand meme merci :)

Reply

Marsh Posté le 02-08-2005 à 15:53:47    

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

Reply

Marsh Posté le 02-08-2005 à 16:35:18    

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

Reply

Marsh Posté le 05-08-2005 à 14:46:51    

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>
  6. multimap<string, vector<int> > maM;
  8. // [on remplit la multimap]
  10. for (multimap<string, vector<int> >::iterator it = maM.begin() ; it != maM.end() ; ++it)
  11. {
  12.     if (/* condition pour détecter le dernier élément */)
  13.     {
  14.         // actions ...
  15.     }
  16. }


 
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.

Reply

Marsh Posté le 05-08-2005 à 14:54:29    

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

Reply

Marsh Posté le 05-08-2005 à 15:20:37    

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 ...)

Reply

Marsh Posté le 05-08-2005 à 15:28:17    

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 ...

Reply

Marsh Posté le 05-08-2005 à 15:49:03    

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

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed