Stackbasierte Liste



  • Ich hätte gern eine Liste, bei der alle Knoten auf dem Stack liegen und die next/prev Zeiger auf structs auf dem Stack zeigen. Wenn ich die nur temporär brauche und ich weiß, dass alle Nodes so lange gültig sind, dürfte das funktionieren. Ich hab schon sowas geschrieben, aber so wirklich gefallen tut es mir nicht. Macht es Sinn? Gibt es schon fertige Lösungen für wirklich leichtgewichtige Listen auf dem Stack?


  • Mod

    Stack Liste schrieb:

    Macht es Sinn?

    Kann es durchaus. Du musst doch bereits mindestens einen Grund gefunden haben, wofür du das brauchst.

    Gibt es schon fertige Lösungen für wirklich leichtgewichtige Listen auf dem Stack?

    Nicht beschränkt für Listen auf den Stack, aber Boosts intrusive Container überlassen dem Anwender, sich um die Elemente zu kümmern. Der Container übernimmt bloß die Organisation der logischen Struktur. Das heißt, der Anwender kann auch alles auf den Stack legen, wenn er das möchte.



  • Wenn es ausschliesslich auf dem Stack liegt, darf es nicht sehr gross sein. In diesem Fall ist aber eine Liste mit next/prev-Zeiger sehr ungünstig. Nimm ein Array, und wenn ein Element gelöscht wird, verschiebe die anderen. Normalerweise ist das schneller als eine Liste.

    Alternativ ist eine (ebenfalls durch ein normales Array) implementierte Skip-Liste.

    Für Arrays gibt es eine schöne Syntax in C++14.



  • Die intrusive container hatte ich jetzt in dem Zusammenhang nicht gefunden, schaut aber auf jeden Fall interessant aus. Danke!

    @stackswapper: die Größe dürfte kein Problem sein, da die Daten eh schon auf dem Stack liegen (und viel ist es nicht). Würden nur die paar Zeiger dazukommen, das sollte schon gehen.


Log in to reply