this is a homework question. I am working on my Hash Table
assignment and I got stuck on the re-hash
function. When I run the code I pasted below this error gets thrown:
terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_M_construct null not valid
Aborted (core dumped)
And after reading this I'm still very confused on what's happening.
My best effort of producing a minimal reproducible example:
// {
// @note I really tried to shorten it down as much as possible, but I still need certain functions and class declarations in order for the code to run
// }
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>
#include <atomic>
class DataEntry {
private:
std::string date;
std::string country;
int c_cases;
int c_deaths;
public:
DataEntry() {
this->date = "\0";
this->country = "\0";
this->c_cases = 0;
this->c_deaths = 0;
}
inline void set_date(std::string set_date) { this->date = set_date;};
inline void set_country(std::string set_country) { this->country = set_country;};
inline void set_c_deaths(int set_c_deaths) { this->c_deaths = set_c_deaths;};
inline void set_c_cases(int set_c_cases) { this->c_cases = set_c_cases;};
inline int get_c_cases() { return c_cases;};
inline int get_c_deaths() { return c_deaths;};
inline std::string get_date() { return date;};
inline std::string get_country() { return country;};
};
class CovidDB {
private:
int size = 17;
std::vector<std::vector<DataEntry*>> HashTable;
public:
inline CovidDB() {
HashTable.resize(size);
}
/** @note Copy constructor */
CovidDB(const CovidDB& other) {
size = other.size;
HashTable.resize(size);
for (int i = 0; i < size; ++i) {
for (const auto& entry : other.HashTable[i]) {
HashTable[i].push_back(new DataEntry(*entry));
}
}
}
inline void clear() {
for (auto& row : HashTable) {
for (auto& entry : row) {
delete entry;
}
row.clear();
}
HashTable.clear();
HashTable.shrink_to_fit();
///@link https://stackoverflow.com/questions/12587774/destructor-not-being-called
}
inline ~CovidDB() { //handles memory
clear();
}
/** @note Move constructor */
CovidDB(CovidDB&& other) noexcept {
size = other.size;
HashTable = std::move(other.HashTable);
other.size = 0;
}
/** @note Overloaded assigment operator*/
CovidDB& operator=(const CovidDB& other) {
if (this == &other) {
return *this; // Self-assignment
}
// clear the data and resources
for (auto& row : HashTable) {
for (auto& entry : row) {
delete entry;
}
row.clear();
}
HashTable.clear();
HashTable.shrink_to_fit();
// copy the data from the other object
size = other.size;
HashTable.resize(size);
for (int i = 0; i < size; ++i) {
for (const auto& entry : other.HashTable[i]) {
HashTable[i].push_back(new DataEntry(*entry));
}
}
return *this;
}
void rehash();
void display_table();
bool add(DataEntry*);
int re_hash_key(std::string);
int hash(std::string);
};
int CovidDB::re_hash_key(std::string country) {
int sum = 0;
int count = 0;
for (char c : country) {
sum = sum + ((count + 1) * c);
count++;
}
return sum % size; //returns the new hash
}
void CovidDB::rehash() {
auto is_prime = [](int num) {
if (num <= 1)
return false;
for (int i = 2; i <= std::sqrt(num); ++i) {
if (num % i == 0)
return false;
}
return true;
};
auto find_next_prime = [&is_prime](int num) {
while (true) {
if (is_prime(num))
return num;
++num;
}
};
int new_size = size * 2;
int new_prime_size = find_next_prime(new_size);
size = new_prime_size; //re-assign size
//CovidDB new_table(std::move(HashTable));//call move constructor, size 37
std::vector<std::vector<DataEntry*>> newHashTable(size); //temp object
newHashTable.resize(size);
// rehash all entries from the original table to the new table
for (std::vector<DataEntry*> row : HashTable) {
for (DataEntry* entry : row) {
int re_hash_i = re_hash_key(entry->get_country());
newHashTable[re_hash_i].push_back(entry);
}
}
// Clear the original table and update it with the new table
clear(); //predefined function that I removed due to MRE
HashTable = newHashTable;
std::cout << "SIZE: " << size << std::endl;
return;
}
void CovidDB::display_table() {
for(std::vector<DataEntry*> vec : HashTable) {
for(DataEntry* entry : vec) {
if (entry != nullptr) { //guard against dereferencing nullptr
std::cout << std::flush;
std::cout << "[Date: " << entry -> get_date() << "], "
<< "[Country: " << entry -> get_country() << "], "
<< "[Cases: " << entry -> get_c_cases() << "], "
<< "[Deaths: " << entry -> get_c_deaths() << "] "
<< std::endl;
}
}
}
std::cout << std::endl;
return;
}
int CovidDB::hash(std::string country) {
int sum = 0;
int count = 0;
for (char c : country) {
sum = sum + ((count + 1) * c);
count++;
}
return sum % size; //returns the hash
}
bool CovidDB::add(DataEntry* entry) {
int index = hash(entry->get_country());
HashTable[index].push_back(entry);
return true;
}
int main() {
CovidDB base;
DataEntry* data1 = new DataEntry();
DataEntry* data2 = new DataEntry();
data1->set_date("01/01/23");
data1->set_country("Slovenia");
data1->set_c_cases(1);
data1->set_c_deaths(1);
data2->set_date("02/02/23");
data2->set_country("Slovenia");
data2->set_c_cases(1);
data2->set_c_deaths(1);
// Add the entries to the CovidDB
base.add(data1);
base.add(data2);
base.display_table();
base.rehash();
base.display_table();
}
The main problem is my re-hash
method. My general idea was to:
-
Get the new size
size * 2
and thennext_prime(new_size)
to get the actual size, I used a couple of lambdas to achieve that. That part works since the new size is 37 as it should be. -
I emailed my professor about my problem and she said I need to follow the rule of 5 so I made my move constructor and my overloaded operator. I don't believe the move constructor is my answer here since I don't want a copy of my original table, but I want to parse all of the existing entries, re-hash and add them to the table. I could be wrong.
-
Finally, I decided to create a new object
CovidDB
and re-hash all of the. old/existing entries and push them into the new table. This sort of works but my compiler says there is no definition of the=
and the[]
operator if I make a new object. If I make a new 2Dstd::vecotr<std::vector<DataEntry*>>
instead of an object that works Again I don't think that's the right solution.
The strange part to me is the fact that here:
bool CovidDB::add(DataEntry* entry) {
int index = hash(entry->get_country());
HashTable[index].push_back(entry);
return true;
}
I can index my HasHTable
object using the []
operator, but I can't do the same thing in my re_hash
function. I get this error:
error: no match for ‘operator[]’ (operand types are ‘CovidDB’ and ‘int’)
155 | new_table[re_hash_i].push_back(entry);
for this:
CovidDB new_table;
for (std::vector<DataEntry*> row : HashTable) {
for (DataEntry* entry : row) {
int re_hash_i = re_hash_key(entry->get_country());
new_table[re_hash_i].push_back(entry);
}
}
Can someone help me figure out where I potentially went wrong and why would an error be thrown for the []
operator in one case but not the other?
I tried rubber duck debugging the code, especially the operator but came up empty-handed. My debugger throws me into the std::vector
library.
Aucun commentaire:
Enregistrer un commentaire