C / 3 Dim. Array dynamisch allokieren
Hallo Liste, ich bin auf der Suche nach einem Beispiel das mir armseligen (neuen)C Coder aufzeigt, wie ich mit einem 3 dimensionalen int Array umzugehen hab, von dessen Gesamtgroesse ich zunaechst nur weis, dass es drei Dimensionen hat. Nach dem Durchsuchen von gaengiger "Herold" Literatur, dem Internet und meinen Schulungsunterlagen musste ich feststellen, dass sich ab der 3. Dimension eines Arrays und der Beschaffung von dynamischen Speicher die Informationen in Grenzen halten. Die Aussagen die ich bisher gesammelt habe reichen von "Nur wenn Du die ersten beiden Dimensionen kennst" bishin zu "stell dich nicht so bloed an". Der zugehoerige Code reicht dann auch von "VooDoo" ueber "geht scho" bis "schau mer mal". Die Vorschlaege zu Loesung schliessen sich dem an und finden sich eher in der Gegend "hier gehts" oder "malloc,calloc,realloc ist dein Freund". Ich hab das was ich bisher weis zusammengetragen und auf ein ganz einfaches Beispiel runtergebrochen. Das Beispiel findet sich auf: www.olibaer.de/c/ Leider habe ich keine Ahnung, obwohl es offentsichtlich funktioniert, ob ich mir irgendwann nen SuperGau einfange. Mir geht es im Moment auch nicht darum das moeglichst effizient zu gestalten ( Blockweise allokieren ) sondern eher darum, später einmal hemmungslos : arr[1][2][3]=10 und arr[57][0][12]=767 zuweisen zu koennen ohne voher zu wissen, dass es arr[1][2][3] oder arr[57][0][12] im Programmverlauf geben wird. Wenn Sich also schon Eine/Einer ganz tief da reingedacht hat, weis wo ich nen Beispiel finde, weis worauf ich achten muss...nur zu. ...schlag auf den Hinterkopf genuegt. Danke Oli
Hallo Oli, ich habe noch nie ein 3D Array gebraucht, also sollte mein Zeug mit Vorsicht zu geniessen sein. On Tuesday 04 March 2003 01:40, Oli Weiss wrote:
Hallo Liste,
ich bin auf der Suche nach einem Beispiel das mir armseligen (neuen)C Coder aufzeigt, wie ich mit einem 3 dimensionalen int Array umzugehen hab, von dessen Gesamtgroesse ich zunaechst nur weis, dass es drei Dimensionen hat. Nach dem Durchsuchen von gaengiger "Herold" Literatur, dem Internet und meinen Schulungsunterlagen musste ich feststellen, dass sich ab der 3. Dimension eines Arrays und der Beschaffung von dynamischen Speicher die Informationen in Grenzen halten.
Die Aussagen die ich bisher gesammelt habe reichen von "Nur wenn Du die ersten beiden Dimensionen kennst" bishin zu "stell dich nicht so bloed an". Der zugehoerige Code reicht dann auch von "VooDoo" ueber "geht scho" bis "schau mer mal". Die Vorschlaege zu Loesung schliessen sich dem an und finden sich eher in der Gegend "hier gehts" oder "malloc,calloc,realloc ist dein Freund".
Ich hab das was ich bisher weis zusammengetragen und auf ein ganz einfaches Beispiel runtergebrochen. Das Beispiel findet sich auf: www.olibaer.de/c/
Leider habe ich keine Ahnung, obwohl es offentsichtlich funktioniert, ob ich mir irgendwann nen SuperGau einfange.
Mir geht es im Moment auch nicht darum das moeglichst effizient zu gestalten ( Blockweise allokieren ) sondern eher darum, später einmal hemmungslos : arr[1][2][3]=10 und arr[57][0][12]=767 zuweisen zu koennen ohne voher zu wissen, dass es arr[1][2][3] oder arr[57][0][12] im Programmverlauf geben wird.
Du kannst das auch auf dem Heap oder dem Stack anlegen:
char* p = malloc( dim1 * dim2 * dim3);
*(p + i * dim2 * dim3 + j * dim3 + k) == p [i][j][k]
Z.B.
#include <iostream>
#include
On Tuesday 04 March 2003 10:33, Sebastian Huber wrote:
#include <iostream>
#include
using namespace std;
void f( int a, int b, int c) { int* a1 = (int*) malloc( a * b * c); int a2 [a][b][c]; for (int i = 0; i < a; ++i) { for (int j = 0; j < b; ++j) { for (int k = 0; k < c; ++k) { cout << (*(a1 + i * a * b + j * b + k) = i * 100 + j * 10 + k) << " == " << (a2 [i][j][k] = i * 100 + j * 10 + k) << "\t"; } cout << endl; } cout << endl; } }
Das ist natuerlich Unfug, da etwas wenig Speicher anlegt wird, so muesste es passen: void f( int a, int b, int c) { int* a1 = (int*) malloc( a * b * c * sizeof( int)); int a2 [a][b][c]; for (int i = 0; i < a; ++i) { for (int j = 0; j < b; ++j) { for (int k = 0; k < c; ++k) { cout << (*(a1 + i * a * b + j * b + k) = i * 100 + j * 10 + k) << " == " << (a2 [i][j][k] = i * 100 + j * 10 + k) << "\t"; } cout << endl; } cout << endl; } }
Hi, On Tue, 4 Mar 2003, Oli Weiss wrote:
www.olibaer.de/c/
In deinen Beispielen hast du immer off-by-one Fehler in der
Dimensionierung drin. Ich will man eine Stelle herausnehmen:
// Ist das so richtig hier ?
arrdrei = (int ***)realloc(arrdrei,1*sizeof(int***) );
*arrdrei = (int **)realloc(*arrdrei,1*sizeof(int**) );
arrdrei[0][0] = (int *)realloc(arrdrei[0][0],1*sizeof(int*) );
arrdrei[0][0][0] = (int)realloc((arrdrei),1*sizeof(int) );
arrdrei[0][0][0] = 6;
Also, arrdrei ist ein int***. Der realloc-Aufruf wuerde also so aussehen:
arrdrei = (int ***) realloc (arrdrei, 1*sizeof (int **));
Der Unterschied ist hier im sizeof, du nimmst (int***), ich (int**). Hier
macht es im Endeffekt noch keinen Unterschied, aber das zieht sich weiter
durch, womit du ein realloc zu viel machst.
Also mal beim Urschleim anfangen: Wenn du ein dynamisches Array von N T's
haben willst, dann so: "(T *) malloc (N * sizeof (T))". Dein arrdrei ist
ja ein Array von T's, mit T==(int**). Jetzt ist also arrdrei[0] ..
arrdrei[N-1] alloziert (du hast hier ja N==1). Nun die naechste
Dimension:
arrdrei[0] = (int **) realloc (arrdrei[0], 1 * sizeof (int *));
(Wieder im Unterschied zu dir, der sizeof(int**) hat). Nun ist auch
arrdrei[0][0] .. arrdrei[0][M-1] alloziert (bei dir wieder M==1). Die
letzte Dimension dann:
arrdrei[0][0] = (int *) realloc (arrdrei[0][0], 1 * sizeof(int));
Und hier faengt es jetzt an, einen Unterschied zu machen. Du hattest
sizeof(int*) hier, was nicht korrekt ist. Man stelle sich eine Plattform
mit 64bit pointern und 32bit ints vor, da wuerde bei die zu viel alloziert
werden. Du hast wieder bloss ein Element allozierst, also
arrdrei[0][0][0]. Aber dieses ist jetzt schon ein "int". Damit machst
du jetzt aber noch merkwuerdige Sachen, wie:
arrdrei[0][0][0] = (int)realloc((arrdrei),1*sizeof(int) );
Huh? realloc gibt einen Pointer zurueck. Wieso willst du den nach (int)
casten? Ausserdem uebergibst du arrdrei selbst als zu vergroesserndes
Array an, was aber hier voellig falsch ist.
arrdrei[0][0][0] = 6;
Ausserdem ueberschreibst du das ja gleich wieder hier. Ich kann bloss
vermuten, das du noch mehr Speicher allozieren wolltest, naemlich fuer
Element [0][0][0]. Aber wie gesagt, das ist ja schon alloziert.
arrdrei[0][0][1] = (int)realloc((arrdrei),2*sizeof(int) );
arrdrei[0][0][1] = 7;
Ja, und hier faengt es jetzt an, voellig falsch zu werden. Du hast vorher
immer nur ein Element pro Dimension alloziert, also gibt's gar keinen
Speicher fuer [0][0][1]. Das 2* sieht auch komisch aus, und der Fehler
mit dem ersten Argument passiert auch wieder.
Also, mal in Kuerze, wie man ein LxMxN int-Array alloziert (feste
Groesse!), welches null-initialisiert ist:
int ***
get_3d_array (int l, int m, int n)
{
int ***a;
int i, j;
a = (int ***) malloc (l * sizeof (int **));
for (i = 0; i < l; i++)
{
a[i] = (int **) malloc (m * sizeof (int *));
for (j = 0; j < m; j++)
a[i][j] = (int *) calloc (n, sizeof (int));
}
return a;
}
Zugreifbar per a[i][j][k]. Es muss aber eben gelten, das i arr[1][2][3]=10 und arr[57][0][12]=767 zuweisen zu koennen
ohne voher zu wissen, dass es arr[1][2][3] oder arr[57][0][12]
im Programmverlauf geben wird. Ehh? Du willst in den Speicher schreiben, ohne zu wissen, ob es ihn gibt?
Du meinst du willst ein dynamisch wachsendes Array haben, oder? Das geht
in C nicht gar so einfach, da der syntaktische Array-Zugriff (also die
x[bla][blubb] Dinger), nicht gecheckt sind, und auch keine hooks haben.
D.h. man braucht ne eigene Datenstruktur, mit einem eigenen Element-set
operator. Etwa so:
struct DynArray {
int l, m, n; /* Die aktuelle Dimension */
int ***data; /* Und der Speicher dafuer */
};
int *
get_element (struct DynArray *a, int i, int j, int k)
{
if (i < a->l && j < a->m && k < a->n)
return &(a->data[i][j][k]);
/* Wie muessen das Ding vergroessern. */
...
}
Vorsicht, das vergroessern an sich ist nicht total trivial. Benutzt
wuerde es dann so:
*get_element (x, 43, 421, 23) = 1;
Ciao,
Micha.
On Wednesday 05 March 2003 15:05, Michael Matz wrote: [...]
int *** get_3d_array (int l, int m, int n) { int ***a; int i, j; a = (int ***) malloc (l * sizeof (int **)); for (i = 0; i < l; i++) { a[i] = (int **) malloc (m * sizeof (int *)); for (j = 0; j < m; j++) a[i][j] = (int *) calloc (n, sizeof (int)); } return a; }
Zugreifbar per a[i][j][k]. Es muss aber eben gelten, das i
Ist das nicht ein bischen viel Overhead fuer eine bequemere Syntax und geringfuegig schnellere Indexberechnung? Hier habe ich ja 'L*M*N*sizeof(T)' Speicher fuer die Daten plus 'L*M*sizeof(void*)' Speicher fuer die Zeiger. Als C++ Alternative waeren da auch noch valarray mit Slices.
Hi, On Wed, 5 Mar 2003, Sebastian Huber wrote:
Ist das nicht ein bischen viel Overhead fuer eine bequemere Syntax und geringfuegig schnellere Indexberechnung? Hier habe ich ja 'L*M*N*sizeof(T)' Speicher fuer die Daten plus 'L*M*sizeof(void*)' Speicher fuer die Zeiger.
Kommt eben drauf an. Wenn man ehh alle Elemente braucht, und die Multiplikationen schneller als Speicherzugriffe sind (je nach Zugriffspattern kommen die aus dem Cache), dann kann eine flache Implementierung (also das 3D- auf ein 1D-Array gemappt) schneller sein. Wenn man aber nur einige Elemente braucht, oder das Ding resizen koennen will, dann ist die dynamische Variante eher geeignet. Ciao, Micha.
Hallo, On Wednesday 05 March 2003 21:37, Michael Matz wrote:
Hi,
On Wed, 5 Mar 2003, Sebastian Huber wrote:
Ist das nicht ein bischen viel Overhead fuer eine bequemere Syntax und geringfuegig schnellere Indexberechnung? Hier habe ich ja 'L*M*N*sizeof(T)' Speicher fuer die Daten plus 'L*M*sizeof(void*)' Speicher fuer die Zeiger.
Kommt eben drauf an. Wenn man ehh alle Elemente braucht, und die Multiplikationen schneller als Speicherzugriffe sind (je nach Zugriffspattern kommen die aus dem Cache), dann kann eine flache Implementierung (also das 3D- auf ein 1D-Array gemappt) schneller sein.
Also wenn man alle Elemente bearbeiten will, dann kommt man auch mit
Additionen aus, im Gegensatz zu Inkrementen, z.B.:
for (i=0;i Wenn man aber nur einige Elemente braucht, oder das Ding resizen koennen
will, dann ist die dynamische Variante eher geeignet. Die Indizierung ist sicherlich schwieriger, aber bei niedriger dimensionalen
"Unterraeumen" nicht wesentlich ineffizienter (Addition contra einfaches
Inkrement).
Ein Resize fuehrt halt zu massiven Kopieraktionen, aber fuer haeufige Resizes
ist ein Array eh praktikabel.
Ciao
participants (3)
-
Michael Matz
-
Oli Weiss
-
Sebastian Huber