2d boolean array initialization in c++

Question

I don't use C that much and I recently got confused about 2d array initialization problem. I need to debug somebody's code and stuck in the following(her original code):

const int location_num = 10000;
bool **location_matrix;
if (node_locations)
    {
        location_matrix = (bool **)malloc(location_num*sizeof(bool *));
        if (!location_matrix)
        {
                cout<<"error 1 allocating location_matrix" << endl;
                exit;
        }
        for (i=0; i<location_num; i++)
        {
                location_matrix[i] = (bool *) malloc(location_num*sizeof(bool ));
                if (!location_matrix[i])
                {
                        cout<<"error 2 allocating location_matrix" << endl;
                        exit;
                }
                for (j=0; j<location_num; j++)
                        location_matrix[i][j] = false;
        }
    }

I thought is was redundant, so I changed it to the following:

location_matrix[location_num][location_num] = { {false} };

However, segmentation fault happens at runtime. My question is: how does the above code fail? If it looks right, what's the difference between dynamically allocation and static allocation? Is it just because the dimension might not be constant, so we need to do it dynamically? Also, just for curiosity, how do I malloc 2d array that stores pointers? Thanks.

Why are you using `malloc(n * sizeof(T))` instead of `new T[n]`? — moshbear, Nov 10 '11 at 19:06

Mark Wilkins · Answer 1 · 2013-02-18T23:58:04.113

4

The change would likely require about 100MB (10,000 * 10,000 * 1) on the stack, so the segmentation fault was likely due to a stack overflow.

Edit I originally stated 400MB in the answer, but @Mooing Duck points out bool will likely be 1 byte. I was thinking the Win32 BOOL (for no real reason at all), which is typedefed to an int.

edited Feb 18 '13 at 23:58

answered Nov 10 '11 at 18:02

Mark Wilkins

40,729
5
57
110

I don't know about c, but in c++ when it runs out of memory, the system will print "bad alloc", so are you saying that segmentation fault can also represent stack overflow in c? – Shang Wang Nov 10 '11 at 18:05
It depends on the compiler, but an "allocation" on the stack is basically an addition to the stack pointer (or subtraction ... I forget now if it typically goes up or down). If there is no stack checking enabled, then any reads/writes to that local variable that goes past the valid stack will be accessing memory that is outside the valid address space, which may result in the segmentation fault. – Mark Wilkins Nov 10 '11 at 18:08
@MarkWilkins: I think (in most implementaitons) a bool is only 1 byte. Still, StackOverflow seems likely. – Mooing Duck Nov 10 '11 at 18:13
@Mooing Duck: That is probably true. I will edit it. I was basing it (for no good reason) on the Win32 BOOL, which is 4 bytes. – Mark Wilkins Nov 10 '11 at 18:29

Mysticial · Accepted Answer · 2011-11-10T18:14:02.433

I actually don't see anything wrong with the code.

The following code doesn't work because location_matrix is not allocated:

location_matrix[location_num][location_num] = { {false} };

GCC will allow the following (as an extension):

bool location_matrix[location_num][location_num] = { {false} };

But it will blow your stack because 10000 x 10000 is too large.

Currently, your code uses dynamic allocation. That's the correct way to do it because the matrix is too large to be done as a static array (and may overrun the stack).

As for your last question, "how to make a 2d array that stores pointers": It can be done almost the same way as your current code. Just change bool to int*.

So a 2D array of NULL int pointers will look like this:

int ***location_matrix;
if (node_locations)
{
    location_matrix = (int***)malloc(location_num*sizeof(int**));
    if (!location_matrix)
    {
            cout<<"error 1 allocating location_matrix" << endl;
            exit;
    }
    for (i=0; i<location_num; i++)
    {
            location_matrix[i] = (int**) malloc(location_num*sizeof(int*));
            if (!location_matrix[i])
            {
                    cout<<"error 2 allocating location_matrix" << endl;
                    exit;
            }
            for (j=0; j<location_num; j++)
                    location_matrix[i][j] = NULL;
    }
}

`location_num` is a compile-time initialised local `const int` so this code should work in C++ (even w/o compiler extensions), unless I’m momentarily confused. — Konrad Rudolph, Nov 10 '11 at 18:05
@KonradRudolph: I was referring to the array initializer as the GCC extension. — Mysticial, Nov 10 '11 at 18:07
The initialiser looks OK to me, too. Now, you’re of course right about the size. — Konrad Rudolph, Nov 10 '11 at 18:10

score 3 · Answer 3 · answered Nov 10 '11 at 21:26

3

The standard library is your friend.

#include <vector>

int
main()
{
  int location_num = 1000;
  std::vector<std::vector<bool> > location_matrix(location_num, std::vector<bool>(location_num, false));
}

answered Nov 10 '11 at 21:26

emsr

15,539
6
49
62

2

Be aware that vector has issues - it is not an array of bools really. The standard library specialized vector so it packs bits into an attempt at a dynamic bitset. If you really need an array of bools so that .data() gives you a pointer to bool* then put std::deque inside. – emsr Nov 11 '11 at 15:08

score 2 · Answer 4 · edited May 23 '17 at 12:17

Second, the array is likely too large to fit on the stack, so you'd need to dynamically allocate it -- but you can simplify the code as long as the difference between a 2-dimensional array and an array of pointers won't be an issue (as it would be if you needed to pass the array to a function or use pointer arithmetic with it).

You could use something like this:

bool (*location_matrix)[location_num];

location_matrix = (bool (*)[location_num])calloc( location_num, 
                                                  location_num * sizeof(bool) );

...which allocates space for the whole two-dimensional array and gives a pointer to an array of bool arrays with location_num elements each.

2d boolean array initialization in c++

4 Answers4