Array Creation Problems in C++

Question

I'm a novice programmer trying to get a head start on some classes before the summer semester starts, and I've run into this problem while trying to create a Quick Union algorithm in C++.

I've been trying to figure out why my program creates two identical arrays, despite having two separate for loops designed to create two different arrays. Whenever my program runs to completion and prints id[] and sz[], it always outputs 1 as the element at every index in both arrays.

class quickUnionUF{
private:
    int id[];
    int sz[];
    int root(int);
public:
    quickUnionUF(int, int);
    bool connected(int, int);
    void unionPoint(int, int);
    void print();
};

quickUnionUF::quickUnionUF(int n, int b){
    id[n];
    sz[b];
    for(int i=0;i<n;i++){
        id[i] = i;
    }
    for(int j=0;j<b;j++){
        sz[j] = 1;
    }
}

For example, if I create quickUnionUF(5, 5);

id[] should now contains elements:

0, 1, 2, 3, 4

And sz[] contains elements:

1, 1, 1, 1, 1

However, the program creates an array sz[] AND array id[] with elements:

1, 1, 1, 1, 1

Any thoughts as to why this is happening?

Answer 1

Your code hints at a two very important mistakes:

1. C++ does not work like Java. int id[] is not an reference to an array of arbitrary size on the garbage collected heap. It is instead a member array of undefined size used to implement dynamic arrays (and similar features) in C99. You should never use this syntax unless you know exactly what you are doing, because it is almost guaranteed to be wrong otherwise.

2. id[n] does not allocate an array at all. Instead it just indexes id and discards the result.

Listen to your compiler!

First, your code should not compile due to the fact, that only the last member of a struct may be a flexible array type. In fact clang howls:

main.cpp:53:9: error: field has incomplete type 'int []'
    int id[];

MSVC howls:

1>main.cpp(54): error C2229: class 'quickUnionUF' has an illegal zero-sized array

And g++ only warns (well, g++ is strange in what it accepts sometimes):

main.cpp:53:12: warning: ISO C++ forbids zero-size array ‘id’ [-Werror=pedantic]
    int id[];

Note: g++ is wrong in compiling this, even if one allows flexible array members. This is defined in C99 6.7.2.1§16 and C11 6.7.2.1§18 both of which begin with (emphasis is mine):

As a special case, the last element of a structure with more than one named member may have an incomplete array type; this is called a flexible array member. [...]

What is happening?

Well, assuming you got your code to compile anyway, it basically means the following:

Create an object with the alignment of integers, but NO elements at all. Take a peek at the following test program:

quickUnionUF q;
::std::cout << sizeof(quickUnionUF) << "\n";
::std::cout << &q << "\n" << &q.id[0] << "\n" << &q.sz[0] << "\n";

The only compiler that managed to compile this at all (gcc 4.9.0) gave the following result:

0
0x7fff1bf6274c
0x7fff1bf6274c
0x7fff1bf6274c

So, this is a zero byte object (yes, this is illegal C++, since every C++ object has a size > 0) and the first element of each array is at the same position (OUTSIDE YOUR OBJECT!). Remember, you declared id and sz to have zero elements!

Therefore, you are writing to the same arbitrary position. You can consider this the extreme case of a buffer overflow: By writing 5 integers to a zero size buffer, you are overflowing from the first zero size buffer through the second zero size buffer into memory totally not under your control.

This also explains your observed result: The second loop simply overwrites what the first did (and it still does it by corrupting your stack).

How do I fix this?

Just use a vector. You can tell it how big you want it and you can ask it to tell you when you are indexing to some position that is not yours.

Answer 2

Standard C++ does not have sizeless array members. Use std::vector<int> as dynamically sized arrays in C++.

#include <vector>
class quickUnionUF{
private:
    std::vector<int> id;
    std::vector<int> sz;
    int root(int);
public:
    quickUnionUF(int, int);
    bool connected(int, int);
    void unionPoint(int, int);
    void print();
};

quickUnionUF::quickUnionUF(int n, int b)
    : id(n)
    , sz(b)
{
    for(int i=0;i<n;i++){
        id[i] = i;
    }
    for(int j=0;j<b;j++){
        sz[j] = 1;
    }
}