¿Cómo se formatean las matrices multidimensionales en la memoria?

185

En C, sé que puedo asignar dinámicamente una matriz bidimensional en el montón usando el siguiente código:

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

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

Claramente, esto en realidad crea una matriz unidimensional de punteros a un conjunto de matrices unidimensionales separadas de enteros, y "El Sistema" puede entender a qué me refiero cuando pido:

someNumbers[4][2];

Pero cuando declaro estáticamente una matriz 2D, como en la siguiente línea ...:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

... ¿se crea una estructura similar en la pila, o es de otra forma completamente? (es decir, ¿es una matriz de punteros 1D? Si no es así, ¿qué es y cómo se resuelven las referencias?)

Además, cuando dije: "El sistema", ¿qué es realmente responsable de resolver eso? El grano? ¿O el compilador de C lo soluciona mientras compila?

Chris Cooper
fuente
8
Daría más de +1 si pudiera.
Rob Lachlan
1
Advertencia : ¡No hay una matriz 2D en este código!
demasiado honesto para este sitio
@toohonestforthissite De hecho. Para ampliar eso: los bucles y las llamadas malloc()no dan como resultado una matriz N-dimensional. . Resulta en conjuntos de punteros [a conjuntos de punteros [...] para separar completamente conjuntos unidimensionales . Consulte Asignación correcta de matrices multidimensionales para ver cómo asignar matrices VERDADERAS de N dimensiones.
Andrew Henle

Respuestas:

145

Una matriz bidimensional estática se parece a una matriz de matrices: se presenta contiguamente en la memoria. Las matrices no son lo mismo que los punteros, pero debido a que a menudo puedes usarlos de manera intercambiable, a veces puede ser confuso. Sin embargo, el compilador realiza un seguimiento adecuado, lo que hace que todo se alinee bien. Debe tener cuidado con las matrices 2D estáticas como menciona, ya que si intenta pasar una a una función que toma un int **parámetro, sucederán cosas malas. Aquí hay un ejemplo rápido:

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

En la memoria se ve así:

0 1 2 3 4 5

exactamente lo mismo que:

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

Pero si intentas pasar array1a esta función:

void function1(int **a);

recibirá una advertencia (y la aplicación no podrá acceder a la matriz correctamente):

warning: passing argument 1 of function1 from incompatible pointer type

Porque una matriz 2D no es lo mismo que int **. La descomposición automática de una matriz en un puntero solo tiene "un nivel de profundidad", por así decirlo. Debe declarar la función como:

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

o

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

Para hacer todo feliz.

Este mismo concepto se extiende a las matrices n- dimensionales. Sin embargo, aprovechar este tipo de negocios divertidos en su aplicación generalmente solo hace que sea más difícil de entender. Así que ten cuidado allá afuera.

Carl Norum
fuente
Gracias por la explicación. Entonces "void function2 (int a [] [2]);" aceptará tanto las 2D declaradas estática como dinámicamente? Y supongo que sigue siendo una buena práctica / esencial pasar la longitud de la matriz también si la primera dimensión se deja como []?
Chris Cooper
1
@Chris No lo creo, tendrá dificultades para hacer que C se mezcle con una matriz asignada globalmente o en una pila de punteros.
Carl Norum
66
@JasonK. - No. Las matrices no son punteros. Las matrices "decaen" en punteros en algunos contextos, pero no son absolutamente lo mismo.
Carl Norum
1
Para ser claros: Sí, Chris "sigue siendo una buena práctica pasar la longitud de la matriz" como un parámetro separado; de lo contrario, use std :: array o std :: vector (que es C ++, no C antigua). Creo que estamos de acuerdo en @CarlNorum, tanto conceptualmente para los nuevos usuarios como prácticamente, para citar a Anders Kaseorg en Quora: “El primer paso para aprender C es comprender que los punteros y las matrices son lo mismo. El segundo paso es comprender que los punteros y las matrices son diferentes ".
Jason K.
2
@JasonK. "El primer paso para aprender C es comprender que los punteros y las matrices son lo mismo". - ¡Esta cita es muy incorrecta y engañosa! De hecho, es el paso más importante para comprender que no son lo mismo, ¡pero que las matrices se convierten en un puntero al primer elemento para la mayoría de los operadores! sizeof(int[100]) != sizeof(int *)(a menos que encuentre una plataforma con 100 * sizeof(int)bytes / int, pero eso es algo diferente.
demasiado honesto para este sitio el
85

La respuesta se basa en la idea de que C realmente no tiene matrices 2D, sino matrices de matrices. Cuando declaras esto:

int someNumbers[4][2];

Está solicitando someNumbersser una matriz de 4 elementos, donde cada elemento de esa matriz es de tipo int [2](que en sí mismo es una matriz de 2 ints).

La otra parte del rompecabezas es que las matrices siempre se presentan contiguamente en la memoria. Si solicita:

sometype_t array[4];

entonces eso siempre se verá así:

| sometype_t | sometype_t | sometype_t | sometype_t |

(4 sometype_tobjetos dispuestos uno al lado del otro, sin espacios intermedios). Entonces, en su someNumbersmatriz de matrices, se verá así:

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

Y cada int [2]elemento es en sí mismo una matriz, que se ve así:

| int        | int        |

Entonces, en general, obtienes esto:

| int | int  | int | int  | int | int  | int | int  |
coste y flete
fuente
1
mirar el diseño final me hace pensar que se puede acceder a int a [] [] como int * ... ¿verdad?
Narcisse Doudieu Siewe
2
@ user3238855: los tipos no son compatibles, pero si obtiene un puntero al primero inten la matriz de matrices (por ejemplo, evaluando a[0]o &a[0][0]) entonces sí, puede compensar eso para acceder secuencialmente a cada uno int).
caf
28
unsigned char MultiArray[5][2]={{0,1},{2,3},{4,5},{6,7},{8,9}};

en memoria es igual a:

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

En respuesta a su también: Ambas, aunque el compilador está haciendo la mayor parte del trabajo pesado.

En el caso de arreglos asignados estáticamente, "El Sistema" será el compilador. Reservará la memoria como lo haría para cualquier variable de pila.

En el caso de la matriz malloc'd, "The System" será el implementador de malloc (el núcleo generalmente). Todo lo que el compilador asignará es el puntero base.

El compilador siempre manejará el tipo como lo que se declara que es, excepto en el ejemplo que dio Carl donde puede descubrir el uso intercambiable. Es por eso que si pasa un [] [] a una función, debe asumir que es un plano asignado estáticamente, donde ** se supone que es un puntero a otro.

Jon L
fuente
@ Jon L. No diría que malloc es implementado por el kernel, sino por la libc encima de los primitivos del kernel (como brk)
Manuel Selva
@ManuelSelva: dónde y cómo mallocse implementa no está especificado por el estándar y se deja a la implementación, resp. ambiente. Para entornos independientes, es opcional, como todas las partes de la biblioteca estándar que requieren funciones de enlace (eso es lo que realmente dan como resultado los requisitos, no literalmente lo que establece el estándar). Para algunos entornos alojados modernos, de hecho depende de las funciones del núcleo, ya sea el material completo o (por ejemplo, Linux) como escribió utilizando stdlib y kernel-primitives. Para sistemas de proceso único de memoria no virtual, solo puede ser stdlib.
demasiado honesto para este sitio
2

Supongamos que tenemos a1y a2definimos e inicializamos como a continuación (c99):

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

a1es una matriz 2D homogénea con un diseño continuo simple en la memoria y la expresión (int*)a1se evalúa en un puntero a su primer elemento:

a1 --> 142 143 144 145

a2se inicializa a partir de una matriz 2D heterogénea y es un puntero a un valor de tipo int*, es decir, la expresión de referencia se *a2evalúa en un valor de tipo int*, el diseño de memoria no tiene que ser continuo:

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

A pesar del diseño de memoria totalmente diferente y la semántica de acceso, la gramática del lenguaje C para las expresiones de acceso a la matriz se ve exactamente igual para la matriz 2D homogénea y heterogénea:

  • la expresión a1[1][0]obtendrá valor 144fuera de la a1matriz
  • la expresión a2[1][0]obtendrá valor 244fuera de la a2matriz

El compilador sabe que la expresión de acceso para a1opera en tipo int[2][2], cuando la expresión de acceso para a2opera en tipo int**. El código de ensamblaje generado seguirá la semántica de acceso homogénea o heterogénea.

El código generalmente se bloquea en tiempo de ejecución cuando la matriz de tipo int[N][M]se convierte en tipo y luego se accede como tipo int**, por ejemplo:

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

Para acceder a una matriz 2D particular, considere el mapa de memoria para una declaración de matriz como se muestra en el siguiente código:

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

Para acceder a cada elemento, es suficiente simplemente pasar qué matriz le interesa como parámetros a la función. Luego use offset para columna para acceder a 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
fuente