C / C++ MultiDimensional Array-Interna

Lesezeit: 7 Minuten

Benutzer-Avatar
Arrakis

Ich habe eine Frage dazu, wie C / C ++ intern mehrdimensionale Arrays speichert, die mit der Notation deklariert wurden foo[m][n]. Ich frage nicht reine Zeiger auf Zeiger usw. Ich frage aus Geschwindigkeitsgründen …

Korrigieren Sie mich, wenn ich falsch liege, aber syntaktisch foo ist ein Array von Zeigern, die selbst auf ein Array zeigen

int foo[5][4]
*(foo + i)           // returns a memory address
*( *(foo + i) + j)    // returns an int

Ich habe von vielen Stellen gehört, dass der C/C++-Compiler konvertiert foo[m][n] zu einem eindimensionalen Array hinter den Kulissen (Berechnung des erforderlichen eindimensionalen Index mit i * width + j). Wenn dies jedoch wahr wäre, würde das Folgende gelten

*(foo + 1)          // should return element foo[0][1]

Also meine Frage: Stimmt das foo[m][n] wird (immer?) als flaches eindimensionales Array im Speicher gespeichert?? Wenn ja, warum funktioniert der obige Code wie gezeigt?

  • Falls andere die gleiche Frage haben, hier noch ein paar weitere Infos: *foo == foo[0] == &foo[0][0] *(foo+1) == foo[1] == &foo[1][0] (int *)foo + 1 == &foo[0][1]

    – Arrakis

    16. Oktober 2011 um 14:39 Uhr


  • Nein, foo ist kein Array von Zeigern; es ist ein Array von Arrays.

    – Keith Thompson

    16. Oktober 2011 um 14:51 Uhr

Benutzer-Avatar
Keith Thompson

Ein zweidimensionales Array:

int foo[5][4];

ist nichts mehr oder weniger als ein Array von Arrays:

typedef int row[4];   /* type "row" is an array of 4 ints */
row foo[5];           /* the object "foo" is an array of 5 rows */

Hier gibt es keine Zeigerobjekte, weder explizit noch implizit.

Arrays sind keine Zeiger. Zeiger sind keine Arrays.

Was oft für Verwirrung sorgt, ist, dass ein Array Ausdruck wird in den meisten Kontexten implizit in einen Zeiger auf sein erstes Element umgewandelt. (Und eine separate Regel besagt, dass das, was wie eine Array-Parameterdeklaration aussieht, in Wirklichkeit eine Zeigerdeklaration ist, aber das trifft auf dieses Beispiel nicht zu.) Ein Array Objekt ist ein Array-Objekt; Durch die Deklaration eines solchen Objekts werden keine Zeigerobjekte erstellt. Der Verweis auf ein Array-Objekt kann einen Zeiger erzeugen Wert (die Adresse des ersten Elements des Arrays), aber es ist kein Zeigerobjekt im Speicher gespeichert.

Das Array-Objekt foo wird im Speicher als 5 zusammenhängende Elemente gespeichert, wobei jedes Element selbst ein Array von 4 zusammenhängenden Elementen ist int Elemente; das ganze wird also als 20 zusammenhängend gespeichert int Objekte.

Der Indizierungsoperator ist in Form von Zeigerarithmetik definiert; x[y] ist äquivalent zu *(x + y). Typischerweise ist der linke Operand entweder ein Zeigerausdruck oder ein Array-Ausdruck; Wenn es sich um einen Array-Ausdruck handelt, wird das Array implizit in einen Zeiger konvertiert.

So foo[x][y] ist äquivalent zu *(foo[x] + y)was wiederum äquivalent ist zu *(*(foo + x) + y). (Beachten Sie, dass keine Umwandlungen erforderlich sind.) Glücklicherweise müssen Sie es nicht so schreiben, und foo[x][y] ist viel einfacher zu verstehen.

Beachten Sie, dass Sie kann Erstellen Sie eine Datenstruktur, auf die damit zugegriffen werden kann foo[x][y] Syntax, aber wo foo ist wirklich ein Zeiger auf Zeiger auf int. (In diesem Fall das Präfix von each [] operator ist bereits ein Zeigerausdruck und muss nicht konvertiert werden.) Dazu müssten Sie jedoch deklarieren foo als Zeiger-auf-Zeiger-auf-int:

int **foo;

und weisen Sie dann den gesamten erforderlichen Speicher zu und initialisieren Sie ihn. Dies ist flexibler als int foo[5][4]da Sie die Anzahl der Zeilen und die Größe (oder sogar Existenz) jeder Zeile dynamisch bestimmen können.

§ 6 des comp.lang.c FAQ erklärt das sehr gut.

BEARBEITEN:

Als Antwort auf den Kommentar von Arrakis ist es wichtig, die Unterscheidung zwischen im Auge zu behalten Typ und Darstellung.

Zum Beispiel diese beiden Arten:

struct pair { int x; int y;};
typedef int arr2[2];

sehr wahrscheinlich die gleiche Darstellung im Gedächtnis haben (zwei aufeinanderfolgende int Objekte), aber die Syntax für den Zugriff auf die Elemente ist ganz anders.

Ebenso die Typen int[5][4] und int[20] haben das gleiche Speicherlayout (20 aufeinanderfolgende int Objekte), aber die Syntax für den Zugriff auf die Elemente ist anders.

Du kann Zugang foo[2][2] wie ((int*)foo)[10] (Behandeln des 2-dimensionalen Arrays, als wäre es ein 1-dimensionales Array). Und manchmal ist es nützlich, dies zu tun, aber genau genommen ist das Verhalten undefiniert. Sie können wahrscheinlich damit durchkommen, weil die meisten C-Implementierungen keine Überprüfung der Array-Grenzen durchführen. Auf der anderen Seite können optimierende Compiler davon ausgehen dass das Verhalten Ihres Codes definiert ist, und generieren Sie willkürlichen Code, wenn dies nicht der Fall ist.

  • Danke für die Antwort. Mein anfängliches Problem war in der Tatsache, dass foo[5][4] im Speicher ist ein 1D-Array – nicht 2D. Ich war also verwirrt darüber, warum *(*(foo + 1) +2) würde einen numerischen Wert ergeben, da dies 2 Dereferenzen sind (offensichtlich ungültig in einem 1D-Array). Mein Verständnis ist jetzt, dass der Code dieses Array der Array-Notation darstellt, obwohl es nicht das ist, was darunter passiert. Casting zu (int *) foo legt somit die reale Speicherstruktur offen foo

    – Arrakis

    16. Oktober 2011 um 15:16 Uhr


  • Ich bin verwirrt über dasselbe, was @Arrakis ist. Ich verstehe jetzt den Unterschied. Die Unterscheidung ist gering, aber sehr gefährlich, wenn sie missverstanden wird. w

    – Kendrik

    17. Oktober 2011 um 3:14 Uhr

  • @hackks: Wie würden Sie einen Compiler “zwingen”, Array-Grenzen zu überprüfen?

    – Keith Thompson

    19. Oktober 2013 um 17:35 Uhr

  • @hackks: Ja, das hat ein undefiniertes Verhalten. Sehen N1570. Die Regel ist in 6.5.6p8 angegeben: “… ansonsten ist das Verhalten undefiniert”, bestätigt in Anhang J, Abschnitt 2: “Ein Array-Index ist außerhalb des Bereichs, selbst wenn ein Objekt anscheinend mit dem angegebenen Index (wie im lvalue-Ausdruck a[1][7] die Deklaration gegeben int a[4][5]) (6.5.6).

    – Keith Thompson

    19. Oktober 2013 um 18:46 Uhr

  • @hackks: Das relevante Array-Objekt ist eine einzelne Zeile des 2D-Arrays. Es gibt kein 25-Element-Array von intnur ein 5-Element-Array von int[5] Elemente.

    – Keith Thompson

    19. Oktober 2013 um 19:21 Uhr

Benutzer-Avatar
Michael Goldshteyn

Ja, C/C++ speichert ein mehrdimensionales (rechteckiges) Array als zusammenhängenden Speicherbereich. Aber Ihre Syntax ist falsch. Element ändern foo[0][1]der folgende Code wird funktionieren:

*((int *)foo+1)=5;

Die explizite Besetzung ist notwendig, weil foo+1ist das gleiche wie &foo[1] was überhaupt nicht dasselbe ist wie foo[0][1]. *(foo+1) ist ein Zeiger auf das fünfte Element im flachen Speicherbereich. Mit anderen Worten, *(foo+1) ist grundsätzlich foo[1] und **(foo+1) ist foo[1][0]. So ist der Speicher für einige Ihrer zweidimensionalen Arrays ausgelegt:

Geben Sie hier die Bildbeschreibung ein

  • Ja das kenne ich Wille funktionieren, aber WENN foo nur ein flaches 1D-Array war (von sagen wir ints), dann sollten Sie nicht zweimal dereferenzieren können – es sollte nicht einmal 2 Zeiger geben !!!!

    – Arrakis

    16. Oktober 2011 um 14:10 Uhr

  • @Arrakis, aber es ist kein flaches 1D-Array für den Compiler, sondern ein 2D-Array. Es passiert einfach so, dass das 2D-Array im Speicher genauso angeordnet ist wie ein 1D-Array aus dem Größenprodukt der beiden Dimensionen.

    – Michael Goldshteyn

    16. Oktober 2011 um 14:13 Uhr

  • Es gibt zwei Zeiger, weil Sie zwei angefordert haben, indem Sie ein mehrdimensionales Array erstellt haben. Wie es im Speicher gespeichert wird, hat keinen Einfluss darauf, wie es vom Code referenziert wird.

    – Kendrik

    16. Oktober 2011 um 14:15 Uhr

  • Nein, es gibt keinen Zeiger auf Zeiger, weder im Speicher gespeichert noch als Teil eines gültigen Ausdrucks hier.

    – Keith Thompson

    16. Oktober 2011 um 14:41 Uhr

  • Es ist keine Besetzung erforderlich. foo[1][0] ist *(*(foo + 1) + 0).

    – Keith Thompson

    16. Oktober 2011 um 15:05 Uhr

Benutzer-Avatar
Christoph

C-Arrays – auch mehrdimensionale – sind zusammenhängend, dh ein Array vom Typ int [4][5] ist strukturell äquivalent zu einem Typ-Array int [20].

Diese Typen sind jedoch gemäß der C-Sprachsemantik immer noch inkompatibel. Insbesondere der folgende Code verstößt gegen den C-Standard:

int foo[4][5] = { { 0 } };
int *p = &foo[0][0];
int x = p[12]; // undefined behaviour - can't treat foo as int [20]

Der Grund dafür ist, dass der C-Standard (wahrscheinlich absichtlich) so formuliert ist, dass Bounds-Checking-Implementierungen möglich sind: As p ist abgeleitet von foo[0]die Typ hat int [5]gültige Indizes müssen im Bereich liegen 0..5 (bzw. 0..4 wenn Sie tatsächlich auf das Element zugreifen).

Viele andere Programmiersprachen (Java, Perl, Python, JavaScript, …) verwenden gezackte Arrays, um mehrdimensionale Arrays zu implementieren. Dies ist auch in C möglich, indem ein Array von Zeigern verwendet wird:

int *bar[4] = { NULL };
bar[0] = (int [3]){ 0 };
bar[1] = (int [5]){ 1, 2, 3, 4 };
int y = bar[1][2]; // y == 3

Gezackte Arrays sind jedoch nicht zusammenhängend, und die Arrays, auf die gezeigt wird, müssen keine einheitliche Größe haben.

Aufgrund der impliziten Konvertierung von Array-Ausdrücken in Zeigerausdrücke sieht die Indizierung von gezackten und nicht gezackten Arrays identisch aus, aber die tatsächlichen Adressberechnungen werden ganz anders sein:

&foo[1]    == (int (*)[5])((char *)&foo + 1 * sizeof (int [5]))

&bar[1]    == (int **)((char *)&bar + 1 * sizeof (int *))

&foo[1][2] == (int *)((char *)&foo[1] + 2 * sizeof (int))
           == (int *)((char *)&foo + 1 * sizeof (int [5]) + 2 * sizeof (int))

&bar[1][2] == (int *)((char *)bar[1] + 2 * sizeof (int)) // no & before bar!
           == (int *)((char *)*(int **)((char *)&bar + 1 * sizeof (int *))
                      + 2 * sizeof (int))

int foo[5][4];

foo ist kein Array von Zeigern; es ist ein Array von Arrays. Das folgende Bild hilft.

Geben Sie hier die Bildbeschreibung ein

1353800cookie-checkC / C++ MultiDimensional Array-Interna

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy