Art "ArrayList" in C

xruxl

Ich brauche eine Art "ArrayList", in der ich eine unbestimmte Anzahl von Strings speichern kann. Ich hab mir dazu eine Lösung überlegt, die auch funktioniert, aber ich weiß nicht ob das vom Konzept her so richtig ist.

Das Konzept (vereinfacht):

Code

**char liste = NULL;


//Einlesen
int numElements = 0;
while (/* lese Eingabedaten */) {
   numElements++;
   liste = realloc(liste, sizeof(*char)*numElements);
   strncopy(*(liste + numElements - 1), /* Eingabe */, MAXLENGTH);
}


//Ausgabe
int i;
for (i = 0; i < numElements; i++) {
   fprintf(stdout, "%s", *(liste + numElements));
}


//Speicher löschen
for (i = 0; i < numElements; i++) {
   free(*(liste + numElements));
}


free(liste);

Alles anzeigen

Besonders das Speicherfreigeben ist mir auch noch nicht ganz klar. Die Schleife um den Speicher für die einzelnen Strings freizugeben ist meiner Meinung nach nötig, weil sonst nur die Pointer auf die Strings gelöscht werden, stimmt das? Und gibt realloc() den alten Speicherbereich (wenn verschoben) selbst wieder frei oder muss ich das machen?

Plantschkuh!

Zitat von xruxl

Code

numElements++;
   liste = realloc(liste, sizeof(*char)*numElements);

Das ist vom Konzept her richtig, kann aber bei sehr vielen Elementen ziemlich lahm werden: realloc muß immer wieder alle "alten" Elemente kopieren, im Allgemeinen werden quadratisch viele Elemente kopiert werden. Der gängige Ratschlag ist, die Größe der Liste bei Bedarf exponentiell steigen zu lassen, indem man bei jedem realloc doppelt so viel anlegt wie beim letzten; dann verschwendet man im schlimmsten Fall gleich viel Speicher wie man verwendet, aber man braucht nur logarithmisch viele Aufrufe von realloc und dementsprechend nur O(N log N) Kopien (für N = numElements).

Solche Optimierungen kann man sich aber für später aufheben.

Zitat

Code

strncopy(*(liste + numElements - 1), /* Eingabe */, MAXLENGTH);

Als erstes Argument meinst du liste[numElements - 1]. Das ist mit deinem Ausdruck zu 100% gleichbedeutend, aber es ist für Menschen lesbarer. Und natürlich mußt du das Element liste[numElements - 1] auch irgendwie initialisieren, z.B. mit malloc. Du mußt dann auch nicht unbedingt strncpy und MAXLENGTH verwenden. Und: Überleg dir, was passiert, wenn die Eingabe MAXLENGTH oder mehr Zeichen enthält (falls das überhaupt möglich ist).

Abgesehen davon ist an dieser Zeile nichts auszusetzen

Zitat

Code

for (i = 0; i < numElements; i++) {
   free(*(liste + numElements));
}

Du meinst liste[i], nicht liste[numElements]. Und ja, das geht so, wenn du oben jedes Element der Liste mit malloc, calloc oder realloc initialisierst.

Zitat
Code
free(liste);

Sehr brav

Zitat

Und gibt realloc() den alten Speicherbereich (wenn verschoben) selbst wieder frei oder muss ich das machen?

realloc macht das für dich.

Kampi

vielleicht noch ein paar hints damit du weiszt wo man sich solche fragen selbst beantworten kann:

double-size-realloc: okay, wenn man genug code liest stolpert man drueber, eben einer dieser klassichen tricks.

pointer und arrays: dazu gibt es ein kapitel auf der auch sonst empfehlenswerten seite c-faq.com (leider im moment offline :-/ )

wie verhaelt sich <insert glibc function here>: "man <insert glibc function here>" da steht zum beispiel ganz klar:

Zitat von man realloc

If the area pointed to was moved, a free(ptr) is done.

[edit]und damit ich etwas neues beitrage fuers selbststudium: warum ist prefix ++ besser als postfix und warum ist es in dem fall vollkommen egal[/edit]

Jetzt mitmachen!