Search code examples
c++linked-listhashtable

Confused on why i have an std::logic_error in my hashtable code


I'm trying to show the index structure of my hashtable by organizing a struct "Student" by age. I don't know how to debug what I have because all I'm left with when trying to run the code is:

"terminate called after throwing an instance of 'std::logic_error' what(): basic_string::_M_construct null not valid"

which I don't understand.

This is what my code looks like:

#include<iostream>
#include<list>
using namespace std;

struct Student {
    string name;
    int age;
    double fee;

    Student() {
        name = "";
        age = 0;
        fee = 0.0;
    }
    Student(string n, int a, double d) {
        name = n;
        age = a;
        fee = d;
    }
};

class Hash {
private:
    int tableSize;
    list<Student>* HT;
public:
    Hash(int s) {
        this->tableSize = s;
        HT = new list<Student>[tableSize];
    }

    int hashFunction(int key) {
        return (key % tableSize);
    }

    void insert(int key, Student x) {
        int index = hashFunction(key);
        HT[index].push_back(x);
    }

    void print() {
        for (int i = 0; i < tableSize; i++) {
            cout << i;
            for (auto x : HT[i]) {
                cout << ", " << x.age;
            }
            cout << endl;
        }
        cout << endl;
    }

};

int main() {
    Student s1 = Student("s1", 25, 20.25);
    Student s2 = Student("s2", 19, 25.17);
    Student s3 = Student("s3", 18, 16.72);
    Student s4 = Student("s4", 11, 17.35);
    Student s5 = Student("s5", 32, 18.43);
    Student array[5] = { s1, s2, s3, s4, s5 };
    Hash HT(7);

    int n = sizeof(array) / sizeof(array[0].age);

    for (int i = 0; i < n; i++) { HT.insert(array[i].age, array[i]); };

    HT.print();

    return 0;
}

Could anyone help explain to me what this error means and how I can fix my code so I can print out my hash table structure?


Solution

  • Immidiate problems:

    • You calculate the number of elements in array erroneously.
      int n = sizeof(array) / sizeof(array[0].age);
      
      should be
      auto n = sizeof(array) / sizeof(array[0]);
      
      or better
      auto n = std::size(array);
      
    • You don't delete[] HT; in the destructor
      ~Hash() {
           delete[] HT;
      }
      

    I recommend using a std::vector<std::list<Student>> instead of doing manual memory management. It also has a size() member function to save you the trouble of calculating the size.