choses étranges se sont produites lors de l'implémentation de hashmap en C++

Question

J'essaie d'implémenter ma propre hashmap en C++. Mon-tête est

class MyMap 
{ 
public: 


    MyMap(); 
    ~MyMap(); 

    int get(int key) const; 
    void put(int key, int value); 
    bool containsKey(int key); 
    Vector<int> keys() const; 
    int size(); 

    void sanityCheck(); 
    MyMap(const MyMap &myMap); // copy constructor 
    MyMap& operator= (const MyMap &myMap); // assignment overload 
    friend ostream &operator<<(ostream &out, MyMap &myMap); 
    friend istream &operator>>(istream &in, MyMap &myMap); 
private: 

    struct key_val_pair { 
     int key; 
     int value; 
     key_val_pair* next; 
    }; 

    typedef key_val_pair** bucketArray; // just renaming the pointer to pointer. 

    bucketArray createBucketArray(int nBuckets); 
    int hashFunction(int input) const; 

    bucketArray buckets; 

    int nBuckets; 
    int nElems; 
    int INIT_N_BUCKETS = 128; 

}; 

J'initialize ma carte à l'aide

MyMap::MyMap() { 
    bucketArray buckets = createBucketArray(INIT_N_BUCKETS); 
    nBuckets = INIT_N_BUCKETS; 
    nElems = 0; 
} 
MyMap::bucketArray MyMap::createBucketArray(int nBuckets) { 
    bucketArray newBuckets = new key_val_pair*[nBuckets]; 
    for (int i = 0; i < nBuckets; i++) { 
     newBuckets[i] = nullptr; 
    } 
    return newBuckets; 

}

Et voici mon code à mettre des éléments en hashmap

void MyMap::put(int key, int value) { 
    // compute hash; 
    int bucket = hashFunction(key) % nBuckets ; 
    key_val_pair *entry = buckets[bucket];  
    key_val_pair *prev = nullptr; 
    if(entry == nullptr) { 

     entry = new key_val_pair; 
     entry->key = key; 
     entry->value = value; 
     entry->next = nullptr; 
     buckets[bucket] = entry; 
     nElems++; 
    } 
    else{ 
     while(entry && entry->key != key){ 
      prev = entry; 
      entry = entry->next; 
     } 

     if(!entry){ 
      entry = new key_val_pair; 
      entry->key = key; 
      entry->value = value; 
      entry->next = nullptr; 
      if(!prev) buckets[bucket] = entry; 
      else prev->next = entry; 
      nElems++; 
     } 
     else{ 
      entry->value = value; 
     } 
    } 

} 

Maintenant, est ici la partie bizarre, même juste après l'initialisation. Par exemple, je laisse MyMap m = MyMap();. Et j'ai entré des paires (i, i), je de 0 à 100. J'ai trouvé que pas tous mes seaux [i] sont des pointeurs nuls (j'ai ajouté des phrases dans le put tel que buckets[bucket] == null)! avant de mettre des paires sur la carte. Certains sont, mais certains ne le sont pas! Comment ça s'est passé? Comme je viens de les initialiser tous à nullptr? FYI, à l'intérieur du constructeur, j'ai vérifié et tous les compartiments [i] sont effectivement nullptr. Ce bug me rend fou .... Quelqu'un pourrait m'aider à ce sujet? Merci!

Answer 1

Vous déclarez une autre bucketarray dans le constructeur, mais vous ne donnez pas à votre membre de la classe:

bucketArray buckets = createBucketArray(INIT_N_BUCKETS);

devrait être:

buckets = createBucketArray(INIT_N_BUCKETS); 

Ou mieux encore, initialisez tous vos membres aiment ceci:

MyMap::MyMap() 
: 
INIT_N_BUCKETS(128), 
buckets(createBucketArray(INIT_N_BUCKETS)), 
nBuckets(INIT_N_BUCKETS), 
nElems(0) 
{ } 

Vous avez Ve pour déplacer INIT_N_BUCKETS plus haut dans la classe car l'ordre est important lors de l'initialisation.

code Exemple: https://ideone.com/b8RN1Q