example - multidimensional array javascript

Acceso unidimensional a una matriz multidimensional: C bien definido

Question

Me imagino que todos estamos de acuerdo en que se considera idiomático C el acceso a una verdadera matriz multidimensional al desreferenciar un puntero (posiblemente desplazamiento) a su primer elemento de una manera unidimensional, por ejemplo:

void clearBottomRightElement(int *array, int M, int N)
{
    array[M*N-1] = 0;  // Pretend the array is one-dimensional
}


int mtx[5][3];
...
clearBottomRightElement(&mtx[0][0], 5, 3);

Sin embargo, el abogado de idiomas en mí necesita convencerse de que esto está realmente bien definido. En particular:

1. ¿La norma garantiza que el compilador no colocará relleno entre, por ejemplo, mtx[0][2] y mtx[1][0] ?

2. Normalmente, indexar fuera del final de una matriz (que no sea un pasado) es indefinido (C99, 6.5.6 / 8). Entonces, lo siguiente claramente no está definido:

   struct {
       int row[3];           // The object in question is an int[3]
       int other[10];
   } foo;
   int *p = &foo.row[7];     // ERROR: A crude attempt to get &foo.other[4];

   Entonces, por la misma regla, uno esperaría que lo siguiente no esté definido:

   int mtx[5][3];
   int (*row)[3] = &mtx[0];  // The object in question is still an int[3]
   int *p = &(*row)[7];      // Why is this any better?

   Entonces, ¿por qué debería definirse esto?

   int mtx[5][3];
   int *p = &(&mtx[0][0])[7];

Entonces, ¿qué parte del estándar C explícitamente permite esto? (Supongamos C99 por el bien de la discusión).

EDITAR

Tenga en cuenta que no tengo dudas de que esto funciona bien en todos los compiladores. Lo que estoy preguntando es si esto está explícitamente permitido por el estándar.

Answer 1

1. Es seguro que no hay relleno entre los elementos de una matriz.

2. Hay una disposición para hacer el cálculo de direcciones en un tamaño más pequeño que el espacio de direcciones completo. Esto podría usarse, por ejemplo, en el modo enorme de 8086 para que la parte de segmento no siempre se actualice si el compilador sabía que no se podía cruzar un límite de segmento. (Hace demasiado tiempo que recuerdo si los compiladores que utilicé se beneficiaron de eso o no).

Con mi modelo interno, no estoy seguro de que sea exactamente el mismo que el estándar y es muy doloroso de verificar, la información se distribuye por todas partes.

• lo que está haciendo en clearBottomRightElement es válido.

• int *p = &foo.row[7]; es indefinido

• int i = mtx[0][5]; es indefinido

• int *p = &row[7]; no compila (gcc está de acuerdo conmigo)

• int *p = &(&mtx[0][0])[7]; está en la zona gris (la última vez que verifiqué detalles como este, terminé considerando C90 no válido y C99 válido, podría ser el caso aquí o podría haberme perdido algo).

Answer 2

El único obstáculo para el tipo de acceso que desea hacer es que los objetos de tipo int [5][3] e int [15] no puedan alias entre sí. Por lo tanto, si el compilador sabe que un puntero de tipo int * apunta a una de las matrices int [3] del primero, podría imponer restricciones de límites de matriz que impedirían acceder a cualquier elemento fuera de esa matriz int [3] .

Es posible que pueda solucionar este problema colocando todo dentro de una unión que contenga la matriz int [5][3] y la matriz int [15] , pero no tengo muy claro si la unión hackea el uso de la gente para el tipo -punning en realidad están bien definidos. Este caso podría ser un poco menos problemático ya que no estarías haciendo tic-tac de células individuales, solo la lógica de la matriz, pero aún no estoy seguro.

Un caso especial que debe tenerse en cuenta: si su tipo no tiene unsigned char (o cualquier tipo de char ), acceder a la matriz multidimensional como una matriz unidimensional estaría perfectamente bien definido. Esto se debe a que la matriz unidimensional de unsigned char que se superpone está explícitamente definida por el estándar como la "representación" del objeto, y se le permite inherentemente alias.

Answer 3

Mi comprensión del estándar C99 es que no es necesario que las matrices multidimensionales se establezcan en un orden contiguo en la memoria. Siguiendo la única información relevante que encontré en el estándar ( se garantiza que cada dimensión es contigua).

Si desea utilizar el acceso x [COLS * r + c], le sugiero que se adhiera a las matrices de una dimensión.

Matriz de subscripción

Los operadores de subíndices sucesivos designan un elemento de un objeto de matriz multidimensional. Si E es una matriz n-dimensional (n ≥ 2) con dimensiones i × j ×. . . × k, luego E (usado como otro que no sea un lvalue) se convierte en un puntero a una matriz (n - 1) dimensional con dimensiones j ×. . . × k. Si el operador unario * se aplica a este puntero explícitamente, o implícitamente como resultado de la subscripción, el resultado es la matriz apuntada a (n - 1) -dimensional, que a su vez se convierte en un puntero si se usa como un valor distinto de un lvalor . De esto se deduce que las matrices se almacenan en orden de fila mayor (el último subíndice varía más rápido).

Tipo de matriz

- Un tipo de matriz describe un conjunto de objetos no vacíos asignados contiguamente con un tipo de objeto miembro particular, llamado tipo de elemento. 36) Los tipos de matriz se caracterizan por su tipo de elemento y por la cantidad de elementos en la matriz. Se dice que un tipo de matriz se deriva de su tipo de elemento, y si su tipo de elemento es T, el tipo de matriz a veces se denomina '''' matriz de T ''''. La construcción de un tipo de matriz a partir de un tipo de elemento se denomina '''' derivación de tipo de matriz ''''.

Answer 4

Todas las matrices (incluidas las multidimensionales) están libres de relleno. Incluso si nunca se menciona explícitamente, se puede inferir del sizeof reglas.

Ahora, la suscripción de matriz es un caso especial de aritmética de puntero, y la sección 6.5.6, §8 de C99 establece claramente que el comportamiento solo se define si el operando de puntero y el puntero resultante se encuentran en la misma matriz (o un elemento pasado), lo que hace comprobaciones de límites implementaciones del lenguaje C posibles.

Esto significa que su ejemplo es, de hecho, un comportamiento indefinido. Sin embargo, como la mayoría de las implementaciones de C no verifican los límites, funcionarán como se espera: la mayoría de los compiladores tratan expresiones de punteros indefinidas como

mtx[0] + 5 

homólogos de idéntica a bien definidos como

(int *)((char *)mtx + 5 * sizeof (int))

que está bien definido porque cualquier objeto (incluida la matriz bidimensional completa) siempre se puede tratar como una matriz unidimensional de tipo char .

En una mayor meditación sobre la redacción de la sección 6.5.6, dividir el acceso fuera de límites en subexpresiones aparentemente bien definidas como

(mtx[0] + 3) + 2

razonamiento que mtx[0] + 3 es un puntero a un elemento más allá del final de mtx[0] (haciendo la primera adición bien definida) y también un puntero al primer elemento de mtx[1] (haciendo que el segundo Además, bien definido) es incorrecto:

Aunque mtx[0] + 3 y mtx[1] + 0 tienen la garantía de comparar iguales (ver sección 6.5.9, §6), son semánticamente diferentes. Por ejemplo, el primero no puede ser desreferenciado y, por lo tanto, no apunta a un elemento de mtx[1] .