C++

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

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : STL - multimap - ou le mystère de l'iterator perdu (non résolu)

ahmlot-khmen

age = 5 ans

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

Publicité

theshockwave

I work at a firm named Koslow

#include <algorithm>

std::remove_if

non ?

ahmlot-khmen

age = 5 ans

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 ?

theshockwave

I work at a firm named Koslow

Code :

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

Message édité par theshockwave le 02-08-2005 à 10:24:08

ahmlot-khmen

age = 5 ans

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 :

multimap<string, vector<int> > pMaMultimap;
pMaMultimap.erase(remove_if(pMaMultimap.begin(), pMaMultimap.end(),
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.

theshockwave

I work at a firm named Koslow

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

bool cond(const std::pair<const std::string, std::vector<int> > &e) {
return !e.second.size();
}
int main() {
std::multimap<std::string, std::vector<int> > mm;
std::multimap<std::string, std::vector<int> >::iterator it;
while((it = std::find_if(mm.begin(), mm.end(), cond)) != mm.end())
mm.erase(it);
return 0;
}

ahmlot-khmen

age = 5 ans

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 :

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

plutôt que :

Code :

while((it = std::find_if(mm.begin(), mm.end(), cond)) != mm.end())
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 ?

theshockwave

I work at a firm named Koslow

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

ahmlot-khmen

age = 5 ans

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

Taz

bisounours-codeur

return !e.second.size();

perdu, c'est pas encore ça ... not e.empty()

Publicité

theshockwave

I work at a firm named Koslow

ah, oui, tiens [:petrus75]

ahmlot-khmen

age = 5 ans

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 ?

theshockwave

I work at a firm named Koslow

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:

theshockwave

I work at a firm named Koslow

Code :

struct KeysFunctor {
std::list<std::string> keys;
void operator()(const std::pair<const std::string, std::vector<int> > &e) {
if(e.second.empty())
keys.push_back(e.first);
}
};
int main() {
std::multimap<std::string, std::vector<int> > mm;
KeysFunctor keysFunct;
std::for_each(mm.begin(), mm.end(), keysFunct);
for(std::list<std::string>::const_iterator it = keysFunct.keys.begin(); it != keysFunct.keys.end(); ++it)
mm.erase(*it);
return 0;
}

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

ahmlot-khmen

age = 5 ans

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.

theshockwave

I work at a firm named Koslow

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

ahmlot-khmen

age = 5 ans

cherchi, pas trouvi, quand meme merci

theshockwave

I work at a firm named Koslow

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

Taz

bisounours-codeur

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

ahmlot-khmen

age = 5 ans

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 :

using namespace std;
#include <string>
#include <vector>
#include <map>
multimap<string, vector<int> > maM;
// [on remplit la multimap]
for (multimap<string, vector<int> >::iterator it = maM.begin() ; it != maM.end() ; ++it)
{
if (/* condition pour détecter le dernier élément */)
{
// actions ...
}
}

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.

Taz

bisounours-codeur

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

ahmlot-khmen

age = 5 ans

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

Taz

bisounours-codeur

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

Taz

bisounours-codeur

Code :

template<typename InputIterator>
void tous_sauf_dernier(InputIterator begin, InputIterator end)
{
if (begin == end)
return;
InputIterator last(end);
--last;
while (begin != last) {
std::cout << begin->first << ", ";
++begin;
}
std::cout << '\n'
<< "Last is : << " << last->first << '\n';
}

Publicité

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 header	pb de requête [RESOLU]
[résolu] Générer aléatoirement des données	SQL 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)

Page générée en 0.091 secondes