Implementierung eines Stack als Struktur (Problem: Methoden innerhalb der Struktur)



  • Hallo zusammen,

    ich schätze ich habe hier ein Verständnisproblem, wäre cewl wenn mir einer auf die Sprünge helfen kann. Ich würde gerne alle Methoden, die im Zusammenhang mit der Struktur "Stack" verwendet werden, auch im Stack deklarieren.

    Probleme bereitet mir hier die Methode/Funktion "create_stack()". Wie man unter main() sehen kann, erstelle ich einen Pointer, der über die Methode create_stack() initialisiert werden soll. Das bereitet natürlich Probleme, wenn ich die Adresse benötige um überhaupt auf die Methode zugreifen zu können...

    Ich hab die interessanten Zeilen mal markiert.

    So wie ich das sehe, müsste ich das "new Stack" aus der stack.cpp schon in der "main()" anwenden und dann als zusätzlichen Parameter an "create_stack()" übergeben?

    stack.h

    #ifndef _stack_h_
    #define _stack_h_
    
    struct Stack {
    	private:
    	unsigned int 	depth;	// Tiefe des Stacks
    	char  		*content;	// Inhalt des Stacks
    	unsigned int 	top;		// Index des obersten  
    						// freien Elements
    	public:
    	[b]Stack* create_stack(unsigned int);[/b]
    	void push(Stack *, char);
    	char pop(Stack *);
    	int isEmpty(Stack *);
    	void destroy_stack(Stack *);
    } ;
    
    #endif
    

    main.cpp

    #include <iostream>
    using namespace std;
    
    #include "stack.h"
    
    int main()
    { 				
    // Test der Datenstruktur STACK
    
    [b]   Stack *s;
       s=s->create_stack(3);[/b]
       s->push(s,'a');
    
        . . . usw.
    }
    

    stack.cpp

    #include "stack.h"
    #include <iostream>
    using namespace std;
    
    Stack* Stack::create_stack (unsigned int size){
    	Stack * s = new Stack;
    	s->depth=size-1;
    	s->content=new char [size];
    	s->top=0;
    	return s;
    }
    ... usw.
    


  • So:

    #ifndef _stack_h_
    #define _stack_h_
    
    struct Stack {
        private:
        unsigned int     depth;    // Tiefe des Stacks
        char          *content;    // Inhalt des Stacks
        unsigned int     top;        // Index des obersten  
                            // freien Elements
        public:
        static Stack* create_stack(unsigned int);
        void push(Stack *, char);
        char pop(Stack *);
        int isEmpty(Stack *);
        void destroy_stack(Stack *);
    } ;
    
    #endif
    


  • Oh man... da zerbrech ich mir 1h den Kopf 😃 . Dank dir!



  • Da würde ich an deiner Stelle aber noch ein paar Sachen ändern:

    • Das zugehörige Stack-Objekt hast du bei nicht-statischen member-Funktionen, eh schon als this verfügbar. (Ansonsten wäre wohl auch eine Referenz sinnvoller).
    • unique_ptr für RAII
    • const isEmpty-Funktion
    • destroy_stack ist sehr wahrscheinlich nicht sinnvoll, dafür gibt es einen Destruktor
    #ifndef _stack_h_
    #define _stack_h_
    
    struct Stack {
        private:
        unsigned int     depth;    // Tiefe des Stacks
        char          *content;    // Inhalt des Stacks
        unsigned int     top;        // Index des obersten  
                            // freien Elements
        public:
        static std::unique_ptr<Stack> create_stack(unsigned int);
        void push(char);
        char pop();
        int isEmpty() const;
        ~Stack();
    } ;
    
    #endif
    

    Zudem solltest du dir Gedanken machen, ob ein Template nicht sinnvoller wäre, da du sonst für jeden Datentyp neu implementieren musst.

    btw: Dein create_stack klingt eigentlich auch nach einem normalen Konstruktor

    Stack(unsigned int);
    

    Gruß,
    XSpille



  • Wenn Speicherplatz nicht das wichtigste Kriterium ist (das ist ausser im Embedded-Bereich wohl kaum der Fall), dann ist eine Implementierung mit Arrays wesentlich effizienter.



  • icarus2 schrieb:

    Wenn Speicherplatz nicht das wichtigste Kriterium ist (das ist ausser im Embedded-Bereich wohl kaum der Fall), dann ist eine Implementierung mit Arrays wesentlich effizienter.

    Wieso wesentlich effizienter?
    Wenn du

    char* content;
    

    durch

    char[Size] content;
    

    ersetzt, wobei Size ein Template-Parameter ist, dann hast du auf das Element gerade mal eine Indirektion pro Zugriff weniger.
    Dafür kannst du die Größe on demand nicht ändern.

    Oder wie meintest du das?
    Also nen Array wäre meiner Meinung nach ein Entscheidung in die falsche Richtung.

    Außerdem: Wieso sollte ein Array mehr Speicherplatz benötigen? Also auf es benötigt dann Platz auf dem Stack, statt des Heaps, wenn man das Objekt auf dem Stack anlegt... Meintest du den Stack-Speicherplatz?



  • 1. Weshalb Array-Implementierungen schneller sind:
    Arrayzugriff (wie man ihn bei einer Stack Implementierung braucht) ist grundsaetzlich schneller als Listenzugriff, da Array Werte dicht im Speicher liegen. Dadurch hat man viel bessere Speicherlokalitaet, wodurch der Cache sehr gut genutzt werden kann.
    Bei Listen hast du beinahe Random Access, wodurch Cache Heuristiken ueber den Haufen geworfen werden.
    Das ist auch der Grund, warum std::vector in fast allen Faellen schneller ist als std::list.

    2. Weshalb Array-Implementierung (etwas) mehr Speicher brauchen:
    Im Prinzip braucht man dynamische Arrays, da der Stack wachsen und schrumpfen kann. Dies macht man meistens so, dass amortisiert jede Einfuege- und Loeschoperation konstante Laufzeit hat. Dies erreicht man indem man die Arraygroessen z.B. beim vergroessern immer verdoppelt und beim verkleinern immer viertelt. Bei der genannten Implementierung kann also der Fall auftreten, dass du vier Mal mehr Speicher brauchst als notwendig.

    PS:
    Ich hoffe, dass ich das nicht zu "technisch" geschrieben habe und dass es einigermassen verstaendlich ist.



  • icarus2 schrieb:

    1. Weshalb Array-Implementierungen schneller sind:
    Arrayzugriff (wie man ihn bei einer Stack Implementierung braucht) ist grundsaetzlich schneller als Listenzugriff, da Array Werte dicht im Speicher liegen. Dadurch hat man viel bessere Speicherlokalitaet, wodurch der Cache sehr gut genutzt werden kann.
    Bei Listen hast du beinahe Random Access, wodurch Cache Heuristiken ueber den Haufen geworfen werden.
    Das ist auch der Grund, warum std::vector in fast allen Faellen schneller ist als std::list.

    Niemand hier will einen stack als linked list implementieren.
    Schau dir den Code vom OP an:
    char *content; // Inhalt des Stacks



  • Shade Of Mine schrieb:

    icarus2 schrieb:

    1. Weshalb Array-Implementierungen schneller sind:
    Arrayzugriff (wie man ihn bei einer Stack Implementierung braucht) ist grundsaetzlich schneller als Listenzugriff, da Array Werte dicht im Speicher liegen. Dadurch hat man viel bessere Speicherlokalitaet, wodurch der Cache sehr gut genutzt werden kann.
    Bei Listen hast du beinahe Random Access, wodurch Cache Heuristiken ueber den Haufen geworfen werden.
    Das ist auch der Grund, warum std::vector in fast allen Faellen schneller ist als std::list.

    Niemand hier will einen stack als linked list implementieren.
    Schau dir den Code vom OP an:
    char *content; // Inhalt des Stacks

    Well this is embarrassing... Bier und im Forum schreiben endet fuer mich irgendwie jedes Mal in einem Desaster 🙄



  • icarus2 schrieb:

    1. Weshalb Array-Implementierungen schneller sind:
    Arrayzugriff (wie man ihn bei einer Stack Implementierung braucht) ist grundsaetzlich schneller als Listenzugriff, da Array Werte dicht im Speicher liegen. Dadurch hat man viel bessere Speicherlokalitaet, wodurch der Cache sehr gut genutzt werden kann.
    Bei Listen hast du beinahe Random Access, wodurch Cache Heuristiken ueber den Haufen geworfen werden.
    Das ist auch der Grund, warum std::vector in fast allen Faellen schneller ist als std::list.

    Generell gebe ich dir bezüglich den Vorteilen für Caching von Speicherbblöcken recht, aber er fordert einen Speicherblock per new[] an (ich würde hier malloc wegen einem möglichen realloc bevorzugen)

    s->content=new char [size];
    

    Also hat er die gleiche Lokalität, wie bei einem Array und somit bezüglich Caching keine Nachteile.

    icarus2 schrieb:

    2. Weshalb Array-Implementierung (etwas) mehr Speicher brauchen:
    Im Prinzip braucht man dynamische Arrays, da der Stack wachsen und schrumpfen kann. Dies macht man meistens so, dass amortisiert jede Einfuege- und Loeschoperation konstante Laufzeit hat. Dies erreicht man indem man die Arraygroessen z.B. beim vergroessern immer verdoppelt und beim verkleinern immer viertelt. Bei der genannten Implementierung kann also der Fall auftreten, dass du vier Mal mehr Speicher brauchst als notwendig.

    Wieso 4mal? Doppelt so viel, kann ich nachvollziehen...
    Wenn du es als Verkettung von Elementen machen würdest, dann bräuchtest du pro Eintrag zusätzlich einen Zeiger auf das vorherige Stack-Element und somit erst frühestens eine Ersparnis - Annahme 2mal - falls die Objektgröße größer ist als ein Zeiger, was bei einem char wohl definitiv nicht der Fall sein sollte 😉

    EDIT: Hatte die letzten beiden Beiträge erst danach gesehen



  • Oha... da hab ich ja was losgetreten.

    Um ein bisschen Licht in die Sache zu bringen. Es handelt sich hier um eine Übungsaufgabe (Einstieg OOP). Die Prototypen und Stack-Variablen waren gegeben und durften nicht abgeändert werden.

    Kann also gut sein, dass es bessere Wege gibt einen Stack abzubilden :).



  • create_stack() ist auch vorgegeben? Wirf den Dozenten weg.



  • Swordfish schrieb:

    create_stack() ist auch vorgegeben? Wirf den Dozenten weg.

    Da Du weder die Aufgabe noch den Dozenten kennst ist das unangemessen.

    Die Aufgabe riecht für mich mehr nach C, denn nach C++ und dann ergeben auch die Prototypen Sinn.
    Vielleicht will der Dozent einen C Stack aus struct und freien Funktionen im Laufe der Vorlesung in eine C++ Klasse ändern...



  • Furble Wurble schrieb:

    Swordfish schrieb:

    create_stack() ist auch vorgegeben? Wirf den Dozenten weg.

    Da Du weder die Aufgabe noch den Dozenten kennst ist das unangemessen.

    Die Aufgabe riecht für mich mehr nach C, denn nach C++ und dann ergeben auch die Prototypen Sinn.
    Vielleicht will der Dozent einen C Stack aus struct und freien Funktionen im Laufe der Vorlesung in eine C++ Klasse ändern...

    definitiv ist es C. schlechtes.



  • Furble Wurble schrieb:

    Die Aufgabe riecht für mich mehr nach C, [...]

    unskilled schrieb:

    definitiv ist es C. schlechtes.

    JonnyJohn schrieb:

    struct Stack {
    	private:
    /* ... */
    	public:
    /* ... */
    };
    

    Ja ne, is klar. 🙄

    // tagsoup



  • ja, die einzigen beiden anhaltspunkte, dass der dozent doch versucht, es c++ zu nennen. ändert nichts daran, dass es grottenschlecht ist und nichts mit C++ zu tun hat.



  • Die Aufgabe ist aus einer Einführungsveranstaltung in OOP.
    Wenn der Dozent beschließt das Einführungsbeispiel in der C "Untermenge" von C++ implementieren zu lassen ist das doch sein gutes Recht.

    @JonnyJohn:
    Wenn die Aufgabe ist "Implementieren Sie eine Stack-Datenstruktur. Benutzen Sie die gegebenen Prototypen und die Stack Struktur." (o.ä. 🙂 )

    struct Stack {
      unsigned int  depth;     // Tiefe des Stacks
      char*         content;   // Inhalt des Stacks
      unsigned int  top;       // Index des obersten  
                               // freien Elements
    };
    
    Stack* create_stack(unsigned int);
    void push(Stack *, char);
    char pop(Stack *);
    int isEmpty(Stack *);
    void destroy_stack(Stack *);
    

    Dann solltest Du das IMHO einfach machen.
    Wenn Du darüberhinaus beschließt der Veranstaltung vorzugreifen und eine Klasse Stack mit öffentlicher Schnittstelle, Kapselung, Schnickschnack zu erstellen, dann mach Dir auch die Mühe, die Schnittstelle sauber zu gestalten.
    Ich bin mir sicher, dass alle hier gerne evtl. auftretende Fragen beantworten.


Log in to reply