Frage zu malloc()

ach langsam frustrierts mich immer falsche antworten zu geben also laut wikipedia
ist ein dynamisches array ungefähr so definiert

Linked  Array   Dynamic
                                list            array
-----------------------------------------------------------------
Indexing                        O(n)    O(1)    O(1)
Insertion/deletion at end       O(1)    N/A     O(1)
Insertion/deletion in middle    O(1)    N/A     O(n)
Wasted space (average)          O(n)    0       O(n)

für mich war bisher immer eine linked list ein dynamisches array evtl. kommt das
auch daher das ich einfach zu lang mit script sprachen gecoded hab wo man sich
um das ganze zeug nicht kümmern mußte

Barbarossa

nwp2 schrieb:

Du hast das schon richtig analysiert. Das Beispiel im Buch hat das Problem übrigens nicht, da nur einmal Speicher angefordert wird und sich das Programm danach beendet, wonach eh der Speicher freigegeben wird.

In deinem Beispiel kannst du in Zeile 13 ein free(p); schreiben.

Aber im Beispielcode des Buches wurde doch eine do while Schleife implementiert, und so lang der nutzer nicht 0 eingibt, kann er immer wieder Heap allozieren??? Und dabei wird ja jedes Mal der frühere, zu klein, reservierte Bereich nicht mehr freigegeben...

Logisch ist das bei diesem Beispiel "egal" nur das soll ja nur als Beispiel herhalten.

Meine Frage ist nur: Hat der Auto von C von A bis Z das free() vergessen/bewusst darauf verzichtet (dann ist das Thema abgehackt) oder hab ich etwas total falsch verstanden.

Friedrich Barbarrosa

PS: Noch etwas: Du sagst bei Beendigung des Programms würde aller Heap eh wieder freigegeben. Frage: Kann ich mich den darauf verlassen??? Also ich meine bei Windows/Linux ist das glaub schon so, aber wenn ich es z. B. auf meinem Taschenrechner ausführe, wird da der Heap auch wieder frei gegeben oder nur vielleicht?

Barbarossa schrieb:

Meine Frage ist nur: Hat der Auto von C von A bis Z das free() vergessen/bewusst darauf verzichtet (dann ist das Thema abgehackt) oder hab ich etwas total falsch verstanden.

er hat es entweder vergessen, oder er wusste es nicht besser. der autor von 'c von a-z' ist, was C betrifft, ein totaler blindgänger. sein machwerk ist voller schrecklicher fehler, ein vergessenes 'free' ist noch einer der harmlosesten.

Barbarossa schrieb:

PS: Noch etwas: Du sagst bei Beendigung des Programms würde aller Heap eh wieder freigegeben. Frage: Kann ich mich den darauf verlassen??? Also ich meine bei Windows/Linux ist das glaub schon so, aber wenn ich es z. B. auf meinem Taschenrechner ausführe, wird da der Heap auch wieder frei gegeben oder nur vielleicht?

wenn du dir nicht sicher bist, darfst du das 'free' nicht weglassen. windows z.b. gibt den speicher eines prozesses frei, wenn dieser stirbt. aber z.b. ein system ohne übergeordnete ressourcenverwaltung würde das nicht tun. daher: wenn man's genau nimmt, darf man auf 'free' niemals verzichten.

;fricky schrieb:

wenn du dir nicht sicher bist, darfst du das 'free' nicht weglassen. windows z.b. gibt den speicher eines prozesses frei, wenn dieser stirbt. aber z.b. ein system ohne übergeordnete ressourcenverwaltung würde das nicht tun. daher: wenn man's genau nimmt, darf man auf 'free' niemals verzichten.

welche systeme wären das zum beispiel?

vcxvc schrieb:

welche systeme wären das zum beispiel?

ich denke uCLinux z.b, das hat ja kein virtuelles speichermanagement und auch kein brk/sbrk usw. malloc/realloc greifen speicher vom globalen pool ab. vergisst ein prozess, den speicher wieder freizugeben, ist er futsch.

pointercrash**

vcxvc schrieb:

welche systeme wären das zum beispiel?

Embedded Controller z.B.
Wenn nicht gerade zwingende Gründe dagegen sprechen (die gibt's fallweise auch), sollte jedes malloc() sein free() bekommen, das hält den Code kompatibel, ob nun ein OS mit Kontextüberwachung drüber sitzt oder nicht.

PS: Was für'ne blöde Idee, ohne realloc auszukommen. Ist ja so, wie geh' zum 100m- Sprint, hack' Dir aber vorher ein Bein ab. Eine passende Prothese wäre übrigens memcpy()

nwp2

Barbarossa schrieb:

Aber im Beispielcode des Buches wurde doch eine do while Schleife implementiert, und so lang der nutzer nicht 0 eingibt, kann er immer wieder Heap allozieren??? Und dabei wird ja jedes Mal der frühere, zu klein, reservierte Bereich nicht mehr freigegeben...

Ich habe nicht weitergelesen und mir nur das erste Beispiel angesehen. Ja, im letzten Beispiel fehlt ein free.

Du kannst auch davon ausgehen, dass dein Taschenrechner keinen Heap hat und malloc wohl eher nicht benutzt werden würde.

nwp2 schrieb:

Du kannst auch davon ausgehen, dass dein Taschenrechner keinen Heap hat und malloc wohl eher nicht benutzt werden würde.

http://sense.net/~egan/hpgcc/ *fg*

nwp2

Ich will so einen haben.

pointercrash() schrieb:

PS: Was für'ne blöde Idee, ohne realloc auszukommen. Ist ja so, wie geh' zum 100m- Sprint, hack' Dir aber vorher ein Bein ab. Eine passende Prothese wäre übrigens memcpy()

Ich weiss nicht in wie weit es richtig ist, aber da realloc immer als langsam angepriesen wird ist diese Funktion für mich auch ein gebranntes Kind .

player4245 schrieb:

Ich weiss nicht in wie weit es richtig ist, aber da realloc immer als langsam angepriesen wird ist diese Funktion für mich auch ein gebranntes Kind .

Höre ich jetzt gerade zum ersten mal.

hab gerade mal gsucht und nirgends was gefunden. Ich bin mir aber sicher das mal irgendwo gelesen zu haben.

player4245 schrieb:

Ich weiss nicht in wie weit es richtig ist, aber da realloc immer als langsam angepriesen wird ist diese Funktion für mich auch ein gebranntes Kind

naja, realloc/malloc/free usw. sind generell langsam, jedenfalls viel langsamer beim allozieren als z.b. GC-heaps (wie in Java und C# z.b.) und natürlich viel-viel langsamer als feste arrays (hallo nwp2 *fg*). realloc's worst-case ist, wenn der bestehende speicherblock nicht erweitert werden kann. dann wird ein neuer angelegt, alles rüberkopiert und der alte freigegeben.

player4245 schrieb:

Ich weiss nicht in wie weit es richtig ist, aber da realloc immer als langsam angepriesen wird ist diese Funktion für mich auch ein gebranntes Kind .

Kommt drauf an, wie man realloc einsetzt. Nimmt man es z.B. für ein Zeigerarray, das die Zeiger von irgendwelchen Elementen ( z.B. Strukturen ) speichert, indem es bei jedem neu hinzugekommen Element um eins allokiert, dann ist es gegenüber einer verketteten Liste nicht nur langsam, sondern nur langsam.
:p
Dann ist es schon besser, wenn man ganze Blöcke von Zeigern mit NULL vorbelegt. Das Allokieren findet dann nicht mehr so oft statt, sondern nur dann, wenn ein Block aufgebraucht ist.