Warum sind negative Array-Indizes sinnvoll?

14

Ich habe eine seltsame Erfahrung in der C-Programmierung gemacht. Betrachten Sie diesen Code:

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

Wenn ich dies kompiliere und ausführe, erhalte ich keine Fehler oder Warnungen. Wie mein Dozent sagte, -1greift der Array-Index auf eine andere Variable zu. Ich bin immer noch verwirrt, warum um alles in der Welt hat eine Programmiersprache diese Fähigkeit? Ich meine, warum negative Array-Indizes zulassen?

Mohammed Fawzan
quelle
2
Während diese Frage mit C als konkreter Programmiersprache motiviert ist, kann sie meiner Meinung nach als konzeptionelle Frage verstanden werden, die hier (wenn auch kaum) aktuell ist.
Raphael
6
@Raphael Ich bin anderer Meinung und glaube, dass es auf SO gehören sollte, so oder so ist dies ein undefiniertes Verhalten des Lehrbuchs (Bezug auf Speicher außerhalb des Arrays) und richtige Compiler-Flags sollten davor warnen
Ratschenfreak
Ich bin mit @ratchetfreak einverstanden. Es scheint ein Compilerfehler zu sein, da der gültige Indexbereich [0, 5] ist. Alles, was sich außerhalb befindet, muss ein Kompilierungs- / Laufzeitfehler sein. Vektoren sind im Allgemeinen ein spezieller Fall von Funktionen, deren erster Elementindex dem Benutzer überlassen ist. Da C contract ist, dass Elemente bei Index 0 beginnen, ist es ein Fehler, auf negative Elemente zuzugreifen.
Val
2
@Raphael C hat zwei Besonderheiten gegenüber typischen Sprachen mit Arrays, die hier von Bedeutung sind. Eine davon ist, dass C Subarrays hat und die Bezugnahme auf ein Element -1eines Subarrays eine absolut gültige Möglichkeit ist, auf das Element vor diesem Array im größeren Array zu verweisen. Der andere Grund ist, dass das Programm ungültig ist, wenn der Index ungültig ist. In den meisten Implementierungen wird jedoch ein stummes Fehlverhalten und kein Fehler außerhalb des Bereichs angezeigt.
Gilles 'SO- hör auf böse zu sein'
4
@ Gilles Wenn das der Punkt der Frage ist, sollte dies in der Tat auf Stack Overflow gewesen sein .
Raphael

Antworten:

27

Die Array-Indizierungsoperation a[i]erhält ihre Bedeutung aus den folgenden Merkmalen von C

  1. Die Syntax a[i]entspricht *(a + i). Es gilt also zu sagen 5[a], am 5. Element von zu gelangen a.

  2. Pointer-Arithmetik , so daß ein gegebener Zeiger pund eine ganze Zahl ist i, p + i der Zeiger pdurch vorgeschoben i * sizeof(*p)Bytes

  3. Der Name eines Arrays geht asehr schnell in einen Zeiger auf das 0-te Element von übera

Tatsächlich ist die Array-Indizierung ein Sonderfall der Zeigerindizierung. Da ein Zeiger kann innerhalb eines Arrays, jeden beliebigen Ausdruck an einem beliebigen Ort hinweist , dass sieht aus wie p[-1]ist nicht durch Prüfung falsch, und so Compiler nicht (nicht) alle solche Ausdrücke als Fehler betrachten.

Ihr Beispiel, a[-1]bei dem aes sich tatsächlich um den Namen eines Arrays handelt, ist tatsächlich ungültig. IIRC wird nicht definiert , wenn es gibt ein sinnvolles Zeigerwert als das Ergebnis des Ausdrucks , a - 1wo awissen , ist ein Zeiger auf das 0 - te Element eines Arrays zu sein. Ein cleverer Compiler könnte dies also erkennen und als Fehler markieren. Andere Compiler können weiterhin kompatibel sein, während Sie sich selbst in den Fuß schießen können, indem Sie einen Zeiger auf einen zufälligen Stapelplatz geben.

Die Informatik-Antwort lautet:

  • In C wird der []Operator anhand von Zeigern definiert, nicht anhand von Arrays. Insbesondere wird es in Bezug auf Zeigerarithmetik und Zeiger-Dereferenzierung definiert.

  • In C ist ein Zeiger abstrakt ein Tupel (start, length, offset)mit der Bedingung, dass 0 <= offset <= length. Die Zeigerarithmetik ist im Wesentlichen eine aufgehobene Arithmetik für den Versatz, mit der Warnung, dass ein undefinierter Wert vorliegt, wenn das Ergebnis der Operation die Zeigerbedingung verletzt. Das Aufheben der Referenzierung eines Zeigers fügt eine zusätzliche Einschränkung hinzu, die offset < length.

  • C hat eine Vorstellung von undefined behaviourdem einen Compiler konkret darzustellen , das Tupel als eine einzelne Zahl erlaubt, und nicht jede Verletzung des Zeigers Zustand erkennen müssen. Jedes Programm, das die abstrakte Semantik erfüllt, ist mit der konkreten (verlustbehafteten) Semantik sicher. Alles, was gegen die abstrakte Semantik verstößt, kann vom Compiler kommentarlos akzeptiert werden und es kann alles tun, was es damit tun möchte.

Hari
quelle
Bitte versuchen Sie, eine allgemeine Antwort zu geben, die nicht von Besonderheiten einer bestimmten Programmiersprache abhängt.
Raphael
5
@Raphael, die Frage betraf ausdrücklich C. Ich glaube, ich habe die spezielle Frage angesprochen, warum ein C-Compiler einen scheinbar bedeutungslosen Ausdruck innerhalb der Definition von C.
Hari
Insbesondere Fragen zu C sind hier offen; Beachten Sie meinen Kommentar zu der Frage.
Raphael
4
Ich halte den vergleichenden sprachwissenschaftlichen Aspekt der Frage nach wie vor für nützlich. Ich glaube, ich habe eine ziemlich "computerwissenschaftliche" Beschreibung gegeben, warum eine bestimmte Implementierung eine bestimmte konkrete Semantik aufwies.
Hari
15

Arrays werden einfach als zusammenhängende Speicherbereiche angelegt. Ein Arrayzugriff wie a [i] wird in einen Zugriff auf den Speicherort addressOf (a) + i konvertiert . Damit der Code a[-1]vollkommen verständlich ist, bezieht er sich einfach auf die Adresse eins vor dem Start des Arrays.

Das mag verrückt erscheinen, aber es gibt viele Gründe, warum dies zulässig ist:

  • Es ist teuer zu prüfen, ob der Index i zu a [-] innerhalb der Grenzen des Arrays liegt.
  • Einige Programmiertechniken nutzen tatsächlich die Tatsache aus, dass sie a[-1]gültig sind. Wenn ich beispielsweise weiß, dass dies anicht der Anfang des Arrays ist, sondern ein Zeiger in die Mitte des Arrays, wird a[-1]einfach das Element des Arrays abgerufen, das sich links vom Zeiger befindet.
Dave Clarke
quelle
6
Mit anderen Worten, es sollte wahrscheinlich nicht verwendet werden. Zeitraum. Was, Ihr Name ist Donald Knuth und Sie versuchen, weitere 17 Anweisungen zu speichern? Auf jeden Fall weitermachen.
Raphael
Danke für die Antwort, aber ich habe keine Ahnung. Übrigens werde ich es immer wieder lesen, bis ich verstehe .. :)
Mohammed Fawzan
2
@Raphael: Bei der Implementierung des Cola-Objektmodells wird die vtable an der Position -1 gespeichert: piumarta.com/software/cola/objmodel2.pdf . Somit werden die Felder im positiven Teil des Objekts und die Tabelle im negativen Teil gespeichert. Ich kann mich nicht an die Details erinnern, aber ich denke, das hat mit Beständigkeit zu tun.
Dave Clarke
@ DeZéroToxin: Ein Array ist eigentlich nur ein Speicherort. Einige Speicherorte daneben sind logischerweise Teil des Arrays. Tatsächlich ist ein Array jedoch nur ein Zeiger.
Dave Clarke
1
@ Raphael, a[-1]macht durchaus Sinn für einige Fälle von a, in diesem speziellen Fall ist es einfach illegal (aber nicht vom Compiler abgefangen)
vonbrand
4

Wie die anderen Antworten erklären, ist dieses Verhalten in C undefiniert . Beachten Sie, dass C als "Assembler auf hoher Ebene" definiert wurde (und meistens verwendet wird). Die Benutzer von C schätzen es für seine kompromisslose Geschwindigkeit, und das Überprüfen von Dingen zur Laufzeit kommt (meistens) aus Gründen der Leistung nicht in Frage. Einige C-Konstrukte, die für Leute, die aus anderen Sprachen stammen, unsinnig aussehen, sind in C wie folgt durchaus sinnvoll a[-1]. Ja, es macht nicht immer Sinn (

vonbrand
quelle
1
Ich mag diese Antwort. Gibt einen wahren Grund, warum dies in Ordnung ist.
Darxsys
3

Mit einer solchen Funktion können Speicherzuweisungsmethoden geschrieben werden, die direkt auf den Speicher zugreifen. Eine solche Verwendung besteht darin, den vorherigen Speicherblock unter Verwendung eines negativen Array-Index zu überprüfen, um festzustellen, ob die beiden Blöcke zusammengeführt werden können. Ich habe diese Funktion bei der Entwicklung eines nichtflüchtigen Speichermanagers verwendet.

Theron W Genaux
quelle
2

C ist nicht stark typisiert. Ein Standard-C-Compiler prüft keine Array-Grenzen. Die andere Sache ist, dass ein Array in C nichts anderes als ein zusammenhängender Speicherblock ist und die Indizierung bei 0 beginnt, so dass ein Index von -1 die Stelle ist, an der sich das vorhergehende Bitmuster befindet a[0].

Andere Sprachen nutzen negative Indizes auf nette Weise. Gibt in Python a[-1]das letzte Element, a[-2]das vorletzte Element usw. zurück.

Saadtaame
quelle
2
Wie hängen starke Typisierungs- und Array-Indizes zusammen? Gibt es Sprachen mit einem Typ für Naturals, bei denen Array-Indizes Naturals sein müssen?
Raphael
@Raphael Starkes Tippen bedeutet meines Wissens, dass Tippfehler abgefangen werden. Ein Array ist ein Typ, IndexOutOfBounds ist ein Fehler. In einer stark typisierten Sprache wird dies gemeldet, in C nicht. Das ist es was ich meinte.
Saadtaame
In den Sprachen , die ich kenne, Array - Indizes sind vom Typ int, so a[-5]und, allgemeiner, int i; ... a[i] = ...;korrekt eingegeben haben . Indexfehler werden nur zur Laufzeit erkannt. Natürlich kann ein cleverer Compiler einige Verstöße erkennen.
Raphael
@ Raphael Ich spreche über den Array-Datentyp als Ganzes, nicht über die Indextypen. Das erklärt, warum C es Benutzern erlaubt, ein [-5] zu schreiben. Ja, -5 ist der richtige Indextyp, aber er liegt außerhalb des zulässigen Bereichs und das ist ein Fehler. In meiner Antwort wird keine Überprüfung des Kompilierungs- oder Laufzeit-Typs erwähnt.
Saadtaame
1

In einfachen Worten:

Alle Variablen (einschließlich Arrays) in C werden gespeichert. Angenommen, Sie haben 14 Byte "Speicher" und initialisieren Folgendes:

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

Berücksichtigen Sie außerdem die Größe eines Int als 2 Byte. Dann wird hypothetisch in den ersten 2 Bytes des Speichers die ganze Zahl a gespeichert. In den nächsten 2 Bytes wird die ganze Zahl der ersten Position des Arrays gespeichert (das bedeutet Array [0]).

Wenn Sie dann Array [-1] sagen, verweisen Sie auf die Ganzzahl, die im Speicher direkt vor Array [0] gespeichert ist. Dies ist in unserem Fall hypothetisch die Ganzzahl a. In Wirklichkeit werden Variablen nicht auf diese Weise im Speicher abgelegt.

Dchris
quelle
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
quelle
Willkommen bei CS.SE! Wir suchen nach Antworten, die eine Erklärung oder eine Beschreibung der Lesung enthalten. Wir sind keine Codierungssite, und wir möchten keine Antworten, die nur ein Codeblock sind. Sie könnten überlegen, ob Sie Ihre Antwort bearbeiten können, um diese Art von Informationen bereitzustellen. Vielen Dank!
DW