Hi,
 
Je suis un peu perdu... Il y a une différence entre une map et une hash map ?
 
En C++ je connais un petit peu la map de la std, existe t-il une classe map dans boost ?
Si il y a une différence entre map et hash map, existe t-il une hash map dans la std? dans boost?
 
Merci

Pas de différence entre hashmap et map dans le principe, les deux désignent un tableau associatif. En Java à la limite, où Map est une interface et Hashmap une implémentation, mais en C++, dans la STL, il n'y a que std::map qui remplit très bien son office.
Pour la doc C++, tu peux aller ici : http://cplusplus.com
 
Pour boost je ne peux pas répondre à tes questions.

std::map est implémenté à base d'arbres binaires équilibrés (c'est pourquoi il lui faut une fonction de comparaison).
 
Il y a pas mal d'implémentations de la bibliothèque standard qui fournisse aussi une hash_map implémentée à base de tables de hachage.  C++0X aura une std::unordered_map à cet effet (pas hash_map pour éviter la confusion avec les implémentations existantes, qui sont incomptabibles entre elles).

Euh, moi je vois le fait qu'une map soit ordonnée comme une de ces caractéristiques principales.

Ah oui, bien vu.

ordonnée, selon ses clefs ou ses données ??

Les clés.

map :
- temps d'accès en log2(n) * K
- ordonnée (par le critère que tu veux sur les clés)
- nécéssite une relation d'ordre stric sur les clés (typiquement l'operateur< ), ayant une complexité de K (typiquement O(1))
- ne déplace pas ses nodes (ajouter/supprimer un élément n'invalide pas les autres iterateurs)
 
hash_map (ou unordered_map, c'est pareil)
- temps d'accés en O(1) * K en général mais O(n) dans le (rare) pire des cas.
- pas ordonnée (d'où son nom)
- nécéssite une fonction de hashage ET une fonction de comparaison (typiquement l'operateur==), ayant une complexité de K (typiquement O(1))
- peut déplacer ses nodes, ça dépend de l'implémentation. Certaines version de STLPort déplacent les nodes, mais pas celles de microsoft. Donc ajouter/supprimer un élément invalide tous les itérateurs. Le futur standard C++0x imposera de ne pas déplacer ses nodes, mais c'est pas encore appliqué.
 
J'introduis la compléxité K car elle est souvent négligée, mais pas négligeable. Pour une map de std::string par exemple, comparer 2 strings (avec < ou ==) est en compléxité O(m), avec m la longueur des strings. Ca peut être grand devant log2(n), et d'autant plus devant O(1). D'où l'intérêt de bien optimiser les fonctions de comparaison et de hashage. La fonction de hashage doit à la fois être performante et ne pas provoquer trop de collisions.

T'as le bout de doc qui en parle ? Je me suis pris le bec la dessus avec un collègue et pas moyen de retrouver le bout qui dit ça.

Section 23.1.2 (Table 69) de la norme.

nickel merci

 
Dans ce cas, un trie sera peut être plus adapté.

Ouais enfin bon O(m) c'est du O.
En implémentant bien == ou < pour des chaînes, on sort vite de l'ornière. Là tu vas me dire "oui mais si les chaînes sont de même taille et avec un préfixe commun" ... ben je te retourne le problème avec ta trie qui se transforme en liste chaînée / peigne.
(Mais on ne parle pas de la complexité du stockage)

 
Y'avait "peut être" dans ma phrase Ça dépends clairement du dataset mais c'est jamais mauvais de savoir que ça existe et de penser à essayer le jour ou une (hash_)map à du mal.