eigene Stack-Class sinnvoll

Nexus

Der Stack der Standardbibliothek ist kein richtiger Container, sondern ein Adapter. Darunter kannst du eigentliche STL-Container wie std::vector , std::list etc. benutzen.

Ich sehe keinen Grund ausser zu Lernzwecken, sich einen Stack zu basteln. Du kannst immer noch eine existierende Datenstruktur wrappen, um das Interface zu verkleinern -- oder gleich std::stack nehmen, der tut nämlich genau das.

Im Internet findest du viele Beispiele. Du wirst auch zahlreiche Leute finden, die mit äusserst klugen Argumenten wie "mein Stack ist schneller als die STL (von 1997)", "mit meinem Stack habe ich mehr Kontrolle, da ich genau weiss was passiert" oder "mein Stack hat mehr Features wie Sortieren" versuchen, sich eine Rechtfertigung für die Neuerfindung des Rads zurechtzulegen.

SeppJ

Eigene Containerklassen brauchst du in C++ sehr selten (und die wenigen, die man vielleicht noch zusätzlich haben möchte, gibt es auch längst fertig in gängigen Bibliotheken wie Boost). Es ist aber ein beliebtes Thema in Lehrbüchern. Vermutliche Gründe:
-Die Autoren haben das selber mal gemacht, als sie vor 30 Jahren programmieren gelernt haben und fertige Containerbibliotheken noch nicht verbreitet waren
-Den Autoren fällt nichts besseres ein
-Es ist ein recht vielseitiges Thema, an dem man viele wichtige Techniken lernen kann. Der Schwierigkeitsgrad kann je nach Container dabei recht variabel zwischen sehr einfach und sehr fortgeschritten gewählt werden
-Man kann das Ergebnis hinterher mit den Standardbibliothekscontainern vergleichen und so wird dem Lernenden vielleicht klarer, wie und warum die Standardcontainer aufgebebaut sind
(-Bösartige Unterstellung: Bei manchen Autoren bin ich mir auch gar nicht mal so sicher, ob sie std::stack überhaupt kennen. Man ist ja schon fast froh, wenn ein Autor std::vector und std::string kennt.)

Marthog

Es kommt immer auf den Einsatzzweck an.

std::stack stellt zwar einen Stack dar, hat aber nur sehr eingeschränkte Funktionalität. Ich selber habe z.B. schon manchmal Stacks gebraucht, aber std::stack noch nie verwendet, denn häufig brauche ich zwar die Funktionalität eines Stacks, will aber trotzdem noch Lesezugriff auf die Mitte haben und in manchen Fällen auch mehr als nur ein Element gleichzeitig löschen.

Außerdem vermisse ich bei std::stack (auch bei queue und ganz schlimm: priority_queue) eine Funktion, die ein temporäres Objekt so zurückgibt:

object = stack.pop();

Stattdessen muss man schreiben

object = std::move(stack.back());
stack.pop();

Bashar

Marthog schrieb:

Außerdem vermisse ich bei std::stack (auch bei queue und ganz schlimm: priority_queue) eine Funktion, die ein temporäres Objekt so zurückgibt:
object = stack.pop();
Stattdessen muss man schreiben
object = std::move(stack.back());
stack.pop();

Na mit Sicherheit ohne move (du solltest dich nochmal informieren, was das macht). Davon abgesehen kann eine Funktion, die das oberste Objekt löscht und zurückgibt, prinzipiell nicht exceptionsafe sein, weshalb es diese Trennung in top() (nicht back...) und pop() gibt.

Bashar schrieb:

Na mit Sicherheit ohne move (du solltest dich nochmal informieren, was das macht).

Nathan

Bashar schrieb:

Marthog schrieb:
Außerdem vermisse ich bei std::stack (auch bei queue und ganz schlimm: priority_queue) eine Funktion, die ein temporäres Objekt so zurückgibt:
object = stack.pop();
Stattdessen muss man schreiben
object = std::move(stack.back());
stack.pop();
Na mit Sicherheit ohne move (du solltest dich nochmal informieren, was das macht). Davon abgesehen kann eine Funktion, die das oberste Objekt löscht und zurückgibt, prinzipiell nicht exceptionsafe sein, weshalb es diese Trennung in top() (nicht back...) und pop() gibt.

Korrigier mich, wenn ich falsch liege, aber das Problem liegt doch darin, dass wenn bei der Kopie zwecks Wertrückgabe eine Exception fliegt, das Objekt schon unwideruflich gelöscht wurde.
Setzt man allerdings einen nothrow-Moveconstructor voraus, sollte es aber keine Probleme geben, oder?

Marthog

Das Objekt wird durch den pop-befehl gelöscht. Es kann also als temporary betrachtet werden und damit nicht unnötig kopiert wird, verwende ich hier move.
Außerdem garantiert werder pop noch top, dass keine Exception ausgelöst wird. Natürlich ist das Verschieben/kopieren des objektes eine zusätzliche Fehlerquelle, aber wieso sollte es nicht zusätzlich eine Methode geben, die das so machen kann?

Marthog schrieb:

Außerdem garantiert werder pop noch top, dass keine Exception ausgelöst wird.

Doch, sowohl pop als auch top garantieren, dass keine Exception ausgelöst werden.

Das Problem ist:

size_t s = stack.size();
try {
  object = stack.pop(); // Kopierkonstruktor wirft
} catch(...) {
  assert(stack.size() == s); // failt
}

Bashar

Marthog schrieb:

Das Objekt wird durch den pop-befehl gelöscht. Es kann also als temporary betrachtet werden und damit nicht unnötig kopiert wird, verwende ich hier move.

Das ist nicht die Funktion von move.

Außerdem garantiert werder pop noch top, dass keine Exception ausgelöst wird.

Exceptionsicher heißt ja auch nicht, dass keine Exception ausgelöst wird.

Nathan schrieb:

Setzt man allerdings einen nothrow-Moveconstructor voraus, sollte es aber keine Probleme geben, oder?

Mag sein, dann ist meine Begründung vielleicht veraltet. Aber das Design von std::stack ist ja genauso alt.

Columbo

Das Objekt wird durch den pop-befehl gelöscht. Es kann also als temporary betrachtet werden und damit nicht unnötig kopiert wird, verwende ich hier move.

pop würde aber doch keine Referenz zurückgeben, sondern eine Kopie. Da aber ein Funktionsaufruf einer Funktion die ein Objekt zurückgibt ein (p)rvalue ist, ist move dort nicht nötig - es wird automatisch gemoved.