[STL] Parcours de maps de maps de char*

**FenX.** · 13/07/2007, 12h02

Bonjour à tous

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 : Sélectionner tout - Visualiser dans une fenêtre à part
```
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 !

**poukill** · 13/07/2007, 12h25

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**FenX.** · 13/07/2007, 14h05

Tout simplement, suis-je bête

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

**Laurent Gomila** · 13/07/2007, 14h33

find ne pourra jamais fonctionner avec des char*, car la comparaison se fera sur les adresses et non sur le contenu des chaînes.

**poukill** · 13/07/2007, 14h46

Remplace tes char* par des std::string !

**poukill** · 13/07/2007, 14h49

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

Et l'utilisation de find ne pose pas de problèmes ?

**r0d** · 13/07/2007, 14h57

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)

**Laurent Gomila** · 13/07/2007, 15h03

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.

**poukill** · 13/07/2007, 15h16

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

Y'a pas un problème là ?

**Laurent Gomila** · 13/07/2007, 15h27

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.

**FenX.** · 13/07/2007, 15h40

En ajoutant, au début de mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

**poukill** · 13/07/2007, 15h41

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**poukill** · 13/07/2007, 15h47

Envoyé par FenX.

En ajoutant, au début de mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**Laurent Gomila** · 13/07/2007, 15h54

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.

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.

**poukill** · 13/07/2007, 16h17

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**Laurent Gomila** · 13/07/2007, 16h37

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

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 ?

**poukill** · 13/07/2007, 16h55

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à !

**Laurent Gomila** · 13/07/2007, 17h08

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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);
    }
}

**poukill** · 13/07/2007, 18h02

Ouuulà OK j'étais complètement à l'Ouest !

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: