[STL] Parcours de maps de maps de char*

Version imprimable

Bonjour à tous :)

Voici un résumé du code qui me pose un petit problème :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
typedef map<char*, char*> M_OID;
typedef map<char*, M_OID> M_OIDS;
typedef map<char*, M_OIDS> M_PDUS;
typedef map<char*, M_PDUS> M_LOGONS;
typedef map<char*, M_LOGONS> M_STS;
 
M_OID mapOid;
M_OIDS mapOids;
M_PDUS mapPdus;
M_LOGONS mapLogons;
M_STS mapSts;
 
 
void fillMaps()
{
	mapOid["Name"] = ".1.2";	
	mapOids["OID12"] = mapOid;
	mapPdus["pdu1"] = mapOids;
	mapLogons["Normal"] = mapPdus;
	mapSts["ABC123"] = mapLogons;
}
 
 
void readMaps()
{
	M_OIDS::iterator itOid;
	M_PDUS::iterator itPdu;
	M_LOGONS::iterator itLogon;
	M_STS::iterator itSt;
 
	M_OID mapOidFound;
	M_OIDS mapOidsBrowsed;
	M_PDUS mapPdusFound;
	M_LOGONS mapLogonsFound;
 
	itSt = mapSts.find("ABC123");
	if ( itSt != mapSts.end() )
	{
		mapLogonsFound = itSt->second;
 
		itLogon = mapLogonsFound.find("Normal");
		if ( itLogon != mapLogonsFound.end() )
		{
			mapPdusFound = itLogon->second;
 
			// Dans mon code réel, je ne connais pas le nom de la PDU où se trouve l'OID recherché,
			// alors je vais toutes les parcourir
			for ( itPdu = mapPdusFound.begin(); itPdu != mapPdusFound.end(); itPdu++ ) 
			{
				mapOidsBrowsed = itPdu->second;
 
				itOid = mapOidsBrowsed.find("OID12");
				if ( itOid != mapOidsBrowsed.end() )
				{
					mapOidFound = itOid->second;
 
					printf("OID Found: %s", mapOidFound["Name"]); 
				}
			}
		}
	}
}
 
 
void main()
{
	fillMaps();
	readMaps();
}

En effet, j'ai une erreur sur chacune des lignes de type : <= Edit : Corrigé par Poukill :)

Code:

mapxFound = itX->second();
De plus, le find ne semble pas fonctionner... : lors du " if iterator != map.end() " il ne rentre jamais dans le then...

Où se trouve le problème d'après vous ? Car là j'avoue que je sèche complètement...

Merci d'avance pour votre aide !

13/07/2007, 12h25
poukill
Code:

mapxFound = itX->second;

suffira!

Quelques remarques:
- pourquoi utiliser des char*, et pas des std::string ?
- Le printf peut avantageusement être remplacé par un std::cout
13/07/2007, 14h05
FenX.

Tout simplement, suis-je bête :D

Concernant le fait que j'utilise des char* et printf, c'est à cause du programme que je dois faire évoluer et qui a déjà été ( mal ! ) codé de cette manière... :(

Et concernant mon problème de find ? :(

Merci beaucoup pour ta réponse en tout cas :)
13/07/2007, 14h33
Laurent Gomila

find ne pourra jamais fonctionner avec des char*, car la comparaison se fera sur les adresses et non sur le contenu des chaînes.
13/07/2007, 14h46
poukill

Remplace tes char* par des std::string ! ;)

Euh... Laurent, j'ai trouvé ça dans la doc de la STL:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};
 
int main()
{
  map<const char*, int, ltstr> months;
 
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
 
  cout << "june -> " << months["june"] << endl;
  map<const char*, int, ltstr>::iterator cur  = months.find("june");
  map<const char*, int, ltstr>::iterator prev = cur;
  map<const char*, int, ltstr>::iterator next = cur;    
  ++next;
  --prev;
  cout << "Previous (in alphabetical order) is " << (*prev).first << endl;
  cout << "Next (in alphabetical order) is " << (*next).first << endl;
}

Y'a bien des char * non? :koi:
Et l'utilisation de find ne pose pas de problèmes ?

13/07/2007, 14h57
r0d

En fait, j'allais en parler. C'est faisable, mais en créant une nouvelle classe map qui modifie la politique (cf. faq c++ => classe de politique)
13/07/2007, 15h03
Laurent Gomila

Citation:

Y'a bien des char * non?
Et l'utilisation de find ne pose pas de problèmes ?

Tu vois bien qu'on est obligé de lui passer en plus un foncteur qui va réaliser une comparaison de chaînes plutôt que la comparaison de pointeurs qui aurait été faite par défaut.
13/07/2007, 15h16
poukill

Oui, bien sûr!
Mais le fait qu'on aie

Code:

strcmp(s1, s2) < 0

ne va t-il pas produire des erreurs lorsqu'on va utiliser la méthode find?

[QUOTE = cplusplus]A zero value indicates that both strings are equal.
A value greater than zero indicates that the first character that does not match has a greater value in str1 than in str2; And a value less than zero indicates the opposite.[/QUOTE]
Si on a une valeur positive pour strcmp, ça revenir au même que si on avait zéro, i.e les deux chaines sont identiques ? 8O
Y'a pas un problème là ?
13/07/2007, 15h27
Laurent Gomila

Non, strcmp renvoie :
- Une valeur négative si la première chaîne est inférieure à la seconde
- Zéro si les chaînes sont identiques
- Une valeur positive si la première chaîne est supérieure à la seconde

Donc, pour avoir s1 < s2, il faut bien renvoyer strcmp(s1, s2) < 0.
13/07/2007, 15h40
FenX.
En ajoutant, au début de mon code :
Code:

1 2 3 4 5 6 7 8 struct ltstr { bool operator()(const char* s1, const char* s2) const { return strcmp(s1, s2) < 0; } };
et en déclarant mes maps de la manière suivante :
Code:

1 2 3 map<char*, char*, ltstr> M_OID; ...
Cela fonctionne pour mon exemple :)
Mais cela fonctionnera-t-il dans tous les cas, d'après vous ?

Oui bien sûr, mais pour la méthode find !

Code:

map<const char*, int, ltstr>::iterator cur = months.find("june");

Il va y avoir une comparaison de chaine de caractère définie par le foncteur.
Par exemple la comparaison entre "june" et "september" sera juste vu que strcmp("june", "september") > 0...

Dans l'exemple précédent,
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 struct ltstr { bool operator()(const char* s1, const char* s2) const { return strcmp(s1, s2) < 0; } }; int main() { map<const char*, int, ltstr> months; months["january"] = 31; months["february"] = 28; months["march"] = 31; months["april"] = 30; months["may"] = 31; months["june"] = 30; months["july"] = 31; months["august"] = 31; months["september"] = 30; months["october"] = 31; months["november"] = 30; months["december"] = 31; map<const char*, int, ltstr>::iterator cur = months.find("juuuuune"); }
L'itérateur en question va bien trouver une valeur > 0 avant d'arriver à la fin de la map, même si "juuuuune" n'existe pas.
Disons qu'il n'y a pas moyen de tester si la valeur était vraiment dans la map.

13/07/2007, 15h47
poukill
Citation:
Envoyé par FenX.

En ajoutant, au début de mon code :

Code:

1 2 3 4 5 6 7 8 struct ltstr { bool operator()(const char* s1, const char* s2) const { return strcmp(s1, s2) < 0; } };

et en déclarant mes maps de la manière suivante :

Code:

1 2 3 map<char*, char*, ltstr> M_OID; ...

Cela fonctionne pour mon exemple :)
Mais cela fonctionnera-t-il dans tous les cas, d'après vous ?
Dans ton exemple oui.
Après moi je te le déconseille fortement. Car quand tu auras plusieurs valeurs, ton itSt != mapSts.end() n'aura plus aucun sens. Il ne t'assura pas que ta valeur n'était pas dans ta map.
13/07/2007, 15h54
Laurent Gomila

Citation:

L'itérateur en question va bien trouver une valeur > 0 avant d'arriver à la fin de la map, même si "juuuuune" n'existe pas.
Disons qu'il n'y a pas moyen de tester si la valeur était vraiment dans la map.

Citation:

Après moi je te le déconseille fortement. Car quand tu auras plusieurs valeurs, ton itSt != mapSts.end() n'aura plus aucun sens. Il ne t'assura pas que ta valeur n'était pas dans ta map.

Qu'est-ce que tu veux dire par là ? A partir du moment où le foncteur de comparaison définit une relation < valide (strict weak ordering -- me rappelle plus les termes français), alors le conteneur fonctionnera correctement. En l'occurence si end() est renvoyé c'est que l'élément ne figure pas dans le conteneur.
13/07/2007, 16h17
poukill

Que va t-il se passer si on fait un:

Code:

map<const char*, int, ltstr>::iterator cur = months.find("juuuuune");

dans la map précédente avec les mois?
Va t-il valloir end()?
Avec l'opérateur de comparaison défini, l'itérateur pointera vers "november" non?
Car "november" est le premier élément du conteneur dont le strcmp est > 0...

Je dois avoir tord, mais j'arrive pas à exprimer clairement mon idée là dessus. :aie:
13/07/2007, 16h37
Laurent Gomila

Il va se passer que tu vas récupérer end(), puisque "juuuuune" n'est pas dans le conteneur.

Citation:

Avec l'opérateur de comparaison défini, l'itérateur pointera vers "november" non?
Car "november" est le premier élément du conteneur dont le strcmp est > 0...

Et pourquoi il ferait ça ? Comment penses-tu que l'algorithme de recherche fonctionne ? ;)
13/07/2007, 16h55
poukill

Ben je pensais que l'exemple dans la STL était du pseudo "bol", car la map est triée suivant le foncteur. Ainsi l'ordre des mois n'est plus respectée (ce qui est normal).
Ensuite, lors de la recherche avec find, il parcours tous les éléments du conteneurs à commencer par begin(), i.e le premier élément toujours suivant l'ordre de tri décidé par le foncteur...
Dans tous les premiers cas, la comparaison entre l'élément recherché ("juuuune") et l'élément pointé par l'itérateur sera du même signe (à cause du tri préalable). Et puis quand il trouve l'élément il renvoit 0.
Mais il n'y a pas de diffrérence entre 0 et 1 puisque le tri se fait suivant strcmp < 0. 0 et 1 ont donc le même status...

C'est pourquoi la fonction find fonctionne dans l'exemple de la STL, grâce au tri préalable. Mais à la différence d'un conteneur où on compare des std::string (là on teste une égalité et pas une comparaison), si une valeur n'est pas dans le conteneur, que va t-il se passer?
Pour juuuuune, lorsque l'itérateur pointera sur "september", la valeur de strcmp sera > 0, non?

J'espère que tu vas éclairer ma lanterne, car je suis un peu perdu là ! 8O

Tu te trompes, 0 et 1 ne sont pas équivalents, et std::map n'utilise aucune égalité, seulement l'équivalence. Deux éléments X et Y sont équivalents si et seulement si !Pred(X, Y) et !Pred(Y, X) (avec Pred le foncteur perso, ou l'opérateur < par défaut).

En gros voici comment l'algo de recherche pourrait être implémenté (je rappelle que std::map est implémenté avec une structure d'arbre binaire) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 iterator map::node::find(const ELT& element) { if (Pred(element, key)) { // L'élement est inférieur à la clé du noeud courant : // on recherche dans le sous-arbre gauche return left ? left->find(element) : end(); } else if (Pred(key, element)) { // L'élement est supérieur à la clé du noeud courant : // on recherche dans le sous-arbre droit return right ? right->find(element) : end(); } else { // L'élément est équivalent à la clé du noeud courant // (ni inférieur ni supérieur -- mais pas nécessairement égal !) // donc on l'a trouvé return iterator(this); } }

13/07/2007, 18h02
poukill
Ouuulà OK j'étais complètement à l'Ouest ! :lol:
Je ne savais pas comment fonctionnait le find de la STL. Oui effectivement ici avec le double prédicat à respecter, évidemment "juuuune" ne sera pas trouvé.

Merci Laurent! C'est bon pour moi! ;)

Pour revenir au post initial, oui tu peux utiliser ce foncteur pour ton programme. En gros, tu as deux solutions:
- remplacer char* par std::string pour permettre la comparaison d'éléments.
- Définir ce foncteur dans tes map.
Bonne continuation ! :)
17/07/2007, 09h50
FenX.

J'ai utilisé le foncteur car j'étais contraint par le reste du code existant :)

Merci à tous pour votre aide et vos explications on ne peut plus claires !