Mehrdimensionale Arrays, dynamisch?

[Che]

Ich hab mal wieder eine Frage:
Wie eindimensionale dynamische (will heißen Größe ist erst zur Laufzeit bekannt) funktionieren ist mir klar. Heute denke ich so herum (;)), und dabei stoße ich auf die Frage wie denn das mit mehrdimensionalen Arrays zu machen ist.
Vorschlag:

int **multiArray=NULL;

void xyz()
{
int größe1=berechnung1(); //hier kommt die 1. größe von irgendwoher
int größe2=berechnung2(); //hier kommt die 2. größe daher

multiArray = new int[größe1][größe2];
}


Ja/Nein, was meint ihr?

[Demirug]

Das geht mit C++ leider nicht. Man muss in einem solchen Fall ein eindimensionale Array erzeugen und sich um die Spalten/Zeilen umrechnung in die Linare Position selber kümmern.

Die Alternative wäre ein Array von Arrays.

[Xmas]

Originally posted by Che
Ich hab mal wieder eine Frage:
Wie eindimensionale dynamische (will heißen Größe ist erst zur Laufzeit bekannt) funktionieren ist mir klar. Heute denke ich so herum (;)), und dabei stoße ich auf die Frage wie denn das mit mehrdimensionalen Arrays zu machen ist.
Vorschlag:

int **multiArray=NULL;

void xyz()
{
int größe1=berechnung1(); //hier kommt die 1. größe von irgendwoher
int größe2=berechnung2(); //hier kommt die 2. größe daher

multiArray = new int[größe1][größe2];
}


Ja/Nein, was meint ihr?

Das geht so nicht, aus mehreren Gründen. Der erste wäre dass du Umlaute verwendest ;)

Du hast multiArray als einen Pointer auf einen Pointer auf int deklariert, was nur Sinn machen würde wenn du ein eindimensionales Pointer-Array anlegen würdest, dessen Elemente wiederum auf Int-Arrays zeigen. Dann würdest du aber mehr Speicherplatz als nötig belegen und hättest eine weitere Indirektion. Nicht sehr sinnvoll also. Der Zugriff auf Elemente würde dann so aussehen:
(*multiArray[a])[b]

So wie der Compiler Zugriffe auf Arrays umsetzt, müssen alle bis auf eine Dimension bekannt sein.
Denn wenn du schreibst:
int zahlen[3][10][5];
int a = zahlen[2][2][4];
Dann ist das im Endeffekt dasselbe wie dies hier:
int zahlen[150];
int a = zahlen[2*50 + 2*5 + 4];
Dieselbe Umrechnung kannst du auch selbst machen, und das ist die einfachste Variante.

Eine weitere Möglichkeit wäre, eine Klasse für ein "dynamisches" (eigentlich dann statisch, aber zur Laufzeit generiert) Array zu schreiben. Dann brauchst du auch nicht auf das Freigeben des Speichers zu achten.


class Array2D
{
public:
Array2D( int Hoehe, int Breite )
{
Daten = new int[Hoehe * Breite];
B = Breite;
}
~Array2D() { if( NULL != Daten ) delete [] Daten; }

int* operator[]( int Y ) { return &Daten[Y*B]; }

private:
int* Daten;
int B;
};



Und noch eine Möglichkeit wäre, die STL zu verwenden, mit vector<vector<int>>. Aber das geht schon etwas übers Ziel hinaus.

[Che]

Hm, das ist ja interessant, sowas aehnliches hab ich mir auch schon gedacht. (wär auch zu schoen wenns so gehen wuerde wie ich dachte)

Konkret brauche ich ein 2dimensionales Array, damit wuerde ich mir dann die Umrechnung sparen:

zeile=2;
spalte=5;

x=Array[2][5]; //oder andersrum?

statt

anzahl_spalten=10;
zeile=2;
spalte=5;

x=Array[zeile*anzahl_spalten + spalte];


AFAIK ist doch ein Array von Arrays nichts anderes als eine Liste von Pointern (Zeilen) die auf Arrays (Spalten) zeigt. Und da der Name eines Arrays auch ein Pointer ist, kam ich auf die Idee einen Array von Arrays als

int **array;

zu deklarieren.

Xmas' Klasse verstehe ich nicht ganz. Der Sinn eines 2dimensionalen Arrays ist doch dass ich mit "[][]" auf die Elemente zugreifen kann. WEnn ich alles richtig verstanden habe bekomme ich mit

Array2D test(10,10);
x=test[2];

das 20. Element zurueck. ???

(keine umlaute, alles so wie sichs gehoert ;))

[Xmas]

Originally posted by Che
AFAIK ist doch ein Array von Arrays nichts anderes als eine Liste von Pointern (Zeilen) die auf Arrays (Spalten) zeigt. Und da der Name eines Arrays auch ein Pointer ist, kam ich auf die Idee einen Array von Arrays als

int **array;

zu deklarieren.

Du kannst das ganze auch mit einem Array von Pointern auf Arrays lösen, aber das ist recht umständlich, da du beim Anlegen erst einmal die Pointer initialisieren musst. Und die Schreibweise (*multiArray[a])[b] ist auch nicht schön.

Xmas' Klasse verstehe ich nicht ganz. Der Sinn eines 2dimensionalen Arrays ist doch dass ich mit "[][]" auf die Elemente zugreifen kann. WEnn ich alles richtig verstanden habe bekomme ich mit

Array2D test(10,10);
x=test[2];

das 20. Element zurueck. ???

Nope, du bekommst einen Pointer auf das 20. Element zurück =)
Also kannst du
int x = test[3][5];
schreiben.

[zeckensack]

Originally posted by Che
Xmas' Klasse verstehe ich nicht ganz. Der Sinn eines 2dimensionalen Arrays ist doch dass ich mit "[][]" auf die Elemente zugreifen kann. WEnn ich alles richtig verstanden habe bekomme ich mit

Array2D test(10,10);
x=test[2];

das 20. Element zurueck. ???

(keine umlaute, alles so wie sichs gehoert ;)) Nö :)

Du bekommst einen Zeiger auf das zwanzigste zurück. Den mußt du dann noch dereferenzieren, also ist
*test[2]
das zwanzigste Element selbst, genauso wie
test[2][0]

Klingelt's?

test[2][1]
wäre das einundzwanzigste Element, usw.

edit: *gnarf* @ XMas

[Che]

Du bekommst einen Zeiger auf das zwanzigste zurück. undNope, du bekommst einen Pointer auf das 20. Element zurück
-> sternchen übersehen :D

Oh Mann, jetzt komm ich schön langsam durcheinander mit diesen ganzen Zeigern;)

Aber ich glaub ich habs:
Der Operator [] liefert mir einen Zeiger auf die Zeile, (Daten[Y*B], wenn ich mich recht entsinne) mit diesem Zeiger kann ich ich dann mit [] auf die Spalte zugreifen - praktisch :)
Danke ihr beiden!

[Matrix316]

Originally posted by Demirug
Das geht mit C++ leider nicht. Man muss in einem solchen Fall ein eindimensionale Array erzeugen und sich um die Spalten/Zeilen umrechnung in die Linare Position selber kümmern.


Und dynamisch wirds, wenn man statt einem Array die klasse "vector" benutzt. ;)

Aber so schlimm ist das garnet. Man gibt halt 2 Werte ein, einer für die Zeile, einer für die Spalte. Dann zwei for schleifen, und die richtigen Werte eingeben. Beim Zugriff muss man halt etwas überlegen. ;) Aber man kann ja ne neue Klasse schreiben die das einlesen und ausgeben der Sachen erledigt. Fertig.

[Demirug]

Originally posted by Matrix316


Und dynamisch wirds, wenn man statt einem Array die klasse "vector" benutzt. ;)

Aber so schlimm ist das garnet. Man gibt halt 2 Werte ein, einer für die Zeile, einer für die Spalte. Dann zwei for schleifen, und die richtigen Werte eingeben. Beim Zugriff muss man halt etwas überlegen. ;) Aber man kann ja ne neue Klasse schreiben die das einlesen und ausgeben der Sachen erledigt. Fertig.

Ich brauche keine STL für sowas. Das geht auch alles mit dem guten alten new und delete.

[Matrix316]

Originally posted by Demirug


Ich brauche keine STL für sowas. Das geht auch alles mit dem guten alten new und delete.

Blablabla..."ich brauch keine STL für sowas"...blablabla...Wen interessiert STL?

Schreib einfach:

#include <vector>

danach:

std::vector<int> irgendwas;

fürs Einlesen:

irgendwas.push_back(wert);

für die Ausgabe:

std::cout<<irgendwas[i];

That´s it. Es ist nicht schwer. Es ist nicht umständlich. Für Dynamische Sachen wurde sowas erfunden, also warum nicht nutzen?

[zeckensack]

Matrix316,

vector <int> ist aus der STL ;)

[Demirug]

Matrix316, ich mag die STL nicht weil sie (zumindestens die implemetierung die MS im VC 6.0 übernommen hat) eine sehr schlechte performance an den Tag legt. Man kann das zwar mit eigenen allocatoren etwas nachhelfen aber dann wird es schon wieder aufwendig.

[Matrix316]

Originally posted by zeckensack
Matrix316,

vector <int> ist aus der STL ;)

Ich weiß! Aber dadurch wirds für mich nicht zum Teufelszeug, sondern ein hilfreiches Mittel zum Zweck. :)

Ich meine, obs aus der STL oder nicht ist, interessiert mich eher weniger. Die Klasse ist vorhanden - also warum nicht nutzen?

[Matrix316]

Originally posted by Demirug
Matrix316, ich mag die STL nicht weil sie (zumindestens die implemetierung die MS im VC 6.0 übernommen hat) eine sehr schlechte performance an den Tag legt. Man kann das zwar mit eigenen allocatoren etwas nachhelfen aber dann wird es schon wieder aufwendig.

Als ab das bei heutigen PCs ein Argument ist...

[Demirug]

Originally posted by Matrix316


Als ab das bei heutigen PCs ein Argument ist...

Ja ist es. Wenn man Echtzeitanwedungen schreibt kommt man sehr schnell auch bei heutigen an die limits. Wir haben ein Serversystem welches eine grössere Anzahl Clients mit Echtzeitdaten versorgen muss. Die STL hat nun die unangenehme Eigenschaft ständig Heap Funktionen aufzurufen. Heap Funktionen haben nun ein paar unschöne Eigenschaften.

1. Mit zunehmender Speichermenge die ein Programm braucht werden sie immer langsamer. Wir brauchen viel Speicherblöcke weil wir alles im RAM halten müssen.

2. Mit zunehmender Laufzeit neigen die Funktionen dazu den Heap zu fragmentieren. Dadurch wird er langsamer. Unsere Software soll im 24/7 Betrieb stabil laufen.

3. Heap funktionen sind Gift für Multiprocessorsysteme. Es kann immer nur eine CPU auf den Heap zugreifen. Sobald es beide versuchen wird eine blockiert.

Lange rede kurzer Sinn. Ohne Speicheroptimierungen hat die Server software jeden verfügbaren Rechner sehr schnell an die Limits gebracht. Nachdem wir für die zentralen Funktionen die Speicherverwaltung komplett überarbeitet haben (alles selbst gemacht) kommen wir kaum noch über 10% CPU Belastung bei einem Dual 1,2 PIII.

EDIT: Und es wird sich doch ständig beschwert das die Games CPU limitiert sind.

[Matrix316]

Die Frage ist, ob es sich wirtschaftlich ist, ein Programm dermaßen auf Speed zu optimieren.

PS.: Wie wäre es mit Assembler? Da kommt selbst das optimierteste C Programm kaum mit. ;)

[Demirug]

Originally posted by Matrix316
Die Frage ist, ob es sich wirtschaftlich ist, ein Programm dermaßen auf Speed zu optimieren.

Wenn es keine Alternative gibt muss man es tun. Wobei der Code im Prinzip gar nicht so sehr auf Speed ausgelegt ist. Wir haben nur die Speicherverwaltung überarbeitet. ca 3-4 Mannwochen arbeit.

PS.: Wie wäre es mit Assembler? Da kommt selbst das optimierteste C Programm kaum mit. ;)

Das lohnt inzwischen kaum noch. Die Compiler sind so gut das sie inzwischen besseren Code als ein mittelmäsiger Assembler programmierer erzeugen. Und hier zählt das Argument der Wirtschaftlichkeit auf jeden Fall.

[Che]

Originally posted by Matrix316


Als ab das bei heutigen PCs ein Argument ist...

Ich habe durch das Entfernen von 5 if-Abfragen und einen Funktionsaufruf 5 FPS mehr erreicht. Es ist zugegebenermaßen ein SEHR einfaches Programm, wo jede eingesparte zeile Code sich bemerkbar macht, aber...ja, das ist bei heutigen PCs ein Argument.

Originally posted by Matrix316
PS.: Wie wäre es mit Assembler? Da kommt selbst das optimierteste C Programm kaum mit.
Gerade C ist doch AFAIK dafür bekannt besseren Maschinencode zu erzeugen als dies von Hand möglich wäre.
Originally posted by Demirug
Ich brauche keine STL für sowas. Das geht auch alles mit dem guten alten new und delete.
Meine Meinung. Und solange es nicht allzu kompliziert wird werde ich auch weiterhin versuchen soviel wie möglich selbst zu schreiben.