Wie werden mehrdimensionale Arrays im Speicher formatiert?

182

In C weiß ich, dass ich ein zweidimensionales Array auf dem Heap mithilfe des folgenden Codes dynamisch zuordnen kann:

int** someNumbers = malloc(arrayRows*sizeof(int*));

for (i = 0; i < arrayRows; i++) {
    someNumbers[i] = malloc(arrayColumns*sizeof(int));
}

Dies erzeugt eindeutig ein eindimensionales Array von Zeigern auf eine Reihe separater eindimensionaler Arrays von ganzen Zahlen, und "The System" kann herausfinden, was ich meine, wenn ich frage:

someNumbers[4][2];

Aber wenn ich statisch ein 2D-Array deklariere, wie in der folgenden Zeile ...:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

... wird eine ähnliche Struktur auf dem Stapel erstellt oder hat sie eine vollständig andere Form? (dh ist es ein 1D-Array von Zeigern? Wenn nicht, was ist es und wie werden Verweise darauf herausgefunden?)

Und als ich "The System" sagte, was ist eigentlich dafür verantwortlich, das herauszufinden? Der Kernel? Oder sortiert der C-Compiler dies beim Kompilieren?

Chris Cooper
quelle
8
Ich würde mehr als +1 geben, wenn ich könnte.
Rob Lachlan
1
Warnung : Dieser Code enthält kein 2D-Array!
zu ehrlich für diese Seite
@toohonestforthissite In der Tat. Um das zu erweitern: Schleifen und Aufrufen führen malloc()nicht zu einem N-dimensionalen Array. . Es führt zu Arrays von Zeigern [zu Arrays von Zeigern [...]], um eindimensionale Arrays vollständig zu trennen . Weitere Informationen zum Zuweisen von TRUE N-dimensionalen Arrays finden Sie unter Richtiges Zuweisen mehrdimensionaler Arrays.
Andrew Henle

Antworten:

142

Ein statisches zweidimensionales Array sieht aus wie ein Array von Arrays - es ist nur zusammenhängend im Speicher angeordnet. Arrays sind nicht dasselbe wie Zeiger, aber da Sie sie häufig austauschbar verwenden können, kann es manchmal verwirrend werden. Der Compiler behält jedoch den Überblick, wodurch alles gut ausgerichtet ist. Sie müssen mit statischen 2D-Arrays, wie Sie sie erwähnen, vorsichtig sein, denn wenn Sie versuchen, eines an eine Funktion zu übergeben, die einen int **Parameter verwendet, werden schlimme Dinge passieren. Hier ist ein kurzes Beispiel:

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

Im Gedächtnis sieht es so aus:

0 1 2 3 4 5

genau das gleiche wie:

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

Wenn Sie jedoch versuchen, array1auf diese Funktion zuzugreifen:

void function1(int **a);

Sie erhalten eine Warnung (und die App kann nicht richtig auf das Array zugreifen):

warning: passing argument 1 of function1 from incompatible pointer type

Weil ein 2D-Array nicht dasselbe ist wie int **. Das automatische Zerfallen eines Arrays in einen Zeiger geht sozusagen nur "eine Ebene tief". Sie müssen die Funktion wie folgt deklarieren:

void function2(int a[][2]);

oder

void function2(int a[3][2]);

Um alles glücklich zu machen.

Das gleiche Konzept erstreckt sich auf n- dimensionale Arrays. Die Nutzung dieser Art von witzigem Geschäft in Ihrer Anwendung erschwert jedoch im Allgemeinen nur das Verständnis. Also sei da draußen vorsichtig.

Carl Norum
quelle
Danke für die Erklärung. Also "void function2 (int a [] [2]);" Akzeptiert sowohl statisch als auch dynamisch deklarierte 2Ds? Und ich denke, es ist immer noch eine gute Praxis / wichtig, die Länge des Arrays zu übergeben, wenn die erste Dimension als [] belassen wird?
Chris Cooper
1
@ Chris Ich glaube nicht - es fällt Ihnen schwer, C dazu zu bringen, ein stapel- oder global zugewiesenes Array in eine Reihe von Zeigern zu verwandeln.
Carl Norum
6
@ JasonK. - Nein. Arrays sind keine Zeiger. Arrays "zerfallen" in einigen Kontexten in Zeiger, aber sie sind absolut nicht gleich.
Carl Norum
1
Um es klar auszudrücken: Ja Chris "Es ist immer noch eine gute Praxis, die Länge des Arrays zu übergeben" als separaten Parameter, andernfalls verwenden Sie std :: array oder std :: vector (das ist C ++, nicht altes C). Ich denke, wir sind uns einig, dass @CarlNorum sowohl konzeptionell für neue Benutzer als auch praktisch Anders Kaseorg zu Quora zitiert: „Der erste Schritt zum Erlernen von C besteht darin, zu verstehen, dass Zeiger und Arrays dasselbe sind. Der zweite Schritt besteht darin, zu verstehen, dass Zeiger und Arrays unterschiedlich sind. “
Jason K.
2
@ JasonK. "Der erste Schritt zum Erlernen von C besteht darin, zu verstehen, dass Zeiger und Arrays dasselbe sind." - Dieses Zitat ist so sehr falsch und irreführend! Es ist in der Tat der wichtigste Schritt zu verstehen, dass sie nicht gleich sind, sondern dass Arrays für die meisten Operatoren in einen Zeiger auf das erste Element konvertiert werden! (es sei denn, Sie finden eine Plattform mit Bytes / , aber das ist eine andere Sache.sizeof(int[100]) != sizeof(int *)100 * sizeof(int)int
zu ehrlich für diese Seite
84

Die Antwort liegt auf der Idee , dass C nicht wirklich hat 2D - Arrays - es hat Arrays-of-Arrays. Wenn Sie dies deklarieren:

int someNumbers[4][2];

Sie möchten someNumbersein Array von 4 Elementen sein, wobei jedes Element dieses Arrays vom Typ ist int [2](was selbst ein Array von 2 ints ist).

Der andere Teil des Puzzles besteht darin, dass Arrays immer zusammenhängend im Speicher angeordnet sind. Wenn Sie fragen nach:

sometype_t array[4];

dann wird das immer so aussehen:

| sometype_t | sometype_t | sometype_t | sometype_t |

(4 sometype_t nebeneinander angeordnete Objekte ohne Zwischenräume). In Ihrem someNumbersArray von Arrays sieht es also so aus:

| int [2]    | int [2]    | int [2]    | int [2]    |

Und jedes int [2]Element ist selbst ein Array, das so aussieht:

| int        | int        |

Insgesamt erhalten Sie also Folgendes:

| int | int  | int | int  | int | int  | int | int  |
caf
quelle
1
Wenn ich mir das endgültige Layout ansehe, denke ich, dass auf int a [] [] als int * ... zugegriffen werden kann, oder?
Narcisse Doudieu Siewe
2
@ user3238855: Die Typen sind nicht kompatibel. Wenn Sie jedoch einen Zeiger auf den ersten intim Array von Arrays erhalten (z. B. durch Auswerten a[0]oder &a[0][0]), können Sie diesen versetzen, um nacheinander auf alle zuzugreifen int.
Café
28
unsigned char MultiArray[5][2]={{0,1},{2,3},{4,5},{6,7},{8,9}};

im Speicher ist gleich:

unsigned char SingleArray[10]={0,1,2,3,4,5,6,7,8,9};
Kanghai
quelle
5

Als Antwort auf Ihre Frage auch: Beides, obwohl der Compiler den größten Teil des schweren Hebens erledigt.

Bei statisch zugewiesenen Arrays ist "The System" der Compiler. Der Speicher wird wie für jede Stapelvariable reserviert.

Im Fall des malloc'd-Arrays ist "The System" der Implementierer von malloc (normalerweise der Kernel). Der Compiler weist lediglich den Basiszeiger zu.

Der Compiler wird den Typ immer so behandeln, wie er deklariert ist, außer in dem Beispiel, das Carl gegeben hat, wo er die austauschbare Verwendung herausfinden kann. Wenn Sie ein [] [] an eine Funktion übergeben, muss davon ausgegangen werden, dass es sich um eine statisch zugewiesene Wohnung handelt, wobei ** als Zeiger auf Zeiger angenommen wird.

Jon L.
quelle
@ Jon L. Ich würde nicht sagen, dass malloc vom Kernel implementiert wird, sondern von der libc über Kernel-Primitiven (wie brk)
Manuel Selva
@ManuelSelva: Wo und wie mallocimplementiert wird, ist nicht im Standard festgelegt und der Implementierung überlassen. Umgebung. Für freistehende Umgebungen ist es optional, wie alle Teile der Standardbibliothek, für die Verknüpfungsfunktionen erforderlich sind (dies führt tatsächlich zu den Anforderungen, nicht wörtlich zu den Angaben im Standard). In einigen modernen gehosteten Umgebungen basiert es in der Tat auf Kernelfunktionen, entweder auf dem gesamten Material oder (z. B. Linux), wie Sie es mit stdlib- und Kernel-Primitiven geschrieben haben. Für Einzelprozesssysteme mit nicht virtuellem Speicher kann nur stdlib verwendet werden.
zu ehrlich für diese Seite
2

Nehmen wir an , wir haben a1und a2definiert und initialisiert wie unter (c99):

int a1[2][2] = {{142,143}, {144,145}};
int **a2 = (int* []){ (int []){242,243}, (int []){244,245} };

a1ist ein homogenes 2D-Array mit einem einfachen kontinuierlichen Layout im Speicher, und der Ausdruck (int*)a1wird als Zeiger auf sein erstes Element ausgewertet:

a1 --> 142 143 144 145

a2wird aus einem heterogenen 2D-Array initialisiert und ist ein Zeiger auf einen Wert vom Typ int*, dh der Dereferenzierungsausdruck wird *a2zu einem Wert vom Typ ausgewertet. Das int*Speicherlayout muss nicht kontinuierlich sein:

a2 --> p1 p2
       ...
p1 --> 242 243
       ...
p2 --> 244 245

Trotz völlig unterschiedlicher Speicherlayouts und Zugriffssemantik sieht die C-Sprach-Grammatik für Array-Zugriffsausdrücke für homogene und heterogene 2D-Arrays genau gleich aus:

  • Ausdruck a1[1][0]holt Wert 144ausa1Array
  • Ausdruck a2[1][0]holt Wert 244aus a2Array

Der Compiler weiß, dass der Zugriffsausdruck für den a1Typ bearbeitet int[2][2], wenn der Zugriffsausdruck für den a2Typ bearbeitet int**. Der generierte Assemblycode folgt der homogenen oder heterogenen Zugriffssemantik.

Der Code stürzt normalerweise zur Laufzeit ab, wenn ein Array vom Typ int[N][M]typisiert und dann als Typ aufgerufen wird int**, zum Beispiel:

((int**)a1)[1][0]   //crash on dereference of a value of type 'int'
sqr163
quelle
1

Um auf ein bestimmtes 2D-Array zuzugreifen, betrachten Sie die Speicherzuordnung für eine Array-Deklaration wie im folgenden Code gezeigt:

    0  1
a[0]0  1
a[1]2  3

Um auf jedes Element zuzugreifen, reicht es aus, nur das Array, an dem Sie interessiert sind, als Parameter an die Funktion zu übergeben. Verwenden Sie dann den Versatz für die Spalte, um auf jedes Element einzeln zuzugreifen.

int a[2][2] ={{0,1},{2,3}};

void f1(int *ptr);

void f1(int *ptr)
{
    int a=0;
    int b=0;
    a=ptr[0];
    b=ptr[1];
    printf("%d\n",a);
    printf("%d\n",b);
}

int main()
{
   f1(a[0]);
   f1(a[1]);
    return 0;
}
AlphaGoku
quelle