Freaky Art der Zuordnung von zweidimensionalen Arrays?

110

In einem Projekt hat jemand diese Zeile verschoben:

double (*e)[n+1] = malloc((n+1) * sizeof(*e));

Was angeblich ein zweidimensionales Array von (n + 1) * (n + 1) verdoppelt.

Angeblich , sage ich, weil mir bisher niemand, den ich gefragt habe, genau sagen konnte, was dies bewirkt, woher es stammt oder warum es funktionieren sollte (was angeblich der Fall ist, aber ich kaufe es noch nicht).

Vielleicht fehlt mir etwas Offensichtliches, aber ich würde es begrüßen, wenn mir jemand die obige Zeile erklären könnte. Denn ich persönlich würde mich viel besser fühlen, wenn wir etwas verwenden würden, das wir tatsächlich verstehen.

User1291
quelle
15
Auch wenn es funktioniert, feuern Sie den Drücker.
Martin James
22
@ MartinJames Warum? Wie würden Sie sonst ein 2D-Array im benachbarten Speicher zuordnen? Ein verstümmeltes 1D-Array? Das ist die Programmierung der 90er Jahre, wir haben jetzt VLAs.
Lundin
43
Für den Datensatz ist dies die einzige Möglichkeit, ein tatsächliches 2D-Array dynamisch zuzuweisen.
Quentin
15
@Kninnug Nein, das würde ein Array von Zeigern deklarieren, kein 2D-Array. Wenn Sie ein 2D-Array möchten, gibt es keinen Grund, warum Sie jemals ein Array von Zeigern zuweisen möchten. Es ist aufgrund der Heap-Fragmentierung und der schlechten Auslastung des Cache-Speichers langsam und unsicher, da Sie es nicht als Array verwenden können (mit memcpy usw.). Außerdem ist der Code aufgebläht. Sie würden mehrere free () -Aufrufe benötigen und es wäre leicht, Speicherlecks zu verursachen. So weit verbreitet ein solcher Code auch sein mag, er ist einfach schlecht.
Lundin
15
Dieses Problem wäre klarer zu erklären / zu beantworten gewesen, wenn die Stichprobe nicht die gleichen Abmessungen verwendet hätte, n+1sonderndouble (*e)[rows] = malloc(columns * sizeof *e);
chux - Monica am

Antworten:

87

Die Variable eist ein Zeiger auf ein Array von n + 1Elementen vom Typ double.

Wenn Sie den Dereferenzierungsoperator aktivieren, erhalten eSie den Basistyp e"Array von n + 1Elementen vom Typ double".

Der mallocAufruf nimmt einfach den Basistyp e(siehe oben) und erhält seine Größe, multipliziert ihn mit n + 1und übergibt diese Größe an die mallocFunktion. Zuweisen eines Arrays von n + 1Arrays von n + 1Elementen von double.

Ein Programmierer
quelle
3
@MartinJames sizeof(*e)entspricht sizeof(double [n + 1]). Multiplizieren Sie das mit n + 1und Sie bekommen genug.
Einige Programmierer Typ
24
@ MartinJames: Was ist daran falsch? Es ist nicht so augenfällig, es garantiert, dass zugewiesene Zeilen zusammenhängend sind, und Sie können es wie jedes andere 2D-Array indizieren. Ich benutze diese Redewendung häufig in meinem eigenen Code.
John Bode
3
Es mag offensichtlich erscheinen, aber dies funktioniert nur für quadratische Arrays (gleiche Abmessungen).
Jens
18
@Jens: Nur in dem Sinne, dass n+1das Ergebnis quadratisch ist , wenn Sie beide Dimensionen eingeben . Wenn Sie dies tun double (*e)[cols] = malloc(rows * sizeof(*e));, hat das Ergebnis die von Ihnen angegebene Anzahl von Zeilen und Spalten.
user2357112 unterstützt Monica
9
@ user2357112 Nun, da ich viel lieber sehen würde. Auch wenn es bedeutet , müssen Sie hinzufügen int rows = n+1und int cols = n+1. Gott rette uns vor klugem Code.
candied_orange
56

Dies ist die typische Methode, mit der Sie 2D-Arrays dynamisch zuweisen sollten.

  • eist ein Array-Zeiger auf ein Array vom Typ double [n+1].
  • sizeof(*e)gibt daher den Typ des spitzen Typs an, der die Größe eines double [n+1]Arrays hat.
  • Sie weisen n+1solchen Arrays Platz zu.
  • Sie setzen den Array-Zeiger so e, dass er auf das erste Array in diesem Array von Arrays zeigt.
  • Auf diese Weise können Sie verwenden eals für e[i][j]den Zugriff einzelner Elemente in der 2D - Array.

Persönlich denke ich, dass dieser Stil viel einfacher zu lesen ist:

double (*e)[n+1] = malloc( sizeof(double[n+1][n+1]) );
Lundin
quelle
12
Nette Antwort, außer ich stimme Ihrem vorgeschlagenen Stil nicht zu und bevorzuge den ptr = malloc(sizeof *ptr * count)Stil.
chux
Schöne Antwort, und ich mag Ihren bevorzugten Stil. Eine leichte Verbesserung könnte darin bestehen, darauf hinzuweisen, dass Sie dies auf diese Weise tun müssen, da möglicherweise ein Auffüllen zwischen den zu berücksichtigenden Zeilen vorhanden ist. (Zumindest denke ich, dass das der Grund ist, warum Sie es so machen müssen.) (Lassen Sie mich wissen, wenn ich falsch
liege
2
@davidbak Das ist das gleiche. Die Array-Syntax ist lediglich selbstdokumentierender Code: Mit dem Quellcode selbst heißt es "Platz für ein 2D-Array zuweisen".
Lundin
1
@davidbak Hinweis: Ein kleiner Nachteil des Kommentars malloc(row*col*sizeof(double)) tritt auf, wenn er row*col*sizeof()überläuft, aber sizeof()*row*colnicht. (zB row, col are int)
chux - Reinstate Monica
7
@davidbak: sizeof *e * (n+1)ist einfacher zu pflegen; Wenn Sie sich jemals dazu entschließen, den Basistyp zu ändern ( z. B. von doublebis long double), müssen Sie nur die Deklaration von ändern e. Sie müssen den sizeofAusdruck im mallocAufruf nicht ändern (was Zeit spart und Sie davor schützt, ihn an einer Stelle zu ändern, an der anderen jedoch nicht). sizeof *egibt Ihnen immer die richtige Größe.
John Bode
39

Diese Redewendung fällt natürlich aus der 1D-Array-Zuordnung heraus. Beginnen wir mit der Zuweisung eines 1D-Arrays eines beliebigen Typs T:

T *p = malloc( sizeof *p * N );

Einfach, richtig? Der Ausdruck *p hat den Typ T, sizeof *pergibt also das gleiche Ergebnis wie sizeof (T), sodass wir genügend Speicherplatz für ein NElement-Array von zuweisen T. Dies gilt für jeden TypT .

Ersetzen wir nun Tdurch einen Array-Typ wie R [10]. Dann wird unsere Zuordnung

R (*p)[10] = malloc( sizeof *p * N);

Die Semantik hier entspricht genau der 1D-Zuordnungsmethode. Alles, was sich geändert hat, ist die Art von p. Stattdessen T *ist es jetzt R (*)[10]. Der Ausdruck *phat einen Typ, Tder Typ ist R [10], also sizeof *päquivalent zu sizeof (T)dem, der äquivalent zu ist sizeof (R [10]). Wir weisen also genügend Speicherplatz für ein NBy- 10Element-Array von zu R.

Wir können das noch weiter gehen, wenn wir wollen; Angenommen, es Rist selbst ein Array-Typ int [5]. Ersetzen Sie das Rund wir bekommen

int (*p)[10][5] = malloc( sizeof *p * N);

Das gleiche Geschäft - sizeof *pist das gleiche wie sizeof (int [10][5]), und wir werden am Ende einen zusammenhängenden Speicherblock zuweisen, der groß genug ist, um ein NBy- 10by- 5Array von zu halten int.

Das ist also die Zuordnungsseite; Was ist mit der Zugangsseite?

Denken Sie daran , dass der []tiefgestellte Operation definiert in Bezug auf die Zeigerarithmetik: a[i]ist definiert als *(a + i)1 . Somit dereferenziert der Indexoperator [] implizit einen Zeiger. Wenn pes sich um einen Zeiger auf handelt T, können Sie auf den Wert zugreifen, auf den verwiesen wird, indem Sie explizit mit dem unären *Operator dereferenzieren :

T x = *p;

oder mithilfe des []Indexoperators:

T x = p[0]; // identical to *p

Wenn Sie also pauf das erste Element eines Arrays zeigen , können Sie mit einem Index auf den Zeiger auf jedes Element dieses Arrays zugreifen p:

T arr[N];
T *p = arr; // expression arr "decays" from type T [N] to T *
...
T x = p[i]; // access the i'th element of arr through pointer p

Lassen Sie uns nun unsere Ersetzungsoperation erneut ausführen und durch Tden Array-Typ ersetzen R [10]:

R arr[N][10];
R (*p)[10] = arr; // expression arr "decays" from type R [N][10] to R (*)[10]
...
R x = (*p)[i];

Ein sofort offensichtlicher Unterschied; Wir dereferenzieren explizit, pbevor wir den Indexoperator anwenden. Wir wollen nicht abonnieren p, wir wollen abonnieren, auf welche p Punkte (in diesem Fall das Array arr[0] ). Da unary *eine niedrigere Priorität als der Indexoperator hat [], müssen wir Klammern verwenden, um explizit pmit zu gruppieren *. Aber denken Sie von oben daran, dass dies *pdasselbe ist wie p[0], also können wir das durch ersetzen

R x = (p[0])[i];

oder nur

R x = p[0][i];

Wenn pwir also auf ein 2D-Array zeigen, können wir wie folgt in dieses Array indizieren p:

R x = p[i][j]; // access the i'th element of arr through pointer p;
               // each arr[i] is a 10-element array of R

Nehmen Sie dies zu dem gleichen Schluss wie oben und ersetzen Sie es Rdurch int [5]:

int arr[N][10][5];
int (*p)[10][5]; // expression arr "decays" from type int [N][5][10] to int (*)[10][5]
...
int x = p[i][j][k];

Dies funktioniert genauso , wenn pPunkte auf eine regelmäßige Anordnung, oder wenn es um Speicherpunkte zugewiesen durch malloc.

Diese Redewendung hat folgende Vorteile:

  1. Es ist einfach - nur eine Codezeile im Gegensatz zur stückweisen Zuweisungsmethode
    T **arr = malloc( sizeof *arr * N );
    if ( arr )
    {
      for ( size_t i = 0; i < N; i++ )
      {
        arr[i] = malloc( sizeof *arr[i] * M );
      }
    }
    
  2. Alle Zeilen des zugewiesenen Arrays sind * zusammenhängend *, was bei der oben beschriebenen schrittweisen Zuweisungsmethode nicht der Fall ist.
  3. Die Freigabe des Arrays ist mit einem einzigen Aufruf von genauso einfach free. Auch dies gilt nicht für die stückweise Zuweisungsmethode, bei der Sie die Zuordnung aufheben müssen, arr[i]bevor Sie die Zuordnung aufheben können arr.

Manchmal ist die stückweise Zuweisungsmethode vorzuziehen, z. B. wenn Ihr Heap stark fragmentiert ist und Sie Ihren Speicher nicht als zusammenhängenden Block zuordnen können, oder wenn Sie ein "gezacktes" Array zuweisen möchten, bei dem jede Zeile eine andere Länge haben kann. Aber im Allgemeinen ist dies der bessere Weg.


1. Denken Sie daran, dass Arrays keine Zeiger sind. Stattdessen werden Array- Ausdrücke nach Bedarf in Zeigerausdrücke konvertiert.

John Bode
quelle
4
+1 Ich mag die Art und Weise, wie Sie das Konzept präsentieren: Das Zuweisen einer Reihe von Elementen ist für jeden Typ möglich, auch wenn diese Elemente selbst Arrays sind.
logo_writer
1
Ihre Erklärung ist wirklich gut, aber beachten Sie, dass die Zuweisung von zusammenhängendem Speicher kein Vorteil ist, bis Sie ihn wirklich benötigen. Angrenzender Speicher ist teurer als nicht zusammenhängender. Bei einfachen 2D-Arrays gibt es für Sie keinen Unterschied im Speicherlayout (mit Ausnahme der Anzahl der Zeilen für die Zuweisung und Freigabe). Verwenden Sie daher lieber nicht zusammenhängenden Speicher.
Oleg Lokshyn