[STL] Exemple de Hash_set

txitxou wrote:

Bonjour à tous!

Salut !

je cherche actuellement un tutorial sur l'utilisation des hash_set inclues
dans la librarie STL de SGI.

Ce n'est pas exactement ce que tu cherches, et tu es peut-être déjà
tombé dessus :
http://www.sgi.com/tech/stl/hash_map.html

Je cherche en fait un exemple complet d'utilisation et pas simplement une
insertion ou une recherche comme on peut le voir dans MSDN.

Qu'est-ce que tu voudrais faire d'autre avec ?


A+

Christophe


--
Christophe de Vienne

Qu'est-ce que tu voudrais faire d'autre avec ?

Je voudrais faire une classe qui contient un hash_set, mais je ne connais
pas le fonctionnement exact.
C'est à dire : est ce que dans la classe je dois aussi inclure une autre
table contenant les éléments non cryptés pour pouvoir les voir, ou est il
possible a partir de la hash table de les décrypter.
Comment surcharger la fonction de hash?
Comment choisir l'allocator?
Quand j'insers un élément qui est un CString , la fonction de hash s'appelle
t-elle toute seule lors de l'insertion? et comment récuperer la clé générée
quand l'élement est inseré?
Comment gérer les collisions?

Je sais pas si je suis très clair, mais j'ai pleins de petites questions
(dont certaines doivent etre stupide) mais ne connaissant pas du tout ce
type de containers, je pense qu'un exemple réel (et pas les 10 lignes de
SGI) pourrait bcp m'éclairer.

Merci,

Gilles Crouspeyre.

txitxou wrote:

Qu'est-ce que tu voudrais faire d'autre avec ?

Je voudrais faire une classe qui contient un hash_set, mais je ne connais

pas le fonctionnement exact.

Je pense que d'une manière ou d'une autre les réponses se trouvent dans
la doc de sgi.

C'est à dire : est ce que dans la classe je dois aussi inclure une autre
table contenant les éléments non cryptés pour pouvoir les voir, ou est il
possible a partir de la hash table de les décrypter.

Les valeurs manipulées par la hash_map sont des pairs key/value.

Comment surcharger la fonction de hash?

L'exemple fourni te le montre :

int main()
{
hash_map<const char*, int, hash<const char*>, eqstr> months;
^^^^^^^^^^^^^^^^^

ça c'est un type foncteur qui sera utilisé pour le hashage (cf tableau
des Template parameters).

Comment choisir l'allocator?

A l'instanciation, c'est un des paramètres templates, cf le tableau dans
la doc sgi.

Quand j'insers un élément qui est un CString , la fonction de hash s'appelle
t-elle toute seule lors de l'insertion?

Je ne vois pas comment il pourrait en être autrement.

et comment récuperer la clé générée
quand l'élement est inseré?

En rappelant la fonction de hashage dessus ?

Comment gérer les collisions?

Que veux-tu dire par là ?

Je sais pas si je suis très clair, mais j'ai pleins de petites questions
(dont certaines doivent etre stupide) mais ne connaissant pas du tout ce
type de containers, je pense qu'un exemple réel (et pas les 10 lignes de
SGI) pourrait bcp m'éclairer.

Je suis pourtant sûr qu'il s'y trouve la réponse à une grande majorité
de questions...


Christophe

--
Christophe de Vienne

Christophe de VIENNE <cdevienne@alphacent.com> writes:

txitxou wrote:

et comment récuperer la clé générée quand l'élement est inseré?

En rappelant la fonction de hashage dessus ?

J'ai bien l'impression que c'est ce qu'il veut savoir. Néanmoins,
s'il demande la clef, c'est bien ce qu'il fournit, à operator[] par
exemple, de type key_type, et non le résultat de la fonction de
hashage.

Je me demande ce qu'il peut bien vouloir faire avec le résultat de
la fonction de hashage.

--drkm, en recherche d'un stage : http://www.fgeorges.org/ipl/stage.html

"txitxou" <jacksongilllou@hotmail.com> disait:

Qu'est-ce que tu voudrais faire d'autre avec ?

Je voudrais faire une classe qui contient un hash_set, mais je ne
connais pas le fonctionnement exact.
C'est à dire : est ce que dans la classe je dois aussi inclure une
autre table contenant les éléments non cryptés pour pouvoir les voir,
ou est il possible a partir de la hash table de les décrypter.
Comment surcharger la fonction de hash?
Comment choisir l'allocator?
Quand j'insers un élément qui est un CString , la fonction de hash
s'appelle t-elle toute seule lors de l'insertion? et comment récuperer
la clé générée quand l'élement est inseré?
Comment gérer les collisions?

Je sais pas si je suis très clair, mais j'ai pleins de petites
questions (dont certaines doivent etre stupide) mais ne connaissant pas
du tout ce type de containers, je pense qu'un exemple réel (et pas les
10 lignes de SGI) pourrait bcp m'éclairer.

Un hash_set, à priori, ce n'est rien d'autre que std::set avec une
implémentation différente. C'est-à-dire que l'interface visible par
l'utilisateur doit être la même, à un détail près: la fonction de
hashage en argument template.

Tant que tu ne veux pas donner une fonction de hashage customizée, tu
n'as pas à t'en préoccuper à priori, et tu traites ton hash_set comme
un std::set normal. Vu l'interface de la chose, à priori je ne vois pas
d'autre manière de s'en servir. Connaître la clé hashée utilisée en
interne par le containeur ne te servira pas à grand chose.

--
Cyrille

Un hash_set, à priori, ce n'est rien d'autre que std::set avec une
implémentation différente. C'est-à-dire que l'interface visible par
l'utilisateur doit être la même, à un détail près: la fonction de
hashage en argument template.

Tant que tu ne veux pas donner une fonction de hashage customizée, tu
n'as pas à t'en préoccuper à priori, et tu traites ton hash_set comme
un std::set normal. Vu l'interface de la chose, à priori je ne vois pas
d'autre manière de s'en servir. Connaître la clé hashée utilisée en
interne par le containeur ne te servira pas à grand chose.

--
Cyrille

Ok , bin merci bcp , je vais regarder ca Lundi :).
Merci aussi à Christophe et drkm :)

"txitxou" <jacksongilllou@hotmail.com> writes:

Merci aussi à Christophe et drkm :)

Mouais. Mes articles ne sont pas encore sur Google, et je n'arrive
pas à les retrouver. Mais il me semble que j'ai cru que tu parlais de
« hash_map » plutôt que de « hash_set ». Tiens-en peut-être compte si
tu ne comprends pas mes articles.

Désolé si j'ai apporté de la confusion.

Néanmoins, si tu cherches effectivement à récupérer la valeur de la
fonction de hashage, pourquoi est-ce ?

--drkm, en recherche d'un stage : http://www.fgeorges.org/ipl/stage.html

"txitxou" <jacksongilllou@hotmail.com> wrote in message
news:<411cb912$0$29674$636a15ce@news.free.fr>...

Qu'est-ce que tu voudrais faire d'autre avec ?

Je voudrais faire une classe qui contient un hash_set, mais je ne
connais pas le fonctionnement exact.

Je suis tempté à dire que c'est là l'intérêt principal de la chose:-).

En fait, ce qui t'intéresse, pour t'en servir, c'est l'interface.
L'implémentation interne ne doit pas avoir de l'importance.

C'est à dire : est ce que dans la classe je dois aussi inclure une
autre table contenant les éléments non cryptés pour pouvoir les voir,
ou est il possible a partir de la hash table de les décrypter.

Je ne comprends pas trop. D'où vient les éléments cryptés ? Si tu
encryptes des éléments, tu dois savoir les decrypter. Et quel est
l'intérêt à les crypter si tu dois les garder en clair dans une autre
table.

Mais je crains que tu confonds « hachage » et « cryptage », bien que ce
soit deux conceptes pas trop apparentés. Le hachage, c'est fait dans le
hash_set, pour ces besoins internes. Toi, tu ne vois jamais la valeur
hachée. (Selon l'implémentation, elle peut être stockée ou non.)

Comment surcharger la fonction de hash?

Ça dépend de l'implémentation. (Et je ne suis pas sûr que « surcharger »
est le mot qui convient.) Dans le cas du hash_set de SGI, ce n'est pas
nécessairement une fonction. La solution la plus simple, pour des types
définis par l'utilisateur, c'est de définir une spécialisation du
template hash (aussi dans la bibliothèque), p.e. :

template<>
struct hash< MonType >
{
size_t operator()( MonType const& obj ) const
{
return ... ;
}
}

hash_set< MonType > monSet ;

Pour utiliser une fonction, faudrait écrire :

size_t
hashIt( MonType const& obj )
{
// ...
return ... ;
}

hash_set< MonType, size_t (*)( MonType const& ) >
monSet( 100, &hashIt ) ;

Dans ce cas-ci, la fonction réele de hachage n'est pas déterminée
complètement par le type. Il faut donc la passer au constructeur, et
autant que je vois, il n'y a aucun constructeur qui prend une function
de hachage sans aussi exiger un compte de buckets.

En passant, il faut aussi faire attention que la fonction de hachage
soit compatible avec la fonction d'équalité. Par défaut, le hash_set
utilise l'opérateur ==, mais on peut aussi spécifier d'autre chose.
Ce qui est en général nécessaire si le type contenu est un pointeur, par
exemple, mais aussi si c'est une classe qui n'a pas défini ==. (C-à-d :
dans la pratique, beaucoup plus souvent qu'on imaginera au départ. Je ne
me suis prèque jamais servi des hash_set, mais pour les hash_map et
leurs équivalents, je constate que peut-être les deux tiers, sinon plus,
utilise un std::string comme clé, mais que dans prèsque tous les autres
cas, il a fallu que je définisse mon propre fonction d'équivalence.)

Comment choisir l'allocator?

Pourquoi choisir l'allocator ? Je me suis toujours servi du défaut,
quelque soit la collection. Définir ces propres allocateurs, c'est un
travail pour les experts, et on n'en a besoin que vraiment
exceptionnellement.

Quand j'insers un élément qui est un CString,

CString ? Alors, tu te sers de VC++. Qu'est-ce qui t'amène à utiliser le
hash_set de SGI, et non celui qui vient avec ton compilateur ?

Je pose la question, parce qu'à l'encontre de la reste de la
bibliothèque, les hash_set ne sont pas identique.

la fonction de hash s'appelle t-elle toute seule lors de l'insertion?

Elle serait appelée par l'implémentation quand elle en a besoin.
Certainement lors de l'insertion ; éventuellement à d'autres moments
aussi.

et comment récuperer la clé générée quand l'élement est inseré?

En appelant la fonction de hachage toi-même. Mais pour quoi faire ?

Si c'est pour valider la fonction de hachage, et si tu utilises
l'implémentation de la SGI (mais non celle qui vient avec VC++), il y a
des fonctions bucket_count() et hash_funct(). Pour un objet donné,
l'expression :

table.hash_funct()( obj ) % table.bucket_count()

doit donné le bucket où il est stocké. En itérant sur tous les objets
dans la collection (table.begin() et table.end()), avec l'aide de cette
expression, tu doit pouvoir calculer toutes les statistiques
intéressantes.

Comment gérer les collisions?

Ce n'est pas ton problème.

Je sais pas si je suis très clair, mais j'ai pleins de petites
questions (dont certaines doivent etre stupide) mais ne connaissant
pas du tout ce type de containers, je pense qu'un exemple réel (et pas
les 10 lignes de SGI) pourrait bcp m'éclairer.

J'ai l'impression que tu ne comprends pas encore très bien les conceptes
de l'encapsulation et des types de données abstraits -- tes questions
semblent mélanger l'utilisation (l'interface) et l'implémentation (ce
qui ne te régarde pas).

--
James Kanze GABI Software http://www.gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Dans news:411cdf7a$0$26560$636a15ce@news.free.fr, Cyrille

Un hash_set, à priori, ce n'est rien d'autre que std::set avec
une implémentation différente. C'est-à-dire que l'interface
visible par l'utilisateur doit être la même, à un détail près:
la fonction de hashage en argument template.

Et le fait que les données ne sont pas en ordre, ce qui change
les itérateurs.

--
Michel Michaud mm@gdzid.com
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/