IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

SL & STL C++ Discussion :

stl hash map


Sujet :

SL & STL C++

  1. #1
    Membre confirmé
    Inscrit en
    Septembre 2006
    Messages
    63
    Détails du profil
    Informations forums :
    Inscription : Septembre 2006
    Messages : 63
    Par défaut stl hash map
    ce que je sais c que la difference entre une map est une multimap, c au niveau des doublons
    mais quelle difference y a t il entre les deux conteneurs precedants et la hash_map ???

  2. #2
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 394
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 394
    Par défaut
    Une hash_map n'est pas triée, et son acces est généralement plus rapide (généralement simplifié en O(1) au lieu de O(Log N)).

    Par contre, j'ignore si elle peut ou non contenir des doublons, mais j'en doute.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  3. #3
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 635
    Par défaut
    Salut,

    L'un des premiers liens fournis par google est http://www.sgi.com/tech/stl/hash_map.html

    Assez bizarement, la description qui en est donnée sur cette page ressemble énormément à la map

    Une autre recherche essayant de mettre les deux en parallelle semble indiquer que le but de la hash_map est d'améliorer le temps de recherche par rapport à la map

    Mais la litérature que j'ai trouvée ne semble pas indiquer précisement comment ils comptent s'y prendre
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  4. #4
    Rédacteur
    Avatar de Laurent Gomila
    Profil pro
    Développeur informatique
    Inscrit en
    Avril 2003
    Messages
    10 651
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2003
    Messages : 10 651
    Par défaut
    std::map est un arbre binaire ordonné (enfin, c'est juste une conséquence de ses spécifications dans la norme), la recherche est donc en temps logarithmique puisqu'il faut au pire des cas parcourir toute la hauteur de l'arbre.

    hash_map est une table de hachage, càd que la clé donne directement l'indice de l'élément correspondant par hachage (les algorithmes de hachages pour les types courants sont bien connus), ce qui implique le temps de recherche en temps constant. Selon le type de table de hachage, les collisions (plusieurs clés ayant la même valeur de hachage) peuvent être gérées, dans ce cas une clé renverra non pas à un élément, mais à une liste d'éléments.

    Voir un cours d'algo / structures de données pour plus de détails.

Discussions similaires

  1. Hash map et stl
    Par Ange_blond dans le forum C++
    Réponses: 13
    Dernier message: 11/06/2010, 09h35
  2. [STL std::map] element precedant
    Par ZaaN dans le forum SL & STL
    Réponses: 1
    Dernier message: 17/05/2007, 00h52
  3. Réponses: 8
    Dernier message: 27/06/2006, 07h40
  4. [STL]std::map<std::string, structure> Parcour...
    Par Zenol dans le forum SL & STL
    Réponses: 5
    Dernier message: 11/02/2006, 13h46
  5. STL: les map et la methode find. que fait-elle?
    Par cokmes dans le forum SL & STL
    Réponses: 6
    Dernier message: 07/11/2005, 08h31

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo