PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : C++ - malloc & array


Durcairion
2005-10-24, 09:59:33
Hey, ich stehe vor einem Problem in der C++ programmierung.

Bis Mittwoch muss ich ein Programm erstellt haben mit folgneden Voraussetzungen:

Der speicher soll vorher mittels malloc reserviert werden.

Nun aber zu meinem Problem:

Ich brauche ein Array der größe a[n+1][n+1]

Wie reserviere ich nun den Speicher für dieses Array und lege gleichzeitig das Array auch an?

Das Array soll vom Typ int** sein.

Vielen Dank im Voraus

Corrail
2005-10-24, 10:44:24
Erstmal würd ich dir in C++ empfehlen ein Array mit new und nicht mit malloc anzulegen. Ansonsten musst du es so machen:

int ** my_array;

my_array = new int*[n+1]; // (int**)malloc(sizeof(int*)*(n+1));

for (int i = 0; i < n+1; i++)
my_array[i] = new int[n+1]; // (int*)malloc(sizeof(int)*(n+1));

Xmas
2005-10-24, 10:50:52
Wenn es int** sein muss:

int ** array = malloc((n+1) * sizeof(int *));
array[0] = malloc((n+1) * (n+1) * sizeof(int));
for(int i = 1; i < n + 1; ++i)
array[i] = array[i - 1] + (n + 1);

//...

free(array[0]);
free(array);

Ungetestet.

muhkuh_rs
2005-10-24, 11:00:39
Im Prinzip gibt es bei C++ so etwas wie ein dynamisch erzeugtes Array als Datenstruktur gar nicht (STL mal außen vor). Alles was man hat ist Pointerarithmetik.

Für ein 2D m*n Array musst Du Speicher anlegen, der alle Elemente des Arrays aufnehmen kann:

int * * pArray=(int**)malloc(m*n*sizeof(int**));

(Schöner wäre aber C++ zu verwenden: int ** pArray=new int**[m*n]; )

In dem Stück Speicher kannst du jetzt mit Pointerarithmetik navigieren:

pArray[0], pArray[1], pArray[2] ... pArray[m*n]

Da du pArray als zweidimensionales Feld haben willst, musst du dir den Index selber berechnen. Stell dir bei einem 2D-Array von m Zeilen und n Spalten vor, die Zeilen würden alle aneinandergehängt. Das ergibt dann ein eindimensionales Array mit m*n Elementen (so eins wie wir erstellt haben). Wenn Du mittels Zeilen- und Spaltenindex auf das Array zugreifen willst, musst du den 2D-Index in einen 1D-Index umrechnen.

Will man Zeile a und Spalte b aus einem 2D-Array mit m Zeilen und n Spalten, dann ergibt sich der index als:a*n+b:

pArray[a*n+b]

Durcairion
2005-10-24, 11:20:37
Ok danke werde gleich testen

Ich stehe aber immer noch vor dem Problem das ich ja ein 2D Array benötige und mit einem 1D Array wenig anfangen kann :/

noid
2005-10-24, 11:33:29
Ok danke werde gleich testen

Ich stehe aber immer noch vor dem Problem das ich ja ein 2D Array benötige und mit einem 1D Array wenig anfangen kann :/

dein "2D-Array" ist in wahrheit auch nur ein zusammenhängender Speicherbereich ohne klare Indizierung.

die [][] dienen auch nur der Berechnung des Offsets. Du könntest also auch mit dem int**-Zeiger und dem relativen Offset direkt arbeiten. Ist aber auf dauer etwas doof ,) Du hast also einen "2D-Array".

ein int[2][2] sieht im Speicher auch nicht anders aus als ein array int[4].

Durcairion
2005-10-24, 12:26:39
dein "2D-Array" ist in wahrheit auch nur ein zusammenhängender Speicherbereich ohne klare Indizierung.

ein int[2][2] sieht im Speicher auch nicht anders aus als ein array int[4].

Das ist mir schon klar, nur damit zu arbeiten ist viel komplizierter als mit einem a[][] array :>

noid
2005-10-24, 12:29:29
du kannst doch auf den int** mit [][] zugreifen? Ist doch kein Problem.

Durcairion
2005-10-24, 12:45:04
du kannst doch auf den int** mit [][] zugreifen? Ist doch kein Problem.

Wie wo was?

noid
2005-10-24, 13:25:16
Speicher anlegen, dann mit <zeigername>[index][index2] darauf zugreifen?

GloomY
2005-10-24, 14:45:34
Mal 'ne Frage, die mit malloc zusammenhängt: Wenn man sauber programmieren will, sollte man dann nicht jedesmal testen, ob malloc() NULL zurückliefert und in diesem Falle das Programm mit einer Fehlermeldung beenden?


Xmas,

deine Lösung ist verdammt tricky ;) Erst dachte ich, dass es nicht funktioniert, aber dann habe ich es nach einer Weile doch verstanden. Pointer-Arithmetik rult ;)

Xmas
2005-10-24, 15:09:05
Mal 'ne Frage, die mit malloc zusammenhängt: Wenn man sauber programmieren will, sollte man dann nicht jedesmal testen, ob malloc() NULL zurückliefert und in diesem Falle das Programm mit einer Fehlermeldung beenden?
Ja sollte man natürlich, genauso wie man den cast beim malloc nicht vergessen sollte. ;)

Durcairion
2005-10-24, 15:44:11
Speicher anlegen, dann mit <zeigername>[index][index2] darauf zugreifen?

Leider funktioniert das nicht ...

Ich habe nun ein Programm mit folgendem Array geschrieben:

int quad[n+2][n+2];

ersetze ich die Zeile nun durch:

int ** quad=new int*[(n+2)*(n+2)];

So bringt er immer einen Speicherfehler und ein Programmabsturz ist die Folge

Xmas
2005-10-24, 15:51:31
Das funktioniert auch so nicht. Wenn du ein dynamisch allokiertes Array als int** mit [x][y] nutzen willst, musst du es so machen wie in Corrails oder meinem Beispiel.
Allerdings sollte dir klar sein dass das Speicherverschwendung ist und du auch ein eindimensionales Array mit [(n+1) * y + x] ansprechen kannst (nichts anderes macht der Compiler bei statischen mehrdimensionalen Arrays).

muhkuh_rs
2005-10-24, 16:13:36
Leider funktioniert das nicht ...

Ich habe nun ein Programm mit folgendem Array geschrieben:

int quad[n+2][n+2];

ersetze ich die Zeile nun durch:

int ** quad=new int*[(n+2)*(n+2)];

So bringt er immer einen Speicherfehler und ein Programmabsturz ist die Folge

Mehrdimensionale Arrays mit [][] funktionieren nur, wenn zur Kompilierzeit bekannt ist, welche Dimensionen das Array hat. Dann erstellt der Compiler auch nur ein eindimensionales Array und berechnet den korrekten Index beim Übersetzen.

Wenn schon C++, dann richtig:

#include <vector>

template <class T>
class TArray2D
{
public:
void SetSize(const int iWidth, const int iHeight)
{
m_iWidth=iWidth;
m_vData.resize(m_iWidth*iHeight);
}

int GetWidth() { return m_iWidth; }
int GetHeight() { return m_vData.size()/m_iWidth; }

TArray2D() { m_iWidth=0; }

T & Element(const int iWidthIndex, const int iHeightIndex)
{
return m_vData[iHeightIndex*m_iWidth + iWidthIndex];
}

private:
std::vector<T> m_vData;
int m_iWidth;
};

typedef TArray2D<int> CIntArray;

int main(const char * args[], int iNumArgs)
{
CIntArray intArray;
intArray.SetSize(7, 8);

intArray.Element(4,5)=7;

int iTest=intArray.Element(4,5);
}

Durcairion
2005-10-24, 16:45:57
Das funktioniert auch so nicht. Wenn du ein dynamisch allokiertes Array als int** mit [x][y] nutzen willst, musst du es so machen wie in Corrails oder meinem Beispiel.
Allerdings sollte dir klar sein dass das Speicherverschwendung ist und du auch ein eindimensionales Array mit [(n+1) * y + x] ansprechen kannst (nichts anderes macht der Compiler bei statischen mehrdimensionalen Arrays).


Vielen Dank! Habe es nun geschafft ... Danke für die Hilfreiche Unterstützung

Coda
2005-10-24, 16:48:22
Wenn schon C++, dann richtig: http://www.boost.org/libs/multi_array/doc/index.html :tongue:

Corrail
2005-10-24, 23:16:02
Wenn es int** sein muss:

int ** array = malloc((n+1) * sizeof(int *));
array[0] = malloc((n+1) * (n+1) * sizeof(int));
for(int i = 1; i < n + 1; ++i)
array[i] = array[i - 1] + (n + 1);

//...

free(array[0]);
free(array);

Ungetestet.

Hey, sowas ist mir noch nie eingefallen. Cooler Trick, danke ;)

GloomY
2005-10-25, 11:55:15
Sehe ich das richtig, dass Xmas Version gegenüber der Schleifen-Version vom Anfang (Corrail) besser ist, weil es garantiert ein zusammenhängender Speicherbereich ist und damit Fragmentierung verhindert (jeder Aufruf von malloc() innerhalb der Schleife kann einen anderen Speicherbereich allozieren) räumliche Datenlokalität besser ausnutzt, also insbesondere zu einer besseren Cacheausnutzung führt? vielleicht sogar bei der Initialisierung schneller ist, weil weniger malloc() Aufrufe notwendig sind (2 vs. Anzahl der Zeilen)?In dem Fall werde ich in Zukunft wohl Xmas Version verwenden =)


edit: Das mit den weniger Speicherzugriffen stimmt natürlich nicht.

Corrail
2005-10-25, 12:20:38
Ja, Xmax Version ist auf jeden Fall effektiver als meine. Schon allein die "vielen" malloc Aufrufe kosten Performance und was ist mitbekommen hab ist, dass Speicherverwaltung (sei es über malloc/free oder new/delete) teuer ist.

GloomY
2005-10-25, 12:30:07
Ja, Xmax Version ist auf jeden Fall effektiver als meine. Schon allein die "vielen" malloc Aufrufe kosten Performance und was ist mitbekommen hab ist, dass Speicherverwaltung (sei es über malloc/free oder new/delete) teuer ist.Ist nicht jeder Aufruf von malloc() ein Syscall und damit mit einem Kerneintritt verbunden?! Und wir wissen ja alle, wie teuer diese sind...

Coda
2005-10-25, 19:55:00
Ja, das stimmt soweit ich weiß. Aber ich glaube eher dass die Laufzeit des Allokators dort das Problem ist und nicht der Kerneintritt.

Gast
2005-10-25, 22:14:11
Das funktioniert auch wunderbar:

#include <vector>
using namspace std;

vector<vector<char> > vAR;

void Create(int rows,int cols)
{
vAR.resize(rows);
vector<vector<char> >:iterator it = vAr.begin();
for(;it!=vAR.end();++it)
*it.resize(cols);
}

Coda
2005-10-25, 22:21:18
Ja das funktioniert. Nur leider hast du dann kein Speicherstück, sondern einzelne Vektoren und den Overhead beim Zugriff über den 2. Vektor.

Die beste Lösung ist imho immer noch boost::multi_array.

Gast
2005-10-26, 10:53:02
>Ja das funktioniert. Nur leider hast du dann kein Speicherstück, sondern >einzelne Vektoren und den Overhead beim Zugriff über den 2. Vektor.
Der Overhead welcher durch die 1. Dimension ensteht ist sehr gering.
Da Vector nicht fragmentiert und der ungeprüfte Zugriff flott von statten geht. Das ich nicht ein Speicherstück habe war mir schon bewust.

>Die beste Lösung ist imho immer noch boost::multi_array.
Da werd ich mir mal die Implementierung ansehen müssen.
Und dazu braucht man die boost Lib. Welche nicht überall verfügbar ist.

Coda
2005-10-26, 16:06:06
Der Overhead welcher durch die 1. Dimension ensteht ist sehr gering.
Da Vector nicht fragmentiert und der ungeprüfte Zugriff flott von statten geht. Das ich nicht ein Speicherstück habe war mir schon bewust.Cache Lokalität, etc. Es ist um einiges besser das Array am Stück zu haben.

Da werd ich mir mal die Implementierung ansehen müssen.
Und dazu braucht man die boost Lib. Welche nicht überall verfügbar ist.Dann läd man sie halt kurz runter. Man braucht nichtmal was zu kompilieren, weil header (Templates).

zeckensack
2005-10-26, 18:18:28
Ist nicht jeder Aufruf von malloc() ein Syscall und damit mit einem Kerneintritt verbunden?! Und wir wissen ja alle, wie teuer diese sind...Es kommt auf die Qualität der C/C++-Runtime an.
malloc muss nicht zwingend ein Syscall sein; schon garnicht bei kleinen Speichermengen. Die Runtime kann (und sollte, IMO) in der malloc-Implementation den Speicher in größeren Blocks vom OS anfordern, und davon dann scheibchenweise an die Applikation abgeben.

Eine Runtime mit besonders gutem malloc hat zB GCC bzw MingW.
(ich weiß dass MingW zT auf die MSVC6-Runtime aufsetzt, aber das tut nichts zur Sache)

GloomY
2005-10-26, 19:35:27
Es kommt auf die Qualität der C/C++-Runtime an.
malloc muss nicht zwingend ein Syscall sein; schon garnicht bei kleinen Speichermengen. Die Runtime kann (und sollte, IMO) in der malloc-Implementation den Speicher in größeren Blocks vom OS anfordern, und davon dann scheibchenweise an die Applikation abgeben.Genau das war der Grund für meine Frage. Ich wusste doch, dass ich da mal was in der Richtung gehört hatte...

btw: Ist unter Linux die Runtime ein Bestandteil der glibc?
Eine Runtime mit besonders gutem malloc hat zB GCC bzw MingW.
(ich weiß dass MingW zT auf die MSVC6-Runtime aufsetzt, aber das tut nichts zur Sache)Es gibt ja auch spezielle Runtime-Libraries wie z.B. Smartheap (http://www.microquill.com/smartheap/index.html).

Und weil du so vom GCC schwärmst ;) : Gibt's Vergleichswerte zu anderen Runtimes?