Wie bestimmt dieser Code die Arraygröße ohne sizeof ()?

134

Beim Durchlaufen einiger C-Interview-Fragen habe ich eine Frage gefunden, die besagt: "Wie wird die Größe eines Arrays in C ermittelt, ohne den Operator sizeof zu verwenden?", Mit der folgenden Lösung. Es funktioniert, aber ich kann nicht verstehen warum.

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

Wie erwartet wird 5 zurückgegeben.

edit: Leute haben auf diese Antwort hingewiesen , aber die Syntax unterscheidet sich ein wenig, dh die Indizierungsmethode

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

Daher glaube ich, dass beide Fragen gültig sind und eine etwas andere Herangehensweise an das Problem haben. Vielen Dank für die immense Hilfe und gründliche Erklärung!

janojlic
quelle
13
Nun, ich kann es nicht finden, aber genau genommen sieht es so aus. In Anhang J.2 heißt es ausdrücklich: Der Operand des unären * Operators hat einen ungültigen Wert und ist ein undefiniertes Verhalten. Hier &a + 1wird nicht auf ein gültiges Objekt verwiesen, daher ist es ungültig.
Eugene Sh.
5
Verwandte Themen: Ist es *((*(&array + 1)) - 1)sicher, das letzte Element eines automatischen Arrays abzurufen? . tl; dr *(&a + 1)ruft Undefined Behvaior
Spikatrix
5
Mögliches Duplikat von Find size of array ohne sizeof in C
Alma Do
@AlmaDo gut, die Syntax unterscheidet sich ein wenig, dh der Indizierungsteil, also glaube ich, dass diese Frage für sich allein noch gültig ist, aber ich könnte mich irren. Vielen Dank für den Hinweis!
Janojlic
1
@janojlicz Sie sind im Wesentlichen die gleichen, weil (ptr)[x]ist das gleiche wie *((ptr) + x).
SS Anne

Antworten:

135

Wenn Sie einem Zeiger 1 hinzufügen, ist das Ergebnis die Position des nächsten Objekts in einer Folge von Objekten vom Typ, auf die gezeigt wird (dh ein Array). Wenn pauf ein intObjekt zeigt, p + 1zeigt es intin einer Sequenz auf das nächste . Wenn pauf ein 5-Element-Array von int(in diesem Fall den Ausdruck &a) verweist , p + 1wird auf das nächste 5-Element-Array vonint in einer Sequenz verwiesen.

Das Subtrahieren von zwei Zeigern (vorausgesetzt, beide zeigen auf dasselbe Array-Objekt oder einer zeigt auf das letzte Element des Arrays) ergibt die Anzahl der Objekte (Array-Elemente) zwischen diesen beiden Zeigern.

Der Ausdruck &aliefert die Adresse von aund hat den Typ int (*)[5](Zeiger auf 5-Element-Array von int). Der Ausdruck &a + 1liefert die Adresse des nächsten 5-Element-Arrays der intfolgenden aund hat auch den Typ int (*)[5]. Der Ausdruck *(&a + 1)dereferenziert das Ergebnis von &a + 1, so dass er die Adresse des ersten intnach dem letzten Element von ergibt aund den Typ hat int [5], der in diesem Zusammenhang zu einem Ausdruck vom Typ "zerfällt" int *.

In ähnlicher Weise a"zerfällt" der Ausdruck in einen Zeiger auf das erste Element des Arrays und hat den Typ int *.

Ein Bild kann helfen:

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

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

Dies sind zwei Ansichten desselben Speichers - links sehen wir ihn als eine Folge von 5-Element-Arrays von int, während wir ihn rechts als eine Folge von anzeigen int. Ich zeige auch die verschiedenen Ausdrücke und ihre Typen.

Beachten Sie, dass der Ausdruck *(&a + 1)zu undefiniertem Verhalten führt :

...
Wenn das Ergebnis eins nach dem letzten Element des Array-Objekts zeigt, darf es nicht als Operand eines unären * Operators verwendet werden, der ausgewertet wird.

C 2011 Online Draft , 6.5.6 / 9

John Bode
quelle
13
Dieser Text „darf nicht verwendet werden“ ist offiziell: C 2018 6.5.6 8.
Eric Postpischil
@EricPostpischil: Haben Sie einen Link zum Pre-Pub-Entwurf 2018 (ähnlich wie N1570.pdf)?
John Bode
1
@ JohnBode: Diese Antwort hat einen Link zur Wayback-Maschine . Ich habe den offiziellen Standard in meinem gekauften Exemplar überprüft.
Eric Postpischil
7
Wenn man also size = (int*)(&a + 1) - a;diesen Code schreiben würde, wäre er vollständig gültig? : o
Gizmo
@ Gizmo das haben sie wahrscheinlich ursprünglich nicht geschrieben, weil man auf diese Weise den Elementtyp angeben muss; Das Original wurde wahrscheinlich als Makro für die typgenerische Verwendung auf verschiedenen Elementtypen definiert.
Leushenko
35

Diese Linie ist von größter Bedeutung:

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

Wie Sie sehen können, nimmt es zuerst die Adresse von aund fügt eine hinzu. Dann wird der Zeiger dereferenziert und der ursprüngliche Wert von subtrahiert a.

Die Zeigerarithmetik in C bewirkt, dass die Anzahl der Elemente im Array zurückgegeben wird, oder 5. Hinzufügen eines und&a ist ein Zeiger auf das nächste Array von 5 ints danach a. Danach dereferenziert dieser Code den resultierenden Zeiger und subtrahiert a(einen Array-Typ, der zu einem Zeiger zerfallen ist) von diesem, wobei die Anzahl der Elemente im Array angegeben wird.

Details zur Funktionsweise der Zeigerarithmetik:

Angenommen, Sie haben einen Zeiger xyz, der auf einen intTyp zeigt und den Wert enthält (int *)160. Wenn Sie eine Zahl von subtrahieren xyz, gibt C an, dass der tatsächliche Betrag, von dem subtrahiert xyzwird, die Zahl multipliziert mit der Größe des Typs ist, auf den er zeigt. Wenn Sie zum Beispiel, subtrahierten 5von xyzdem Wert vonxyz wäre resultierenden xyz - (sizeof(*xyz) * 5)wenn Pointer - Arithmetik nicht anwendbar.

Wie abei einem Array von 5 intTypen lautet der resultierende Wert 5. Dies funktioniert jedoch nicht mit einem Zeiger, sondern nur mit einem Array. Wenn Sie dies mit einem Zeiger versuchen, wird das Ergebnis immer sein1 .

Hier ist ein kleines Beispiel, das die Adressen zeigt und wie dies undefiniert ist. Die linke Seite zeigt die Adressen:

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

Dies bedeutet, dass der Code avon &a[5](oder a+5) subtrahiert und gibt5 .

Beachten Sie, dass dies ein undefiniertes Verhalten ist und unter keinen Umständen verwendet werden sollte. Erwarten Sie nicht, dass das Verhalten auf allen Plattformen konsistent ist, und verwenden Sie es nicht in Produktionsprogrammen.

SS Anne
quelle
27

Hmm, ich vermute, das ist etwas, das in den frühen Tagen von C nicht funktioniert hätte. Es ist jedoch klug.

Führen Sie die einzelnen Schritte aus:

  • &a erhält einen Zeiger auf ein Objekt vom Typ int [5]
  • +1 erhält das nächste derartige Objekt unter der Annahme, dass es ein Array von diesen gibt
  • * konvertiert diese Adresse effektiv in einen Typzeiger auf int
  • -a subtrahiert die beiden int-Zeiger und gibt die Anzahl der int-Instanzen zwischen ihnen zurück.

Ich bin mir nicht sicher, ob es vollständig legal ist (hier meine ich Sprachanwalt - es wird in der Praxis nicht funktionieren), angesichts einiger der laufenden Operationen. Beispielsweise dürfen Sie nur dann zwei Zeiger "subtrahieren", wenn sie auf Elemente im selben Array zeigen. *(&a+1)wurde durch Zugriff auf ein anderes Array, wenn auch ein übergeordnetes Array, synthetisiert, ist also eigentlich kein Zeiger auf dasselbe Array wie a. Während Sie einen Zeiger nach dem letzten Element eines Arrays synthetisieren dürfen und jedes Objekt als Array mit einem Element behandeln können, ist die Operation dereferencing ( *) für diesen synthetisierten Zeiger nicht "erlaubt", obwohl dies der Fall ist hat in diesem Fall kein Verhalten!

Ich vermute, dass in den frühen Tagen von C (K & R-Syntax, irgendjemand?) Ein Array viel schneller in einen Zeiger zerfiel, sodass das *(&a+1)möglicherweise nur die Adresse des nächsten Zeigers vom Typ int ** zurückgibt. Die strengeren Definitionen von modernem C ++ ermöglichen definitiv, dass der Zeiger auf den Array-Typ existiert und die Array-Größe kennt, und wahrscheinlich sind die C-Standards gefolgt. Der gesamte C-Funktionscode verwendet nur Zeiger als Argumente, sodass der technisch sichtbare Unterschied minimal ist. Aber ich rate nur hier.

Diese Art der detaillierten Legalitätsfrage gilt normalerweise für einen C-Interpreter oder ein Flusentyp-Tool anstelle des kompilierten Codes. Ein Interpreter kann ein 2D-Array als Array von Zeigern auf Arrays implementieren, da eine Laufzeitfunktion weniger implementiert werden muss. In diesem Fall wäre eine Dereferenzierung von +1 fatal, und selbst wenn dies funktioniert, würde dies die falsche Antwort liefern.

Eine weitere mögliche Schwäche kann sein, dass der C-Compiler das äußere Array ausrichtet. Stellen Sie sich vor, dies wäre ein Array mit 5 Zeichen ( char arr[5]). Wenn das Programm ausgeführt &a+1wird, ruft es das Verhalten "Array of Array" auf. Der Compiler kann entscheiden, dass ein Array mit einem Array von 5 Zeichen ( char arr[][5]) tatsächlich als Array mit einem Array mit 8 Zeichen ( char arr[][8]) generiert wird , sodass das äußere Array gut ausgerichtet ist. Der Code, den wir diskutieren, würde jetzt die Arraygröße als 8 und nicht als 5 angeben. Ich sage nicht, dass ein bestimmter Compiler dies definitiv tun würde, aber es könnte sein.

Gem Taylor
quelle
Meinetwegen. Aus schwer zu erklärenden Gründen verwendet jedoch jeder sizeof () / sizeof ()?
Gem Taylor
5
Die meisten Leute tun es. Gibt beispielsweise sizeof(array)/sizeof(array[0])die Anzahl der Elemente in einem Array an.
SS Anne
Der C-Compiler darf das Array ausrichten, aber ich bin nicht überzeugt, dass er danach den Typ des Arrays ändern darf. Die Ausrichtung würde realistischer implementiert, indem Füllbytes eingefügt werden.
Kevin
1
Das Subtrahieren von Zeigern ist nicht auf nur zwei Zeiger in dasselbe Array beschränkt - die Zeiger dürfen auch eins nach dem Ende des Arrays sein. &a+1ist definiert. Wie John Bollinger bemerkt, *(&a+1)ist dies nicht der Fall, da versucht wird, ein nicht existierendes Objekt zu dereferenzieren.
Eric Postpischil
5
Ein Compiler kann kein char [][5]as implementieren char arr[][8]. Ein Array besteht nur aus den wiederholten Objekten. Es gibt keine Polsterung. Zusätzlich würde dies das (nicht normative) Beispiel 2 in C 2018 6.5.3.4 7 brechen, das uns sagt, dass wir die Anzahl der Elemente in einem Array mit berechnen können sizeof array / sizeof array[0].
Eric Postpischil