question sur les unordered_map

**deubelte** · 02/10/2010, 23h00

bonjour

J'ai une question concernant les unordered_map. C'est très simple:
je ne comprends pas pourquoi le code suivant ne retrouve pas dans la map l'élément correspondant à la clé "ddd".
merci

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 typedef std::unordered_map<const char*, int> Mymap; 
    Mymap c1;
    typedef Mymap::value_type type_sousjacent; 
    const char* u=new char[4];
	u="ddd";
 
	const char* w=new char[4];
	w="edd";
 
    c1.insert(type_sousjacent("ddd", 1));
    c1.insert(type_sousjacent("edd", 1)); 
	Mymap::key_type vv="ddd";
    Mymap::const_iterator it=c1.find(u);

(EDIT:en fait j'ai compris, du moins, je pense, c'est un pb d'adresse).
Mais je vois pas trop comment le résoudre

**Goten** · 02/10/2010, 23h35

Tu compares des pointeurs pas des chaines de caractères. La solution : introduit le bon prédicat. La meilleure solution, utilise des strings.

**deubelte** · 03/10/2010, 13h46

Le problème, c'est que si j'utilise un std::string:

Code :

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

1
2
3
4
5
    typedef std::unordered_map<std::string, int> Mymap; 
    Mymap c1;
    typedef Mymap::value_type type_sousjacent;
 std::string s="ddd";
	 c1.insert(type_sousjacent(s, 1));

j'obtiens comme erreur:

Error 3 error C2678: binary '==' : no operator found which takes a left-hand operand of type 'const std::string' (or there is no acceptable conversion)

**Goten** · 03/10/2010, 14h23

Poste un code complet minimal compilable.. parce que là ce que tu montres y'a pas de soucis ...

**deubelte** · 03/10/2010, 14h27

héhé, ca marche j'avais oublié le #include<string>

Mais en revanche, je veux utiliser le const char*.
Comment puis-je faire pour qu'il n'y ait pas de comparaison de pointeurs, mais d'objets pointés?

merci

**Arzar** · 03/10/2010, 15h00

Il faut que tu fournisses la fonction de hash qui va bien de la même manière qu'il faut fournir un prédicat à une std::map.

Une fonction de hash doit prendre en paramètre la clé et renvoyer un size_t.
Par exemple :

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
 
struct HashCStringFunc
{
   size_t operator()(const char* Key) const
   {
      size_t Val = 2166136261U;
      size_t First = 0;
      size_t Last = strlen(Key);
      size_t Stride = 1 + Last / 10;
 
      for(; First < Last; First += Stride)
         Val = 16777619U * Val ^ (size_t) Key[First];
      return (Val);
   }
};
 
int main()
{
   typedef std::unordered_map<const char*, int, HashCStringFunc> HashCString;
   HashCString m;
 
   m["ddd"] = 1;
   m["edd"] =  1; 
   HashCString::const_iterator it = m.find("ddd");
}

Évidement la difficulté est de choisir une bonne fonction de hash bien adapté au problème, car c'est elle qui va conditionner les performances de la hashtable. Pour l'exemple ci-dessus, vu que j'y connais rien dans ce domaine, j'ai juste repris la fonction de hash prévu à la base pour les std::string dans les headers de la STL fourni avec VS2010 en remplaçant par des char*.

HS :Au fait attention à ça :

Code :

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

1
2
3
 
   const char* u=new char[4];
   u="ddd";

C'est au mieux une fuite mémoire et au pire au segfault si tu fais un delete[] sur u, car u pointe maintenant sur la string-litteral "ddd".

**deubelte** · 03/10/2010, 15h17

Merci,
c'est bizarre qu'il faille fournier une fonction de hash.
Je pensais que la fonction était déjà fournie. N'y a t il pas une fonction fournie par défaut.

**deubelte** · 03/10/2010, 15h28

Au fait, je viens de tester ton prog, j'ai toujours la même erreur:
Badptr.

**Arzar** · 03/10/2010, 15h30

Dans VS2010 il y a des fonction de hash par défaut prévues pour unsigned long long et long long (pour couvrir tous les types entiers comme int, short etc), d'autres pour float, double et long double, et aussi d'autres pour std::string et std::wstring.

Il y a aussi une fonction de hash prévu pour les pointeurs mais elle hash la valeur du pointeur (l'adresse) et pas l'objet pointé. Ça me semble plutôt logique, comment une fonction de hash pourrait-elle deviner la bonne manière de hasher l'objet pointé ? Par exemple si je choisis comme clé des Toto* comment la hashmap est censé savoir hasher des Toto ? Et dans le cas des char* faut-il :
1) hasher la valeur du pointeur (l'adresse) ?
2) hasher la valeur du char pointée ?
3) Considérer que le char* est en fait une string terminé par un \0 et hasher comme une string ?
Y a pas vraiment de bonne réponse...

**Arzar** · 03/10/2010, 15h34

Badptr à quel moment ?

**deubelte** · 03/10/2010, 15h38

cf l'image

**Arzar** · 03/10/2010, 15h48

??
On est bien d'accord que ton programme est similaire à celui-ci :

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
 
#include <iostream>
#include <unordered_map>
 
struct HashStringFunc
{
   size_t operator()(const char* Key) const
   {
      std::cout << "Fonction de hash pour const char*" << std::endl;
      size_t Val = 2166136261U;
		size_t First = 0;
		size_t Last = strlen(Key);
		size_t Stride = 1 + Last / 10;
 
		for(; First < Last; First += Stride)
			Val = 16777619U * Val ^ (size_t) Key[First];
		return (Val);
   }
};
 
int main()
{
   typedef std::unordered_map<const char*, int, HashStringFunc> HashString;
   HashString m;
 
   m["ddd"] = 1;
   m["edd"] =  1; 
   HashString::const_iterator it = m.find("ddd");
   std::cout << it->first;
}

Qui est censé afficher sous VS2010 plusieurs fois ""Fonction de hash pour const char*" puis "ddd" ?

**deubelte** · 03/10/2010, 15h53

oui, j'ai fait un copié collé de ton code et:

Unhandled exception at 0x705528ec (msvcr100.dll) in Proj1.exe: 0xC0000005: Access violation reading location 0xbaadf00d.

**deubelte** · 03/10/2010, 22h05

en revanche, ca fonctionne parfaitement avec des int*:
cela ne me renvoie pas des bad ptr:

Code :

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

1
2
3
4
5
6
7
8
9
    typedef std::unordered_map<const int*, int> Mymap; 
    Mymap c1;
    typedef Mymap::value_type type_sousjacent;
 
	int* tab=new int[3];
	tab[0]=2;tab[1]=2;tab[2]=2;
 
	 c1.insert(type_sousjacent(tab, 1));
	  	Mymap::const_iterator dddd=c1.find(tab)

j'arrive pas à comprendre pq ca fonctionne pas dans l'autre cas.

**koala01** · 04/10/2010, 06h52

Salut,

Envoyé par deubelte

héhé, ca marche j'avais oublié le #include<string>

Mais en revanche, je veux utiliser le const char*.
Comment puis-je faire pour qu'il n'y ait pas de comparaison de pointeurs, mais d'objets pointés?

merci

A vrai dire, la première question qui me vient à l'esprit, c'est "pourquoi

"

Il n'y a que des inconvénients à vouloir manipuler des pointeurs sur char au lieu de chaines de caractères:

Cela t'oblige à gérer "par toi même" la mémoire allouée à tes pointeurs.
Un pointeur n'est jamais... qu'une variable numérique représentant une adresse mémoire, même lorsqu'il s'agit d'un pointeur sur char, destiné à représenter une chaine de caractères "C style", et il faut donc utiliser les fonctions C de manipulation de chaines pour manipuler ces dernières "correctement"
Il est possible de convertir un pointeur sur char en std::string de manière totalement transparente
Il est possible de récupérer une chaine de caractères "C style" au départ d'une std::string
Etant donné que la chaine de caractères sert de clé, il n'est pas opportun de laisser quoi que ce soit la modifier, surtout si on la manipule sous la forme d'une chaine C style

De plus, même si, pour une raison qui ne tient qu'à toi, tu venais à vouloir utiliser ton pointeur sur char sous la forme d'un... tableau de caractères (comprend: une succession de valeurs numérique comprises entre 0 et 255

), il serait alors largement préférable d'utiliser un ... std::vector<char>, pour les même raisons (ou du moins celles qui sont applicables)

**deubelte** · 04/10/2010, 08h52

Ok, mais en fait, je ne pense pas que ce soit possible d'utiliser un unordered_map sur des const char* dans le but de stocker, hacher, et surtout comparer des pointeurs, car même si dans mon esprit, il faut comparer une chaine de caractères, le compilateur va comparer le pointeur et non pas la chaine de caractères.

Si on passe un objet en valeur et non en adresse, il va falloir passer un string.

Le problème est que dans RogueWave, qui doit avoir 10 ans, il y a un moyen pour utiliser des unordered_map soit pour des valeurs, soit pour des pointeurs:

http://www2.roguewave.com/support/do...ictionary.html

http://www2.roguewave.com/support/do...ictionary.html

Mais le premier compare non pas des pointeurs, mais les objets pointés par ces pointeurs. Alors ma question est:

comment reproduire avec la STL/TR cette possibilité?

merci

question sur les unordered_map

C++

Discussions similaires

Partager

Partager