C malloc-"Array" 2-D nutzen -Verständnisfrage

[SparkMonkay]

Moinsen!

Ich habe eine Frage zu malloc in verbindung zu Arrays, ich fasse es mal kurz, da ich es anhand eines minimalen Beispiels verstehen möchte.

ich habe einen Pointer , auf den ich den Rückgabewert von malloc setzte, bzw den Anfang vom reservierten Speicherberich.
So z.B.

long *arraypointer=NULL;
arraypointer=malloc(n*m*sizeof(long));

Ich habe mir auf meinem Whiteboard die Struktur des Arrays aufgezeichnet, jedoch ist mir das zu umständlich dieses Array 1-D zu behandeln und ich bin auf die glorreiche Idee gekommen dieses Array dann 2-D zu nutzen.

Nehmen wir mal an dass n*m=6 sind, dann hat mein Array wenn ich es 1-D benutze die Elemente auf den Plätzen von 0-5. 2-D hätte ich dann ein Array mit einer "Breite" von 3 und einer "Höhe" von 2.
Ich verstehe es dann so, bzw. von C-HOW-TO, dass ich dieses Array 2-Dimensional nutzen kann, das freute mich.

Jedoch ist das irgendwie nicht so wie gelaufen wie geplant, denn:

arraypointer[0][0]=irgendwas;

Das bringt folgenden Fehler:

error: subscripted value is neiter array nor pointer

und zeigt mir dann auf die zweite eckige Klammer.
Es wird unter Linux programmiert (x86), GCC ist aktuell.

Ich hoffe meine Frage, bzw. dass was ich gerne erklärt bekommen habe möchte ist auch verständlich.
Danke für hilfreiche Antworten!

 

[VikingGe]

Das geht bei dynamisch erstellten Arrays nicht. Irgendwo müsste ja bekannt sein, wie breit das Array ist, um den Index berechnen zu können.

Ab davon - für sonderlich umständlich halte ich das jetzt auch nicht, aber man könnte sich natürlich eine Hilfsfunktion bauen.

inline size_t arrayIndex2D(const size_t x, const size_t y, const size_t width) {
  return x + y * width;
}

 

[SparkMonkay]

Inordnung, also sind die Array's wie in dem Link von C-How-To anders angelegt im Speicher den ich quasi über malloc erzeuge?

 

[NemesisFS]

Das Problem ist, dass ein dereferenzierter long-pointer (ob mit * oder []) ein long ist. Wenn du dymamisch allokierte multidimensionale arrays haben möchtest, musst du getrennt die zeilen und spalten allokieren.

#define N 1024
#define M 1024

long **arr;
arr = (long**) malloc(N*sizeof(long));
for (int i = 0; i < N; i++) {
    arr[i] = (long*) malloc(M*sizeof(long));
}

Ein Problem an der Lösung ist, dass dein zweidimensionales array leider nicht hintereinander im Speicher liegt, du hast viele, potentiell teure Allokationen. Eine Lösung dafür könnte so aussehen:

#define N 1024
#define M 1024

long *arr[N];
long *raw_arr = (long*) malloc(N*M*sizeof(long));
for (int i = 0; i < N; i++) {
    arr[i] = raw_arr + M*i;
}

Hier hast du ein kleines array was die pointer auf die speicherstellen speichert im stack, der eigentliche speicher des arrays ist mit auf dem heap.

EDIT: Die arrays aus dem howto sind auf dem stack angelegt, da muss zur compile-zeit feststehen wie groß die arrays sind, damit diese größe reserviert werden kann (im Beispiel 8*8*sizeof(int) byte)

 

[Rage]

Hallo SparkMonkay, ja aus irgendeinem Grund macht sowas wie

 double Array[<int>][<int>];

immer Probleme wenn man später wie auf einen dynamisch angelegten Doppelzeiger zugreifen möchte. Ich würde Dir für Dein Anliegen eine Funktion wie diese hier:

double** Doppelzeiger(int m, int n)
{
	int i;
	double** A;
	
	A = (double**) calloc(m, sizeof(double*));

	if (A == NULL)
	{
		fprintf(stderr, "Fehler beim Anlegen der Spalten!\n");
		exit(1);
	}	

	for(i=0; i<m; i++)
	{
		A[i] = (double*) calloc(n, sizeof(double));

		if (A[i] == NULL)
		{
			fprintf(stderr, "Fehler beim Anlegen der Matrixeinträge!\n");
			exit(2);
		}
	}
	return A;
}

empfehlen, wenn Du dann irgendwo im Programmcode

 A = Doppelzeiger(m,n);

aufrufst, kannst Du wie gewollt per A[j] auf die Einträge von A zugreifen.

Edit: Da war jemand schneller. Ohne Pointer angelegte Doppelzeiger können übrigens nicht größer als 8MiB werden, so zumindest meine Erfahrung mit C auf OS X und Linux Mint 17 - deshalb besser immer Zeiger benutzen. Ich bevorzuge calloc übrigens über malloc, weil calloc Nullinitiiert, das ist für manche Sachen angenehmer und schließt Fehler aus.

 

[NemesisFS]

Hallo SparkMonkay, ja aus irgendeinem Grund macht sowas wie

 double Array[<int>][<int>];

immer Probleme wenn man später wie auf einen dynamisch angelegten Doppelzeiger zugreifen möchte.

Das sollte doch super funktionieren, man hat halt nur stack statt heap speicher, oder nicht?

Ohne Pointer angelegte Doppelzeiger können übrigens nicht größer als 8MiB werden, so zumindest meine Erfahrung mit C auf OS X und Linux Mint 17 - deshalb besser immer Zeiger benutzen.

Meinst du, dass man Probleme kriegt wenn man mehr als 8MiB am Stück zu allokieren versucht?

Ich bevorzuge calloc übrigens über malloc, weil calloc Nullinitiiert, das ist für manche Sachen angenehmer und schließt Fehler aus.

Das ist natürlich die sicherere Variante, war mir noch nicht bekannt.

 

[Rage]

Ich hatte damit eigentlich immer Probleme, deshalb habe ich das gelassen. Hab sowas für LR-Zerlegung, CC-Zerlegung, Minesweeper etc. schonmal in C benutzt und es war immer die angenehmere Variante, direkt (Doppel-)Zeiger zu nehmen. Man spart ja auch nichts mehr, wenn man eine Funktion geschrieben hat die (Doppel-)Zeiger anlegt.

Ich habe Probleme beim allozieren von Speicher über 8MiB bekommen, sofern nicht mit Pointern passiert - gab dann immer einen Segmentation fault. Mit Pointern ist das weniger problematisch, da kann man so viel allozieren, wie zusammenhängend im RAM verfügbar ist.

 

[SparkMonkay]

Gut, danke erstmals!

ich habe es gestern jetzt 1-D umgesetzt.
Aber gut zu Wissen, wie ich das eigentlich umsetzen muss.

 

[rob-]

Naja, stell dir erstmal vor was ein 2D Array überhaupt ist.

1D: Eine Linie, praktisch eine Zeile mit beliebigen Spalten (malloc(sizeof(int)*5) für 5 Spalten mit Breite eines Integer
2D: Tabelle mit Zeilen und Spalten, [0][1] wäre also Zeile 0 mit Spalte 1
3D: Mehrere Tabellen hintereinander, [0][1][2] wäre Tabelle 0, Zeile 1, Spalte 2
4D: Dateien in denen Tabellen drin sind, die Zeilen und Spalten haben
5D: Festplatten, mit Dateien in denen Tabellen drin sind, die Zeilen und Spalten haben
6D...immer weiter schachteln, Platte in Kiste, Kisten auf Palette, Paletten in LKW usw.

Bei 1D Array hast du dann halt sowas hier, die Zahlen sind int [0][1][3][4][5]
Bei 2D Array hast du da keine Zahlen drin, sondern 1D Arrays, oder besser gesagt Pointer auf 1D Arrays.

Dein äußeres 1D Array wird also nicht mehr über malloc(sizeof(int)) eingerichtet, sondern über malloc(sizeof(int*))

Nachdem du dein äußeres 1D Array gemacht hast, musst du jedem Element [0], [1] etc. ein neues malloc() für ein weiteres 1D Array zuteilen, wobei malloc() Pointer liefert ! Z.b. array[0] = malloc(sizeof(int)*10). Dann hast du auf array[0] den Pointer hin zum Zahlenarray und per [0][x] kannst du dann auf die Zahlen zugreifen.

Bei 3D Array hättest das selbe wie oben, nur wäre [0][0] ein Pointer (und kein Zahlenarray wie oben) der auf ein Zahlenarray zeigt und dessen Elemente du dann per [0][0][0] holen könntest.

Mit C lernt man halt was, mit Java benutzt man nur das Wissen ohne es zu wissen

 

[Magogan]

Am einfachsten und effizientesten ist immer noch ein Makro oder eine Funktion für den Index. Du scheinst ja eine feste Anzahl von Elementen im Array zu haben. In C++ könntest du auch eine class Array2D erstellen und den Operator [] überladen, in C geht das nicht. Ein struct mit dem Zeiger und der Breite geht aber auch in C, dazu noch Funktionen für die Initialisierung, den Zugriff auf das Element (inline) und für das Löschen des Arrays.

Von einem Array aus Zeigern auf 1D-Arrays kann ich nur abraten, das ist unnötig und ineffizient, es sei denn, du hast 1D-Arrays mit unterschiedlicher Größe, also Zeile 1 hat z.B. 5 Elemente und Zeile 2 hat 17.

 

[rob-]

Naja, [] ist einfach nur ein shortcut. Also Pointer Adresse + Offset bis zur Zahl hin.
Damit kann man auch normal rechnen. Zb. Pointer + sizeof(int) liefert [1] eines int array.

Warum sollen Pointer ineffizient sein? Bzw. wie willst sonst ein 2D Array bauen ?
Um auf ein Array zuzugreifen braucht man den Pointer davon, dieser zeigt auf die Startadresse ganz vorne.
Per [2] etc. rechnet C dann der Startadresse den Offset drauf und so kommst zum Inhalt des Array.

 

[Magogan]

Ja, aber ein 2D-Array, bei dem Breite und Höhe beliebig, aber fest sind, kann man einfach als Array aus 1D-Arrays anordnen, also Zeile 1 | Zeile 2 | Zeile 3 | ...

Entsprechend greift man auf die Elemente mit Zeile*Länge der Zeilen + Position in Zeile zu. Also bei einem Array aus 2x3 Elementen (2 Zeilen, 3 Spalten) mit 1*3+2 für die Stelle (1, 2). Da brauchst du kein Array aus Zeigern zu erstellen, die jeweils auf einen Speicherbereich zeigen, an dem die Zeile steht. Bei großen Arrays dauert der Zugriff auf ein Element bei letztere Variante unter Umständen doppelt so lange, und das sind locker 500 Zyklen statt 250, weil du 2 mal einen Cache Miss hast und das Laden aus dem RAM sehr lange dauert verglichen mit einem Cache Hit.

 

[rob-]

Naja, zwei 1D Arrays sind nun mal kein 2D Array
Es wird nur simuliert...

 

[VikingGe]

Und das Problem ist wo? Dein "echtes" 2D-Array als 1D-Array von gleich langen (!) 1D-Arrays ist jedenfalls unnötig langsam und viel zu kompliziert zu handhaben.

Nebenbei ist die "simulierte" Variante auch nicht als unechter als die andere. Letztenendes sind das 1D-Arrays, die im Speicher direkt hintereinander liegen. Man kann sich auch immer noch so eine tolle Pointer-Struktur für die erste Ebene bauen:

int* array = malloc(w * h * sizeof(int));
int** rows = malloc(h * sizeof(int*));
for (size_t i = 0; i < h; i++)
  rows[i] = array + w * i;

...nur, dass das kein Mensch braucht, weil man den korrekten Pointer auf jedes Element sehr effizient berechnen kann.

Das ist etwa so wie mit einem binären Heap fester Größe - niemand würde auf die Idee kommen, den als echten Binärbaum zu implementieren, weil es mit einem Array eben deutlich einfacher geht. Und gerade solche Sachen - wie man etwas effizient macht - gehören doch auch hierzu:

Mit C lernt man halt was

 

[rob-]

Es geht nicht um obfuscated Code zur Effizienz es geht um 2D Arrays...
Kompliziert ist da nix, das wird wie in Java und sonstwo auch gehandhabt.

Bei deinen losen 1D Arrays musst erst mal Pointer dazu verwalten, sie anlegen usw. alles zu kompliziert

 

[VikingGe]

Es wäre wirklich nett, wenn du mal dein Anliegen erklären würdest. Ich verstehe einfach nicht, was du sagen willst und warum das, was du sagst, irgendeine praktische Relevanz hat.

 

[rob-]

Weil kein Mensch Positionen berechnen möchte wenn er auf ein 2D Array zu greift ? Da müsstest dann schon Operatoren überschreiben, was in C nicht geht.

Man kann jegliche Datenhaltung in ein ewig langes 1D Array ausrollen, nur irgendwann ist der Aufwand nicht mehr gerechtfertigt. In der heutigen Programmierung, mit Ausnahme Embedded Systems, geht es nicht um Effizienz sondern um einfach wartbaren Code, da produziert man nicht eigens ausgedachtes sondern hält sich an Standards. Dieser lautet nunmal bei 2D Array Variable[Zeile][Spalte]

Abwandeln darf man nur wenn man es maskieren kann, so dass sich keiner um die Funktionsweise scheren braucht und array[0][1] nutzen kann. Dies geht aber nur in Sprachen wo man [] überschreiben kann.

 

[andy_m4]

wartbarer Code

Weil kein Mensch Positionen berechnen möchte wenn er auf ein 2D Array zu greift ? Da müsstest dann schon Operatoren überschreiben, was in C nicht geht.

Das kann ja auch durch eine Funktion, bzw. wie auch schon vorgeschlagen, ein Makro erledigt werden.

geht es nicht um Effizienz sondern um einfach wartbaren Code, da produziert man nicht eigens ausgedachtes sondern hält sich an Standards.

Na wer wartbaren Code haben möchte, wird auch nur in Ausnahmefällen zu C greifen. :-)

Gruß
Andy