Eigener 'Stack' in C++
Verfasst: 22.12.2013, 15:54
Hallo,
ich versuche seit Tagen erfolglos eine eigene explizite Variante des User-Stacks zu programmieren. Grund ist, dass ich in einer rekursiven Berechnung eine weitere Baumstruktur verwende, die aber nicht unbedingt in der selben Richtung (höher oder tiefer im Baum) durchlaufen wird wie die Rekursion im Programmablauf. Außerdem verspreche ich mir davon, eine rekursive Verarbeitung unterbrechen, fortsetzen und auf mehrere Threads umverteilen zu können.
Ich brauche nicht die ganze Flexibilität des echten Stacks, aber es sollte in etwa sowas geben:
wobei die eigentlichen Objekte von StackFrame abgeleitet werden.
Nun das große Problem: Der Stack kann die Objekte nicht in einem Array StackFrame stack[] oder STL-vector oder oder oder speichern, weil die Objekte ja abgeleitet und dann verschieden groß sind. Ich kann sie auch nicht 'von Hand' in einen Speicher legen, weil ich in C++ keine Möglichkeit sehe, zur Laufzeit die echte Größe des Objektes herauszufinden.
Zwar kann man den new-Allokator überladen, und dann mit StackFrame* s=new(stack) StackFrame(); das Objekt 'pushen', aber dann gibt es keinen überladbaren delete-Operator dazu, und es fehlt die klassische 'push', 'pop' Semantik.
Andere schlugen mir vor, std::shared_ptr's in einem std::vector zu speichern, aber dann sind die echten Objekte ja auf dem Heap letztlich mit malloc reserviert, und nur die Pointer darauf effizient auf dem Stack reserviert. Das ist nicht Sinn der Sache... ich hätte gerne die echten Objekte linear im Speicher abgelegt, um sie effizient pushen und poppen zu können.
Kann man da was machen?
ich versuche seit Tagen erfolglos eine eigene explizite Variante des User-Stacks zu programmieren. Grund ist, dass ich in einer rekursiven Berechnung eine weitere Baumstruktur verwende, die aber nicht unbedingt in der selben Richtung (höher oder tiefer im Baum) durchlaufen wird wie die Rekursion im Programmablauf. Außerdem verspreche ich mir davon, eine rekursive Verarbeitung unterbrechen, fortsetzen und auf mehrere Threads umverteilen zu können.
Ich brauche nicht die ganze Flexibilität des echten Stacks, aber es sollte in etwa sowas geben:
Code: Alles auswählen
class StackFrame
{
....
}
class Stack
{
public:
void push(StackFrame& frame);
StackFrame pop();
StackFrame* peek();
}
Nun das große Problem: Der Stack kann die Objekte nicht in einem Array StackFrame stack[] oder STL-vector oder oder oder speichern, weil die Objekte ja abgeleitet und dann verschieden groß sind. Ich kann sie auch nicht 'von Hand' in einen Speicher legen, weil ich in C++ keine Möglichkeit sehe, zur Laufzeit die echte Größe des Objektes herauszufinden.
Zwar kann man den new-Allokator überladen, und dann mit StackFrame* s=new(stack) StackFrame(); das Objekt 'pushen', aber dann gibt es keinen überladbaren delete-Operator dazu, und es fehlt die klassische 'push', 'pop' Semantik.
Andere schlugen mir vor, std::shared_ptr's in einem std::vector zu speichern, aber dann sind die echten Objekte ja auf dem Heap letztlich mit malloc reserviert, und nur die Pointer darauf effizient auf dem Stack reserviert. Das ist nicht Sinn der Sache... ich hätte gerne die echten Objekte linear im Speicher abgelegt, um sie effizient pushen und poppen zu können.
Kann man da was machen?