C - dynamic matrix allocation: something doesn't make sense to me

Question

I was wondering, why does this work

// read n as matrix dimension, then:

int* M;
M = (int*)malloc(n * n * sizeof(int));

// cycle through each "cell" in the matrix and read a number with

scanf("%d", &M[i * n + j]);

and this doesn't?

// read n as matrix dimension, then:

int** M;
M = malloc(n * n * sizeof(int));

// cycle through each "cell" in the matrix and read a number with

scanf ("%d", &M[i][j]);

I just don't get it. In both cases they should be double pointers, am I right?

You are wrong. (Well, if you weren't you could not have asked this.) The second is, no matter its dimensions, a pointer to an *array of pointers*. Which are not allocated yet. — Jongware, Feb 15 '18 at 18:26
See also [this](https://stackoverflow.com/a/45397733/841108) approach: matrix as an abstract data type. — Basile Starynkevitch, Feb 15 '18 at 19:47

user2736738 · Answer 1 · 2018-02-15T19:35:24.140

int ** is supposed to point to an int*. Here you have allocated some memory - to be precise sizeof(int)*rows*cols bytes and then you use M[i] etc. Here M[i] which is basically *(M+i) we will access i*sizeof(int*) offset from the one address returned by malloc but you allocated for rows*cols int's not int*-s - so you will eventually access memory that you shouldn't (typically on a system where sizeof(int*) > sizeof(int)) which will lead you to undefined behavior.

What is the solution then? Well allocate for int*-s.

int ** M = malloc(sizeof *M * rows);
if(!M){
   perror("malloc");
   exit(EXIT_FAILURE);
}
for(size_t i = 0; i < rows; i++){
  M[i] = malloc(sizeof *M[i] * cols);
  if(!M[i]){
     perror("malloc");
     exit(EXIT_FAILURE);
  }
 }

For your case rows = N and cols = N.

This will you give you a jagged array which you can access like you did. With malloc comes the responsibility of checking the return type of it and freeing the memory when you are done working with it. Do that.

On the first case you are accessing the allocated chunk of memory and you have realized the memory access using indices i and j to give yourself a flavor of accessing memory that you do in case of 2d array. So there is no point using double pointer here. It is legal what you did.

In both cases they should be double pointers

No they shouldn't be. The first one is different than the second one. They are not in anyway indicating the same thing.

Achal · Accepted Answer · 2018-02-15T19:46:38.527

Case 1 :-

int* M;
M = (int*)malloc(n * n * sizeof(int));

Here memory is allocated for M which is single pointer. Let's say you want to store 5 integers into that memory. So it looks like

    -------------------------------
   |  10  |  20  | 30  | 40  | 50  |
    -------------------------------
  M  M[0]   M[1]   M[2]  m[3]  M[4] <--- Its a 1D array, only one row of 5 int

Case 2 :-

int **M;
M = malloc(n * n * sizeof(int));


 M[0][0]  M[0][1] 
        |         |     |    |   .......    |       |    <---- If below one is not done then how will you store the numbers into these  
        -----------      -----              --------- 
             |            |         |          |
            M[0]         M[1]      M[2] ....  M[4]      <---  didn't allocated memory for these rows or 1D array
             |            |         |          |
             -----------------------------------   
                             |  
                             M                          <----  allocated memory for this

It doesn't work because M is double pointer and you allocated memory only for M, you didn't allocated memory for M[row]. thats why below statement didn't work.

 scanf ("%d", &M[i][j]);

So to make it work first Allocate the memory for M as you did

M = malloc(row*sizeof(*M)); /* row indicates no of rows */

and then allocate for each row

for(int index = 0 ;index < row;index++) {
M[index] = malloc(col * sizeof(*M[index])); /* col indicates number of columns */
}

And scan the matrix input

for(int index = 0 ;index < row;index++) {
   for(int sub_index = 0 ;sub_index < col; sub_index++)
      scanf("%d",&M[index][sub_index]);
   }

and once work is done with matrix free the dynamically allocated memory using free() for each row to avoid memory leakage.

Although `M = malloc(row*sizeof(int*));` works when `M` is a `int **`. `M = malloc(row * sizeof *M);` works when `M` is any pointer type. Easier to code, review and maintain. — chux - Reinstate Monica, Feb 15 '18 at 19:33
perfect @chux `sizeof(*M)` makes more sense to me, it works for any pointer type. Thanks for pointing that. — Achal, Feb 15 '18 at 19:36

score 0 · Answer 3 · answered Feb 15 '18 at 19:45

The other answers (suggesting one malloc for M and n mallocs for the rows) are correct, but not the most efficient way to allocate a matrix. You can, however, allocate the matrix with only one malloc call, while still allowing you to index it by row and column with M[i][j], as follows:

int (*M)[cols] = malloc(rows * sizeof *M);

This declares M as a pointer to array of int with length cols and requests malloc to allocate rows number of such arrays, meaning you get a single block of rows * cols ints (sizeof *M == sizeof(int) * cols).

When the malloc succeeds, you can use M as if it were declared as int M[rows][cols] so you can read into it with

scanf("%d", &M[i][j]);

It looks more complicated, but allocates M as one contiguous block of memory, which allows the processor to optimize access to it.

And as an added bonus you can also free it with just one call:

free(M);

This does require C99 support, or at least support for variable-length arrays, but the matrix itself is not a proper variable-length array. It is still allocated by malloc, but the declaration of M allows you to use it like one.

C - dynamic matrix allocation: something doesn't make sense to me

3 Answers3