Discussion :

[douls]

bonjour,
Je cherche à créer une table à hachage externe(cette table doit contenir des informations sur des clients). Pour ce faire la seul solution que j'ai trouvé actuellement est de créer une map qui contient des vectors de type client: La déclaration devient alors map<int , vector <Client> > HashTable;


La déclaration de cette variable s'effectue dans une autre classe:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Classe Client 
{
 
private:
      string nom;
      ....
 
}
 
Classe Hash
{
private:
       map<int , vector <Client> > HashTable;
}

Le problème que je rencontre est de pouvoir utiliser les fonctions associé à vectors.
Par exemple :

Code :

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

1
2
3
4
5
6
void Hash::afficher(Client Cl)
{
	int cle=Cl.cleHashage();
 
	cout << HashTable[cle].begin(); // L'opérateur << est surchargé dans la classe Client.
}

L'erreur du compilateur est (pour visual studio 2008 ) :

Error 1 error C2679: binary '<<' : no operator found which takes a right-hand operand of type 'std::_Vector_iterator<_Ty,_Alloc>' (or there is no acceptable conversion)

Ceux qui voudrait dire selon moi que HashTable[cle] n'est pas considérée comme un Client.

De plus autre erreur mais avec une autre fonction :

Code :

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

1
2
3
4
5
6
void Hash::ajouter(Client Cl)
{
	int cle=Cl.cleHashage();
 
	Clients[cle].push_back(Cl); 
}

le compilateur me donne comme erreur :

Error 1 error C2558: class 'Client' : no copy constructor available or copy constructor is declared 'explicit'

Ca je ne comprend pas.


Merci d'avance,

Douls

[coyotte507]

Bonsoir,

Code :

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

1
2
3
4
5
6
void Hash::afficher(Client Cl)
{
	int cle=Cl.cleHashage();
 
	cout << *(HashTable[cle].begin()); // L'opérateur << est surchargé dans la classe Client.
}

(renseigne-toi sur les iterators)

et:

Code :

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

1
2
3
4
5
6
7
void Hash::ajouter(Client Cl)
{
	int cle=Cl.cleHashage();
 
        //erreur si cle >= Clients.size(), utiliser Clients.resize() pour réserver de la place
	Clients[cle]= Cl; 
}

Un peu plus sur la STL (vectors, maps): http://www.cplusplus.com/reference/stl/

Néanmoins j'ai peur que tu aies des problèmes à l'exécution, sans autre code je ne peux rien dire...

[JolyLoic]

bonjour,
Je cherche à créer une table à hachage externe(cette table doit contenir des informations sur des clients).

Tu sais qu'il existe déjà des hash_table avec la plupart des compilateurs ? Ceux qui implémentent l'extension TR1du standard (tu parles de visual studio 2008 plus loin, il l'implémente avec le feature pack, dont je parle ici : http://loic-joly.developpez.com/futur-vc++/) ont std::unordered_map, mais même souvent les autres ont quelquechose d'équivalent.

Code :

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

1
2
3
4
5
6
 
Classe Hash
{
private:
       map<int , vector <Client> > HashTable;
}

Le problème que je rencontre est de pouvoir utiliser les fonctions associé à vectors.
Par exemple :

Code :

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

1
2
3
4
5
6
void Hash::afficher(Client Cl)
{
	int cle=Cl.cleHashage();
 
	cout << HashTable[cle].begin(); // L'opérateur << est surchargé dans la classe Client.
}

begin retourne un itérateur sur le vecteur. Un itérateur n'est pas directement affichable. Essaye cout << *(HashTable[cle].begin()); ou bien cout << HashTable[cle].front();
(dans les deux cas, attention à gérer le cas vector vide)

Code :

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

1
2
3
4
5
6
void Hash::ajouter(Client Cl)
{
	int cle=Cl.cleHashage();
 
	Clients[cle].push_back(Cl); 
}

le compilateur me donne comme erreur :

Error 1 error C2558: class 'Client' : no copy constructor available or copy constructor is declared 'explicit'

Tu aurais le même problème avec un simple vector<Client> dans lequel tu voudrais ajouter des éléments. Les données qu'on peut mettre dans un vector doivent répondre à certains critères, comme d'être copiables, ce qui n'est visiblement pas le cas de Client. Les solutions classiques sont soit de rendre Client copiable, soit si ça n'a pas de sens, faire un vector<Client*>, ou d'une variante de pointeur intelligent, ou utiliser boost::ptr_vector.

[douls]

Tu sais qu'il existe déjà des hash_table avec la plupart des compilateurs ? Ceux qui implémentent l'extension TR1du standard (tu parles de visual studio 2008 plus loin, il l'implémente avec le feature pack, dont je parle ici : http://loic-joly.developpez.com/futur-vc++/) ont std::unordered_map, mais même souvent les autres ont quelquechose d'équivalent.

Ça va faire presque 2 semaines que je cherche sans répits une fonction de hash_table sans aucune réussite

C'est pourquoi je me suis rabattu sur map.

Serait-il possible que tu me donnes un exemple ou un site qui en parle s'il te plait?

De plus je suis un peu novice en C++ donc il y a certaine fonction telle que boost::ptr_vector que je ne connais pas encore

En tous cas merci à vous deux pour m'avoir prodigué un peu d'aide dans ce monde de code ...

[JolyLoic]

http://www.dinkumware.com/manuals/?m...dered_map.html

http://www.open-std.org/jtc1/sc22/wg...003/n1456.html
Fourni aussi des explications sur les choix de design effectués

[douls]

Merci je vais étudier cela

[douls]

Bon je comprend pas du tout comme faire une table de hachage externe...

[douls]

J'ai changé un peu mon code pour pouvoir avoir des list dans les cases de ma map:

Code :

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

1
2
3
4
5
 
map < int , Client > m_Clients;
map< int,Client >::iterator it;
list < Client*  > test;
list < Client *>::iterator i;

Après dans mon fonction je fais ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
void JMClients::Ajouter(JMClient Cl)
{
	int cle=Cl.cleHashage();
 
	JMClient *Cl1=&Cl; 
	test.push_front(Cl1);
	i=test.begin();
	for ( i=test.begin();i!=test.end(); i++ )
	cout << " " <<  *i << endl;

et la j'obtient l'adresse de Cl dans le cout et moi je voudrais avoir le contenu...

De plus maintenant que j'ai ma list creer je voudrais l'ajouter dans ma map à la bonne clé ? Comment je peux faire?
}

[coyotte507]

Salut,

pour la première question, c'est:

Code :

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

cout << *(*i) << endl;

Pour ajouter à ta map, je verrais bien:

Code :

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

1
2
for ( i=test.begin();i!=test.end(); i++ )
m_Clients[(*i)->cleHashage()] = *(*i);

[JolyLoic]

Voici un bout de code qui j'espère devrait te donner plus d'informations sur comment utiliser ce genre de conteneur.

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
#include <iostream>
#include <unordered_map>
 
 
using namespace std;
 
class Personne
{
public:
	Personne (string n, string p) : nom(n), prenom(p) {}
	string nom;
	string prenom;
};
 
bool operator==(Personne const &p1, Personne const &p2)
{
	return p1.nom == p2.nom && p1.prenom == p2.prenom;
}
 
class Hash
{
public:
	size_t operator()(Personne const &p) const
	{
		std::tr1::hash<string> h;
		return h(p.nom) * h(p.prenom);
	}
};
 
 
int main()
{
	typedef std::tr1::unordered_map<Personne, int, Hash> MyHashMap;
	MyHashMap map;
	map[Personne("Potter", "Harry")] = 10;
	map[Personne("Potter", "Severus")] = 2;
	map[Personne("Potter", "Harry")] = 42;
	map[Personne("Snape", "Severus")] = 6;
	for(MyHashMap::iterator it = map.begin();
		it != map.end();
		++it)
	{
		std::cout << it->first.nom << " " << it->first.prenom << " : " << it->second << endl;
	}
}

[douls]

Voici un bout de code qui j'espère devrait te donner plus d'informations sur comment utiliser ce genre de conteneur.

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
#include <iostream>
#include <unordered_map>
 
 
using namespace std;
 
class Personne
{
public:
	Personne (string n, string p) : nom(n), prenom(p) {}
	string nom;
	string prenom;
};
 
bool operator==(Personne const &p1, Personne const &p2)
{
	return p1.nom == p2.nom && p1.prenom == p2.prenom;
}
 
class Hash
{
public:
	size_t operator()(Personne const &p) const
	{
		std::tr1::hash<string> h;
		return h(p.nom) * h(p.prenom);
	}
};
 
 
int main()
{
	typedef std::tr1::unordered_map<Personne, int, Hash> MyHashMap;
	MyHashMap map;
	map[Personne("Potter", "Harry")] = 10;
	map[Personne("Potter", "Severus")] = 2;
	map[Personne("Potter", "Harry")] = 42;
	map[Personne("Snape", "Severus")] = 6;
	for(MyHashMap::iterator it = map.begin();
		it != map.end();
		++it)
	{
		std::cout << it->first.nom << " " << it->first.prenom << " : " << it->second << endl;
	}
}

Merci beaucoup.

Par contre j'ai un nouveau problème quand j'essaye d'exécuter ton code visual studio 2008 me dit :
Error 1 fatal error C1083: Cannot open include file: 'unordered_map':

Ce qui m'étonne c'est que normalement la bibliothèque unordered_map est incluse dans visual 2008 (enfin si j'ai bien compris les différents lien)

[JolyLoic]

Nan, il faut installer le feature pack, qui est une sorte de mini SP1 du studio, sauf qu'au lieu de corriger des bugs, il ajoute des fonctionnalités. Tu devrais trouver un lien d'installation dans mon article ou avec ton moteur de recherche préféré...

Si pour une raison x ou y tu ne veux/peux pas l'installer, tu as quand même accès à une hash map non standard dans visual studio, mais elle porte un autre nom, et a probablement une interface légèrement différente, que je ne connais pas.

[douls]

Yop,

Voila j'ai pu tester et le cout me donne :

Potter Harry : 42
Potter Severus : 2
Snape Severus : 6

Mais qu'en est-il de la ligne

Code :

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

 map[Personne("Potter", "Harry")] = 10;

Enfin la valeur est remplacéé par le 42? Parce que moi justement je voudrais que quand il ya collisions les valeurs ne soit pas remplacée mais s'ajouter dans la case de manière à ce qu'on est :

Potter Harry : 10
Potter Harry : 42
Potter Severus : 2
Snape Severus : 6

[JolyLoic]

Oui. Dans un map, il n'y a qu'une valeur possible associée à chaque clef.

Si tu veux associer plusieurs valeurs :
- Soit tu fais un unordered_map<string, vector<int> >
- Soit tu utilises un unordered_multimap<string, int>

[douls]

Oui. Dans un map, il n'y a qu'une valeur possible associée à chaque clef.

Si tu veux associer plusieurs valeurs :
- Soit tu fais un unordered_map<string, vector<int> >
- Soit tu utilises un unordered_multimap<string, int>

Humm c'est un peu la même méthode que je voulais utiliser dans le titre de mon thread.


Mais je sais pas comment utiliser, avoir accès au vector<int> des différentes cases de ma hash_table ....

[JolyLoic]

Je ne suis pas trop.... Tel que j'avais compris le besoin initial, tu voulais avoir une map<int, vector<Client> > de manière à implémenter une hash map.

Je te proposes un unordered_map<Client, ...> qui est une hash map. Là, tu me dis que les ... tu veux que ce soit un vector<int>, pourquoi pas, mais j'ai l'impression qu'il y a eu une marche loupée quelque part, et que tu veux de nouveau te servir de unordered_map<..., vector<...> > pour implémenter une hash_map, alors que c'en est déjà une...

Peut-être que ce qui te trompe est que j'ai parlé d'une map, qui associe une donnée à une clef, alors que toi tu n'as pas de donnée à associer à un client ? Si c'est le cas, unordered_set<Client> est peut-être la structure qui te convient : Un conteneur de Clients, que l'on retrouve à l'aide d'une table de hash.

[douls]

Bon j'ai trouvé une solution alternative et j'utilise le multimap de la bibliothèque STL.


Merci bcp à tout le monde pour votre aide