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

185

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?

Chris Cooper
fonte
8
Eu daria mais de um se eu pudesse.
Rob Lachlan
1
Aviso : Não há uma matriz 2D neste código!
muito honesto para este site
@toohonestforthissite Indeed. Para expandir: Looping e chamada malloc()não resultam em uma matriz N-dimensional. . Isso resulta em matrizes de ponteiros [para matrizes de ponteiros [...]] para separar completamente matrizes unidimensionais . Consulte Alocação correta de matrizes multidimensionais para ver como alocar TRUE matriz N-dimensional.
Andrew Henle

Respostas:

145

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.

Carl Norum
fonte
Obrigada pelo esclarecimento. Então "void function2 (int a [] [2]);" aceita 2D declarado estaticamente e dinamicamente? E acho que ainda é uma boa prática / essencial passar no comprimento da matriz também se a primeira dimensão for deixada como []?
Chris Cooper
1
@ Chris, eu acho que não - você terá dificuldade em transformar C em um array alocado globalmente ou em pilha em um monte de indicadores.
Carl Norum
6
@JasonK. - não. Matrizes não são ponteiros. Arrays "corrupção" em ponteiros em alguns contextos, mas eles são absolutamente não o mesmo.
quer
1
Para esclarecer: Sim, Chris "ainda é uma boa prática passar o comprimento da matriz" como um parâmetro separado; caso contrário, use std :: array ou std :: vector (que é C ++ e não C antigo). Acho que concordamos que @CarlNorum conceitualmente para novos usuários e praticamente citar Anders Kaseorg no Quora: “O primeiro passo para aprender C é entender que ponteiros e matrizes são a mesma coisa. O segundo passo é entender que ponteiros e matrizes são diferentes. ”
Jason K.
2
@JasonK. "O primeiro passo para aprender C é entender que ponteiros e matrizes são a mesma coisa." - Esta citação é muito errada e enganosa! É realmente o passo mais importante para entender que eles não são os mesmos, mas que os arrays são convertidos em um ponteiro para o primeiro elemento para a maioria dos operadores! sizeof(int[100]) != sizeof(int *)(a menos que você encontre uma plataforma com 100 * sizeof(int)bytes / int, mas isso é uma coisa diferente.
muito honesto para este site
85

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  |
caf
fonte
1
olhar para o layout final me faz pensar que int a [] [] pode ser acessado como int * ... certo?
Narcisse Doudieu Siewe
2
@ user3238855: Os tipos não são compatíveis, mas se você obtiver um ponteiro para o primeiro intna matriz de matrizes (por exemplo, avaliando a[0]ou &a[0][0]), então sim, você pode compensar isso para acessar todos os seqüencialmente int).
Caf
28
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};
kanghai
fonte
5

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.

Jon L
fonte
@ Jon L. Eu não diria que malloc é implementado pelo kernel, mas pela libc em cima de primitivas do kernel (como BRK)
Manuel Selva
@ManuelSelva: Onde e como mallocé implementado não é especificado pelo padrão e deixado para a implementação, resp. meio Ambiente. Para ambientes independentes, é opcional, como todas as partes da biblioteca padrão que requerem funções de vinculação (é nisso que os requisitos realmente resultam, não literalmente no que o padrão declara). Para alguns ambientes hospedados modernos, ele realmente depende das funções do kernel, ou do material completo, ou (por exemplo, Linux), como você escreveu usando stdlib e primitivos do kernel. Para sistemas de processo único de memória não virtual, ele pode ser apenas stdlib.
muito honesto para este site
2

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'
sqr163
fonte
1

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;
}
AlphaGoku
fonte