¿Por qué los índices de matriz negativa tienen sentido?

14

Me he encontrado con una experiencia extraña en la programación en C. Considera este código:

int main(){
  int array1[6] = {0, 1, 2, 3, 4, 5};
  int array2[6] = {6, 7, 8, 9, 10, 11};

  printf("%d\n", array1[-1]);
  return 0;
}

Cuando compilo y ejecuto esto, no recibo ningún error o advertencia. Como dijo mi profesor, el índice de matriz -1accede a otra variable. Todavía estoy confundido, ¿por qué demonios un lenguaje de programación tiene esta capacidad? Quiero decir, ¿por qué permitir índices de matriz negativos?

Mohammed Fawzan
fuente
2
Si bien esta pregunta está motivada con C como lenguaje de programación concreto, creo que puede entenderse como una pregunta conceptual que es tópica aquí (aunque apenas).
Raphael
77
@Raphael No estoy de acuerdo y creo que debería pertenecer a SO, de cualquier manera este es un comportamiento indefinido del libro de texto (haciendo referencia a la memoria fuera de la matriz) y los indicadores del compilador adecuados deberían advertir sobre esto
monstruo de trinquete el
Estoy de acuerdo con @ratchetfreak. Parece ser una falla del compilador ya que el rango de índice válido es [0, 5]. Cualquier cosa que esté afuera debe ser un error de compilación / tiempo de ejecución. En general, los vectores son casos particulares de funciones cuyo primer índice de elemento depende del usuario. Dado que el contrato C es que los elementos comienzan en el índice 0, es un error acceder a elementos negativos.
Val
2
@Raphael C tiene dos peculiaridades sobre los lenguajes típicos con matrices que importan aquí. Una es que C tiene submatrices y -1hacer referencia al elemento de una submatriz es una forma perfectamente válida de referirse al elemento antes de esa matriz en la matriz más grande. La otra es que si el índice no es válido, el programa no es válido, pero en la mayoría de las implementaciones obtendrá un mal comportamiento silencioso, no un error fuera de rango.
Gilles 'SO- deja de ser malvado'
44
@Gilles Si ese es el punto de la pregunta, esto debería haber estado en Stack Overflow .
Raphael

Respuestas:

27

La operación de indexación de matriz a[i]adquiere su significado a partir de las siguientes características de C

  1. La sintaxis a[i]es equivalente a *(a + i). Por lo tanto, es válido decir 5[a]para llegar al quinto elemento de a.

  2. La aritmética de puntero dice que dado un puntero py un entero i, p + i el puntero pavanza por i * sizeof(*p)bytes

  3. El nombre de una matriz ase convierte rápidamente en un puntero al elemento 0 dea

En efecto, la indexación de matrices es un caso especial de indexación de puntero. Dado que un puntero puede apuntar a cualquier lugar dentro de una matriz, cualquier expresión arbitraria que parezca nop[-1] está mal por examen, por lo que los compiladores no (no pueden) considerar todas esas expresiones como errores.

Su ejemplo a[-1]donde arealmente es el nombre de una matriz es realmente inválido. IIRC, no está definido si hay un valor de puntero significativo como resultado de la expresión a - 1donde ase sabe que es un puntero al elemento 0 de una matriz. Entonces, un compilador inteligente podría detectar esto y marcarlo como un error. Otros compiladores pueden seguir cumpliendo mientras le permiten dispararse en el pie al darle un puntero a una ranura de pila aleatoria.

La respuesta informática es:

  • En C, el []operador se define en punteros, no en matrices. En particular, se define en términos de aritmética de puntero y desreferencia de puntero.

  • En C, un puntero es abstractamente una tupla (start, length, offset)con la condición de que 0 <= offset <= length. La aritmética del puntero es esencialmente aritmética elevada en el desplazamiento, con la advertencia de que si el resultado de la operación viola la condición del puntero, es un valor indefinido. Desreferenciar un puntero agrega una restricción adicional que offset < length.

  • C tiene una noción de undefined behaviourque permite a un compilador representar concretamente esa tupla como un número único, y no tener que detectar ninguna violación de la condición del puntero. Cualquier programa que satisfaga la semántica abstracta estará seguro con la semántica concreta (con pérdida). Cualquier cosa que viole la semántica abstracta puede ser aceptada, sin comentarios, por el compilador y puede hacer cualquier cosa que quiera hacer con ella.

Hari
fuente
Intente dar una respuesta general, no una dependiendo de las idiosincrasias de un lenguaje de programación en particular.
Raphael
66
@Raphael, la pregunta era explícitamente sobre C. Creo que abordé la pregunta específica de por qué un compilador de C puede compilar una expresión aparentemente sin sentido dentro de la definición de C.
Hari
Las preguntas sobre C, en particular, no son tópicas aquí; Tenga en cuenta mi comentario sobre la pregunta.
Raphael
55
Creo que el aspecto lingüístico comparativo de la pregunta sigue siendo útil. Creo que di una descripción con sabor a "ciencia de la computación" de por qué una implementación específica exhibió una semántica concreta específica.
Hari
15

Las matrices se presentan simplemente como fragmentos contiguos de memoria. Un acceso a una matriz tal como una [i] se convierte en un acceso a la ubicación de memoria AddressOf (a) + i. Este código a[-1]es perfectamente comprensible, simplemente se refiere a la dirección anterior al inicio de la matriz.

Esto puede parecer una locura, pero hay muchas razones por las cuales esto está permitido:

  • es costoso verificar si el índice i a a [-] está dentro de los límites de la matriz.
  • Algunas técnicas de programación en realidad explotan el hecho de que a[-1]es válido. Por ejemplo, si sé que en arealidad no es el comienzo de la matriz, sino un puntero en el medio de la matriz, a[-1]simplemente obtiene el elemento de la matriz que está a la izquierda del puntero.
Dave Clarke
fuente
66
En otras palabras, probablemente no debería usarse. Período. ¿Cómo te llamas Donald Knuth y tratas de guardar otras 17 instrucciones? Por supuesto, adelante.
Raphael
Gracias por la respuesta, pero no se me ocurrió la idea. Por cierto, lo leeré una y otra vez hasta que entienda .. :)
Mohammed Fawzan
2
@Raphael: La implementación del modelo de objetos de cola utiliza la posición -1 para almacenar la tabla vtable: piumarta.com/software/cola/objmodel2.pdf . Por lo tanto, los campos se almacenan en la parte positiva del objeto y la tabla en el negativo. No puedo recordar los detalles, pero creo que tiene que ver con la coherencia.
Dave Clarke
@ DeZéroToxin: Una matriz es realmente solo una ubicación en la memoria, con algunas ubicaciones al lado que son lógicamente parte de la matriz. Pero realmente, una matriz es solo un puntero.
Dave Clarke
1
@Raphael, a[-1]tiene mucho sentido para algunos casos de a, en este caso particular, es completamente ilegal (pero no compilado por el compilador)
vonbrand
4

Como explican las otras respuestas, este es un comportamiento indefinido en C. Considere que C se definió (y se usa principalmente) como un "ensamblador de alto nivel". Los usuarios de C lo valoran por su velocidad inquebrantable, y verificar cosas en tiempo de ejecución está (en su mayoría) fuera de discusión por el mero rendimiento. Algunas construcciones de C que parecen absurdas para las personas que provienen de otros lenguajes tienen perfecto sentido en C, como estea[-1] . Sí, no siempre tiene sentido (

vonbrand
fuente
1
Me gusta esta respuesta Da una razón real de por qué esto está bien.
darxsys
3

Se puede usar dicha función para escribir métodos de asignación de memoria que accedan a la memoria directamente. Uno de estos usos es verificar el bloque de memoria anterior utilizando un índice de matriz negativo para determinar si los dos bloques pueden fusionarse. He usado esta función cuando desarrollo un administrador de memoria no volátil.

Theron W Genaux
fuente
2

C no está fuertemente tipado. Un compilador de C estándar no verificaría los límites de la matriz. La otra cosa es que una matriz en C no es más que un bloque contiguo de memoria y la indexación comienza en 0, por lo que un índice de -1 es la ubicación de cualquier patrón de bits anteriora[0] .

Otros idiomas explotan los índices negativos de una manera agradable. En Python, a[-1]devolverá el último elemento, a[-2]devolverá el penúltimo elemento, etc.

saadtaame
fuente
2
¿Cómo se relacionan los tipos fuertes y los índices de matriz? ¿Hay idiomas con un tipo para naturales donde los índices de matriz deben ser naturales?
Raphael
@Raphael Hasta donde yo sé, una escritura fuerte significa que se detectan errores de tipografía. Una matriz es un tipo, IndexOutOfBounds es un error, por lo que en un lenguaje fuertemente tipado esto se informará, en C no. A eso me refería.
saadtaame
En los idiomas que conozco, los índices de matriz son de tipo int, por lo que a[-5], en general, int i; ... a[i] = ...;se escriben correctamente. Los errores de índice solo se detectan en tiempo de ejecución. Por supuesto, un compilador inteligente puede detectar algunas violaciones.
Raphael
@Raphael Estoy hablando del tipo de datos de la matriz en su conjunto, no de los tipos de índice. Eso explica por qué C permite a los usuarios escribir un [-5]. Sí, -5 es el tipo de índice correcto, pero está fuera de límites y eso es un error. No hay mención de compilación o verificación del tipo de tiempo de ejecución en mi respuesta.
saadtaame
1

En palabras simples:

Todas las variables (incluidas las matrices) en C se almacenan en la memoria. Digamos que tiene 14 bytes de "memoria" e inicializa lo siguiente:

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

Además, considere el tamaño de un int como 2 bytes. Luego, hipotéticamente, en los primeros 2 bytes de memoria se guardará el entero a. En los siguientes 2 bytes se guardará el entero de la primera posición de la matriz (eso significa matriz [0]).

Entonces, cuando dices matriz [-1] es como referirse al entero guardado en la memoria que está justo antes de la matriz [0], que en nuestro es, hipotéticamente, entero a. En realidad, esta no es exactamente la forma en que las variables se almacenan en la memoria.

Dchris
fuente
0
//:Example of negative index:
//:A memory pool with a heap and a stack:

unsigned char memory_pool[64] = {0};

unsigned char* stack = &( memory_pool[ 64 - 1] );
unsigned char* heap  = &( memory_pool[ 0     ] );

int stack_index =    0;
int  heap_index =    0;

//:reserve 4 bytes on stack:
stack_index += 4;

//:reserve 8 bytes on heap:
heap_index  += 8;

//:Read back all reserved memory from stack:
for( int i = 0; i < stack_index; i++ ){
    unsigned char c = stack[ 0 - i ];
    //:do something with c
};;
//:Read back all reserved memory from heap:
for( int i = 0; i < heap_index; i++ ){
    unsigned char c = heap[ 0 + i ];
    //:do something with c
};;
JMI MADISON
fuente
¡Bienvenido a CS.SE! Estamos buscando respuestas que vengan con una explicación o una descripción de la lectura. No somos un sitio de codificación, y no queremos respuestas que sean solo un bloque de código. Puede considerar si puede editar su respuesta para proporcionar ese tipo de información. ¡Gracias!
DW