wake-up-neo.com

Mehrdimensionale Arrays richtig zuordnen

Der Zweck dieser Frage besteht darin, einen Verweis darauf zu geben, wie multidimensionale Arrays in C dynamisch dynamisch zugewiesen werden. Dies ist ein Thema, das oft missverstanden und in einigen C-Programmierbüchern schlecht erklärt wird. Deshalb haben selbst erfahrene C-Programmierer Schwierigkeiten, es richtig zu machen.  


Mir wurde von meinem Programmierlehrer/Buch/Tutorial beigebracht, dass der richtige Weg zum dynamischen Zuweisen eines mehrdimensionalen Arrays die Verwendung von Zeiger-zu-Zeigern ist. 

Mehrere hochrangige Benutzer auf SO sagen mir jedoch jetzt, dass dies eine falsche und schlechte Praxis ist. Sie sagen, dass Zeiger-zu-Zeiger keine Arrays sind, dass ich eigentlich keine Arrays zuweise und dass mein Code unnötig langsam ist. 

So wurde mir beigebracht, mehrdimensionale Arrays zuzuordnen:

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int** arr_alloc (size_t x, size_t y)
{
  int** pp = malloc(sizeof(*pp) * x);
  assert(pp != NULL);
  for(size_t i=0; i<x; i++)
  {
    pp[i] = malloc(sizeof(**pp) * y);
    assert(pp[i] != NULL);
  }

  return pp;
}

int** arr_fill (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      pp[i][j] = (int)j + 1;
    }
  }

  return pp;
}

void arr_print (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", pp[i][j]);
    }
    printf("\n");
  }
}

void arr_free (int** pp, size_t x, size_t y)
{
  (void) y;

  for(size_t i=0; i<x; i++)
  {
    free(pp[i]);
    pp[i] = NULL;
  }
  free(pp);
  pp = NULL;
}


int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int** pp;

  pp = arr_alloc(x, y);
  pp = arr_fill(pp, x, y);
  arr_print(pp, x, y);
  arr_free(pp, x, y);

  return 0;
}

Ausgabe

1 2 3
1 2 3

Dieser Code funktioniert einwandfrei! Wie könnte es falsch sein?

45
Lundin

Um die Frage zu beantworten, sollten wir zunächst einige Konzepte klären. Was ist ein Array und wie kann es verwendet werden? Und was ist der Code in der Frage, wenn nicht ein Array?


Was ist ein Array?

Die formale Definition eines Arrays findet sich in der C-Norm ISO 9899: 2011 6.2.5/20 Types.

Ein Array-Typ beschreibt eine zusammenhängend zugewiesene nicht leere Menge von Objekten mit einem bestimmten Element-Objekttyp, der als Elementtyp bezeichnet wird.

Im Klartext ist ein Array eine Sammlung von Elementen desselben Typs, die zusammenhängend in benachbarten Speicherzellen zugeordnet sind.

Zum Beispiel würde ein Array mit 3 ganzen Zahlen int arr[3] = {1,2,3}; Im Speicher wie folgt zugewiesen:

+-------+-------+-------+
|       |       |       |
|   1   |   2   |   3   |
|       |       |       |
+-------+-------+-------+

Was ist also mit der formalen Definition eines mehrdimensionalen Arrays? Tatsächlich handelt es sich um dieselbe Definition wie oben. Es gilt rekursiv.

Wenn wir ein 2D-Array zuweisen würden, würde int arr[2][3] = { {1,2,3}, {1,2,3} }; Wie folgt im Speicher zugewiesen:

+-------+-------+-------+-------+-------+-------+
|       |       |       |       |       |       |
|   1   |   2   |   3   |   1   |   2   |   3   |
|       |       |       |       |       |       |
+-------+-------+-------+-------+-------+-------+

Was wir in diesem Beispiel haben, ist tatsächlich ein Array von Arrays. Ein Array mit 2 Elementen, von denen jedes ein Array mit 3 ganzen Zahlen ist.


Ein Array ist ein Typ wie jeder andere

Arrays in C folgen oft demselben Typsystem wie reguläre Variablen. Wie oben gezeigt, können Sie ein Array von Arrays haben, so wie Sie ein Array eines anderen Typs haben können.

Sie können bei n - dimensionalen Arrays auch die gleiche Art von Zeigerarithmetik anwenden wie bei einfachen eindimensionalen Arrays. Bei regulären eindimensionalen Arrays sollte das Anwenden von Zeigerarithmetik trivial sein:

int arr[3] = {1,2,3};
int* ptr = arr; // integer pointer to the first element.

for(size_t i=0; i<3; i++)
{
  printf("%d ", *ptr); // print contents.
  ptr++; // set pointer to point at the next element.
}

Dies wurde durch "Array Decay" ermöglicht. Wenn arr in einem Ausdruck verwendet wurde, "zerfiel" er in einen Zeiger auf das erste Element.

In ähnlicher Weise können wir dieselbe Art von Zeigerarithmetik verwenden, um ein Array von Arrays zu durchlaufen, indem wir einen Array-Zeiger verwenden:

int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array.

for(size_t i=0; i<2; i++)
{
  printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents
  ptr++; // set pointer to point at the next element
}

Wieder gab es Array-Zerfall. Die Variable arr vom Typ int [2][3] Ist in einen Zeiger auf das erste Element zerfallen. Das erste Element war ein int [3] Und ein Zeiger auf ein solches Element wird als int(*)[3] - ein Array-Zeiger deklariert.

Das Verständnis der Array-Zeiger und des Array-Zerfalls ist erforderlich, um mit mehrdimensionalen Arrays arbeiten zu können.


Es gibt weitere Fälle, in denen sich Arrays wie reguläre Variablen verhalten. Der Operator sizeof funktioniert für (Nicht-VLA-) Arrays genauso wie für reguläre Variablen. Beispiele für ein 32-Bit-System:

int x; printf("%zu", sizeof(x)); druckt 4.
int arr[3] = {1,2,3}; printf("%zu", sizeof(arr)); druckt 12 (3 * 4 = 12)
int arr[2][3] = { {1,2,3}, {1,2,3} }; printf("%zu", sizeof(arr)); druckt 24 (2 * 3 * 4 = 24)


Wie jeder andere Typ können Arrays mit Bibliotheksfunktionen und generischen APIs verwendet werden. Da Arrays die Anforderung erfüllen, zusammenhängend zugewiesen zu werden, können wir sie zum Beispiel mit memcpy sicher kopieren:

int arr_a[3] = {1,2,3};
int arr_b[3];
memcpy(arr_b, arr_a, sizeof(arr_a));

Die zusammenhängende Zuordnung ist auch der Grund, warum andere ähnliche Standardbibliotheksfunktionen wie memset, strcpy, bsearch und qsort funktionieren. Sie sind für die Arbeit mit zusammenhängend zugewiesenen Arrays konzipiert. Wenn Sie also über ein mehrdimensionales Array verfügen, können Sie es effizient durchsuchen und mit bsearch und qsort sortieren. Auf diese Weise sparen Sie sich den Aufwand, eine binäre Suche zu implementieren und sich selbst schnell zu sortieren und dadurch neu zu erfinden Das Rad für jedes Projekt.

Alle oben genannten Übereinstimmungen zwischen Arrays und anderen Typen sind eine sehr gute Sache, die wir nutzen möchten, insbesondere bei der generischen Programmierung.


Was ist die Zeiger-zu-Zeiger-Sache, wenn nicht ein Array?

Kommen wir nun zu dem Code in der Frage zurück, der eine andere Syntax mit einem Zeiger-zu-Zeiger verwendet hat. Daran ist nichts Geheimnisvolles. Es ist ein Zeiger auf den Typ, nicht mehr und nicht weniger. Es ist kein Array. Es ist kein 2D-Array. Genau genommen kann es nicht verwendet werden, um auf ein Array zu zeigen, noch kann es verwendet werden, um auf ein 2D-Array zu zeigen.

Ein Zeiger-zu-Zeiger kann jedoch verwendet werden, um auf das erste Element eines Arrays von Zeigern zu zeigen, anstatt auf das gesamte Array zu zeigen. Und so wird es in der Frage verwendet - um einen Array-Zeiger zu "emulieren". In der Frage wird es verwendet, um auf ein Array von 2 Zeigern zu zeigen. Und dann wird jeder der 2 Zeiger verwendet, um auf ein Array von 3 ganzen Zahlen zu zeigen.

Dies ist als Nachschlagetabelle bekannt. Dies ist eine Art abstrakter Datentyp (ADT), der sich vom Konzept einfacher Arrays auf niedrigerer Ebene unterscheidet. Der Hauptunterschied besteht in der Zuordnung der Nachschlagetabelle:

+------------+
|            |
| 0x12340000 |
|            |
+------------+
      |
      |
      v
+------------+     +-------+-------+-------+
|            |     |       |       |       |
| 0x22223333 |---->|   1   |   2   |   3   |
|            |     |       |       |       |
+------------+     +-------+-------+-------+
|            | 
| 0xAAAABBBB |--+
|            |  | 
+------------+  |  
                |
                |  +-------+-------+-------+
                |  |       |       |       |
                +->|   1   |   2   |   3   |
                   |       |       |       |
                   +-------+-------+-------+

Die 32-Bit-Adressen in diesem Beispiel sind zusammengesetzt. Das Feld 0x12340000 Repräsentiert den Zeiger auf den Zeiger. Es enthält eine Adresse 0x12340000 Für das erste Element in einem Array von Zeigern. Jeder Zeiger in diesem Array enthält wiederum eine Adresse, die auf das erste Element in einem Array von Ganzzahlen zeigt.

Und hier fangen die Probleme an.


Probleme mit der Nachschlagetabellenversion

Die Nachschlagetabelle ist über den gesamten Heapspeicher verteilt. Es wird nicht zusammenhängend Speicher in benachbarten Zellen zugewiesen, da jeder Aufruf von malloc() einen neuen Speicherbereich ergibt, der nicht notwendigerweise neben den anderen angeordnet ist. Dies bringt uns wiederum viele Probleme:

  • Wir können die Zeigerarithmetik nicht wie erwartet verwenden. Während wir eine Form der Zeigerarithmetik verwenden können, um die Elemente in der Nachschlagetabelle zu indizieren und darauf zuzugreifen, können wir dies nicht mit Array-Zeigern tun.

  • Wir können den sizeof-Operator nicht verwenden. Wird es für den Zeiger-zu-Zeiger verwendet, ergibt es die Größe eines Zeiger-zu-Zeiger. Bei Verwendung des ersten Elements, auf das verwiesen wird, erhalten wir die Größe eines Zeigers. Keiner von beiden hat die Größe eines Arrays.

  • Wir können keine Standard-Bibliotheksfunktionen verwenden, die einen Array-Typ (memcpy, memset, strcpy, bsearch, qsort und so weiter) ausnehmen auf). Alle diese Funktionen setzen voraus, dass Arrays als Eingabe mit zusammenhängend zugewiesenen Daten erhalten werden. Wenn Sie sie mit unserer Nachschlagetabelle als Parameter aufrufen, treten undefinierte Verhaltensfehler auf, z. B. Programmabstürze.

  • Wiederholte Aufrufe von malloc, um mehrere Segmente zuzuweisen, führen zu einer Heap-Fragmentierung , was wiederum zu einer schlechten Auslastung von RAM Speicher) führt.

  • Da der Speicher verstreut ist, kann die CPU beim Durchlaufen der Nachschlagetabelle keinen Cache-Speicher verwenden. Eine effiziente Nutzung des Datencaches erfordert einen zusammenhängenden Speicherbereich, der von oben nach unten durchlaufen wird. Dies bedeutet, dass die Nachschlagetabelle konstruktionsbedingt eine wesentlich langsamere Zugriffszeit aufweist als ein reales mehrdimensionales Array.

  • Bei jedem Aufruf von malloc() muss der Bibliothekscode, der den Heap verwaltet, berechnen, wo freier Speicherplatz vorhanden ist. Ähnlich gibt es für jeden Aufruf von free() Overhead-Code, der ausgeführt werden muss. Aus Gründen der Leistung ist es daher häufig vorzuziehen, diese Funktionen so wenig wie möglich aufzurufen.


Sind alle Nachschlagetabellen fehlerhaft?

Wie wir sehen können, gibt es viele Probleme mit zeigerbasierten Nachschlagetabellen. Aber sie sind nicht alle schlecht, es ist ein Werkzeug wie jedes andere. Es muss nur für den richtigen Zweck verwendet werden. Wenn Sie nach einem mehrdimensionalen Array suchen, das als Array verwendet werden soll, sind Nachschlagetabellen eindeutig das falsche Werkzeug. Sie können aber auch für andere Zwecke verwendet werden.

Eine Nachschlagetabelle ist die richtige Wahl, wenn Sie alle Abmessungen benötigen, um die Größe individuell zu variieren. Ein solcher Container kann nützlich sein, wenn Sie beispielsweise eine Liste von C-Zeichenfolgen erstellen. Es ist dann oft gerechtfertigt, den oben erwähnten Leistungsverlust der Ausführungsgeschwindigkeit in Kauf zu nehmen, um Speicherplatz zu sparen.

Die Nachschlagetabelle hat außerdem den Vorteil, dass Sie Teile der Tabelle zur Laufzeit neu zuordnen können, ohne ein ganzes mehrdimensionales Array neu zuordnen zu müssen. Wenn dies häufig erforderlich ist, übertrifft die Nachschlagetabelle möglicherweise sogar das mehrdimensionale Array in Bezug auf die Ausführungsgeschwindigkeit. Beispielsweise können ähnliche Nachschlagetabellen verwendet werden, wenn eine verkettete Hash-Tabelle implementiert wird.


Wie kann man ein mehrdimensionales Array dann dynamisch richtig zuordnen?

Die einfachste Form in modernem C besteht darin, einfach ein Array variabler Länge (VLA) zu verwenden. int array[x][y]; Wobei x und y Variablen sind, denen Werte in der Laufzeit und in der vorherigen Array-Deklaration zugewiesen wurden. VLAs haben jedoch einen lokalen Gültigkeitsbereich und bleiben nicht während der gesamten Programmdauer bestehen - sie haben eine automatische Speicherdauer. Während VLAs für temporäre Arrays praktisch und schnell zu verwenden sind, ist sie kein universeller Ersatz für die in Frage kommende Nachschlagetabelle.

Um ein mehrdimensionales Array wirklich dynamisch zuzuweisen, sodass es zugewiesene Speicherdauer erhält, müssen wir malloc()/calloc()/realloc(). Ich werde unten ein Beispiel geben.

In modernem C würden Sie Array-Zeiger auf eine VLA verwenden. Sie können solche Zeiger auch dann verwenden, wenn keine tatsächliche VLA im Programm vorhanden ist. Der Vorteil der Verwendung gegenüber einem einfachen type* Oder einem void* Ist die erhöhte Typensicherheit. Wenn Sie einen Zeiger auf eine VLA verwenden, können Sie die Array-Dimensionen auch als Parameter an die Funktion übergeben, die das Array verwendet, wodurch es sowohl variabel als auch typensicher wird.

Um die Vorteile eines Zeigers auf VLA nutzen zu können, können wir diesen Zeiger leider nicht als Funktionsergebnis zurückgeben. Wenn wir also einen Zeiger auf das Array an den Aufrufer zurückgeben müssen, muss er als Parameter übergeben werden (aus den in Dynamischer Speicherzugriff beschriebenen Gründen funktioniert nur innerhalb der Funktion ). Dies ist eine gute Übung in C, erschwert jedoch das Lesen des Codes. Es würde ungefähr so ​​aussehen:

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

Obwohl diese Syntax mit ein Zeiger auf einen Array-Zeiger etwas seltsam und einschüchternd aussieht, wird sie nicht komplexer, selbst wenn wir mehr Dimensionen hinzufügen:

void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z])
{
  *aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array
  assert(*aptr != NULL);
}

Vergleichen Sie nun diesen Code mit dem Code zum Hinzufügen einer weiteren Dimension zur Nachschlagetabellenversion:

/* Bad. Don't write code like this! */
int*** arr_alloc (size_t x, size_t y, size_t z)
{
  int*** ppp = malloc(sizeof(*ppp) * x);
  assert(ppp != NULL);
  for(size_t i=0; i<x; i++)
  {
    ppp[i] = malloc(sizeof(**ppp) * y);
    assert(ppp[i] != NULL);
    for(size_t j=0; j<y; j++)
    {
      ppp[i][j] = malloc(sizeof(***ppp) * z);
      assert(ppp[i][j] != NULL);
    }
  }

  return ppp;
}

Nun ist das ein ungelesenes Durcheinander von "Drei-Sterne-Programmierung". Und lassen Sie uns nicht einmal 4 Dimensionen betrachten ...


Der vollständige Code einer Version mit echten 2D-Arrays

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

void arr_fill (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      array[i][j] = (int)j + 1;
    }
  }
}

void arr_print (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", array[i][j]);
    }
    printf("\n");
  }
}

int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int (*aptr)[x][y];

  arr_alloc(x, y, &aptr);
  arr_fill(x, y, *aptr);
  arr_print(x, y, *aptr);
  free(aptr); // free the whole 2D array

  return 0;
}
75
Lundin

C hat keine mehrdimensionalen Arrays. Sie könnten jedoch Arrays von Arrays (oder anderen Aggregaten) und Arrays von Zeigern haben.

Ein möglicher Ansatz ist Grund mit einigen abstrakten Datentypen (möglicherweise unter Verwendung von flexiblen Arraymitgliedern , was ein Implementierungstrick ist, und Sie könnten andere Ansätze verwenden) wie in this Antworten .

Wir können keinen abstrakten Datentyp vorschlagen, da dies vom Text Ihrer Hausaufgaben abhängt, den wir nicht haben. Sie müssen Entwerfen Sie Ihren abstrakten Datentyp (auf einem Blatt Papier) und später implementieren.

Nachdem Sie alle erforderlichen Vorgänge (auf Papier oder auf einer Tafel) auf Ihrem ADT aufgelistet haben, ist die Implementierung dieser Vorgänge unkompliziert.

Dieser Code funktioniert einwandfrei! Wie könnte es falsch sein?

Dieser Satz ist inkonsistent (falsch mit welchen Angaben?) ...

Ich empfehle, alle Warnungen und Debug-Informationen zu kompilieren (z. B. mitgcc -Wall -Wextra -g mit GCC ), um den Code so lange zu verbessern, bis keine Warnmeldungen angezeigt werden. Verwenden Sie den Debugger gdb (um zu verstehen, was passiert Ihr Programm) und andere Tools wie valgrind .