Deallocation von rekursiv erstellten Objekten

kater k

Hallo zusammen

Ich habe ein Programm geschrieben zum berechnen eines N-Körper Problems (2D) mit der Fast Multipole Method. Dabei wird die Quadratische Welt sukzesive in 4 glech grosse Quadrate (Box) geteilt, bis in jeder Box nur noch Nmax Partikel sind.

Das Programm funktioniert, jedoch habe ich das Problem, dass es sehr viel Speicher benötigt. Für 1e5 Iterationsschritte (die Teilung der Welt wird bei jedem Iterationsschritt neu ausgeführt => >200 Boxen pro Schritt) benötigte das Programm ca. 3GB Speicher!

Ich glaube es liegt daran dass die mit

new

erstellten Boxen nicht wieder freigegeben werden.

Der dazu relevante Code ist unten angehängt.

struct Box {
//  Members:
    bool bEmpty;            // true if leaf node
    std::complex<float> a[8];   // Multipole expansions of the Box-center
    Box *Parent;
    Box *Children[4];       // Boxes of the 4 children
    float width;            // size of box
    std::complex<float> center;
    unsigned int idx_start; // start of particles in data-vector
    unsigned int Np; // number of particles in Box

//  Constructor:
    Box(Box*,  bool , float , float* , unsigned int , unsigned int);
    ~Box();
//  Split particles in Boxes and recursively create boxes:    
    void Split(std::vector<Box*>&,std::vector<Particle> &, const int);
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Box::Split(/*....*/) {
   // ...... some code......... 
            for (int i=0;i<4;i++) {

                    // create children-box:
                    Children[i] = new Box(this->Parent,false, width*0.5, centerChild,  idx_s, NpChild[i]);

                    // split data in children-box again:
                    Children[i] -> Split(/*.....*/);
            }
    }//end Split()

Ist es notwendig dass die mit "new" erstellten Boxen wieder gelöscht werden?
Wie macht man das? die stl::vector lösche ich mit .clear(), wie macht man das für die rekursiv erstellten Objekte (Box)?

Oberon_0

Mit new erstellte Objekte werden mit delete gelöscht, bei C-Arrays muss man delete[] benutzen.
Alternativ kann man Smart-pointers einsetzen. Es gibt dazu einen Artikel im Magazin hier: http://magazin.c-plusplus.net/artikel/Schlaue%20Zeiger%20-%20Boost%20Smart%20Pointer. shared_ptr und weak_ptr sind bei neueren Compilern auch nach #include <memory> unter std::tr1:: vorhanden.
EDIT: Siehe auch http://www.cplusplus.com/doc/tutorial/dynamic/, Absatz "Operators delete and delete[]"

padreigh

http://en.wikipedia.org/wiki/Quadtree ?

kater k

padreigh, ja die Box Struktur ist ein Quadtree.

Oberon_0, dann müsste ich jedes Children mit delete löschen können. Also habe ich dies versucht:

Box::~Box(){
    for (int i=0;i<4;i++) {
        if (Children[i] != NULL) {
            Children[i]->~Box();
            delete Children[i];
        }

    }
}

Der Versuch dies für die top-level Box rootBox.~Box() aufzurufen führte zum Absturz des Programms.

kater k

Nach langem studieren der Literatur und einigem Ausprobieren habe ich die Lösung gefunden:

Box::~Box(){
    for (int i=0;i<4;i++) {
            delete Children[i];
            Children[i]=NULL;
    }
}

Dies wird für die rootBox automatisch bei beendigung der Funktion ausgeführt.