C++ HashTable Read access violation

Question

I am building a HashTable in C++ which takes a name of a person as the key and stores his/her favorite drink, the hashtable is defined as below:

class HashTable {
private:
    static const int m_tableSize = 10;

    struct item {
        std::string name;
        std::string drink;
        item* next;
    };

    item* Table[m_tableSize];

I am using the constructor to fill every bucket in the hashtable as "empty":

HashTable::HashTable()
{
    for (int i = 0; i < m_tableSize; i++)
    {
        Table[i] = new item;
        Table[i]->name = "empty";
        Table[i]->drink = "empty";
        Table[i]->next = NULL;
    }
}

This code as it is works but, here's the question:

As far as I know, Table[i] = new item; is supposed to allocate each first item of the bucket in the heap instead of allocating in the stack, but if I try to supress this line, in other words, if I want the first item of each bucket to be allocated in the stack, the compiler throws a read access violation exception, why?

I don't necessarily want the first item of each bucket to be allocated in the stack, but I don't understand the compilers behavior in this case. I know it may be a little bit basic, but can some help?

What happens on the stack stays on the stack. Once the function exits, what you did on the stack is rendered invalid. Probably gone and not safe to use if it isn't. Some good reading on the topic: [Can a local variable's memory be accessed outside its scope?](https://stackoverflow.com/q/6441218/4581301) — user4581301, Mar 27 '23 at 22:19
Side note: Don't mix Automatic and Dynamic allocations unless you enjoy pain. You have to manage both differently and if you manage an object allocated with one approach they way you need to manage the other the best you can hope for is a memory leak. — user4581301, Mar 27 '23 at 22:22
Terminology note: With very rare exceptions, the compiler throws *nothing*. The compiler transforms your code into machine code. The computer runs the machine code. By the time the program is run and can throw exceptions, the compiler's job is long over. If the compiler itself throws an exception, you have written code that exposes a compiler bug. If your compiler's relatively up to date the best thing you can do is bundle the code up into a [mre] and file a bug report with the compiler vendor and go looking for a different way to write the program. — user4581301, Mar 27 '23 at 22:26
Additional good reading: [Why are the terms "automatic" and "dynamic" preferred over the terms "stack" and "heap" in C++ memory management?](https://stackoverflow.com/q/9181782/4581301) — user4581301, Mar 27 '23 at 22:30
Unless you're using a "sentinel node" implementation for your lists, you should use a null pointer for an empty bucket instead of a dummy object. — molbdnilo, Mar 28 '23 at 07:23

Andrés Alcarraz · Accepted Answer · 2023-03-29T01:01:38.813

0

I don't think the compiler is throwing that exception, but your code is provoking a read access violation exception at runtime.

The why is because if you don't initialize Table[i] to a memory place under your program can write or read, when you call Table[i] it is pointing to some random memory address your program doesn't have access to. And thus provoking the given error.

That said, Table is not a good name, capitalized aren't used for member variables but for custom types.

Also take into account that you should free all the allocated memory in the destructor, a better option would be that the table is not an array of pointers to item, but an array of item. In that case, you don't need the new item and also don't need to free that memory in the destructor.

In fact, since the hast table is supposed to be big, you should store it in dynamic memory, all the table, not just the items. I would change your code into something like this:

class HashTable {
private:
    static const int m_tableSize = 10;

    struct item {
        std::string name;
        std::string drink;
        item* next;
    };

    item* Table;
...
public:
    HashTable() ;
    ~HashTable() ;

HashTable::HashTable()
{
    Table = new item[m_tableSize]; //allocate dynamic memory for table
    for (int i = 0; i < m_tableSize; i++)
    {
        Table[i].name = "empty";
        Table[i].drink = "empty";
        Table[i].next = nullptr; //nullptr is preferred over NULL
    }
}

HashTable::~HashTable(){
   delete[] Table;
}

edited Mar 29 '23 at 01:01

answered Mar 27 '23 at 22:58

Andrés Alcarraz

1,570
1
12
21

I get that the hashtable being an array of `item` instead of `item*` would imply in not having to be concerned about freeing the memory in the destructor, but, wouldn't it be preferable to dynamically allocate the table in a situation where it is very big and, therefore, will occupy a lot of space in the stack? – AcKoucher Mar 28 '23 at 13:47
Yes, but in that case what you want is a Table pointer, that you would allocate in dynamic memory – Andrés Alcarraz Mar 28 '23 at 18:13
@AcKoucher, I expanded the answer with what I meant in my previous comment, I didn't "fix" the capitalization of the variables. – Andrés Alcarraz Mar 28 '23 at 20:19
After reading the expansion of the answer: As you pointed i was indeed running into a read access violation exception at runtime. Your solution accomplishes exactly what I intended to do, that being not only dynamically allocating the whole table, but using the destructor without having to iterate through the buckets, I appreciate the attention. – AcKoucher Mar 28 '23 at 20:49
One observation about your final answer, in the destructor it's necessary to use `delete[]` instead of `delete`. – AcKoucher Mar 28 '23 at 23:29
You're correct @AcKoucher, thank you, I already fixed the answer. – Andrés Alcarraz Mar 29 '23 at 01:02

C++ HashTable Read access violation

1 Answers1