Stack von Pointern Implementierung



  • Hey,

    ich brauche eine Datenstruktur, in der ich Pointer auf userdefinierte Objekte (keine Vererbung oder so, einfache Instanzen) ablegen kann. (Raw) Pointer, weil ich mir sonst um das Copy-Verhalten meiner Klasse Gedanken machen müsste, das aber eigentlich nicht notwendig sein dürfte.

    Stack nenne ich es, weil ich immer nur an das letzte Element ran muss, damit etwas verarbeite, evtl. neue Objekte auf den Stack packe, [..], und das eben so lang, bis der Stack leer ist.
    Ich hole in jedem Durchlauf einen Pointer vom Stack, und am Ende dieser großen while-Schleife lösche ich das Objekt einfach mittels delete.

    Zur Implementierung habe ich std::vector<MyClass*> benutzt.
    Smart Pointer nutze ich nicht, weil ich gesehen habe, dass raw pointer denen gegenüber nochmal einen gewissen Speed-Up bringen, und ich eigentlich niemals mehr als einen Pointer auf das Objekt habe, so dass ich dachte, "manuelles" Memory Management sollte noch machbar sein.

    Die etwas schwammige Frage: Ist das korrektes Design alles in allem? Ist std::vector der geeignete Container?
    Ich bin etwas stutzig geworden, weil valgrind bei einem Lauf des Programms sowohl mögliche als auch definitive Memory-Leaks ansagt, mit Verweis auf die Zeilen, wo ich neue Objekte aus dem alten vom Stack anlege.

    Ray* wRay;
    while (!rayStack.empty()) {
      wRay = rayStack.back();
      rayStack.pop_back();
    
      [..]
    
      if (langweiligeBedingung) {
        Ray* reflRay = new Ray(*wRay);
        rayStack.push_back(reflRay);
      }
    
      [..]
    
      delete wRay;
    }
    

    Die Idee war, dass eigentlich jeder Ray, der irgendwann einmal angelegt und auf den Stack gepackt wird, da auch irgendwann wieder runterkommt, und dann gelöscht wird.
    Im Copy-Konstruktor von Ray kopiere ich alle Member-Variablen. Deren Copy-Verhalten sollte auch deep copy sein.

    Also: Gute Idee, das so zu implementieren? 😕

    Vielen Dank im Voraus!

    Grüße
    brigg



  • Also so wie geschrieben, musst Du Dir doch auch um das Copy-Verhalten Gedanken machen? Was denkst Du, was in Zeile 9 geschieht?

    Für mich sieht es so aus, als wolltest Du Elemente aus dem Stack in den Vector pushen, falls bestimmte Bedingungen gegeben sind. Dafür wäre bei beiden die Stackvariante ziemlich hübsch, mit einem move. Wenn die schlecht zu kopieren sind, würde ich mir hingegen das delete sparen und dafür in den vector das Elemente pushen, ohne new aufzurufen:

    while(!theStack.empty())
    {
        element* z = theStack.back();
        theStack.pop_back();
        // Condition
        if(/*...*/)
        {
            theVector.push_back(z);
        }
        else
            delete z;
    }
    


  • Hey,

    vielen Dank für die schnelle Antwort und sorry für die irreführende Kürzung.
    Es passiert natürlich noch etwas zwischen Zeile 9 und 10, ich stecke also nicht das gleiche Objekt wieder auf den Stack, was ich vorher runtergeholt habe. Sorry!

    Du hast Recht, dass ich mir um das Copy-Verhalten Gedanken machen muss(te), aber je nachdem, was std::vector intern so tut, wird der Copy-Konstruktor dort mindestens zwei Mal (beim pushen und beim Runterholen) aufgerufen, während bei meinem Design ein Aufruf weniger kommt, oder?

    Grüße
    brigg



  • EDIT: "dort" = "wenn ich Objekte statt Pointern im vector speichere"



  • Was ist denn Ray genau? Wenn es das ist, was ich vermute (kleiner Haufen von floats), dann würde ich mir gar nicht die Mühe machen, die Dinger im Freispeicher anzulegen und mich übner Zeiger zu ärgern. Man muss ja nicht für jeden kleinen Schei* new/delete verwenden.

    Möglicherweise brauchst Du auch nicht einmal die Stack-Klasse, wenn Du deinen Ray-Tracer rekursiv implemtentierst. 😉

    kk



  • Hey,

    es ist zwar ein Raytracer, aber nicht für Computergraphik, sondern für eine wissenschaftliche Anwendung; ich brauche also alle Informationen aller Rays bis zu einem bestimmten Intensitäts-Cutoff Wert. Das ist die langweilige Bedingung. 😃

    Deshalb hat meine Ray-Klasse

    class Ray {
    
    [..]
    
    private:
      arma::cx_mat M;
      arma::vec rProp, rOrig, rNorm, rLastNorm;
      int scatNum;
      double distance;
      bool delta;
    };
    

    noch eine komplexwertige 2x2 Matrix und die vier (reelwertigen) Vektoren im R^3.

    Der Profiler meint, das Programm hätte gerade 35% der Zeit im Copy-Konstruktor von Ray() verbracht. Das bestärkt mich in der Annahme, dass Pointer speichern günstiger ist?!

    Das Problem mit all dem war auch der Memory-Leak, den valgrind gefunden hat. An dem prinzipiellen Aufbau (raw pointer in vector) kann es aber demnach nicht liegen, und ich muss noch woanders nach groben Fehlern suchen gehen?

    Grüße
    brigg



  • Hast du für jedes mit new erstellte Objekt auch ein delete aufgerufen? Man sieht das in deinem Code ja nicht.

    Wenn der copy-ctor so viel Zeit braucht, hm... Ich hätte jetzt gedacht, bei C++0x greift das Move, aber keine Ahnung. Wenn Du viele copys während der Ausführung hast, ist das über Zeiger tatsächlich zu empfehlen.

    Evtl. wäre aber tatsächlich Mal eine genauere Darstellung des Algorithmuses wichtig, wenn es dir um Geschwindigkeit geht.



  • Wenn er nicht explizit moved, wird ganz normal kopiert.



  • Dann sollte er explizit moven!


Log in to reply