How do I correctly access elements of a dynamic matrix via pointer?

Question

As many know (I believe) a multidimensional matrix is stored in memory in a linear way, that is, each line of the matrix goes in memory one after the other. To illustrate I elaborated the following image:

Thus, it is possible to manipulate a multidimensional matrix as if it were a vector using a pointer:

#include <stdio.h>

#define ROWS 4
#define COLUMNS 4

int main(void){

    int matrix[ROWS][COLUMNS]={{17, 10, 14, 78},
                               {4, 14, 15, 10},
                               {14, 45, 56, 70},
                               {47, 15, 49, 10}};

    int *ptr=matrix[0];

    for(unsigned int i=0; i<(ROWS*COLUMNS); i++){

        printf("[%d] ", ptr[i]);
    }

    printf("\n\n\n");

    ptr=NULL;

    return 0;
}

Knowing this, I tried to apply this same concept to a two-dimensional matrix that was dynamically allocated, but when accessing the elements via command for (as in the example above) I ended up getting garbage on the output, ie values that were not in the matrix. Follows the code of "program":

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

#define ROWS 4
#define COLUMNS 4

int main(void){

    int **matrix=(int**)malloc(ROWS*sizeof(int*)); //Alocando as linhas da matriz

    for(unsigned int i=0; i<ROWS; i++){

        matrix[i]=(int*)malloc(COLUMNS*sizeof(int)); //Alocando as colunas
    }

    //Preenchendo a matriz
    for(unsigned int row=0; row<ROWS; row++){

        for(unsigned int column=0; column<COLUMNS; column++){

             matrix[row][column]=42; //42? Seria isso a resposta para "tudo"?
        }
    }

    int *ptr=matrix[0];

    //Exibindo valores
    for(unsigned int i=0; i<(ROWS*COLUMNS); i++){

        printf("[%d] ", ptr[i]);
    }

    printf("\n\n\n");

    for(unsigned int column=0; column<COLUMNS; column++){

        free(matrix[column]); //Desalocando as colunas da matriz
    }

    free(matrix); //Desalocando as linhas da matriz
    ptr=NULL;

    return 0;
}

When I execute the code:

[42] [42] [42] [42] [-2074264339] [134268537] [42] [42] [42] [42] [-2074264339] [134268537] [42] [42] [42] [42]

Why is the displayed result not similar to the first code? What’s wrong?

Answer 1

There is nothing "wrong", only that in dynamic allocation, the data is stored differently (non-linear).

In your example, instead of a block of size ROWS*COLUMNS, 4 pointers of the type are allocated int, pointing to 4 integer vectors.

Here, you allocate the 4 pointers:

int **matrix = (int**)malloc(ROWS*sizeof(int*));

And here, you allocate the 4 vectors:

for(unsigned int i=0; i<ROWS; i++){
    matrix[i] = (int*)malloc(COLUMNS*sizeof(int));
}

The memory scheme is as follows (example):

  ptr
   |
   V
+-------+     +---------+---------+---------+--------+
| *ROW0 |---->| COLUMN0 | COLUMN1 | COLUMN2 |COLUMN3 |
+-------+     +---------+---------+---------+--------+ 
| *ROW1 |---->| COLUMN0 | COLUMN1 | COLUMN2 |COLUMN3 |
+-------+     +---------+---------+---------+--------+ 
| *ROW2 |---->| COLUMN0 | COLUMN1 | COLUMN2 |COLUMN3 |
+-------+     +---------+---------+---------+--------+ 
| *ROW3 |---->| COLUMN0 | COLUMN1 | COLUMN2 |COLUMN3 |
+-------+     +---------+---------+---------+--------+ 

Like ptr points to the first vector, the first 4 elements are 42, but soon after, what is printed is a memory address (2 32bit positions) followed by the next 4 elements and another address and so on.

Therefore, it is not possible to traverse the matrix in the same way (linear).

Even, there is no guarantee that the data will be allocated in the form of the block of the above example, because the malloc can allocate blocks at different positions of the heap, as required (eg if memory is fragmented).

Reference on fragmentation (in English): Dynamic Memory Allocation and Fragmentation in C and C++

Answer 2

I made a few minor modifications to your code, I don’t know exactly if you’re right or not either, but the result matched what you wanted.

What I did was, in the declaration of the ptr variable, add another asterisk and turn it into a pointer pointer, just like its matrix variable, and assign with the variable itself, not with the first line or with the first element. I also modified the print for using two variables i and j to select the desired matrix element.

This is the amended part:

int **ptr = matrix;

//Exibindo valores
for(unsigned int i=0; i<(ROWS); i++){
    for (unsigned int j = 0; j < COLUMNS; j++){
        printf("[%d] ", ptr[i][j]);
    }
}

I’m learning too, so anything, I’m happy to be corrected or complemented.