c: 2d arrays and double pointers

[kamper]

So I did a few semesters in C a couple of years ago and had the whole pointer/array thing down reasonably well. Mostly that int * foo is equivalent to int foo[].

I probably had done some 2d arrays (on the stack at least) and the concept that it's just one chunk of memory with a complex index is clear enough. I'm doing some stuff in c again needing to dynamically allocate a 2d array of integers so I assumed that you could use a double pointer just like a 2d array, but of course I'm wrong.

After reading a bit and thinking I get it that an int ** needs a series of seperately allocated chunks because the first array is an array of pointers. Am I correct in my understanding that you then access it with the same syntax as a 2d array on the stack and the compiler will figure out whether or not to use the indirection to follow your indices? (see code eg #1

Also, is it not possible to malloc a single block and use a cast to trick the compiler into accessing it like a stack 2d array? See code eg #2 for how I picture this (it's not working, obviously).

Edit: btw, the compiler error for eg #2 is "error: array type has incomplete element type" on the line of the cast.

 

[xtknight]

If it helps, I'm fairly sure you can just define a block of memory (i.e. raw_memory) and then address it as if it were defined as a 2D integer array. As in:

int * raw_memory = (int *) malloc(x * y * sizeof(int));
raw_memory[0][0] = 6666;
[...]
free(raw_memory);

Can't say I'm 100% certain but you can give it a try.

I've never seen a cast of int[][] before. If you want to use another variable, just assign the pointer of local_array to the pointer raw_memory.

int * local_array = raw_memory;
local_array[0][0] = 6666;
[...]
free(local_array); // same effect as free(raw_memory);

I think?

 

[kamper]

That makes sense to me but the compiler (currently gcc 4.0 on os x) doesn't like it: "error: subscripted value is neither array nor pointer"

I can't see why it wouldn't be capable of doing it, I guess it's just a bug prevention check? If I wanted the compiler to stop me from shooting myself, I wouldn't be using c, dammit

 

[itachi]

int * raw_memory = (int *)...
raw_memory[0][0] ...
is illegal.. raw_memory is a single dimension array, trying to access it as a 2d array won't work.

in c and c++, when you're casting between incompatible types you have to cast the variable, not the value.
void * raw_memory = malloc(x * y * sizeof(int));
int local_array[][] = *((int ***) &raw_memory);

 

[kamper]

Originally posted by: itachi
int * raw_memory = (int *)...
raw_memory[0][0] ...
is illegal.. raw_memory is a single dimension array, trying to access it as a 2d array won't work.

Hmm, now that I think about it some more I think I understand it finally :light: The compiler can't do it without knowing the supposed size of the 1st dimension. So for a valid 2d array on the stack, it's got to translate the double index to a single index at compile time so it can throw away any knowledge about dimensions. Aha!

in c and c++, when you're casting between incompatible types you have to cast the variable, not the value.
void * raw_memory = malloc(x * y * sizeof(int));
int local_array[][] = *((int ***) &raw_memory);

Alright, but as per above, that won't go either, but what about:
int local_array[x][] = *((int ***) &raw_memory);
?

 

[xtknight]

Oh yeah...well will just raw_memory[x] work as 1D then? As in:

int * raw_memory = (int *) malloc(x * y * sizeof(int));
raw_memory[0] = 6666;

and there should be (x * y) number of array entries possible in raw_memory? Just not that y creates a second dimension or anything.

Irrelevant though because I realize you do want 2D. You want an array of pointers to integers basically?

Do you have to allocate a second dimension based on looping through the first dimension? As in if the first dimension had 50 entries, then if you wanted 4 each in the second dimension, you loop through and create malloc 4 * sizeof(int) for each...something.

Is this of any help? (Dynamic Memory Allocation :: Multi-dimensional Structures)

Maybe this will work. I love it how they don't give a single example as to how you're supposed to address the array.

See below for example. I finally managed to get it to work.

 

[DaveSimmons]

Yes you can malloc a block of size -anything- like malloc ((x * y * z + 5 -12) * sizeof(int) ) and treat it as a 1D array.

You can also malloc one big buffer and "slice it up" into multiple dimensions, but you need an array of pointers to do this.

int *bigff = malloc ( x * y * sizeof (int )) ;
int **twod = malloc ( x * sizeof (int* ) ) ;

int ix = 0 ;
for ( int i = 0 ; i < x ; i++ )
{
twod[ i ] = &bigbuff[ ix ] ;
ix += y ;
}

 

[xtknight]

I got it working! See code below. So what this does is we have in the first dimension (coordinate sets) 0-49 and then in the second we have (coordinates) 0-2 (x=0,y=1,z=2). So to access coordinate set 5's z coordinate we'd address it as xyz[5][2].

Then say we want to add some entries to the first dimension. This adds INCREMENT number of entries. And the values prior to reallocation were preserved as you can see with the first printf afterwards. Hope this helps.

 

[itachi]

Originally posted by: kamper
Hmm, now that I think about it some more I think I understand it finally :light: The compiler can't do it without knowing the supposed size of the 1st dimension. So for a valid 2d array on the stack, it's got to translate the double index to a single index at compile time so it can throw away any knowledge about dimensions. Aha!

it's got nothing to do with dimensions.. when you declare a 1d array, the compiler doesn't know that each entry in the array is a memory address.. so you can't use it as a 2d array, where one array contains the address to another array.

Alright, but as per above, that won't go either, but what about:
int local_array[x][] = *((int ***) &raw_memory);
?

yea, you're right. forgot about the reference indices.

int ** allocate2dArray(int M, int N) {
void * buf; int ** arr;
int i;

buf = malloc(N * M * sizeof(int));
arr = (int **) malloc(N * sizeof(int));

for(i = 0; i < N; i++)
arr = ((int *) buf) + i * M;

return arr;
}

 

[kamper]

Originally posted by: itachi

Originally posted by: kamper
Hmm, now that I think about it some more I think I understand it finally :light: The compiler can't do it without knowing the supposed size of the 1st dimension. So for a valid 2d array on the stack, it's got to translate the double index to a single index at compile time so it can throw away any knowledge about dimensions. Aha!

it's got nothing to do with dimensions.. when you declare a 1d array, the compiler doesn't know that each entry in the array is a memory address.. so you can't use it as a 2d array, where one array contains the address to another array.

But for a 2d array on the stack, it is essentially a 1d array (there's no indirection). When you access it with 2 indices the compiler knows the size of the first dimension so it knows how much to multiply the first index by. I wanted to treat a malloced 1d array the same way but it's just a matter of telling the compiler what the size of the 1st dimension is. At any rate, I'm not going that route for now and this is just a trivial part of the assignment so I've got to move on

 

[itachi]

Originally posted by: kamper
But for a 2d array on the stack, it is essentially a 1d array (there's no indirection). When you access it with 2 indices the compiler knows the size of the first dimension so it knows how much to multiply the first index by. I wanted to treat a malloced 1d array the same way but it's just a matter of telling the compiler what the size of the 1st dimension is. At any rate, I'm not going that route for now and this is just a trivial part of the assignment so I've got to move on

you're not allocating it on the stack. the stack is only for statically allocated data.

 

[kamper]

Originally posted by: itachi

Originally posted by: kamper
But for a 2d array on the stack, it is essentially a 1d array (there's no indirection). When you access it with 2 indices the compiler knows the size of the first dimension so it knows how much to multiply the first index by. I wanted to treat a malloced 1d array the same way but it's just a matter of telling the compiler what the size of the 1st dimension is. At any rate, I'm not going that route for now and this is just a trivial part of the assignment so I've got to move on

you're not allocating it on the stack. the stack is only for statically allocated data.

I know that . What I'm trying to get at is that the compiler treats references to stack allocated arrays different than heap allocated ones and I wanted to fool it into treating a heap array like a stack one.

 

[itachi]

what i said will do just that.

void * raw = malloc(M * N * sizeof(int));
int ** arr = malloc(M * sizeof(int));

for(int i = 0; i < M; i++) arr = raw + i * N;

// arr[0] = raw
// arr[1] = raw + N
// arr[2] = raw + N * 2

if you're trying to get rid of the 1st dereference, then you'd have to do it as a 1d array.

 

[kamper]

Arghh! We're arguing in pointless circles

The code you just posted (same as what DaveSimmons posted earlier) is not what I originally wanted because you've still got multiple allocations. But really it's pointless now.

 

[xtknight]

You can't declare a 1D array and address it as a 2D array. The compiler doesn't know where to include the second dimension. malloc(x*y) is just a single dimension array of x*y number of entries. There is no way you can address that one variable to make it so that x is the first dimension and y is the second dimension. It just doesn't work that way...

However you can declare a second array and have its indices map in a way that the dimensions are divided (like the posters above gave examples of) but like I said, the compiler doesn't do that for you. I mean, how would it know if you wanted a big x*y 1D array, or x being first dimension, y being second, or what? Dimension is something you have to define at declaration time and not when you address it. Hope that answers your question. If you want an example of a completely dynamic/adjustable 2D array you can see my example above.

 

[kamper]

Originally posted by: xtknight
You can't declare a 1D array and address it as a 2D array. The compiler doesn't know where to include the second dimension. malloc(x*y) is just a single dimension array of x*y number of entries. There is no way you can address that one variable to make it so that x is the first dimension and y is the second dimension. It just doesn't work that way...

Yes, that is what I've been saying all along except I've somewhat stupidly been confusing the first dimenion with the second. However, since the addressing of a 2d array on the stack is figured out by the dimension specified on the variable (int array[2][2]) and not the actual memory itself, I still think it should be possible to treat a single chunk of memory like a 2d array if you tell the compiler about the 2nd dimension when you do the cast (as in my banter with itachi above, except for the 1st/2nd dimension confusion). I'm not saying that you can actually do it (haven't seriously tried) but I don't see why they couldn't implement it in the compiler if they wanted to. It would require 'magic', but afaict, 2d arrays on the stack are 'magic' too.

However you can declare a second array and have its indices map in a way that the dimensions are divided (like the posters above gave examples of) but like I said, the compiler doesn't do that for you. I mean, how would it know if you wanted a big x*y 1D array, or x being first dimension, y being second, or what? Dimension is something you have to define at declaration time and not when you address it. Hope that answers your question. If you want an example of a completely dynamic/adjustable 2D array you can see my example above.

I fully understand all that, and I had your example implemented before I made the op, except for the resizing, which I have no use for. Sorry to get snippy, but you're not telling me anything I don't already know.