C++ hash set bad alloc with new

Question

I am doing a hash set project for school. I have an array of type "LinkedList" used for chaining. I wrote my code on Mac and compiled with clang++, everything runs and works fine (with memory leaks but I will fix those). The problem that I am having is compiling on Ubuntu Linux with g++ I get a bad alloc error. When run in valgrind it says conditional jump or move depends on uninitialised value(s). And says the error is coming from the following section:

LinkedList<ItemType>* table;
.
.
.
HashSet () :
    size(0),
    tableSize(0),
    table(new LinkedList<ItemType> [size])
{}

I suspect the error is in constructing the table. If I change the size to 5 (or any other number greater than 0) I get the same error, in other words I do not think that constructing an array of size 0 is the problem. Any ideas on how to fix this? I do not have a copy constructor in my LinkedList class, does the initialization of table call a copy constructor or the standard default constructor?

Answer 1

The order of initialization is not determined by the order of initializers in the constructor initialization list, but by the order in which members are declared in the class' body.

If size is declared below table, then it gets initialized to zero after the memory allocation takes place. By the time table is being initialized, size still contains random garbage, and you are allocating an array of some random size. Your code exhibits undefined behavior.

You can fix the problem simply by writing table(new LinkedList<ItemType>[0]). However, it's not clear why would you want to allocate an array of zero size in the first place. What good do you think that'll do you?

Rather than using a raw array and managing memory manually, consider using std::vector<LinkedList>. And std::list instead of home-grown LinkedList, for good measure.