私は自分のハッシュマップをC++で実装しようとしています。 私のヘッダが C++でハッシュマップの実装中に奇妙なことが起こった
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;
};
である私は
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;
}
を使用して、私のマップを初期化し、ここでハッシュマップ
今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;
}
}
}
に要素を置くための私のコードで、ここれます奇妙な部分は、初期化直後でさえも。たとえば、MyMap m = MyMap();
とします。そして、私は0から100までの対(i、i)を入力しました。私はすべてのバケツ[i]がヌルポインターではないことを発見しました(私はbuckets[bucket] == null
のような文章を追加しました)!私は地図にペアを置く前に。いくつかはありますが、そうではありません! どうしてこのようなことが起こるのでしょうか?私はちょうどそれらをすべてnullptr
に初期化しましたか?
FYI、コンストラクタ内で確認し、すべてのバケット[i]は確かにnullptr
です。このバグが私を狂わせてしまっています.... 誰かが私を助けてくれますか?ありがとう!
はあなたがこれをしてもよろしいです。 '新しいkey_val_pair * [nBuckets];'? (*) – Stefan
@Stefanはい、そうだと思います。リンクされたリストの配列は(キー、値)のペアで構成されています。 – jack
次の行: 'bucketArray buckets = createBucketArray(INIT_N_BUCKETS);'? 'bucketArray'をそれから削除するとどうなりますか? – pmaxim98