Verkettete Listen

[Jens (Gast)]

Hallo zusammen, ich verstehe folgenden Programm Code nicht:

include <iostream>
using namespace std;

struct TListenKnoten
{
    int data;            // simuliert die Daten
    TListenKnoten *next; // Verknüpfung zum Nachfolger
};

TListenKnoten *Anker = 0; // Anfang der Liste

int main()
{
    int Inhalt;
    TListenKnoten *node, *old;
    // Fülle die Liste mit Zahlen, bis 0 eingegeben wird
    do
    {
        cout << "Zahl eingeben (0 für Ende)" << endl;
        cin >> Inhalt;
        if (Inhalt)
        {
            // Neues Element für die Liste erzeugen:
            TListenKnoten *node = new TListenKnoten;
            node->data = Inhalt;  // Besetze die Daten
            node->next = Anker; // Hänge die bisherige Liste an
            Anker = node;       // Setze den Anfangspunkt hierher
        }

Insbesondere die vier Zeilen zur Erzeugung eines neuen Elements. 
Eigentlich sollte next die Adresse des nächsten Elements enthalten. Aber 
Anker ist doch die Adresse der vorherigen Elements. Ich bin etwas 
verwirrt.

[nicht"Gast" (Gast)]

Bei deinem Code wird immer^am Anfang der Liste ein neues Element 
eingefügt. Ungwöhnlich aber nicht falsch.

[Zweifler (Gast)]

Ich bin kein Programmierer, aber:

Mal Dir mal auf, was passiert, wenn ein Element (oder mehr) eingefügt 
wird, dann wird es logischer.

In Prosa: Wenn Inhalt true ist, dann wird ein neues Element erzeugt, und 
an den Anfang der Kette geschoben. (anker = node) Vorher wird der Rest 
der Kette (hängt ja bisher an anker) an den next des neu erzeugten nodes 
gehängt.

[Dr. Sommer (Gast)]

Anker ist immer das erste Element, und die neuen Elemente werden vorne 
eingefügt.

Ansonsten:

Jens schrieb:
> TListenKnoten *Anker = 0; // Anfang der Liste
Ist an der Stelle zwar korrekt, aber sauberer ist nullptr statt 0.

Jens schrieb:
> using namespace std;
Sollte man gar nicht machen:
https://stackoverflow.com/q/1452721

Jens schrieb:
> TListenKnoten *node, *old;
Du definierst node einmal hier, und einmal in der Zeile mit "new". Die 
2. Definition überdeckt die erste. Wozu das?

Du reagierst nicht auf die Exceptions von  "new"; wenn nicht mehr genug 
Speicher da ist, bleiben alle Datenstrukturen im Speicher liegen (Memory 
Leak).

Zusammenfassend:
* Frage an Semester-Ende gestellt
* Wenig Verständnis der Materie
* Schlechter Code
* Folgerung: Zu spätes Lernen für Klausur aufgrund Nicht-Aufpassens in 
der Vorlesung bei schlechtem Lehrkörper.

[Felix U. (ubfx)]

Dr. Sommer schrieb:
> Du reagierst nicht auf die Exceptions von  "new";

Man kann es auch übertreiben

[Dr. Sommer (Gast)]

Felix U. schrieb:
> Man kann es auch übertreiben
Man kann es auch richtig machen. Alternativ Standard-Container ala 
std::list nutzen, die haben das schon fix und fertig eingebaut.

[Carl D. (jcw2)]

Dr. Sommer schrieb:
> Jens schrieb:
>> TListenKnoten *Anker = 0; // Anfang der Liste
> Ist an der Stelle zwar korrekt, aber sauberer ist nullptr statt 0.

Der Code ist aber eher 90er-Style und nullptr gibt es erst ab C++11.

[Felix U. (ubfx)]

Dr. Sommer schrieb:
> Felix U. schrieb:
>> Man kann es auch übertreiben
> Man kann es auch richtig machen. Alternativ Standard-Container ala
> std::list nutzen, die haben das schon fix und fertig eingebaut.

Da wirst du aber schwer enttäuscht sein wenn du mal echten C++ code 
siehst. OOM-Exceptions zu fangen macht nämlich keiner. Guck dir z.b. mal 
Webkit oder Chromium an. Geleakt wird da auch kein Speicher, weil es ja 
direkt danach wegen der Nullpointer dereference crasht.

[Dr. Sommer (Gast)]

Carl D. schrieb:
> Der Code ist aber eher 90er-Style und nullptr gibt es erst ab C++11.
Umso schlimmer. Die 90er sind vorbei, man darf neue Technologien nutzen.

Felix U. schrieb:
> OOM-Exceptions zu fangen macht nämlich keiner.
Fangen braucht man die auch nicht. Vernünftige Datenstrukturen nach 
RAII-Schema mit Destruktoren usw. würden das Problem schon lösen.

Felix U. schrieb:
> Geleakt wird da auch kein Speicher, weil es ja
> direkt danach wegen der Nullpointer dereference crasht.
Wenn's crasht sind hoffentlich noch alle möglichen Ports und Dateien 
offen, sodass man die erstmal nicht benutzen kann? Top Lösung.

[Felix U. (ubfx)]

Dr. Sommer schrieb:
> Wenn's crasht sind hoffentlich noch alle möglichen Ports und Dateien
> offen, sodass man die erstmal nicht benutzen kann? Top Lösung.

Arbeitest du auf einem Amiga64 oder so? Jedes moderne OS schließt alle 
Handles eines gecrashten Prozesses.

[Dr. Sommer (Gast)]

Felix U. schrieb:
> Jedes moderne OS schließt alle
> Handles eines gecrashten Prozesses.
Echt? Linux nicht. So eine Arbeitsweise sollte man sich jedenfalls nicht 
angewöhnen. Manche Software (Server...) muss doch etwas länger laufen.

[yesitsme (Gast)]

Dr. Sommer schrieb:
> Umso schlimmer. Die 90er sind vorbei, man darf neue Technologien nutzen.

Wie würde bei dir ein alle Unabwägbarkeiten abfangendes Beispielprogramm 
aussehen, das std::list verwendet um die Funktionsweise einer 
verketteten Liste zu demonstrieren?

[Carl D. (jcw2)]

Felix U. schrieb:
> Dr. Sommer schrieb:
>> Wenn's crasht sind hoffentlich noch alle möglichen Ports und Dateien
>> offen, sodass man die erstmal nicht benutzen kann? Top Lösung.
>
> Arbeitest du auf einem Amiga64 oder so? Jedes moderne OS schließt alle
> Handles eines gecrashten Prozesses.

Als ich noch jung war, hat der Dr. Sommer sich um die echten Probleme 
der Menschheit gekümmert. Jetzt versucht er mit der Zeit zu gehen. ;-)

[Felix U. (ubfx)]

Dr. Sommer schrieb:
> Felix U. schrieb:
>> Jedes moderne OS schließt alle
>> Handles eines gecrashten Prozesses.
> Echt? Linux nicht.

Doch

https://github.com/torvalds/linux/blob/v4.10/kernel/exit.c#L737

exit_mm(tsk);
[...]
exit_sem(tsk);
exit_shm(tsk);
exit_files(tsk);
exit_fs(tsk);

[Dr. Sommer (Gast)]

yesitsme schrieb:
> Dr. Sommer schrieb:
>> Umso schlimmer. Die 90er sind vorbei, man darf neue Technologien nutzen.
>
> Wie würde bei dir ein alle Unabwägbarkeiten abfangendes Beispielprogramm
> aussehen, das std::list verwendet um die Funktionsweise einer
> verketteten Liste zu demonstrieren?
Ich würd's mal so versuchen:

#include <iostream>
#include <list>
std::list<int> myList;
int main () {
  int Inhalt;
  do {
    std::cout << "Zahl eingeben (0 für Ende)" << std::endl;
    if (std::cin >> Inhalt)
      myList.push_back (Inhalt);
    else
      Inhalt = 0;
  } while (Inhalt);
}

Felix U. schrieb:
> Doch
Ah, gut zu wissen dass das endlich mal gelöst ist. Ich würde dennoch 
sagen, dass "einfach Abstürzen lassen" keine ordentliche 
Herangehensweise ist. Sonst beschweren sich immer alle über instabile 
Software...

[yesitsme (Gast)]

Dr. Sommer schrieb:
> Ich würd's mal so versuchen:

Ja... das zeigt wie man std::list verwendet... aber wie funktioniert 
eine verkette Liste?

[Dr. Sommer (Gast)]

yesitsme schrieb:
> aber wie funktioniert
> eine verkette Liste?

Wenn man eine fertige Komponente nutzt, sieht man wohl kaum die 
Innereien. Dein Wunsch ist ein Widerspruch in sich.

Im <list> Header kann man nachsehen wie das funktioniert. Oder in einem 
guten(!) Buch, wie z.B. "The C++ Programming Language".

[Rolf M. (rmagnus)]

Dr. Sommer schrieb:
> Felix U. schrieb:
>> Man kann es auch übertreiben
> Man kann es auch richtig machen. Alternativ Standard-Container ala
> std::list nutzen, die haben das schon fix und fertig eingebaut.

Dir ist nicht in den Sinn gekommen, dass es gerade darum gehen könnte, 
die Funktionsweise einer verkettete Liste zu verstehen?
Einem Maurerlehrling wird man auch nicht das Mauern beibringen, indem 
man ihm eine Fertigwand aus Beton hinstellt.

Dr. Sommer schrieb:
>> Wie würde bei dir ein alle Unabwägbarkeiten abfangendes Beispielprogramm
>> aussehen, das std::list verwendet um die Funktionsweise einer
>> verketteten Liste zu demonstrieren?
> Ich würd's mal so versuchen:#include <iostream>
> #include <list>
> std::list<int> myList;
> int main () {
>   int Inhalt;
>   do {
>     std::cout << "Zahl eingeben (0 für Ende)" << std::endl;
>     if (std::cin >> Inhalt)
>       myList.push_back (Inhalt);
>     else
>       Inhalt = 0;
>   } while (Inhalt);
> }

Und wo ist da jetzt die von dir für so wichtig erachtete Reaktion auf 
die Exception, wenn kein Speicher mehr da ist? Du willst doch das 
Programm nicht etwa "einfach abstürzen lassen"?

Dr. Sommer schrieb:
> Felix U. schrieb:
>> Doch
> Ah, gut zu wissen dass das endlich mal gelöst ist.

Ich weiß ja nicht, von wann deine Informationen stammen, aber das war 
schon immer so (zumindest seit ich dabei bin, was glaub Kernel 1.2 oder 
so war).

> Ich würde dennoch sagen, dass "einfach Abstürzen lassen" keine
> ordentliche Herangehensweise ist.

In den seltensten Fällen kann man bei einem Speicherüberlauf noch viel 
mehr machen, denn die meisten sinnvollen Reaktionen darauf würden 
ebenfalls dynamischen Speicher brauchen.

[Dr. Sommer (Gast)]

Rolf M. schrieb:
> Dir ist nicht in den Sinn gekommen, dass es gerade darum gehen könnte,
> die Funktionsweise einer verkettete Liste zu verstehen?
Doch. Ich habe nur den Beitrag von yesitsme falsch gelesen und dachte er 
will einfach nur ein Beispiel für std::list. Insbesondere in 
Beispiel-Code darf man korrekt auf Fehler reagieren, damit man es 
richtig lernt.

Rolf M. schrieb:
> Und wo ist da jetzt die von dir für so wichtig erachtete Reaktion auf
> die Exception, wenn kein Speicher mehr da ist?
In std::list.

Rolf M. schrieb:
> Du willst doch das
> Programm nicht etwa "einfach abstürzen lassen"?
Das tut es nicht. Es kommt eine exception, std::list löscht allen 
Speicher, und das Programm beendet sich "sauber". Man könnte noch mit 
try-catch eine Fehlermeldung ausgeben.

Rolf M. schrieb:
> Ich weiß ja nicht, von wann deine Informationen stammen, aber das war
> schon immer so (zumindest seit ich dabei bin, was glaub Kernel 1.2 oder
> so war).
Also bis zu 4.4 oder so wurden offene "Listen"-Ports erst nach mehreren 
Minuten geschlossen, wenn der betroffene Prozess abgestürzt ist. Das war 
etwas lästig, wenn z.B. ein GDB-Server sich verabschiedet hat und man 
erst warten musste bevor man die nächste Debug-Session starten konnte.

Rolf M. schrieb:
> In den seltensten Fällen kann man bei einem Speicherüberlauf noch viel
> mehr machen,
Dateien schließen wäre schonmal etwas.

Es gibt übrigens auch noch mehr Exceptions als bad_alloc; wenn die 
Listenelemente nicht nur einfache Integer sind, sondern Klassen mit 
Konstruktoren welche Exceptions werfen können, muss man beim Hinzufügen 
auch reagieren (z.B. Listenelemente löschen).

[Felix U. (ubfx)]

Dr. Sommer schrieb:
> Ich würd's mal so versuchen:

Dr. Sommer schrieb:
> Das tut es nicht. Es kommt eine exception, std::list löscht allen
> Speicher, und das Programm beendet sich "sauber". Man könnte noch mit
> try-catch eine Fehlermeldung ausgeben.

Ich habe eine Beschwerde!!!! Ich habe diesen Code für ein äußerst 
wichtiges Projekt genutzt und es führte zu einem Absturz bei 
bad_alloc!!! Screenshot angehängt. Das wird mir der Kunde nicht 
verzeihen!

[Dr. Sommer (Gast)]

Felix U. schrieb:
> Ich habe diesen Code für ein äußerst
> wichtiges Projekt genutzt und es führte zu einem Absturz bei
> bad_alloc!!!
Oi. Das ist kein Absturz, sondern eine Exception. Es tritt kein 
Speicherleck auf. Unter Linux könntest du das mit valgrind bestätigen. 
Lediglich die Fehlermeldung ist nicht sehr schön.

[Felix U. (ubfx)]

Dr. Sommer schrieb:
> Felix U. schrieb:
>> Ich habe diesen Code für ein äußerst
>> wichtiges Projekt genutzt und es führte zu einem Absturz bei
>> bad_alloc!!!
> Oi. Das ist kein Absturz, sondern eine Exception. Es tritt /kein/
> Speicherleck auf. Unter Linux könntest du das mit valgrind bestätigen.
> Lediglich die Fehlermeldung ist nicht sehr schön.

Ja und zwar eine ungefangene, die dann auch direkt zum Absturz führt. 
Ergo: ob ich deinen Code oder den vom Fragesteller benutze, macht für 
bad_alloc 0 Unterschied. Ich glaube du hast ein falsches Verständnis von 
Speicherlecks, wenn der Prozess beendet wird (ob sauber oder unsauber) 
wird eh alles ge-freed.

Das mit dem listen-Socket hängt übrigens davon ab, in welchem state der 
Prozess crasht. Wenn du das socket während einer blocking Operation 
selber freigibst, passiert das gleiche.

[Peter (Gast)]

Wenn der Prozess beendet wird braucht man den Speicher nicht mehr 
freigeben. Das kann das Betriebssystem viel schneller und gründlicher.

Eine ungefangene C++-Exception würde ich übrigens auch als Absturz 
bezeichnen. Eine Access Violation (z.B. Zugriff auf Null-Pointer) ist 
auch nichts anderes als eine Exception, nur dass sie vom Prozessor 
ausgelöst wird statt per Software.

[Jens (Gast)]

Das Beispiel stammt von hier 
http://www.willemer.de/informatik/cpp/dynamic.htm

Seit ihr sicher, dass die Liste von hinten nach vorne aufgefüllt wjrd. 
Anker ist Basis und Einstieg in die Liste. Eigentlich sollten  die 
Elemente dahinter dran gehängt werden.

[Dr. Sommer (Gast)]

Felix U. schrieb:
> Ja und zwar eine ungefangene, die dann auch direkt zum Absturz führt.
Ah, du hast Recht, das hatte ich vergessen. Der try-Block ist doch 
notwendig.

Felix U. schrieb:
> Ich glaube du hast ein falsches Verständnis von
> Speicherlecks, wenn der Prozess beendet wird (ob sauber oder unsauber)
> wird eh alles ge-freed.
Ich dachte immer, Speicherlecks sind ein Problem bei Prozessen, die 
länger laufen und Dinge nicht freigeben. Den Prozess zu beenden ist ja 
nicht die einzige mögliche Reaktion auf eine Exception - manchmal möchte 
man ja irgendwie anders weiter machen.

Peter schrieb:
> Eine Access Violation (z.B. Zugriff auf Null-Pointer) ist
> auch nichts anderes als eine Exception, nur dass sie vom Prozessor
> ausgelöst wird statt per Software.
Ah, und wie fängt man die ab, was muss ich da in den catch-Block 
schreiben?

[Dr. Sommer (Gast)]

Jens schrieb:
> Eigentlich sollten  die
> Elemente dahinter dran gehängt werden.
Kommt drauf an was man als "Hinten" definiert. Du könntest dir auch 
"Anker" als Ende vorstellen, dann wird immer am "Ende" eingefügt. Diese 
Liste kann dann aber nur rückwärts iteriert werden.

[Felix U. (ubfx)]

Jens schrieb:
> Seit ihr sicher, dass die Liste von hinten nach vorne aufgefüllt wjrd.

Jap. Anker ist der Einstieg in die Liste und beinhaltet das zuletzt 
eingefügte Element. Also was zuletzt kam steht am Anfang.

Dr. Sommer schrieb:
> Ah, du hast Recht, das hatte ich vergessen. Der try-Block ist doch
> notwendig.

Also wirklich keinerlei Vorteil gegenüber dem Selbstbau-Beispiel, was 
die Allocation betrifft. Dieser ganze Kram ist übrigens der Grund, dass 
ich kein C++ benutze. Da kann man noch so viel Stoustrup gelesen haben, 
am Ende hat man was falsch im Kopf und der Kunde ist sauer.

Dr. Sommer schrieb:
> Ich dachte immer, Speicherlecks sind ein Problem bei Prozessen, die
> länger laufen und Dinge nicht freigeben.

das ist auch so. auf eine Out of Memory kannst du aber fast nicht 
geordnet reagieren. Wenn eine Allocation failed heißt das nicht nur, 
dass der RAM voll ist, sondern offensichtlich auch, dass das disk paging 
nicht mehr funktioniert. Und an dem Punkt wird eh alles den Bach 
runtergehen.

Dr. Sommer schrieb:
> Ah, und wie fängt man die ab, was muss ich da in den catch-Block
> schreiben?

Du brauchst einen structured oder einen vectored Exception Handler. Das 
ist zumindest unter Windows das Konstrukt, mit dem man CPU Exceptions 
fängt. Unter linux kriegst du afaik irgendein signal, was du auch fangen 
kannst.

[René H. (Gast)]

Dr. Sommer schrieb:
> Ah, und wie fängt man die ab, was muss ich da in den catch-Block
> schreiben?

Gar nicht. Man will das core File und behebt die Ursache (den Fehler).
Keine Sau macht sowas.

Grüsse,
René

[Dr. Sommer (Gast)]

Felix U. schrieb:
> Also wirklich keinerlei Vorteil gegenüber dem Selbstbau-Beispiel, was
> die Allocation betrifft.
Ja das ist dann richtig. Man müsste noch ein try-catch (leer) drum herum 
schreiben. Ich bin in Gedanken immer bei größeren Programmen wo man per 
Destruktor o.ä. immer allen Speicher freigeben sollte, so wie es die 
Standard Library Container tun - egal welche Exception es jetzt konkret 
ist.

Felix U. schrieb:
> Wenn eine Allocation failed heißt das nicht nur,
> dass der RAM voll ist, sondern offensichtlich auch, dass das disk paging
> nicht mehr funktioniert.
Oder ulimit o.ä. erschöpft ;-)

Felix U. schrieb:
> Du brauchst einen structured oder einen vectored Exception Handler.
Klingt nicht nach einer Standard C++ Exception, um die es hier ging...

[Yalu X. (yalu) (Moderator)]

Jens schrieb:
> Seit ihr sicher, dass die Liste von hinten nach vorne aufgefüllt wjrd.
> Anker ist Basis und Einstieg in die Liste. Eigentlich sollten  die
> Elemente dahinter dran gehängt werden.

Lass das Programm doch einfach mal laufen:

$ listtest
Zahl eingeben (0 für Ende)
111
Zahl eingeben (0 für Ende)
222
Zahl eingeben (0 für Ende)
333
Zahl eingeben (0 für Ende)
0
333
222
111

Die Zahlen werden in umgekehrter Reihenfolge ausgegeben, d.h. die
zuletzt hinzugefügten Elemente liegen – vom Anker aus gesehen – am
Anfang der Liste.

[Peter (Gast)]

Dr. Sommer schrieb:
> Felix U. schrieb:
>> Du brauchst einen structured oder einen vectored Exception Handler.
> Klingt nicht nach einer Standard C++ Exception, um die es hier ging...

Unter Windows sind C++-Exceptions mittels "Structured Exception 
Handling" implementiert. Eine ungefangene bad_alloc-Exception ist also 
genau so ein Programmabsturz wie ein Access-Violation, die 
beispielsweise in C entsteht, wenn man den Rückgabewert von malloc nicht 
prüft. Das war als Antwort auf Deinen Satz "Das ist kein Absturz, 
sondern eine Exception." gemeint.

[Rolf M. (rmagnus)]

Dr. Sommer schrieb:
> Doch. Ich habe nur den Beitrag von yesitsme falsch gelesen und dachte er
> will einfach nur ein Beispiel für std::list.

Ok.

> Rolf M. schrieb:
>> Und wo ist da jetzt die von dir für so wichtig erachtete Reaktion auf
>> die Exception, wenn kein Speicher mehr da ist?
> In std::list.

Nö.

> Rolf M. schrieb:
>> Du willst doch das
>> Programm nicht etwa "einfach abstürzen lassen"?
> Das tut es nicht. Es kommt eine exception, std::list löscht allen
> Speicher, und das Programm beendet sich "sauber".

std::list löscht gar nichts. Warum sollte sie auch? Die Exception wird 
tatsächlich geworfen, ganz genau wie bei operator new auch. Jegliche 
weitere Reaktion findet dann im Exception-Handler und in den 
Destruktoren irgendwelcher Objekte statt, und zwar gleichermaßen bei 
std::list und operator new.

> Rolf M. schrieb:
>> Ich weiß ja nicht, von wann deine Informationen stammen, aber das war
>> schon immer so (zumindest seit ich dabei bin, was glaub Kernel 1.2 oder
>> so war).
> Also bis zu 4.4 oder so wurden offene "Listen"-Ports erst nach mehreren
> Minuten geschlossen, wenn der betroffene Prozess abgestürzt ist.

Ja, listen-Ports werden für eine Zeitlang blockiert. Da ist aber noch 
ein Unterschied zu: Es bleiben "noch alle möglichen Ports und Dateien 
offen" und: Es "bleiben alle Datenstrukturen im Speicher liegen".

> Rolf M. schrieb:
>> In den seltensten Fällen kann man bei einem Speicherüberlauf noch viel
>> mehr machen,
> Dateien schließen wäre schonmal etwas.
>
> Es gibt übrigens auch noch mehr Exceptions als bad_alloc;

Ja, aber nicht bei int, um den es hier als Elementtyp ja geht.

Dr. Sommer schrieb:
> Peter schrieb:
>> Eine Access Violation (z.B. Zugriff auf Null-Pointer) ist
>> auch nichts anderes als eine Exception, nur dass sie vom Prozessor
>> ausgelöst wird statt per Software.
> Ah, und wie fängt man die ab,

Unter Linux, indem du einen Signalhandler für SIGSEV schreibst.