questions sur hash_map et son implémentation

Murlock wrote:

Bonjour à vous,

En cherchant autour de std::map j'ai vu hash_map qui correspondrait à
mes besoins (un hash_map<std::string, std::string> avec une fonction
hash à définir) puisque le temps d'accès est plus rapide qu'une map
standart. A ma grande surprise, je m'aperçois que hash_map n'est pas
standart à STL. Quel risque cela entraîne-t-il de l'utiliser (ou est-ce
que hash_map est prévue à court ou moyen terme d'être inclus dans la
norme C++ ?

C'est prévu, mais probablement sous un autre nom. Voir par exemple :
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1443.html

Est-ce que l'implémentation de hash_map sur les différents compilos
respecte elle une même interface ?

Le nom peut être différent, l'interface un peu aussi.

--
Loïc

Loïc Joly <loic.actarus.joly@wanadoo.fr> writes:

C'est prévu, mais probablement sous un autre nom. Voir par exemple :
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1443.html

J'aurais plutôt renseigné

<URL:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1687.pdf>

non ? Où le nom est devenu « unordered_map ». Si j'ai bien compris.
Je n'ai fait que survoler de loin le TR1.

--drkm

drkm wrote:

Loïc Joly <loic.actarus.joly@wanadoo.fr> writes:

C'est prévu, mais probablement sous un autre nom. Voir par exemple :
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1443.html

J'aurais plutôt renseigné

<URL:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1687.pdf>

non ? Où le nom est devenu « unordered_map ». Si j'ai bien compris.
Je n'ai fait que survoler de loin le TR1.

Outre le fait qu'en survolant rapidement, je n'avais pas vu le 1687, je
pense que le 1443 est rédigé en anglais, alors que le 1687 est en
standardese, et ne comprend pas toutes les discussions de compatibilités
avec les existants, mais uniquement les résultats de ces discussions.

--
Loïc

Murlock <Murlock@invalid.domain> wrote in message
news:<416c37c6$0$28953$636a15ce@news.free.fr>...

En cherchant autour de std::map j'ai vu hash_map qui correspondrait à
mes besoins (un hash_map<std::string, std::string> avec une fonction
hash à définir) puisque le temps d'accès est plus rapide qu'une map
standart.

Ce n'est pas toujours vrai. Ça dépend de plusieurs facteurs : la taille
de la table, et la qualité de la fonction de hachage. J'ai fait un
certain nombre de benchmarks dans le temps, voir
http://www.gabi-soft.fr/code/Benchmarks/Hashcode/Analysis.txt. Ce que je
conclu, c'est que (au moins sur un Sparc), il faut avoir environ un
millier d'entrées avant que la table hachée (ici, le hash_map de g++)
est plus rapid que std::map, et que même alors, il ne faut pas se
tromper sur la fonction de hachage -- j'ai un cas, avec un tableau d'un
million d'éléments, ou le std::map gagne contre une fonction de hachage
que je croiyais bonne (et qui l'est en fait sur les autres données que
j'ai essayé).

A ma grande surprise, je m'aperçois que hash_map n'est pas
standart à STL. Quel risque cela entraîne-t-il de l'utiliser (ou
est-ce que hash_map est prévue à court ou moyen terme d'être inclus
dans la norme C++ ?

C'est prévu. Il y aurait prèsque certainement un tableau haché dans la
prochaine version de la norme. (Mais je ne sais pas si on peut parler de
court terme pour ça.)

Est-ce que l'implémentation de hash_map sur les différents compilos
respecte elle une même interface ?

Non. En revanche, elles sont assez semblables ; il y a surtout des
paramètres de template qui changent. Alors, éventuellement avec un
#ifdef autour d'un typedef...

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

Intéressant... vu que je n'aurais qu'environ 200 éléments maximun dans
ma hash_map, du coup je me pose la question de son bien-fondé.

Bon, je m'oriente pour l'instant dans une map traditionnelle.

Merci à tous