Hash table constructor

[DarkT]

Hi everyone.
We were given a homework to code a hash table. The objects and their members were given by our professor and we were only supposed to implement the functions (Add, Remove, Contains and Print), so I shouldn't change the objects. I should also do a copy constructor and a assignment operator (but that's another story i don't think I'll have any problems with that after I solve my current problem). The code compiles just fine but at first I got a segmentation fault on the line 158:
HashTable[HashCode(key)].Add(key). In debug mode HashCode(key) = 5 which is OK (5%10 = 5) so I tried to print every element of the array in the constructor itself. HashTable[0] works fine but HashTable[1] gives the segmentation fault so I guess the allocation fails or there's a logical error as I'm pretty new to OOP (although I thought that I pretty much get it).
I'd be thankful for any help.

#include <iostream>
#include <new>

using namespace std;
       
class Set
{
    public: 
        typedef string T;           
        virtual void Add(const T& key) = 0;
        virtual bool Contains(const T& key) = 0;
        virtual void Print() = 0;
        virtual void Remove(const T& key) = 0;
};

class ListSet: public Set
{
    private:  
        struct Node
        {
            T value;
            Node* next;
        };
    
        Node* first;
    public:
        ListSet()
        {
            first = NULL;
        };  
        ~ListSet()
        {
            Node* next = NULL;
            
            while (first != NULL)
            {
                next = first->next;  
                delete first;
                first = next;
            }
        };  
        void Add(const T& key)
        {
            Node* handle = first;
            Node* prev = NULL;            
             
            if (Contains(key) == true)
            {
                return;
            }
            
            while (handle != NULL)
            {
                prev = handle;
                handle = handle->next;
            }
            
            handle = new (nothrow) Node;
            handle->value = key;
            
            if (first == NULL)
            {
                first = handle;
            }          
            
            if (prev != NULL)
            {
                prev->next = handle;
            }            
        };
        bool Contains(const T& key)
        {
            Node* handle = first;
            
            while (handle != NULL)
            {
                if (key.compare(handle->value) == 0)
                {
                    return true;
                }  
                handle = handle->next;
            }
             
            return false;
        };
        void Print()
        {
            Node* handle = first;
            
            if (handle == NULL)
            {
                cout << "Som prazdny...\n";
            }     
            
            while (handle != NULL)
            {
                cout << (handle->value).c_str() << " ";
                handle = handle->next;
            }    
        };
        void Remove(const T& key)
        {
            Node* handle = first;
            Node* prev = NULL;            
             
            if (Contains(key) == false)
            {
                return;
            }
            
            while (key.compare(handle->value) != 0)
            {
                prev = handle;
                handle = handle->next;
            }
            
            if (prev != NULL)
            {
                prev->next = handle->next;
            }
            else
            {
                first = handle->next;
            }
            delete handle;          
        };
};

class HashSet: public Set
{
    private:  
        Set* HashTable;
        short size;
        
        short HashCode(const T& key)
        {
            return (key.length())%size;
        };
    public:
        HashSet(short size = 10)
        {          
            this->size = size;                   
            HashTable = new (nothrow) ListSet [size]; 
            
	    int i;
			
	    for (i=0; i<size; i++)
	   {
                HashTable[i].Print();
            }
        };
        ~HashSet()
        {                        
			delete[] HashTable;
        };
        void Add(const T& key)
        {
            HashTable[HashCode(key)].Add(key); 
        };
        bool Contains(const T& key)
        {
            return HashTable[HashCode(key)].Contains(key);
        };
        void Print()
        {
            int i;
             
            for (i=0; i<size; i++)
            {
                HashTable[i].Print();
                cout << "\n";
            }
        };
        void Remove(const T& key)
        {
            HashTable[HashCode(key)].Remove(key); 
        };
};

int main()
{
    Set* table = new (nothrow) HashSet();
    table->Add("Peter");
    table->Print();
    
    cout << "Pre ukoncenie programu stlacte enter...";
    cin.get();
    delete table;
    return 0;
}

[gashtio]

The problem lies here HashTable = new (nothrow) ListSet [size]; .Short explanation:

You are allocating an array of ListSet objects and handing the returned pointer to a Set * . This is not how inheritance works - you should allocate an array of Set pointers instead, and then allocate a ListSet object for each pointer. In code, that is:

int nSize = ...;
Base ** ppStuff = new Base * [nSize];
for( int i = 0; i < nSize; ++i )
	ppStuff[i] = new Derived();

...

for( int i = 0; i < nSize; ++i )
	delete ppStuff[i];
delete [] ppStuff;

Long explanation:

Every class that has virtual functions has a static virtual table - that's essentially an array of function pointers, one for each virtual function. Hidden from the programmer, the compiler adds a member variable - a pointer to that v-table. So your Set class actually looks something like this (in pseudocode):

class Set
{
public:
	typedef string T;
	virtual void Add(const T& key) = 0;
	virtual bool Contains(const T& key) = 0;
	virtual void Print() = 0;
	virtual void Remove(const T& key) = 0;

	function_ptr * __vfptr; // a pointer to a function pointer
	static function_ptr __vftable[] = { &Set::Add, &Set::Contains, &Set::Print, &Set::Remove };
	__vfptr = &Set::__vftable[0];
};

and the ListSet class:

class ListSet : public Set
{
	...

	static function_ptr __vftable[] = { &ListSet::Add, &ListSet::Contains, &ListSet::Print, &ListSet::Remove }; // this table is different from the Set one
	__vfptr = &ListSet::__vftable[0];
};

When calling a virtual function through a base pointer, the v-table is checked to determine the correct version of the function to be executed.

Now, back to your problem - "HashTable[0] works fine but HashTable[1] gives the segmentation fault":
Assuming 32-bit architecture, the size in bytes of the Set class is 4 bytes (the hidden __vfptr pointer), whereas the ListSet class is 8 bytes (the __vfptr pointer, and the Node * first ). HashTable = new (nothrow) ListSet [size]; allocates size ListSet objects, that you try to access through a Set pointer; Looking at the memory, it is something like this (each cell is 4 bytes):

ListSet obj #1      ListSet obj #2               ListSet obj #size
+---------+---------+---------+---------+        +---------+---------+
| __vfptr |  first  | __vfptr |  first  |  ...   | __vfptr |  first  |
+---------+---------+---------+---------+        +---------+---------+
    ^          ^        ^          ^                 ^           ^
HashTable[0]   |    HashTable[2]   |        HashTable[2*size-2]  |
          HashTable[1]        HashTable[3]              HashTable[2*size-1]

So what happens is that when you call HashTable[0].Print() , the v-table is checked, &ListSet::Print is resolved and executed, and all is fine. When you call HashTable[1].Print() however, a pointer to the v-table is expected in the place where first is; that pointer is invalid hence the segmentation fault.

The solution is to allocate an array of Set pointers first, and then the ListSet objects - that way the v-table will be in the correct place.

[DarkT]

Thanks a lot gashtio. I fixed the problem. There was another one (I wan't initializing next pointers when adding new node to the list that was an easy one to find and solve). Long explanation was really helpful because I like to know how things work. Now that I think about it the error is really obvious.