Dynamically allocate memory to create 2D array

Hi,
If I am not wrong when we declare a 2D (or multiD) array like "char x[3][4]" then it is reserved 3x4=12 contiguous bytes from the memory.
But we can create a 2D array with dynamically allocation of memory.In this case I would like someone to confirm me that it is not certain that the memory locations will be contiguous.
The code for dynamically create a 2D array is:

Code:

#include <stdlib.h>          
void foo ( ) {
    int **array; 
    array = malloc(nrows * sizeof(int *)); 
    if(array == NULL) {         
        fprintf(stderr, "out of memory\n");     
        /*exit or return*/         
    }     
    for(i = 0; i < nrows; i++) {     
        array[i] = malloc(ncolumns * sizeof(int));     
        if(array[i] == NULL) {         
            fprintf(stderr, "out of memory\n");     
            /*exit or return*/             
        }         
    }
}

Originally Posted by nonlinearly

Hi,
If I am not wrong when we declare a 2D (or multiD) array like "char x[3][4]" then it is reserved 3x4=12 contiguous bytes from the memory.
But we can create a 2D array with dynamically allocation of memory.In this case I would like someone to confirm me that it is not certain that the memory locations will be contiguous.

If you are allocating row by row it is almost certain it will not be contiguous.

However... you can do that in a single malloc call...

Code:

int rows = 10;
int cols = 10;
int *array;

array = malloc(rows * cols * sizeof(int));

...in which case it will be contiguous.

Oh yes... BUT in this case my friend we can not refer to an element with 2 dimensional subscripts!!! Thus we do not have a 2D array but 1D!!!

You can wrap the matrix inside a struct declaring it as a char m[ROWS][COLUMNS], where ROWS and COLUMNS are macros. Then you can have a pointer to the struct and allocate it dynamically. Of course you won't be able to resize the matrix or create matrixes of different size as the macros can be defined only at compile time, but at least you would have a contiguos matrix in the heap and you would be able to access it using the m[i][j] notation. That's the first idea i had, hope that helps!

Originally Posted by nonlinearly

BUT in this case my friend we can not refer to an element with 2 dimensional subscripts!!! Thus we do not have a 2D array but 1D!

You can, with another malloc call and a loop:

Code:

int rows = 10;
int cols = 10;
int *data;
int **array;
int i;

/* assume malloc always succeeds */
data = malloc(rows * cols * sizeof(*data));
array = malloc(rows * sizeof(*array));
for (i = 0; i < rows; ++i)
{
    array[i] = &data[i * cols];
}

/* Now access array[i][j] and remember to free both data and array when done */

laserlight... you are right... thank you!

Originally Posted by nonlinearly

Oh yes... BUT in this case my friend we can not refer to an element with 2 dimensional subscripts!!! Thus we do not have a 2D array but 1D!!!

But we can *treat* it as a 2d array thusly...

Code:

#include <stdlib.h> 
#include <stdio.h>

int main( void )
  {

  int *array = malloc(100 * sizeof(int));

  for(int x = 0; x < 10; x++)
    for(int y = 0; y < 10; y++)
      array[(x * 10) + y] = x * 10 + y;

  for(int x = 0; x < 10; x++)
    {
      for(int y = 0; y < 10; y++)
        printf("%d  ",array[(x * 10) + y]);
      printf("\n"); }
  
  
  return 0; }

In fact we can treat that as any rectangular combination of 100 elements... 10x10, 20x5, etc.

Also I would like to change something in your code that I believe makes things more clear.
In line 9 I think that sizeof(*array) may change to sizeof(void *) because we need to allocate memory for a 1D array of pointers. We do not care what the pointers point and who are they. All pointers have the same size in memory.

Originally Posted by CommonTater

In fact we can treat that as any rectangular combination of 100 elements... 10x10, 20x5, etc.

In fact, my example just gets the compiler to do this subscript computation, and it can be generalised to higher orders too. That said, be warned that the larger the contiguous block that you are trying to allocate, the higher the chance that there might not be sufficient contiguous memory available for it.

Originally Posted by nonlinearly

In line 9 I think that sizeof(*array) may change to sizeof(void *) because we need to allocate memory for a 1D array of pointers.

No, in general, given a pointer p, if you want to allocate n elements using malloc and assign the result to p, you can implement it correctly using this pattern:

Code:

p = malloc(n * sizeof(*p));

That p is a pointer to a pointer does not change this.

Originally Posted by nonlinearly

All pointers have the same size in memory.

This is not guaranteed.

Originally Posted by laserlight

In fact, my example just gets the compiler to do this subscript computation, and it can be generalised to higher orders too. That said, be warned that the larger the contiguous block that you are trying to allocate, the higher the chance that there might not be sufficient contiguous memory available for it.

Nice trick.

Contiguous memory is an issue... however it's one with less meaning as each new generation of systems come along with more and more memory. I don't use a lot of in-memory arrays (just a fluke of the work I do) but I have created multi-megabyte arrays (my way) without any real issues at all.

I think the reason I fell into doing it the way I did was that some time back I had to convert an ordering data base over to a new system. I don't recall the exact details of why this happened but they had written this humungous text file, 5 integers per line. The actual data was 10 integers wide... so I needed to convert this data to the useable format and use it to update their new database... What I eventually decided to do was to load the whole file into memory as an Nx5 array and then process it out as an (N/2)x10 array... which is where I hit on the way I did the indexing in my example.

If you know your minor dimension(s) at compile time, you can do the whole thing with one malloc and one pointer.

Code:

int (*p)[10];
p = malloc( 20 * sizeof(*p) );

p now points to something that is a contiguous block capable of being indexed from p[0][0] to p[19][9].

Originally Posted by laserlight

That p is a pointer to a pointer does not change this.

Ok then I replace it with: if p is a pointer to a pointer then we can also do this (using void *).

I have also another issue (tell me if I have to post it in a new thread):
We create a 2D array with classic declaration:int array[3][4]
And we create an array with malloc(): marray[3][4]
In the first array=array[0]
BUT in the second marray does not equal to marray[0]
The second appears to me logical but the first not!

I find the various tricks to enable the [row][col] style of indexing to be a waste of time, I never see them in any real code I've worked on.

array[row * width + col] should not be hard to grasp or remember. It's actually just a special case of the more general:

array[row * rowStride + col * colStride]

Which enables all kinds of awesomeness, such as virtually transposing arrays in place, flipping and mirroring of arrays, all without ever moving data around -- just twiddling the origin of the array and the rowStride and colStride values.

It extends to higher dimensions as well:

array[layer * layerStride + row * rowStride + col * colStride];

Originally Posted by nonlinearly

Ok then I replace it with: if p is a pointer to a pointer then we can also do this (using void *).

I do not see why you are so inclined to use void* when it is unnecessary.

Originally Posted by nonlinearly

I have also another issue (tell me if I have to post it in a new thread):

Please start a new thread with a better description of the problem. Provide code snippets that you tried.