dimanche 28 mai 2023

Use of copy constructor and overloading the assignment operator

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 then next_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 2D std::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