¿Cómo determina este fragmento de código el tamaño de la matriz sin usar sizeof ()?

134

Al revisar algunas preguntas de la entrevista en C, encontré una pregunta que decía "¿Cómo encontrar el tamaño de una matriz en C sin usar el operador sizeof?", Con la siguiente solución. Funciona, pero no puedo entender por qué.

#include <stdio.h>

int main() {
    int a[] = {100, 200, 300, 400, 500};
    int size = 0;

    size = *(&a + 1) - a;
    printf("%d\n", size);

    return 0;
}

Como se esperaba, devuelve 5.

editar: la gente señaló esta respuesta, pero la sintaxis difiere un poco, es decir, el método de indexación

size = (&arr)[1] - arr;

Por lo tanto, creo que ambas preguntas son válidas y tienen un enfoque ligeramente diferente del problema. ¡Gracias a todos por la inmensa ayuda y la explicación detallada!

janojlic
fuente
13
Bueno, no puedo encontrarlo, pero parece que estrictamente hablando lo es. El anexo J.2 establece explícitamente: el operando del operador unario * tiene un valor no válido es un comportamiento indefinido. Aquí &a + 1no apunta a ningún objeto válido, por lo que no es válido.
Eugene Sh.
55
Relacionado: ¿Es *((*(&array + 1)) - 1)seguro usarlo para obtener el último elemento de una matriz automática? . tl; dr *(&a + 1)invoca Undefined Behvaior
Spikatrix
55
Posible duplicado de Find size of array sin usar sizeof en C
Alma Do
@AlmaDo bien, la sintaxis difiere un poco, es decir, la parte de indexación, por lo que creo que esta pregunta sigue siendo válida por sí sola, pero podría estar equivocado. ¡Gracias por señalarlo!
janojlic
1
@janojlicz Son esencialmente lo mismo, porque (ptr)[x]es lo mismo que *((ptr) + x).
SS Anne

Respuestas:

135

Cuando agrega 1 a un puntero, el resultado es la ubicación del siguiente objeto en una secuencia de objetos del tipo señalado (es decir, una matriz). Si papunta a un intobjeto, p + 1apuntará al siguiente inten una secuencia. Si papunta a una matriz de 5 elementos de int(en este caso, la expresión &a), p + 1apuntará a la siguiente matriz de 5 elementos deint una secuencia.

Al restar dos punteros (siempre que ambos apunten al mismo objeto de matriz, o uno esté apuntando uno más allá del último elemento de la matriz) se obtiene el número de objetos (elementos de matriz) entre esos dos punteros.

La expresión &aproduce la dirección de ay tiene el tipo int (*)[5](puntero a la matriz de 5 elementos de int). La expresión &a + 1produce la dirección de la siguiente matriz de 5 elementos de intsiguiente a, y también tiene el tipo int (*)[5]. La expresión *(&a + 1)desreferencia el resultado de &a + 1, de modo que produce la dirección del primero que intsigue al último elemento de a, y tiene tipo int [5], que en este contexto "decae" a una expresión de tipo int *.

Del mismo modo, la expresión a"decae" a un puntero al primer elemento de la matriz y tiene tipo int *.

Una imagen puede ayudar:

int [5]  int (*)[5]     int      int *

+---+                   +---+
|   | <- &a             |   | <- a
| - |                   +---+
|   |                   |   | <- a + 1
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
+---+                   +---+
|   | <- &a + 1         |   | <- *(&a + 1)
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
+---+                   +---+

Estas son dos vistas del mismo almacenamiento: a la izquierda, lo vemos como una secuencia de matrices de 5 elementos int, mientras que a la derecha, lo vemos como una secuencia de int. También muestro las diversas expresiones y sus tipos.

Tenga en cuenta que la expresión *(&a + 1)da como resultado un comportamiento indefinido :

...
Si el resultado apunta uno más allá del último elemento del objeto de matriz, no se utilizará como el operando de un operador unario * que se evalúa.

C 2011 Borrador en línea , 6.5.6 / 9

John Bode
fuente
13
Ese texto "no se utilizará" es oficial: C 2018 6.5.6 8.
Eric Postpischil
@EricPostpischil: ¿Tiene un enlace al borrador previo a la publicación de 2018 (similar a N1570.pdf)?
John Bode
1
@ JohnBode: Esta respuesta tiene un enlace a la Máquina Wayback . Verifiqué el estándar oficial en mi copia comprada.
Eric Postpischil
77
Entonces, si uno escribiera size = (int*)(&a + 1) - a;este código, ¿sería completamente válido? : o
Gizmo
@Gizmo probablemente originalmente no escribieron eso porque de esa manera tienes que especificar el tipo de elemento; el original probablemente se escribió definido como una macro para uso genérico de tipo en diferentes tipos de elementos.
Leushenko
35

Esta línea es de suma importancia:

size = *(&a + 1) - a;

Como puede ver, primero toma la dirección de ay le agrega una. Luego, elimina la referencia de ese puntero y resta el valor original de aél.

La aritmética del puntero en C hace que esto devuelva el número de elementos en la matriz, o 5. Agregar uno y &aes un puntero a la siguiente matriz de 5 ints después a. Después de eso, este código desreferencia el puntero resultante y resta a(un tipo de matriz que se ha desintegrado a un puntero) de eso, dando el número de elementos en la matriz.

Detalles sobre cómo funciona la aritmética del puntero:

Digamos que tiene un puntero xyzque apunta a un inttipo y contiene el valor (int *)160. Cuando resta cualquier número de xyz, C especifica que la cantidad real restada xyzes ese número multiplicado por el tamaño del tipo al que apunta. Por ejemplo, si resta 5de xyz, el valor de xyzresultado sería xyz - (sizeof(*xyz) * 5)si la aritmética del puntero no se aplicara.

Como aes una matriz de 5 inttipos, el valor resultante será 5. Sin embargo, esto no funcionará con un puntero, solo con una matriz. Si intenta esto con un puntero, el resultado siempre será 1.

Aquí hay un pequeño ejemplo que muestra las direcciones y cómo esto no está definido. El lado izquierdo muestra las direcciones:

a + 0 | [a[0]] | &a points to this
a + 1 | [a[1]]
a + 2 | [a[2]]
a + 3 | [a[3]]
a + 4 | [a[4]] | end of array
a + 5 | [a[5]] | &a+1 points to this; accessing past array when dereferenced

Esto significa que el código está restando ade &a[5](o a+5), dando 5.

Tenga en cuenta que este es un comportamiento indefinido y no debe usarse bajo ninguna circunstancia. No espere que el comportamiento de este sea consistente en todas las plataformas, y no lo use en programas de producción.

SS Anne
fuente
27

Hmm, sospecho que esto es algo que no habría funcionado en los primeros días de C. Sin embargo, es inteligente.

Tomando los pasos uno a la vez:

  • &a obtiene un puntero a un objeto de tipo int [5]
  • +1 obtiene el siguiente objeto suponiendo que hay una serie de esos
  • * convierte efectivamente esa dirección en puntero de tipo a int
  • -a resta los dos punteros int, devolviendo el recuento de instancias int entre ellos.

No estoy seguro de que sea completamente legal (en esto me refiero a un abogado de idiomas legal, no funcionará en la práctica), dadas algunas de las operaciones de tipo que están sucediendo. Por ejemplo, solo está "permitido" restar dos punteros cuando apuntan a elementos en la misma matriz. *(&a+1)se sintetizó accediendo a otra matriz, aunque sea una matriz principal, por lo que en realidad no es un puntero en la misma matriz que a. Además, aunque puede sintetizar un puntero más allá del último elemento de una matriz, y puede tratar cualquier objeto como una matriz de 1 elemento, la operación de desreferenciar ( *) no está "permitida" en este puntero sintetizado, aunque no tiene comportamiento en este caso!

Sospecho que en los primeros días de C (sintaxis K&R, ¿alguien?), Una matriz se descompuso en un puntero mucho más rápido, por lo que *(&a+1)podría devolver la dirección del siguiente puntero de tipo int **. Las definiciones más rigurosas de C ++ moderno definitivamente permiten que el puntero al tipo de matriz exista y conozca el tamaño de la matriz, y probablemente los estándares de C han seguido su ejemplo. Todo el código de función C solo toma punteros como argumentos, por lo que la diferencia técnica visible es mínima. Pero solo estoy adivinando aquí.

Este tipo de pregunta de legalidad detallada generalmente se aplica a un intérprete de C, o una herramienta de tipo pelusa, en lugar del código compilado. Un intérprete podría implementar una matriz 2D como una matriz de punteros a matrices, porque hay una característica de tiempo de ejecución menos para implementar, en cuyo caso desreferenciar el +1 sería fatal, e incluso si funcionara, daría la respuesta incorrecta.

Otra posible debilidad puede ser que el compilador de C pueda alinear la matriz externa. Imagine si se tratara de una matriz de 5 caracteres ( char arr[5]), cuando el programa lo realiza &a+1invoca el comportamiento de "matriz de matriz". El compilador podría decidir que una matriz de matriz de 5 caracteres ( char arr[][5]) se genera realmente como una matriz de matriz de 8 caracteres ( char arr[][8]), de modo que la matriz externa se alinea muy bien. El código que estamos discutiendo ahora informaría que el tamaño de la matriz es 8, no 5. No estoy diciendo que un compilador particular definitivamente haga esto, pero podría.

Gema Taylor
fuente
Lo suficientemente justo. Sin embargo, por razones difíciles de explicar, ¿todos usan sizeof () / sizeof ()?
Gema Taylor
55
La mayoría de la gente lo hace. Por ejemplo, sizeof(array)/sizeof(array[0])da el número de elementos en una matriz.
SS Anne
El compilador de C puede alinear la matriz, pero no estoy convencido de que pueda cambiar el tipo de matriz después de hacerlo. La alineación se implementaría de manera más realista insertando bytes de relleno.
Kevin
1
La sustracción de punteros no se limita a solo dos punteros en la misma matriz; los punteros también pueden estar uno más allá del final de la matriz. &a+1se define. Como señala John Bollinger, *(&a+1)no lo es, ya que intenta desreferenciar un objeto que no existe.
Eric Postpischil
55
Un compilador no puede implementar un char [][5]as char arr[][8]. Una matriz es solo los objetos repetidos en ella; No hay relleno. Además, esto rompería el ejemplo (no normativo) 2 en C 2018 6.5.3.4 7, que nos dice que podemos calcular el número de elementos en una matriz con sizeof array / sizeof array[0].
Eric Postpischil