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

XSpille

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?

icarus2

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.

Shade Of Mine

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

icarus2

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

XSpille

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 :).

Swordfish

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...

unskilled

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.

Swordfish

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

unskilled

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.