HashTable Bucketing not working for copy constructor

I am wondering why in the below code the copy constructor is not bucket copying for the hash table
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class,HashTable. I have tried everything and nothing seems to work.
HashTable<TYPE>::HashTable(const HashTable<TYPE>& other) {
	table_ = new  Record*[other.cap];
	size_=other.size_;
	hash = other.hash;
	cap=other.cap;
	for(int i=0;i<other.cap;i++){
		if(other.table_[i]==nullptr){
			table_[i]=nullptr;
			continue;
		}
		string key=other.table_[i]->getKey();
		TYPE data=other.table_[i]->getData();
		table_[i]=new Record(key,data);
		Record* entry=other.table_[i]->getNext();		
		Record* insert=table_[i]->getNext();;
                //Bucketing code
		while(entry!=nullptr && entry->next_){
		insert=new Record(entry->key_,entry->data_);
		entry=entry->getNext();
		insert=insert->getNext();
		}
	}
}

Last edited on
On line 16 you set a local variable insert equal to the value returned by table_[i]->getNext(). On line 19 you throw away that value and set it equal to the result of the new expression. On line 21, you throw that value away too.

Your copy constructor is leaking nearly all of the memory it allocates.

It's impossible to say exactly how you should go about remedying the situation since you've only supplied an incomplete, uncompilable snippet of code that is incapable of reproducing your issue.
Here is my code. I just need the part I comment with bucketing to work, this is the comment
//need to move over elements from next pointers of other.table's element at i for bucketing to work.
#include<algorithm>
#include <stdio.h>
#include <string>
#include <utility>
#include<iostream>

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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
template <class TYPE>
class Table {
public:
	Table() {}
	virtual bool update(const string& key, const TYPE& value) = 0;
	virtual bool remove(const string& key) = 0;
	virtual bool find(const string& key, TYPE& value) = 0;
	virtual ~Table() {}
};
template <class TYPE>
class HashTable :public Table<TYPE> {
	// This is the internal structure for array elements for hastable
	struct Record {
			TYPE data_; // data per array element
			string key_;//key to lookup for data element
			Record* next_; // next record to create linkly linked list for bucketing
			// Constructor to set values of Record
			Record(const string& key, const TYPE& data) {
				key_ = key;
				data_ = data;
				next_=nullptr;
			}
			//Returns key of Record
			string getKey() const {
        			return key_;
    			}
			//Sets key of Record
			string setKey(string key) {
        			key_=key;
    			}
			//Returns data member of Record
    			TYPE getData() const {
				return data_;
		    	}
			//Sets data member of Record 
		    	void setData(TYPE data) {
				data_=data;
		    	}
			//Gets next element in linked list for bucketing	
		    	Record *getNext() const {
				return next_;
		    	}
			//Sets next element in linked list for bucketing
		    	void setNext(Record *next) {
				next_ = next;
			}
			
		};

	Record** table_;   //the table
	int size_;//size_
	int cap;//max number of records allowed in table
	std::hash<std::string> hash;//hash function used
	
public:
	HashTable(int maxExpected);
	HashTable(const HashTable& other);
	HashTable(HashTable&& other);
	int numRecords();
	bool isEmpty();
	virtual bool update(const string& key, const TYPE& value);
	virtual bool remove(const string& key);
	virtual bool find(const string& key, TYPE& value);
	virtual const HashTable& operator=(const HashTable& other);
	virtual const HashTable& operator=(HashTable&& other);
	virtual ~HashTable();
};
/* none of the code in the function definitions below are correct.  You can replace what you need
*/
//returns size of table
template <class TYPE>
int HashTable<TYPE>::numRecords() {
	return size_;
}
//returns if hashtable has no records been inserted
template <class TYPE>
bool HashTable<TYPE>::isEmpty(){
	return size_==0;
}
//Constructor that allocates memory equal to passed amount in maxExpected and sets hashtable to empty state
template <class TYPE>
HashTable<TYPE>::HashTable(int maxExpected) : Table<TYPE>() {
		int size_=0;
		table_=new Record*[maxExpected]();
		cap=maxExpected;
}
//Copy Constructor that creates a copy of passed hashtable as argument to create a new copy of including memory allocations
template <class TYPE>
HashTable<TYPE>::HashTable(const HashTable<TYPE>& other) {
	table_ = new  Record*[other.cap];
	size_=other.size_;
	hash = other.hash;
	cap=other.cap;
	
        for(int i=0;i<other.cap;i++){
		if(other.table_[i]==nullptr){
			table_[i]=nullptr;
			continue;
		}
           //need to move over elements from next pointers of other.table's element at i for bucketing to work
		swap(table_[i],other.table_[i]);
		
	}
}
//Move constructor that moves the hashtable passed into the current table being constructed
template <class TYPE>
HashTable<TYPE>::HashTable(HashTable<TYPE>&& other) {
	swap(size_,other.size_);
	swap(cap,other.cap);
	swap(table_,other.table_);
	swap(hash,other.hash);
}
//Updates record with the string passed to the new data for the record's data element and returns true if found/updated otherwise false
template <class TYPE>
bool HashTable<TYPE>::update(const string& key, const TYPE& value) {
	int hashvalue=hash(key)%cap;
	Record* prev=nullptr;
        Record* entry=table_[hashvalue];

        while (entry != nullptr && entry->getKey() != key) {
            prev=entry;
            entry=entry->getNext();
        }

        if (entry == nullptr) {
            entry = new Record(key, value);
            if (prev == nullptr) {
                // insert as first bucket
                table_[hashvalue] = entry;
            } else {
                prev->setNext(entry);
            }
        } else {
            // just update the value
            entry->setData(value);
        }
	size_++;
	return true;
}
//Removes the record with the string passed for the key value and returns true if removed otherwise false if not found
template <class TYPE>
bool HashTable<TYPE>::remove(const string& key) {
	int  hashValue = hash(key)%cap;
        Record *prev = nullptr;
        Record *entry = table_[hashValue];

        while (entry != nullptr && entry->getKey() != key) {
            prev = entry;
            entry = entry->getNext();
        }

        if (entry == nullptr) {
            // key not found
            return false;
        }
        else {
            if (prev == nullptr) {
                // remove first bucket of the list
                table_[hashValue] = entry->getNext();
            } else {
                prev->setNext(entry->getNext());
            }
            delete entry;
        }
	size_--;
	return true;
}
//Finds value in table and updates with the value passed if found returns true otherwise false
template <class TYPE>
bool HashTable<TYPE>::find(const string& key, TYPE& value) {
	int  hashValue = hash(key)%cap;
        Record* entry =table_[hashValue];
        while (entry != nullptr) {
            if (entry->getKey() == key) {
		value=entry->getData();
                return true;
            }
            entry = entry->getNext();
        }
	return false;
}
//Copy Assignment Operator creates copy of hashtable passed into current hashtable
template <class TYPE>
const HashTable<TYPE>&HashTable<TYPE>::operator=(const HashTable<TYPE>& other) {
	if (table_) {
		delete[] table_;
	}
	table_ = new  Record*[other.cap];
	size_=other.size_;
	hash = other.hash;
	cap=other.cap;
	return *this;
}
//Moves Assignment Operator which moves passed hashtable into current hashtable
template <class TYPE>
const HashTable<TYPE>& HashTable<TYPE>::operator=(HashTable<TYPE>&& other) {
		swap(size_,other.size_);
		swap(table_,other.table_);
		swap(hash,other.hash);
		swap(cap,other.cap);
		return *this;

}
//Destructor this destroys the hashtable when it goes out of scope or is called directly
template <class TYPE>
HashTable<TYPE>::~HashTable() {
	// destroy all buckets one by one
        for (int i = 0; i < cap; ++i) {
            Record *entry = table_[i];
            while (entry != nullptr) {
                Record *prev = entry;
                entry = entry->getNext();
                delete prev;
            }
            table_[i] = nullptr;
        }
        // destroy the hash table
	delete [] table_;
}

It almost works expect for bucketing as stated about. I managed to use swap but it nulls out other so was wondering if there is a way to fix that.
Last edited on
Topic archived. No new replies allowed.