Como as matrizes multidimensionais são formatadas na memória?

Em C, eu sei que posso alocar dinamicamente uma matriz bidimensional na pilha usando o seguinte código:

int** someNumbers = malloc(arrayRows*sizeof(int*));

for (i = 0; i < arrayRows; i++) {
    someNumbers[i] = malloc(arrayColumns*sizeof(int));
}

Claramente, isso realmente cria uma matriz unidimensional de ponteiros para várias matrizes unidimensionais separadas de números inteiros, e "O sistema" pode entender o que quero dizer quando solicito:

someNumbers[4][2];

Mas quando declaro estaticamente uma matriz 2D, como na seguinte linha ...:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

... uma estrutura semelhante é criada na pilha ou é de outra forma completamente? (ou seja, é um conjunto de ponteiros 1D? Se não, o que é e como as referências a ele são descobertas?)

Além disso, quando eu disse: "O sistema", o que é realmente responsável por descobrir isso? O kernel? Ou o compilador C resolve isso enquanto compila?

Uma matriz bidimensional estática se parece com uma matriz de matrizes - é apenas apresentada de forma contígua na memória. Matrizes não são a mesma coisa que ponteiros, mas como você pode frequentemente usá-las de maneira intercambiável, às vezes pode ficar confuso. O compilador mantém o controle adequadamente, o que faz com que tudo seja alinhado de maneira agradável. Você precisa ter cuidado com matrizes 2D estáticas como você mencionou, pois se você tentar passar uma para uma função usando um int **parâmetro, coisas ruins vão acontecer. Aqui está um exemplo rápido:

int array1[3][2] = {{0, 1}, {2, 3}, {4, 5}};

Na memória, fica assim:

0 1 2 3 4 5

exatamente o mesmo que:

int array2[6] = { 0, 1, 2, 3, 4, 5 };

Mas se você tentar passar array1para esta função:

void function1(int **a);

você receberá um aviso (e o aplicativo não conseguirá acessar a matriz corretamente):

warning: passing argument 1 of ‘function1’ from incompatible pointer type

Porque uma matriz 2D não é a mesma que int **. O decaimento automático de uma matriz em um ponteiro atinge apenas "um nível de profundidade", por assim dizer. Você precisa declarar a função como:

void function2(int a[][2]);

ou

void function2(int a[3][2]);

Para fazer tudo feliz.

Esse mesmo conceito se estende a matrizes n- dimensionais. Porém, tirar proveito desse tipo de negócio engraçado em seu aplicativo geralmente dificulta a compreensão. Portanto, tenha cuidado lá fora.

A resposta é baseada na ideia de que C realmente não possui matrizes 2D - ele possui matrizes de matrizes. Quando você declara isso:

int someNumbers[4][2];

Você está solicitando someNumbersuma matriz de 4 elementos, em que cada elemento dessa matriz é do tipo int [2](que é uma matriz de 2 ints).

A outra parte do quebra-cabeça é que as matrizes são sempre dispostas contiguamente na memória. Se você pedir:

sometype_t array[4];

então isso sempre será assim:

| sometype_t | sometype_t | sometype_t | sometype_t |

(4 sometype_tobjetos dispostos um ao lado do outro, sem espaços entre eles). Portanto, na sua someNumbersmatriz de matrizes, ficará assim:

| int [2]    | int [2]    | int [2]    | int [2]    |

E cada int [2]elemento é ele próprio uma matriz, que se parece com isso:

| int        | int        |

Então, no geral, você obtém o seguinte:

| int | int  | int | int  | int | int  | int | int  |

unsigned char MultiArray[5][2]={{0,1},{2,3},{4,5},{6,7},{8,9}};

na memória é igual a:

unsigned char SingleArray[10]={0,1,2,3,4,5,6,7,8,9};

Em resposta à sua também: Ambos, embora o compilador esteja fazendo a maior parte do trabalho pesado.

No caso de matrizes alocadas estaticamente, "O Sistema" será o compilador. Ele reservará a memória como faria para qualquer variável de pilha.

No caso da matriz malloc'd, "The System" será o implementador do malloc (normalmente o kernel). Tudo o que o compilador alocará é o ponteiro base.

O compilador sempre manipulará o tipo como ele é declarado, exceto no exemplo que Carl deu, onde ele pode descobrir o uso intercambiável. É por isso que se você passa um [] [] para uma função, ele deve assumir que é um apartamento alocado estaticamente, onde ** é assumido como ponteiro para ponteiro.

Suponha, temos a1e a2definido e inicializado como abaixo (C99):

int a1[2][2] = {{142,143}, {144,145}};
int **a2 = (int* []){ (int []){242,243}, (int []){244,245} };

a1é uma matriz 2D homogênea com layout contínuo simples na memória e a expressão (int*)a1é avaliada em um ponteiro para seu primeiro elemento:

a1 --> 142 143 144 145

a2é inicializado a partir de uma matriz 2D heterogênea e é um ponteiro para um valor do tipo int*, ou seja, a expressão de desreferência é *a2avaliada em um valor do tipo int*, o layout da memória não precisa ser contínuo:

a2 --> p1 p2
       ...
p1 --> 242 243
       ...
p2 --> 244 245

Apesar do layout de memória e da semântica de acesso totalmente diferentes, a gramática da linguagem C para expressões de acesso à matriz é exatamente a mesma para a matriz 2D homogênea e heterogênea:

• expressão a1[1][0]buscará valor 144fora da a1matriz
• expressão a2[1][0]buscará valor 244fora da a2matriz

O compilador sabe que a expressão de acesso para a1opera no tipo int[2][2], quando a expressão de acesso para a2opera no tipo int**. O código de montagem gerado seguirá a semântica de acesso homogênea ou heterogênea.

O código geralmente falha no tempo de execução quando a matriz do tipo int[N][M]é convertida em tipo e depois acessada como tipo int**, por exemplo:

((int**)a1)[1][0]   //crash on dereference of a value of type 'int'

Para acessar uma matriz 2D específica, considere o mapa de memória para uma declaração de matriz, conforme mostrado no código abaixo:

    0  1
a[0]0  1
a[1]2  3

Para acessar cada elemento, basta passar em qual array você está interessado como parâmetros para a função. Em seguida, use deslocamento para a coluna para acessar cada elemento individualmente.

int a[2][2] ={{0,1},{2,3}};

void f1(int *ptr);

void f1(int *ptr)
{
    int a=0;
    int b=0;
    a=ptr[0];
    b=ptr[1];
    printf("%d\n",a);
    printf("%d\n",b);
}

int main()
{
   f1(a[0]);
   f1(a[1]);
    return 0;
}