C++에서 해시 맵에 유효한 복사 생성자를 작성하십시오.

Question

해시 맵 클래스의 복사 생성자를 생성하는 데 문제가 있습니다. 현재, 배열의 복사 생성자를 수행하는 방법을 이해합니다. 원래 배열에서 다음 배열로 복사합니다. 예를 들어, 다음 배열 목록을 할 것 인 것이다 :

ArrayList::ArrayList(const ArrayList& a) 
    : items{new std::string[a.cap]}, sz{a.sz}, cap{a.cap} 
{ 
    // arrayCopy is a for loop that does items[i] = a.items[i] on each iteration 
    arrayCopy(items, a.items, sz); 
} 

나는 우리가 새로운 배열리스트에 값을 초기화해야하고, 배열의 새로운 목록에 걸쳐 복사하는 것이 이해합니다. 그러나이 문제를 별도로 연결된 해시 맵에서 처리하는 데 어려움을 겪고 있습니다. 내 복사 생성자에 각 노드를 넣어하는 방법을 이해하는 데 도움이 필요

struct Node 
{ 
    std::string key; 
    std::string value; 
    Node* next; 
}; 

: 내 HashMap.hpp 파일에서

는이 같은 변경 불가능한 구조를 가지고있다.

HashMap::HashMap(const HashMap& hm) 
    : hashTable{new Node*[hm.amountOfBuckets]}, amountOfBuckets{hm.amountOfBuckets}, sz{hm.sz} 
{ 
} 

가 어떻게 제대로 원래 테이블에 얼마나 많은에 따라 각 해시 테이블 인덱스를 반복하고, 새로운 노드를 작성 달성 것이다 : 이것은 내 복사 생성자는 실제 "복사"코드없이, 무엇입니까? 네 개의 노드를 만들고, 두 개는 새 테이블을 추적하고, 두 개는 원래 테이블을 추적해야합니까?

나는 이것을 구현하려고 시도하고 do while 루프 내에서 값을 복사하는 방법을 구현하려고 시도했다. 이것은 내가 제대로 새로운 해시 테이블에 각각의 값을 복사하는 방법을 정말 아주 확실하지 않다. 내 코드 (즉 일을 완전히 짜증하지 않습니다 :()이 함께

for(unsigned int i = 0; i < amountOfBuckets; i++) { 
     // target 
     Node* newHead = hashTable[i]; 
     Node* newCurrent = newHead; 
     // source 
     Node* head = hm.hashTable[i]; 
     Node* current = head; 
     do{ 
      newCurrent = new Node(); 
      newCurrent->key = current->key; 
      newCurrent->value = current->value; 
      newCurrent->next = current->next; 
      newCurrent = hashTable[i]; 
     } while(newCurrent != nullptr); 

내가 세그멘테이션 오류로 실행이다 ? 또는이 모두 함께 연결하는 가야하는 방법을 여기에

이 HashMap.hpp

에 대한

#ifndef HASHMAP_HPP 
#define HASHMAP_HPP 
#include <functional> 
#include <string> 
class HashMap 
{ 
public: 
    typedef std::function<unsigned int(const std::string&)> HashFunction; 
    static constexpr unsigned int initialBucketCount = 10; 
public: 
    HashMap(); 

    // This constructor instead initializes the HashMap to use a particular 
    // hash function instead of the default 
    HashMap(HashFunction hasher); 

    HashMap(const HashMap& hm); 
    ~HashMap(); 
    HashMap& operator=(const HashMap& hm); 

    void add(const std::string& key, const std::string& value); 
    void remove(const std::string& key); 
    bool contains(const std::string& key) const; 
    std::string value(const std::string& key) const; 

    unsigned int size() const; 
    unsigned int bucketCount() const; 
    double loadFactor() const; 
    unsigned int maxBucketSize() const; 


private: 
    // This structure describes the nodes that make up the linked lists in 
    // each of this HashMap's buckets. 
    struct Node 
    { 
     std::string key; 
     std::string value; 
     Node* next; 
    }; 
    // hash function gets stored in here 
    HashFunction hasher; 
private: 
    Node** hashTable; 
    unsigned int amountOfBuckets; 
    unsigned int sz; 

public: 
    unsigned int getTableIndex(unsigned int hashVal) const; 
}; 

선언입니다 그리고 여기에 대한 HashMap.cpp. 또한 내 (불완전) 코드, 난하지 않습니다 현재 네임 스페이스에있는 해시 함수를 사용합니다. dict 버켓 인덱스를 사용하여 추가/제거 기능을 테스트합니다.

#include <iostream> 
#include "HashMap.hpp" 

namespace { 
    unsigned int easyHashFunc(const std::string& key) { 
     unsigned int hashValue = 0; 
     for(int i = 0; i < key.length(); i++) { 
      int letterIndex = key.at(i); 
      hashValue += letterIndex; // just add up the letters 
     } // end for 
     return hashValue; 
    } // end easyHashFunc 
} 

HashMap::HashMap() 
    : hasher{easyHashFunc}, hashTable{new Node*[initialBucketCount]()}, amountOfBuckets{initialBucketCount}, sz{0} 
{ 
} 

// constructor that initializes HashMap to use a different hash function other 
// than the default 
HashMap::HashMap(HashFunction hasher) 
    : hasher{hasher}, hashTable{new Node*[initialBucketCount]()}, amountOfBuckets{initialBucketCount}, sz{0} 
{ 
} 

HashMap::HashMap(const HashMap& hm) 
    : hashTable{new Node*[hm.amountOfBuckets]}, amountOfBuckets{hm.amountOfBuckets}, sz{hm.sz} 
{ 
    for(unsigned int i = 0; i < amountOfBuckets; i++) { 
     Node* newHead = hashTable[i]; 
     Node* newCurrent = newHead; 
     // source 
     Node* head = hm.hashTable[i]; 
     Node* current = head; 
     do{ 
      newCurrent = new Node(); 
      newCurrent->key = current->key; 
      newCurrent->value = current->value; 
      newCurrent->next = current->next; 
      newCurrent = hashTable[i]; 
     } while(newCurrent != nullptr); 
    } 
} 


// destructor: deallocate the HashMap 
HashMap::~HashMap() 
{ 
    for(unsigned int i = 0; i < amountOfBuckets; i++) { 
     Node* nextNode = hashTable[i]; // store each hashtable list in a bucket node 
     while(nextNode != nullptr) { 
      Node* deleteCurrent = nextNode; // set current to the bucket node (head) 
      nextNode = nextNode->next; // delete current is on the first node, update head to second node 
      delete deleteCurrent; 
     } // end while 
    } // end for 
    // once done, delete hash table 
    delete[] hashTable; 
} // end destructor 

// Assignment operator that overloads equals 
HashMap& HashMap::operator=(const HashMap& hm) 
{ 
    // incomplete 
    return *this; 
} 

void HashMap::add(const std::string& key, const std::string& value) 
{ 
    // Check if key being stored matches key already in hashmap 
    unsigned int hashedValue = hasher(key); // get hash value (unmodified by buckets) 
    unsigned int tableIndex = getTableIndex(hashedValue); // get the table index 
    // case 1, check to see if current is nullptr, meaning our first node 
    // is the one we should use, ie. we don't need to traverse the list 
    if(contains(key) == true) { // if key is already in the hashtable 
     return; // exit program 
    } else { // otherwise, key is not in the hash table 
     Node* head = hashTable[tableIndex]; 
     Node* current = head; 
     if(current == nullptr) { 
      // nothing in bucket 
      // create a new node 
      current = new Node(); 
      current->key = key; // set username 
      current->value = value; // set pw 
      current->next = nullptr; 
      hashTable[tableIndex] = current; 
      return; // exit 
     } else { 
      do { 
       current = current->next; // advance to next node 
      }while(current != nullptr);// end while 
      // currently at node we want to insert key/value at 
      current = new Node(); 
      current->key = key; // set key(username) 
      current->value = value; // set value (pw) 
      current->next = head; 
      hashTable[tableIndex] = current; // set next to point to nullptr 
     } // end inner if-else (creates node) 
    } // end outer if-else 
} // end add 

// takes in a key (username), removes it and the value (password) associated 
// with it, otherwise, it has no effect 
void HashMap::remove(const std::string& key) 
{ 
    unsigned int hashedValue = hasher(key); 
    unsigned int tableIndex = getTableIndex(hashedValue); 
    if(contains(key) == false) { // could not find key in bucket 
     return; // do nothing 
    } else { 
     Node* prevNode = hashTable[tableIndex]; 
     Node* delNode = prevNode; 
     if(prevNode->key == key) { // first one is a match 
      hashTable[tableIndex] = prevNode->next; // set the head of the hash table to point to the next node 
      delete delNode; 
      return; // exit 
     } else { // otherwise, we must loop through and find the node we want to delete 
      do{ 
       // check for match, if found, break out of do while 
       if(delNode->key == key) { 
        break; 
       } 
       prevNode = delNode; // save current node in previous 
       delNode = delNode->next; // point the searched node to the next node 
      }while(delNode != nullptr); // end do while 
      // set the previous node to point to delNodes next node 
      prevNode->next = delNode->next; 
     } // end inner if-else 
     delete delNode; // de-allocate 
    } // end outer if-else 
} // end remove() 

// returns true if given key is in hash map, otherwise returns false 
// this acts as a find method 
bool HashMap::contains(const std::string& key) const 
{ 
    unsigned int hashedValue = hasher(key); // hash the key given to get an index 
    unsigned int tableIndex = getTableIndex(hashedValue); // get the table index 
    Node* current = hashTable[tableIndex]; 
    // iterate through each node in the linked list 
    // start at first node (this is current) 
    while(current != nullptr) { 
     if(current->key == key) { 
      return true; // found match, exit 
     } 
     current = current->next; 
    } // end while 
     return false; // we haven't found a match 
} 

// value() returns the value associated with the given key in this HashMap 
// if the key is stored in this HashMap; if not, the empty string is returned. 
std::string HashMap::value(const std::string& key) const 
{ 
    if(contains(key) == true) { // found match 
     unsigned int hashedValue = hasher(key); // hash the key given to get an index 
     unsigned int tableIndex = getTableIndex(hashedValue); // get the table index 
     Node* current = hashTable[tableIndex]; 
     while(current != nullptr && current->key != key) { 
      current = current->next; 
     } 
     return current->value; // return value after traversal 
    } else { 
     return ""; // no match, return empty string 
    } 
} 

unsigned int HashMap::size() const 
{ 
    return sz; 
} 

unsigned int HashMap::bucketCount() const 
{ 
    return amountOfBuckets; 
} 

double HashMap::loadFactor() const 
{ 
    return sz/amountOfBuckets; 
} 

// return the table index for a given hashvalue 
unsigned int HashMap::getTableIndex(unsigned int hashVal) const { 
    return hashVal % amountOfBuckets; 
} 

Answer 1

HashMap::HashMap(const HashMap& hm) 
{ 
    amountOfBuckets=hm.amountOfBuckets; 
    hashTable= new Node* [amountOfBuckets]; 

    for (int i=0; i<amountOfBuckets; i++) 
    { 
     Node* n = hm.hashTable[i]; 
     Node** p = &hashTable[i]; 
     *p = NULL; 
     while (n) 
     { 
      Node* c = new Node(*n); // node copy constructor, should set n->next to null 
      *p = c; 
      p=&c->next; 
      n=n->next; 
     } 
    } 
} 

당신이 노드의 복사 생성자가 노드 * C = 새로운 노드 (* N)를 교체하지 않을 경우; with :

 Node* c = new Node; 
     c->key = n->key; 
     c->value = n->value; 
     c->next = NULL;