std::stack / Wieso keine clear Methode?


  • Administrator

    Grüsse zusammen,

    Es hat mich gerade etwas überrascht, dass ich noch nie den stack aus der Standard Bibliothek verwendet habe und noch mehr überrascht hat es mich dann, als ich sah, dass std::stack keine clear Methode aufweist. Klar, man kann einfach folgenden Code schreiben:

    while(!stack.empty()) { stack.pop(); };
    

    Aber trotzdem, erscheint es mir irgendwie unlogisch, wieso ein stack kein clear aufweisen sollte. Zudem könnte ich mir vorstellen, dass der obere Code einiges langsamer sein könnte, als ein sauberes clear.

    Weiss zufällig jemand, wieso das im Standard so definiert wurde?

    Grüssli



  • Ich glaube das ist schon richtig so.
    Wozu braucht ein Stack auch eine Clear-Funktion.
    Er ist ja dafuer da, dass er gefuellt wird. 😃


  • Administrator

    Wieso braucht eine Liste eine clear Funktion, die muss ja gefüllt werden und nicht gelöscht. Die Argumentation geht nicht so ganz auf, nicht?

    Bei mir war es nun gerade der Fall, dass ich genau die Funktionalität eines Stacks brauche. Im normalfall wird Element für Element draufgeschoben und unter gewissen Umständen kann es vorkommen, dass ein Element nach dem anderen von oben wieder abgebaut wird.
    Aber irgendwann ist die Aufgabe beendet und der Stack ist bei mir dann nicht zwingend leer, muss er auch nicht sein. Wenn die Aufgabe aber wieder von vorne beginnen soll, mit dem gleichen Objekt, dann muss der Stack leer sein. Also brauche ich ein clear, welches mir garantiert, das der Stack leer ist, nach dessen aufruf.
    Gut, ich habe es halt jetzt über eine std::list gelöst, aber ein std::stack mit einer clear Funktion, wäre absolut perfekt gewesen.

    Grüssli



  • Hm... du hast recht.
    Aber warum keine Clear-Funktion eingebaut wurde kann ich mir auch nicht erklären.
    Wird schon einen Grund gehabt haben.



  • Dravere schrieb:

    while(!stack.empty()) { stack.pop(); };
    

    Das ist wirklich etwas umständlich, vor allem ist die Laufzeit in O(n). Was eigentlich mit jedem Container geht, ist folgendes:

    stack<int> s;
    // ...
    
    // clear the stack
    s = stack<int>();
    

  • Administrator

    @Christoph,
    Danke, das hatte ich vergessen. Wobei der operator = auf cplusplus.com allerdings nicht angegeben ist. Aber es funktioniert.

    Es beantwortet meine Frage allerdings immer noch nicht *g*
    Ein clear wäre doch deutlich einfacher gewesen. Wieso kein clear, das will mir einfach nicht einleuchten 😉

    Grüssli



  • naja bei einem stack geht man davon aus, das er nie auf einen schalg gelöscht werden muss (auser evtl. fehler fall). Das wäre ja nich sinn und zweck eines stacks.... wenn man ihn benutzt und seine bedeutung kennt, dann ist clear überflüssig^^


  • Administrator

    BorisDieKlinge schrieb:

    naja bei einem stack geht man davon aus, das er nie auf einen schalg gelöscht werden muss (auser evtl. fehler fall).

    Du widerlegst deinen eigenen Satz? ^^

    BorisDieKlinge schrieb:

    Das wäre ja nich sinn und zweck eines stacks.... wenn man ihn benutzt und seine bedeutung kennt, dann ist clear überflüssig^^

    Du hast gerade vorhin in Klammern eine Möglichkeit erwähnt, die bei mir durchaus auch auftreten könnte. Und wer sagt zudem, dass ein Stack so auszusehen hat? Wieso sollte man einen Stack nicht leeren können? Das macht für mich immer noch keinen Sinn.

    Und meine Frage ist immer noch nicht beantwortet. Wieso gibt es keine clear Methode im Standard? Wieso wurde dies so entschieden?

    Grüssli



  • Boris hat schon Recht. Ein Stack hat eine bestimmte Definition, ob es dir passt oder nicht. Wenn dir die Definition nicht passt, mußt du einen anderen Container-Typ wählen. Ist die Frage, ob man Stack überhauptz Container nennen darf?!

    Für Gewöhnlich wird ein Stack wie ein Bücherstapel behandelt: du legst Oben ein Buch drauf, darfst aber auch nur von Oben ein Buch wegnehmen. Du darfst z.B. nicht von der Mitte ein Buch wegnehmen. Das geht bei einem Stack auf keinen Fall!

    http://de.wikipedia.org/wiki/Last_In_–_First_Out

    Folglich ist ein clear unlogisch. Warum? Weil wie arbeitet denn ein Clear? In dem es für gewöhnlich alle Bücher auf einmal weg nimmt. Aber das widerspricht dem LIFO!!! Also hat std::stack auch kein clear. Die While-Schleife ist das einzig erlaubte.

    Wenn einem diese Definition nicht gefällt: auf einen anderen Typ umsteigen, z.B. Vector.



  • http://www.kharchi.eu/wiki/lib/exe/fetch.php?cache=cache&media=cpp:std:stack.png

    Was anderes ist beim Stack nicht erlaubt, und somit auch kein clear möglich.



  • Hi,

    std::stack ist nur ein Containeradapter!
    Das bedeutet, es ist nur eine bestimmte "Sicht" auf einen Container. Es ist selbst kein Container...

    Dravere schrieb:

    ...Wobei der operator = auf cplusplus.com allerdings nicht angegeben ist. Aber es funktioniert....

    Kuhlins/Schader: Die C++-Standardbibliothek schrieb:

    ...Zusätzlich zu den in der Klassendefinition aufgeführten Elemenfunktionen werden vo Compiler automatisch der Copy-Konstruktor, Zuweisungsoperator und Destruktor generiert...

    Eigentlich wie bei allen anderen Klassen.
    ... und folglich werden auch die Standardimplementationen der 3 verwendet. Ich vermute mal, dass der Destruktor des zugrundliegende Containers (Default: deque) ein autmatisches clear() macht und damit der Fehlerfall kein Problem darstellt.

    NACHTRAG:

    Standard, Kap23.5, Table65 schrieb:

    ... note: the destructor is applied to every element von a; all the memory is deallocated...

    Ergo: Beim Abräumen von stack (im Fehlerfall) wird der zugrundeliegende Container mit abgeräumt - ist ja auch nur begrenzt überraschend. 😉

    Gruß,

    Simon2.



  • Noch ein Beispiel:

    void foo()
    {
       int i;
       int t;
    }
    

    i und t liegen auf dem Stack. Wie werden die bei Verlassen von foo weggeräumt? Beide auf einmal? Nein, erst wird t weggeräumt und dann i. Da kannst du dich auf den Kopf stellen, die CPU wird es nicht anders machen, weil der Stack so definiert ist.


  • Administrator

    @BarnieGeroellheimer,
    Ich will ja kein Objekt dazwischen wegenehmen, ich will den ganzen Stack leeren, ALLES! Mir egal, ob er dann automatisch eines nach dem anderen von oben weg nimmt oder nicht, das ist ja scheiss egal. Der Stack muss nachher nur leer sein.
    Und jegliche Container aus der Standard Bibliothek unterstützen ein clear, also wäre das für std::stack kein Problem, noch sowas vorauszusetzen. Es könnte einfach deutlich effizienter ausgeführt werden, bzw. auch eine eindeutige Funktion dafür anbieten.

    @Simon2,
    Ein C++ Standard Buch muss ich mir noch dringend zulegen 😉
    Aber das dies geht, haben ich ja schon festgestellt und das cplusplus.com nicht vollständig ist, weiss ich auch. Wollte es dort nur erwähnt haben. Danke trotzdem für die Absicherung, dass es wirklich Standard ist. 🙂

    Im übrigen, ich habe immer noch keine Antwort erhalten ... 😃
    Wüsste jemand, wo man diese Entscheide nachschauen kann?

    Grüssli



  • Dravere schrieb:

    ...
    Im übrigen, ich habe immer noch keine Antwort erhalten ... 😃

    Hmmm, also ich denke schon, dass die Antwort schon gegeben wurde ... aber sie ist vermutlich noch nicht bei Dir angekommen (kann auch an schlechter Erklärung liegen).

    Stack ist

    • kein Container !!
    • Elementverwaltung (und dazu gehört clear()) ist Container-Aufgabe.

    Du würdest doch auch nicht fragen, wieso die Klasse "Auto" eine Methode "fahren()" hat, die Klasse "Luxusgegenstand" aber nicht (obwohl doch der "Luxusgegenstand" auch ein Auto sein kann).

    Gruß,

    Simon2.


  • Administrator

    @Simon2,
    Ich hätte kein Problem damit, dass std::stack kein clear hat, wenn man auf den interen Container zugreifen könnte und dort das clear ausführen könnte. Das ist aber nicht möglich. Also muss std::stack etwas anbieten, vor allem, wenn man es wirklich effizient lösen könnte.

    Das mit deinem Beispiel funktioniert leider nicht. Und zwar aus dem Grund, weil man ein Stack auch leeren kann, indem man der Reihe nach alle Elemente vom Stack runternimmt. Und wenn das erst noch effizient geht, über eine zusätzliche Methode, wieso sollte man diese nicht implementieren?

    Grüssli



  • Dravere schrieb:

    @BarnieGeroellheimer,
    Ich will ja kein Objekt dazwischen wegenehmen, ich will den ganzen Stack leeren, ALLES! Mir egal, ob er dann automatisch eines nach dem anderen von oben weg nimmt oder nicht, das ist ja scheiss egal. Der Stack muss nachher nur leer sein.
    Und jegliche Container aus der Standard Bibliothek unterstützen ein clear, also wäre das für std::stack kein Problem, noch sowas vorauszusetzen. Es könnte einfach deutlich effizienter ausgeführt werden, bzw. auch eine eindeutige Funktion dafür anbieten.

    Nein, man kann nicht einfach ein clear als Memberfunction anbieten. Das wäre eine Schnittstellenerweiterung. Und Schnittstellen beschreiben, was ein Typ machen kann. Und ein Stack kann nicht "clear" machen. Du solltest nochmal über den Sinn von Memberfunctions nachdenken! 😉

    Wenn du eine Komfort-Funktion suchst (was eigentlich so zu sein scheint!), dann mach sowas:

    void clear(std::stack &s)
    {
         while(!s.empty())
               s.pop();
    }
    

    und leg es in deine Toolbox, wo du von jedem Projekt drauf kommst.



  • Der Grund ist relativ einfach: std::stack kann mit jedem Container benutzt werden der ein paar Voraussetzungen erfüllt:
    http://www.cplusplus.com/reference/stl/stack/

    er muss die methoden back(), push_back() und pop_back() bereitstellen. Jeder Benutzerdefinierte Container (oder wenn wir schon dabei sind auch jeder Container aus einer Fremdbibliothek), der diese drei Methoden anbietet, kann als templateargument für std::stack benutzt werden. Wenn man std::stack jetzt noch mit einem clear() ausstatten wollte müsste man entsprechende Vorgaben an die Container machen und damit die Wiederverwendbarkeit des stack-templates einschränken.
    Wie Boris aber schon ganz richtig festgestellt hat, würde ein clear() bei einem Stack nur selten benutzt - also wäre das eine Enschränkung an die Wiederverwendbarkeit die nur in seltenen Fällen einen kleinen Performance-Vorteil bringen könnte. Kein besonders guter Deal oder?


  • Administrator

    pumuckl schrieb:

    Der Grund ist relativ einfach: std::stack kann mit jedem Container benutzt werden der ein paar Voraussetzungen erfüllt:
    http://www.cplusplus.com/reference/stl/stack/

    Soweit mir bekannt ist, unterstützt jeder Container aus der Standardbibliothek ein clear. Zu den benutzerdefinierten Container später.

    pumuckl schrieb:

    ...
    Wie Boris aber schon ganz richtig festgestellt hat, würde ein clear() bei einem Stack nur selten benutzt - also wäre das eine Enschränkung an die Wiederverwendbarkeit die nur in seltenen Fällen einen kleinen Performance-Vorteil bringen könnte. Kein besonders guter Deal oder?

    Das scheint in erster Linie so zu sein. Aber seien wir mal ehrlich, kennst du einen Container, welcher kein clear aufweist? Bzw. keine Funktion mit dieser Funktionalität? Mir ist ehrlich gesagt keiner bekannt. Es wäre auch ziemlicher Unsinn. Daher sehe ich da keinen schlechten Deal, sondern nur einen Gewinn.

    Und ich verlange ja auch kein insert oder sowas seltsames. Das ist ja auch nicht der Sinn eines Stacks. Aber ein Stack kann geleert werden, das ist eine Eigenschaft eines Stacks. Punkt. Wieso nicht effizient anbieten?

    Grüssli


  • Mod

    std::stack ist doch sowieso die mit Abstand überflüssigste Komponente der Standardbibliothek. Wozu darüber streiten?



  • BarnieGeroellheimer schrieb:

    Noch ein Beispiel:

    void foo()
    {
       int i;
       int t;
    }
    

    i und t liegen auf dem Stack. Wie werden die bei Verlassen von foo weggeräumt? Beide auf einmal? Nein, erst wird t weggeräumt und dann i. Da kannst du dich auf den Kopf stellen, die CPU wird es nicht anders machen, weil der Stack so definiert ist.

    Nein, normalerweise räumt die CPU solche Variablen alle auf einmal weg. Zum Beispiel auf x86 gibt es den Asembler-Befehl "add esp, 8", der beide ints in einem Rutsch vom Stack entfernt. Oder alternativ auch "mov esp, ebp", wenn in ebp der Stackpointer ohne i, j steht.


Log in to reply