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 :

Problème de hashage


Sujet :

SL & STL C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Décembre 2007
    Messages : 19
    Par défaut Problème de hashage
    Bonjour,

    J'ignore si actuellement il faut utiliser "unordered_set" ou "ext/hash_set" avec g++, j'ai essayé les deux et j'ai eu des messages d'erreurs aussi incompréhensible.

    J'ai tendance à supposer que le problème est que j'ai mis ou oublier le mot clef "const" à un endroit alors qu'il n'aurait pas fallu (ou qu'il l'aurait fallu), quand j'ai redéfini les opérateur ==, () /* pour le hashage*/ ou =, et j'avoue que si quelqu'un pouvait avoir une idée de ce qui cause le bug, je lui serai très reconnaissant.

    Je copie colle le code, mais vu que les messages d'erreurs arrivent sur les headers, je pense qu'il n'y aura pas grand chose à lire.

    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
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
     
     
    #include <cstdio>
    #include <vector>
    #include <unordered_set> // ou l'autre ou les deux, au choix
    #include <cmath>
    using namespace __gnu_cxx;
    using namespace std;
     
     
    /*On suppose que n<32*/
    struct graphe{
      vector<unsigned int> ligne;
     
      graphe(unsigned int n){
        ligne.reserve(n);
        for(unsigned int i=0;i<n;i++){
          ligne[i]=0;
        }
      }
     
      bool arrow(unsigned int lig, unsigned int col){
        return ligne[lig]&(1<<col);
      }
     
      void add_arrow(unsigned int lig, unsigned int col){
        ligne[lig]|=(1<<col);
        ligne[col]|=(1<<lig);
      }
     
      void remove_arrow(unsigned int lig, unsigned int col){
        ligne[lig]^=(1<<col);
        ligne[col]^=(1<<lig);
      }
     
      bool operator==( graphe g ){
        if(g.ligne.size()!=ligne.size())return false;
        for(unsigned int i=0;i<g.ligne.size();i++){
          if(g.ligne[i]!=ligne[i])return false;
        }
        return true;
      }
     
      /*bool operator==(const graphe& g1, const graphe& g2){
        if(g1.ligne.size()!=g2.ligne.size())return false;
        for(unsigned int i=0;i<g1.ligne.size();i++){
          if(g1.ligne[i]!=g2.ligne[i])return false;
        }
        return true;
      }*/
     
      size_t operator()(){
        unsigned int tot=0;
        for(unsigned int i=0;i<ligne.size();i++){
          tot*=17;
          tot+=ligne[i];
        }    
        return tot;
      }
      /*size_t operator ()(const graphe& g1){
        unsigned int tot=0;
        for(unsigned int i=0;i<g1.ligne.size();i++){
          tot*=17;
          tot+=ligne[i];
        }    
        return tot;
      }  */
     
      graphe(vector<unsigned int> chemin){
        graphe(chemin.size());
        for(unsigned int i; i<chemin.size()-1;i++){
          add_arrow(chemin[i],chemin[i+1]);
        }
      }
     
      graphe& operator=( graphe g){
        ligne.reserve(g.ligne.size());
        for(unsigned int i; i<g.ligne.size()-1;i++){
          ligne[i]=g.ligne[i];
        }
      }
     
    };
     
    /*struct ham{
      graphe g;
      vector<unsigned int> chemin;
     
      ham(graphe gr, vector<unsigned int> c){
        g=gr;
        chemin=c;
      }
     
      bool operator==(ham h){
        h.g==g;
        for(unsigned int i=0;i<chemin.size();i++){
          if(h.chemin[i]!=chemin[i])return false;
        }
        return true;
      }
     
      size_t operator ()(const ham& h) const{
        return g();
      }
      };*/
     
    unordered_set<graphe> table;
    unsigned int maxi;
     
    void swap(vector<unsigned int> Value, unsigned int i, unsigned int j){
      unsigned int tmp=Value[i];
      Value[j]=Value[i];
      Value[i]=tmp;
    }
     
    void getNext(vector<unsigned int> Value){
      unsigned int N=Value.size();
      unsigned int i = N - 1;
      while (Value[i-1] >= Value[i]) i = i-1;
      unsigned int j = N;
      while (Value[j-1] <= Value[i-1]) j = j-1;
    // swap values at positions (i-1) and (j-1)
      swap(Value,i-1, j-1);    
      i++; j = N;
      while (i < j)
      {
        swap(Value, i-1, j-1);
        i++;
        j--;
      }
    }
     
    pair<unsigned int,unsigned int>  N_vers_N2(unsigned int u) {
      unsigned int y=sqrt(2*u);
      if(y*(y+1)/2>u) 
        y--;
      unsigned int x =u-(y*(y+1))/2 -1;
      pair<unsigned int,unsigned int> p(x,y);
      return p;
    }
     
    void cree(graphe g,unsigned int ar){
      if(ar==maxi){
       table.insert(g);
      }
      pair<unsigned int,unsigned int> p=N_vers_N2(ar);
      unsigned int x=p.first, y=p.second;
      cree(g,ar+1);
      if(!g.arrow(x,y)){
        graphe g2=g;
        g2.add_arrow(x,y);
        cree(g2,ar+1);
      }
    }
     
    int main(){
      unsigned int n=3,fact=1;
      maxi=n*(n+1)/2;
      for(unsigned int i=2;i<=n;i++)fact*=i;
      vector<unsigned int> permut(n);
      for(unsigned int i=0;i<n;i++){
        permut[i]=i;
      }
      for(unsigned int i=0;i<fact;i++){
        getNext(permut);
        graphe g(permut);
      }
      printf("size=%i\n",table.size());
      return 0;
    }
    Et je vous met aussi le message d'erreur:

    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
     
     
    -*- mode: compilation; default-directory: "~/hamilton/Console/" -*-
    Compilation started at Sun Jan 10 01:17:41
     
    g++ Ham2.cpp -W -o ham2 -std=c++0x -Wno-deprecated
    In file included from /usr/include/c++/4.4/unordered_set:47,
                     from Ham2.cpp:3:
    /usr/include/c++/4.4/bits/stl_function.h: In member function ‘bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = graphe]’:
    /usr/include/c++/4.4/tr1_impl/hashtable_policy.h:769:   instantiated from ‘bool std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_M_compare(const _Key&, size_t, std::__detail::_Hash_node<_Value, false>*) const [with _Key = graphe, _Value = graphe, _ExtractKey = std::_Identity<graphe>, _Equal = std::equal_to<graphe>, _H1 = std::hash<graphe>, _H2 = std::__detail::_Mod_range_hashing]’
    /usr/include/c++/4.4/tr1_impl/hashtable:918:   instantiated from ‘std::__detail::_Hash_node<_Value, __cache_hash_code>* std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_find_node(std::__detail::_Hash_node<_Value, __cache_hash_code>*, const _Key&, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type) const [with _Key = graphe, _Value = graphe, _Allocator = std::allocator<graphe>, _ExtractKey = std::_Identity<graphe>, _Equal = std::equal_to<graphe>, _H1 = std::hash<graphe>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = true, bool __unique_keys = true]’
    /usr/include/c++/4.4/tr1_impl/hashtable:983:   instantiated from ‘std::pair<typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::iterator, bool> std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_insert(const _Value&, std::true_type) [with _Key = graphe, _Value = graphe, _Allocator = std::allocator<graphe>, _ExtractKey = std::_Identity<graphe>, _Equal = std::equal_to<graphe>, _H1 = std::hash<graphe>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = true, bool __unique_keys = true]’
    /usr/include/c++/4.4/tr1_impl/hashtable:420:   instantiated from ‘typename __gnu_cxx::__conditional_type<__unique_keys, std::pair<std::__detail::_Hashtable_iterator<_Value, __constant_iterators, __cache_hash_code>, bool>, std::__detail::_Hashtable_iterator<_Value, __constant_iterators, __cache_hash_code> >::__type std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::insert(const _Value&) [with _Key = graphe, _Value = graphe, _Allocator = std::allocator<graphe>, _ExtractKey = std::_Identity<graphe>, _Equal = std::equal_to<graphe>, _H1 = std::hash<graphe>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = true, bool __unique_keys = true]’
    Ham2.cpp:142:   instantiated from here
    /usr/include/c++/4.4/bits/stl_function.h:203: error: passing ‘const graphe’ as ‘this’ argument of ‘bool graphe::operator==(graphe)’ discards qualifiers
     
    Compilation exited abnormally with code 1 at Sun Jan 10 01:17:41
    PS: je suis bien conscient que le temps de calcul de mon algorithme est en O(n!*2^(n^2)) donc si quelqu'un cherche à comprendre ce que fait le code, il n'est pas la peine de me signaler qu'il est mauvais.

  2. #2
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Yvelines (Île de France)

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

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Par défaut
    Citation Envoyé par Arthur Rainbow Voir le message
    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
     
      bool operator==( graphe g ){
        if(g.ligne.size()!=ligne.size())return false;
        for(unsigned int i=0;i<g.ligne.size();i++){
          if(g.ligne[i]!=ligne[i])return false;
        }
        return true;
      }
     
      /*bool operator==(const graphe& g1, const graphe& g2){
        if(g1.ligne.size()!=g2.ligne.size())return false;
        for(unsigned int i=0;i<g1.ligne.size();i++){
          if(g1.ligne[i]!=g2.ligne[i])return false;
        }
        return true;
      }*/
    Ton opérateur == indique qu'il va modifier l'objet courant (this). Essaye :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
      bool operator==( graphe g ) const {
        if(g.ligne.size()!=ligne.size())return false;
        for(unsigned int i=0;i<g.ligne.size();i++){
          if(g.ligne[i]!=ligne[i])return false;
        }
        return true;
      }
    En outre, pourquoi passer l'argument par copie ? Et pourquoi avoir commenté le code en dessous qui me semblait meilleur (passage par référence constante) ?
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  3. #3
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Décembre 2007
    Messages : 19
    Par défaut
    Si je met deux arguments à == il me dit que cet opérateur n'en attend qu'un. J'en ai donc mis qu'un.

    J'ai préféré laisser l'autre en commentaire si jamais je me rendais compte que ça vallait mieux de l'y laisser.

    J'ai rajouté ton const, entre la parenthèse et l'accolade fermante (peut tu confirmer qu'il n'y a pas d'autre différence?)

    Et maintenant j'ai le message encore moins compréhensible

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    -*- mode: compilation; default-directory: "~/hamilton/Console/" -*-
    Compilation started at Sun Jan 10 01:33:55
     
    g++ Ham2.cpp -W -o ham2 -std=c++0x -Wno-deprecated
    /tmp/ccwBPsFK.o: In function `std::__detail::_Hash_code_base<graphe, graphe, std::_Identity<graphe>, std::equal_to<graphe>, std::hash<graphe>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_hash_code(graphe const&) const':
    Ham2.cpp:(.text._ZNKSt8__detail15_Hash_code_baseI6grapheS1_St9_IdentityIS1_ESt8equal_toIS1_ESt4hashIS1_ENS_18_Mod_range_hashingENS_20_Default_ranged_hashELb0EE12_M_hash_codeERKS1_[std::__detail::_Hash_code_base<graphe, graphe, std::_Identity<graphe>, std::equal_to<graphe>, std::hash<graphe>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_hash_code(graphe const&) const]+0x2b): undefined reference to `std::hash<graphe>::operator()(graphe) const'
    /tmp/ccwBPsFK.o: In function `std::__detail::_Hash_code_base<graphe, graphe, std::_Identity<graphe>, std::equal_to<graphe>, std::hash<graphe>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::__detail::_Hash_node<graphe, false> const*, unsigned int) const':
    Ham2.cpp:(.text._ZNKSt8__detail15_Hash_code_baseI6grapheS1_St9_IdentityIS1_ESt8equal_toIS1_ESt4hashIS1_ENS_18_Mod_range_hashingENS_20_Default_ranged_hashELb0EE15_M_bucket_indexEPKNS_10_Hash_nodeIS1_Lb0EEEj[std::__detail::_Hash_code_base<graphe, graphe, std::_Identity<graphe>, std::equal_to<graphe>, std::hash<graphe>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::__detail::_Hash_node<graphe, false> const*, unsigned int) const]+0x3a): undefined reference to `std::hash<graphe>::operator()(graphe) const'
    collect2: ld returned 1 exit status
     
    Compilation exited abnormally with code 1 at Sun Jan 10 01:33:56
    et ceci même si je rajoute "const" à l'argument dans la parenthèse.

  4. #4
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Yvelines (Île de France)

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

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Par défaut
    Citation Envoyé par Arthur Rainbow Voir le message
    Si je met deux arguments à == il me dit que cet opérateur n'en attend qu'un. J'en ai donc mis qu'un.
    Euh, oui, dans ce cas, il faut en faire une fonction libre. Regarde http://cpp.developpez.com/faq/cpp/?p...embre_ou_libre
    Citation Envoyé par Arthur Rainbow Voir le message
    Et maintenant j'ai le message encore moins compréhensible
    C'est mieux comme erreur. Il indique qu'il a réussi à compiler, qu'il a juste du mal à linker, on a progressé d'une étape.
    Il ne trouve pas la définition de std::hash<graphe>::operator()(graphe) const... Et moi non plus. En fait, tu as défini un operateur() sur ton type, il s'attendait à trouver un opérateur() sur le type std::hash<ton type ici>. Donc soit tu spécialise le template std::hash pour ton type en particulier, soit tu indique à ta unordered_map un second argument qui est une fonction de hashage.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  5. #5
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Décembre 2007
    Messages : 19
    Par défaut
    Citation Envoyé par JolyLoic Voir le message
    Donc soit tu spécialise le template std::hash pour ton type en particulier
    J'avais cru que ça voulait dire définir une fonction
    size_t std::hash<graphe>::operator()(const graphe g)
    J'ai donc copier ma fonction operator() en dehors de ma structure, mais ça bug toujours.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    error: too few template-parameter-lists
    Qu'est-ce ce que je peux donner en plus comme paramètre à hash ?

    Citation Envoyé par JolyLoic Voir le message
    , soit tu indique à ta unordered_map un second argument qui est une fonction de hashage.
    Visiblement, il refuse une fonction comme deuxième argument (même précédé par & pour déréférencer)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    error: type/value mismatch at argument 2 in template parameter list fortemplate<class _Value, class _Hash, class _Pred, class _Alloc> class std::unordered_set’
    Ham2.cpp:115: error:   expected a type, got ‘hash_graphe’
    En tout cas merci beaucoup pour ton aide, vu que, comme tu le remarques surement, je n'ai pas trop l'habitude du C++ pour programmer(Ni pour quoi que ce soit d'autre d'ailleurs.)

  6. #6
    Rédacteur
    Avatar de 3DArchi
    Profil pro
    Inscrit en
    Juin 2008
    Messages
    7 634
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2008
    Messages : 7 634
    Par défaut
    Salut,
    Comme l'a dit Loïc, j'ai repris ton code et j'ai rendu l'opérateur == const (l'opérateur, pas l'argument ! ) et cette partie ne génère plus d'erreur :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
      bool operator==( graphe const & g ) const{
        if(g.ligne.size()!=ligne.size())return false;
        for(unsigned int i=0;i<g.ligne.size();i++){
          if(g.ligne[i]!=ligne[i])return false;
        }
        return true;
      }
    D'autre part, pour l'opérateur(), il doit lui aussi être const et spécialisé dans le namespace std :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    namespace std{
     
        template<>
        inline size_t hash<graphe>::operator()(graphe g) const
        {
            return g();
        }
    }
    Ne pas oublier de rendre ton operateur() de graph const aussi !
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
      size_t operator()()const{
        unsigned int tot=0;
        for(unsigned int i=0;i<ligne.size();i++){
          tot*=17;
          tot+=ligne[i];
        }
        return tot;
      }

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Problème de hashage mot de passe
    Par fdweb dans le forum MkFramework
    Réponses: 19
    Dernier message: 20/10/2015, 16h30
  2. Perl: problème avec un hashage de tableau
    Par lorlando dans le forum Langage
    Réponses: 1
    Dernier message: 24/04/2009, 09h44
  3. problème pour trier un tableau de hashage
    Par Jasmine80 dans le forum Langage
    Réponses: 1
    Dernier message: 25/02/2007, 13h02
  4. Problème de pointeur sur une table de hashage
    Par nicdesf dans le forum Langage
    Réponses: 3
    Dernier message: 07/09/2006, 19h23
  5. Problèmes de Hashages et de Tableaux
    Par Chris_LaFouine dans le forum Langage
    Réponses: 4
    Dernier message: 22/07/2005, 10h57

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