Dyn. Memory Allocation

[pfrei]

Hallo zusammen
Ich habe ein Programm, das nur gestartet wird, um ein File nach bestimmten Daten zu durchsuchen, diese auszugeben und dann wieder beendet wird. Es läuft also nicht länger als 2-3 Minuten.
Nun habe ich bisher einen Array definiert, der die Daten aufnehmen soll:


struct response_url {char respurl[MAXURL]; };
struct response_url respnotfound[50000];

Im Forum wurde mir geraten, Dynamic Memory Allocation zu machen, weil die def. 50'000 Arrays wohl viel RAM brauchen... zudem kann es bei der Verarbeitung der Daten sein, dass mehr als 50'000 Daten vorhanden sind, was zu unvorhergesehenem Verhalten führt...
Ich habe nun ein Problem mit der Umsetzung... wie mache ich denn in meinem Beispiel die Allocation mit dem "new"-Operator?? Denn: Ich habe in einem Buch gesehen, dass auch dort die Array-Grösse angegeben werden muss!! -->

float *p = new float [size]->

struct *respnotfound = new struct [50000]Nur: "size" ist ja eben die unbekannte Grösse!!

Kann mir jemand mit einem Beispiel helfen?

Vielen Dank!

[bischi]

Ich glaub, hier würde sich ne Liste anbieten - einfach mal nach (verkettete, doppelt verkettete, zyklische,...)-Liste googeln.

MfG Bischi

[panzi]

Aber da "new" in Code verwendet wurde, wird anscheinend eh C++ programmiert (aber ohne C++ Konstrukte, sprich OOP! :eek:), und dann würde sich std::list und std::string doch anbieten.

#include <iostream>
#include <string>
#include <list>

//...

std::list< std::string > mylist;

// ...
mylist.push_back( "foo" );
mylist.push_back( "bar" );

for( std::list< std::string >::const_iterator i = mylist.begin(), end = mylist.end();
i != end; ++ i ) {
std::cout << *i << std::endl;
}

[pfrei]

O.k. das kannte ich noch nicht. Listen stehen bei mir im Buch unter Container ganz am Schluss :) Das würde aber eine ziemliche Abwandlung meines C++ Progis benötigen :rolleyes:
Also mit dem struct in meinem Beispiel seht Ihr keine andere Möglichkeit?
Gibt's denn nicht so etwas in der Form wie unten dargestellt? Das hier würde doch quasi heissen, "keine vordef. Anzahl Arrays und keine vordef. Array-Inhalte":


struct response_url {char respurl[MAXURL]; };
struct response_url respnotfound[]={ NULL };

[peschmae]

Du könntest natürlich C und die malloc/realloc/free-Funktionen verwenden. Aber das würde ich nicht. Hier ist C++ und da sind die STL Container schon das Ding der Wahl..

MfG Peschmä

[michael.sprick]

Im Forum wurde mir geraten, Dynamic Memory Allocation zu machen, weil die def. 50'000 Arrays wohl viel RAM brauchen... zudem kann es bei der Verarbeitung der Daten sein, dass mehr als 50'000 Daten vorhanden sind, was zu unvorhergesehenem Verhalten führt...
Ich habe nun ein Problem mit der Umsetzung... wie mache ich denn in meinem Beispiel die Allocation mit dem "new"-Operator?? Denn: Ich habe in einem Buch gesehen, dass auch dort die Array-Grösse angegeben werden muss!! -->

float *p = new float [size]->

struct *respnotfound = new struct [50000]Nur: "size" ist ja eben die unbekannte Grösse!!

Kann mir jemand mit einem Beispiel helfen?

Vielen Dank!

Es gibt mehrere Möglichkeiten ein Array zu deklarieren.


int array[10];
//---------------------
const int MAX=20;
int array[MAX];
//---------------------
int array[] = {1,2,3,4,5,6,7,8,9,0};

Was jedoch nicht geht, ist die Länge des Arrays in einer Variablen anzugeben oder sie erst später zu definieren.


int laenge = 10;
int array[laenge]; falsch
//---------------
int array[]; falsch


Hast Du allerdings einen Pointer, dann kannst Du mit new() die Länge später festsetzen - und zwar über eine Variable. Dadurch kannst du dann zur Compile/Laufzeit die Größe des Arrays setzen...



int laenge=10:
int *array;
array = new int[laenge];


In diesem Fall bringt Dich das aber noch nicht sehr viel weiter. Du hast zwar die Größe des gesamten Arrays optimiert, der Pointer zeigt allerdings immernoch auf einen riesigen Brocken im Speicher ( 50.000 Elemente).
Ein Array funktioniert nämlich nur dann, wenn seine Komponenten lückenlos im Speicher hintereinander liegen. Wenn MAXURL z.B 255 ist, dann hast Du bei 50.000 elementen ca. 12MB Ram am Stück belegt.

Mit einer Liste lässt sich das Problem lösen. Wenn Du die nicht nehmen willst, geht auch ein Doppelpointer.

Was ich allerdings noch nicht ganz geblickt habe, wieso verwendest Du structs? Erstmal hast du doch eh nur eine Variable darin (kannst du also auch direkt benutzen) und dann gibt es in C++ doch auch richtige Klassen...

michael

[anda_skoa]

Hallo zusammen
Ich habe ein Programm, das nur gestartet wird, um ein File nach bestimmten Daten zu durchsuchen, diese auszugeben und dann wieder beendet wird.


man grep? ;)

Ciao,
_

[pfrei]

Was ich allerdings noch nicht ganz geblickt habe, wieso verwendest Du structs? Erstmal hast du doch eh nur eine Variable darin (kannst du also auch direkt benutzen) und dann gibt es in C++ doch auch richtige Klassen...
Na ja, ich brauche einfach ein Array, das die Daten im Format:
1 URL-1
2 URL-2
3 URL-3

Hierzu muss ich doch eigentlich einen struct verwenden :confused:

[ContainerDriver]

Hallo,
1. würde ich (wie schon erwähnt) eine verkettet Liste empfehlen. Umkrepeln musst du in deinem Programm dann nur die Methoden zum Hinzufügen & Lesen der Daten in die/aus der Liste (also z.B. statt Speicherung in einem Array-Element).

2. nein, du musst keine Strukturen verwenden, ein mehrdimensionales (zwei) char-Array erfüllt den gleichen Zweck (mit dem Problem, dass du die Größe nicht dynamisch (also ich mein später im Programm den Speicherplatz für das Array) erweitern kannst, oder du benutzt malloc & realloc). Statt eines zweidimensionalen char-Arrays kannst du auch ein String-Array nehmen.

Gruß, Florian

[michael.sprick]

Was die Listen betrifft, so kommt es meiner Meinung nach drauf an, was später mit den Daten passiert.
Um eine bestimmte Komponente zu finden, musst du dich immer erst zum jeweils nächsten Element durchhangeln - kannst also nicht direkt anspringen. Das ist evtl. ein Nachteil wenn es um >50.000 Komponenten geht.

Ein großer Vorteil ist die Geschwindigkeit beim Hinzufügen und Löschen von Elementen. Hierbei werden nämlich nur 2 Pointer umgebogen und fertig. Du musst nicht erst langwierig Elemente kopieren, zwischenspeichern zurückkopieren, usw...

Nachdem Du aber schon sagtest, dass Du eine Liste erstmal vermeiden willst, hier vielleicht ein andere Möglichkeit:

Zunächst nehmen wir statt des structs jetzt eine Klasse.
Eigentschaften sind das 2-dimensionale Array und die Größe desselben. Weil wir hier mit Pointern arbeiten, sollten wir uns auch um Konstruktion und Destruktion kümmern. Außerdem brauchen wir noch eine Methode um Elemente hinzuzufügen(push()) und eine, um Elemente abzufragen - das geht ganz per [] Operator.

class VECTOR
{
private:
char **m_cpData;
int m_iSize;
public:
VECTOR();
~VECTOR();
void push(char*);
char* operator[](int);
};

Im Konstrukor setzen wir den Pointer auf NULL und die Größe naturlich auch auf 0 - es gibt schließlich noch keine Komponenten...


VECTOR::VECTOR
{
m_cpData = NULL;
m_iSize = 0;
}

im Destruktor müssen wir eigentlich nur dafür sorgen, dass der Speicher auch wieder freigegeben wird:

VECTOR::~VECTOR()
{
for(int i=0;i<m_iSize;i++)
delete [] m_cpData[i];
delete [] m_cpData;
}
Dann die Methode um einen String in den Vector reinzupacken:

void VECTOR::push(char *str)
{
char **Data;
int i;
//Daten kopieren
Data = new char*[m_iSize+1];
for(i=0;i<m_iSize;i++)
{
Data[i] = new char[strlen(m_cpData[i])+1];
strcpy(m_cpData[i],Data[i]);
}
// neuen String anhängen
Data[m_iSize] = new char[strlen(str)+1];
strcpy(Data[m_iSize],str);

//altes Array löschen
for(i=0;i<m_iSize;i++)
{
delete [] m_cpData[i];
}
delete [] m_cpData;

// Pointer umbiegen und size inkrementieren
m_cpData = Data;
m_iSize++;
}
Damit man später aus main() dann auch mit dem Indexoperator arbeiten kann und Du z.B. per vector[5] an das 6. Element kommst, müssen wir noch einen Operator überladen...


char* operator[](int index)
{
if(index >= 0 && index < m_iSize)
return(m_cpData[index]);
}

Jo - das wars eigentlich schon...

jetzt kannst Du in main() einfach den Vektor benutzen:


int main()
{
Vector v;
v.push("erstes Element");
v.push("zweites Element");
v.push("drittes Element");
v.push("viertes Element");

cout << v[2] << endl;
return(0);
}

Im Speicher hast Du dann ungefähr folgendes:


[m_cpData]
|------> [0]
| |---------------->["erstes Element"]
|------> [1]
| |---------------->["zweites Element"]
|------> [2]
| |---------------->["drittes Element"]
|------> [3]
|---------------->["viertes Element"]

Da ein Pointer 4 Byte groß ist, und nur die Pointer als Array zusammenhängen, kommst Du bei 50.000 Elementen nun ca. auf einen Block von 200K statt 12MB - die eigentlichen Strings sind wild im Speicher verteilt.

PS: Ich seh - gerade... evtl. ist eine getSize() Methode ganz nützlich - sonst kannst du später nicht durch den Vektor durchiterieren...

[pfrei]

Vielen Dank für Eure hilfreichen Antworten!!!
Ich probiere das sofort aus. Hoffentlich klappt's!!!

[locus vivendi]

Nachdem Du aber schon sagtest, dass Du eine Liste erstmal vermeiden willst, hier vielleicht ein andere Möglichkeit:
Nur sollte man sich bewußt sein, dass deine push-Funktion potentielle Speicherlecks enthält, und sehr ineffizient ist.

[michael.sprick]

kann gut sein... es ging mir auch mehr um die Art und Weise.
Wie können denn dabei Speicherlecks auftreten? und wie vergrößert man ein 2 dimensionales Array effizienter?

[locus vivendi]

Wie können denn dabei Speicherlecks auftreten?
Hier zum Beispiel:

//Daten kopieren
Data = new char*[m_iSize+1];
for(i=0;i<m_iSize;i++)
{
Data[i] = new char[strlen(m_cpData[i])+1];
strcpy(m_cpData[i],Data[i]);
}
Wenn eine der new-Operationen in der Schleife fehlschlägt wird eine Exception geworfen und all der bisher allozierter Speicher in der Funktion geht verloren.


und wie vergrößert man ein 2 dimensionales Array effizienter?
In push allozierst du erst Speicher für die neuen Strings, um sie dann zu kopieren, und den alten Speicher zu löschen. Das ist aber unnötig. Es würde ja reichen, wenn du nur die Pointer in das neue Array kopierst. Nur der eine String, den du als Argument erhälst, müsste kopiert werden.

[michael.sprick]

Ahhh....stimmt. danke!

Dann würde also folgendes reichen?



void VECTOR::push(char *str)
{
char **Data;
int i;
//Daten kopieren
Data = new char*[m_iSize+1];

for(i=0;i<m_iSize;i++)
{
Data[i] = m_cpData[i];
}

// neuen String anhängen
Data[m_iSize] = new char[strlen(str)+1];
strcpy(Data[m_iSize],str);

//altes Zeiger-Array löschen
delete [] m_cpData;

// Pointer umbiegen und size inkrementieren
m_cpData = Data;
m_iSize++;
}



Was müsste denn passieren, wenn beim Änhängen der neuen Komponente das new() fehlschlägt?

sowas?



try
{
Data[m_iSize] = new char[strlen(str)+1];
if(!Data[m_iSize])
{
throw("Speicher konnte nicht alloziert werden");
}
else
{
strcpy(Data[m_iSize],str);
}
}
catch(char* errstr)
{
cout "Fehler: " << errstr << endl;
}



Aber muss ich denn dann auch das gesamte Array wieder mit delete [] freigeben? Ich mein´ , was passiert überhaupt, wenn new fehlschlägt? Steigt mir dann das ganze Programm aus?

Sorry fürs fragen - ich programmier eigentlich mehr in Skriptsprachen... da muss man sich relativ wenig um diese dinge kümmern. ;)

Michael :)

[locus vivendi]

Dann würde also folgendes reichen?
Soweit ich das sehe ja.


Was müsste denn passieren, wenn beim Änhängen der neuen Komponente das new() fehlschlägt?
Wenn new nicht erfolgreich ist, bedeutet das ja gerade, dass eine Ausnahme *von new* geworfen wird. (In diesem Fall genaugenommen "operator new"). Es wird nicht etwas 0 zurückgegeben. Insofern wäre das If-Else Konstrukt nicht sinnvoll. Wenn du tatsächlich mehrere Speicheranforderungen in einer Funktion hast, könntest du Speicherlecks z.B. so verhindern. (Ist nur ein Sketch):


Typ_X* Zeiger1 = 0;
Typ_Y* Zeiger2 = 0;
try {
Zeiger1 = new Typ_X(...);
Zeiger2 = new Typ_Y(...);
}
catch(std::bad_alloc&)
{
// irgendwas vernünftiges tun
// hier könnte man z.B. ein angelegtes Objekt wieder
// zerstören.
}
///Ab hier normal weiterverfahren...
...

Der Witz hierbei ist, das durch die Initialisierung mit 0, bevor new gerufen wird, keiner der beiden Zeiger auf etwas ungültiges Zeigt. Man kann also auf beide Zeiger gefahrlos "delete" anwenden. Natürlich gibt es auch noch Variationen dieses Verfahrens, und auch noch wieder andere Möglichkeiten der Problematik beizukommen. Irgendetwas sollte man aber tun, meiner Meinung nach. Ansonsten gilt, wenn man es vermeiden kann, und es nicht gerade unnötig den Ressourcenbedarf erhöht, sollte man versuchen, möglichst nicht mehrere Speicheranforderungen in einem Code-Teil zu haben. Die Sache ist natürlich, man kommt nicht immer drum herum...


Aber muss ich denn dann auch das gesamte Array wieder mit delete [] freigeben?
Ja. Auch wenn du dir das Umkopieren der Strings jetzt sparst, musst du am Ende natürlich Irgendwann den Speicher wieder freigeben. Das tust du ja auch im Destkruktor.


Ich mein´ , was passiert überhaupt, wenn new fehlschlägt? Steigt mir dann das ganze Programm aus?
Siehe auch oben; Wenn du keine besonderen Vorkehrungen triffst (namentlich catch-Blocks), dann stoppt die Behandlung der geworfenen Exception erst durch den Aufruf von terminate. Mit anderen Worten, das Programm steigt komplett aus.


Sorry fürs fragen - ich programmier eigentlich mehr in Skriptsprachen... da muss man sich relativ wenig um diese dinge kümmern.
Das stimmt gewissermaßen. Allerdings hast du ja auch ein Mittel der Standardbibliothek nachprogrammiert.

[michael.sprick]

Hmmm.... interessante Sache.

Ich habe mir aus indien neulich Eckel´s "Thinking in C++" mitgebracht - ich denke, ich muss mir jetzt endlich mal Zeit nehmen, das zu lesen.

Vielen Dank schonmal für die Erklärungen :)