abgeleitete Objekte dynamisch in einen Vector speichern



  • Off-Topic: Ich würde empfehlen std::vector nicht für 2D/3D/4D Vektoren zu verwenden. Das ist bloss umständlich und auch vergleichsweise schrecklich langsam. Typischerweise verwendet man dafür spezielle Klassen ala Vector2D, Vector3D etc. - die dann direkt die Komponenten als Member haben. Bzw. wenn's schnell gehen muss und man keine passende Library zur Hand hat die das bereitstellt kann man dazu auch gut std::array verwenden.



  • @mawashi Was wäre denn, wenn in deinem shapes vector 3 Kreise und 4 Rechtecke wären und du dann in einer Schleife shape->radius ausgeben wolltest - das würde ja für die Rechtecke nicht funktionieren. Außerdem ist die Idee ja gerade, dass ein vector von AbstractShape das auch gar nicht zu wissen braucht, der behandelt alles wie AbstractShape.

    Warum sind deine Kreise zusammen mit anderen Formen in diesem Vector? Wir schon geschrieben, du kannst immer einen Downcast machen, aber schön ist das nicht. Wenn du eine bestimmte Funktionalität für alle Shapes einbauen willst und sich die Klassenanzahl nicht oft ändert, sind auch Visitors ein mögliches Pattern. Hier passt das aber eher nicht - du scheinst ja nur wild auf irgendeine Membervariable zugreifen zu wollen.

    Vielleicht ist es sinnvoller, eine Liste von Kreisen und eine von Rechtecken separat zu halten.

    Wenn du die Funktion "getType" oft brauchst, dann stimmt irgendwas am Design nicht. Wozu haben die Klassen diesen String? Ok, man kann sich damit leicht auf alle Objekte eines konkreten Typs filtern.

    Vielleicht kann jemand mit Ahnung von OOP mehr dazu beitragen.



  • @hustbaer : Ok. Danke für den Hinweis. Ich werde den Code noch auf arrays umstellen.
    @wob : Eine mögliche Aufgabe später in meinem Code ist es, Abstände zwischen den Formen zu berechnen um den minimalen Abstand zwischen zwei Formen einer Anordnung zu bestimmen. Ich fasse dann also alle Formen einer Anordnung (die irgendwie generiert wird) in dem Vektor shapes zusammen und iteriere über alle möglichen Paare von Formen. Diese Paare können dann in dem Beispiel also Kreis-Kreis, Kreis-Rechteck oder Rechteck-Rechteck sein. Bei den Abstandsberechnungen zwischen den Formen sind natürlich die Eigenschaften der Formen wesentlich, so dass dann genau einmal über die getType Funktion erfragt werden muss, um welche Form es sich handelt. Weiter müssen dann abhängig von der Form die individuellen beschreibenden Parameter wie rbeim Kreis oder width und height beim Rechteck benutzt werden um die tatsächlichen Abstände zu ermitteln.



  • @hustbaer : bloß wenn ich mit std::array arbeite, meine Punkte aber in einem std::vector gespeichert sind, dann habe ich doch das Problem, dass die Übergabe zur inside Funktion beispielsweise nicht funktioniert, da die Funktion ein std::array erwartet oder?
    Ich habe das nach folgendem Schema versucht:

    //...
    const bool Circle<spacedim>::inside(const std::array<double,spacedim>& x) const{
    //..
    int main(){
        const unsigned int dim=2;
        double r1 = 0.25;
        std::array<double,dim> m1{0.0,0.0};
        std::vector<std::vector<double>> points{ {-0.03,0.06}, 
                                                 { 0.5,0.45 } };
    // ..
        rve.indicator_bool( points[0] );
        rve.indicator_bool( points[0].data() );
        rve.indicator_bool( std::array<double,dim>{points[0][0],points[0][1]} );
    }
    

    was mir der Compiler mit der Fehlermeldungen quittiert. Einzig der Ausdruck in Zeile 13 funktioniert, sieht aber nicth gerade schön aus...



  • @mawashi sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

        std::vector<std::vector<double>> points{ {-0.03,0.06}, 
                                                 { 0.5,0.45 } };
    ...
        rve.indicator_bool( std::array<double,dim>{points[0][0],points[0][1]} );
    

    was mir der Compiler mit der Fehlermeldungen quittiert. Einzig der Ausdruck in Zeile 13 funktioniert, sieht aber nicth gerade schön aus...

    Ich hab den Thread jetzt nur überflogen, aber ist hier ein std::vector<std::array<double, dim>> points = ... keine praktikable Lösung? Dann sollte eigentlich auch rve.indicator_bool(points[0]) funktionieren.

    Das dürfte ohnehin performanter sein, da ein std::vector immer noch eine Indirektion über einen im Vector gespeicherten Pointer auf die eigentlichen Daten erfordert - im Gegensatz zu einem "flachen" std::array. Oder eben speziellen Vector2D/Vector3D-Klassen, welche die Koordinaten direkt als Member haben - bei dem, was ich bisher bei deinem Code sehe, macht das denke ich schon Sinn, zumal ich vermute, dass du im weiteren Code auch einiges an Vektorarithmetik machen wirst.

    Wenn sowas ordentlich implementiert ist, dann könnte man auch einige Tests eleganter formulieren, z.B. statt

    template<unsigned int spacedim>
    const bool Circle<spacedim>::inside(const std::vector<double>& x) const{
        bool inside_flag;
        inside_flag = (this->m[0]-x[0])*(this->m[0]-x[0]) 
                     +(this->m[1]-x[1])*(this->m[1]-x[1]) - this->r*this->r <0.;
        return inside_flag;
    };
    

    einfach

    template<unsigned int spacedim>
    const bool Circle<spacedim>::inside(const Vector2D& x) const {
        auto m_x = m - x;
        return dot(m_x, m_x) - r * r < 0.0; // dot = Skalarprodukt
    };
    

    oder auch

    transpose(m_x) * m_x - r * r < 0.0
    

    ... falls man Vektoren als n×1n \times 1-Matrizen auffasst und entsprechende Operatoren implementiert sind.



  • @mawashi
    Naja, wenn dann müsstest du schon durchgehend mit std::array arbeiten.
    Also

        const unsigned int dim=2;
        double r1 = 0.25;
        std::array<double,dim> m1{0.0, 0.0};
        std::vector<std::array<double,dim>> points{ {-0.03, 0.06}, 
                                                    {  0.5, 0.45} };
    // ...
    


  • @Finnegan : Ja genau, das wäre natürlich ein Traum, wenn man diese Vektor-/Matrixarithmetik so formulieren könnte wie man es händisch aufschreibt. In anderen Sprachen wie Fortran oder Python geht das ja auch recht einfach, aber meines (Anfänger-)Wissens nach müsste man diese Funktionen in C++ auch erst einmal selbst implementieren oder? Das Skalarprodukt ist zwar in der Standardbibliothek über #include <numeric> verfügbar, aber wenn ich die Dokumentation richtig verstehe, sieht der entsprechende Befehl dann wie folgt aus:

    std::inner_product(m_x.begin(),m_x.end(),m_x.begin(),0);
    

    also bei weitem nicht so elegant wie du es aufgeschrieben hast...

    @hustbaer : Ok, stimmt, dass hatte ich übersehen. Ich hatte auch versucht aus einem std::vector<double,dim> einen std::array<double,dim> zu machen, leider ohne Erfolg. Da mir an dieser Stelle Geschwindigkeit noch nicht ganz so wichtig ist, bleibe ich erst einmal beim std::vector - Konstrukt um für spätere Eventualitäten flexibler zu bleiben.



  • @mawashi sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

    @Finnegan : Ja genau, das wäre natürlich ein Traum, wenn man diese Vektor-/Matrixarithmetik so formulieren könnte wie man es händisch aufschreibt.

    Schau dir vielleicht mal eine der LinAlg-Bibliotheken an, z.B. Eigen oder blaze oder oder...

    In anderen Sprachen wie Fortran oder Python geht das ja auch recht einfach, aber meines (Anfänger-)Wissens nach müsste man diese Funktionen in C++ auch erst einmal selbst implementieren oder?

    In Python ist gibt es sowas auch nicht. Da muss man es auch selbst schreiben oder eine Bibliothek nutzen (wie z.B. numpy oder scipy.linalg). (zu Fortran kann ich nichts sagen)



  • @wob sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

    @mawashi sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

    @Finnegan : Ja genau, das wäre natürlich ein Traum, wenn man diese Vektor-/Matrixarithmetik so formulieren könnte wie man es händisch aufschreibt.

    Schau dir vielleicht mal eine der LinAlg-Bibliotheken an, z.B. Eigen oder blaze oder oder...

    Meines wissens sind die "grossen " Libs für Lineare Algebra auf riesige Matrizen dynamischer Größe ausgelegt, die vergleichbar mit einem std::vector im Speicher abgelegt sind. Für geometrische Probleme in 2D/3D braucht man aber meist nur Vektoren mit 2-4 Elementen und fast nur quadratische Matrizen in ebenfalls diesen Dimensionen. Diese Bibliotheken bringen daher für diesen Anwendungsfall wahrscheinlich eine Menge Performance-Overhead mit. Ich kann mir nicht vorstellen, dass Algorithmen, die für 1000x1000-Matrizen auf dem Heap optimiert sind, ihre Vorteile voll ausspielen können, wenn man die nur auf 4x4-Matrizen loslässt, die man mit nur einer handvoll SIMD-Operationen multiplizieren könnte.

    Ich würde eine simplere Bibliothek mit flachen Vektoren und Matrizen (wie ein std::array) empfehlen. Ich kenne da nur GLM (ich selbst verwende für sowas eine eigene Implementierung). Das ist wahrscheinlich erstmal der bessere Ansatz, falls die "grossen" Libs das nicht auch als Extra unterstützen (denke aber eher nicht).

    Eigen oder Blaze würde ich dann eventuell zusätzlich mit reinnehmen, wenn geometrische Probleme z.B. die Lösung von großen Gleichungssystemen erfordern oder die riesigen Matrizen anderweitig Sinn machen (z.B. wenn man auf einem Mesh in Adjazenzmatrix-Repräsentation arbeiten will).

    TL;DR: BLAS et al. sind gut, aber für jedes Problem das passende Werkzeug. Für die hier im Thread geschilderten Probleme eher GLM, für weitere dann eventuell BLAS und Verwandte - wenn gerechtfertigt.



  • @Finnegan Eigen behauptet zumindest, dass hinreichend kleine Vektoren / Matritzen intern einfache Arrays seien.

    When should one use fixed sizes (e.g. Matrix4f), and when should one prefer dynamic sizes (e.g. MatrixXf)? The simple answer is: use fixed sizes for very small sizes where you can, and use dynamic sizes for larger sizes or where you have to. For small sizes, especially for sizes smaller than (roughly) 16, using fixed sizes is hugely beneficial to performance, as it allows Eigen to avoid dynamic memory allocation and to unroll loops. Internally, a fixed-size Eigen matrix is just a plain array,



  • @Finnegan sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

    Meines wissens sind die "grossen " Libs für Lineare Algebra auf riesige Matrizen dynamischer Größe ausgelegt

    Natürlich, aber selbstverständlich auch für kleine!

    Beispiel Eigen http://eigen.tuxfamily.org/dox/classEigen_1_1Matrix.html#fixedsize

    Fixed-size versus dynamic-size:
    Fixed-size means that the numbers of rows and columns are known are compile-time. In this case, Eigen allocates the array of coefficients as a fixed-size array, as a class member. This makes sense for very small matrices, typically up to 4x4, sometimes up to 16x16. Larger matrices should be declared as dynamic-size even if one happens to know their size at compile-time.

    Dynamic-size means that the numbers of rows or columns are not necessarily known at compile-time. In this case they are runtime variables, and the array of coefficients is allocated dynamically on the heap.

    Beispiel Blaze: https://bitbucket.org/blaze-lib/blaze/wiki/Vector Types

    The blaze::StaticVector class template is the representation of a fixed size vector with statically allocated elements of arbitrary type.



  • @wob @Schlangenmensch Jo cool. Das war mir nicht bekannt. Schon was länger her dass ich mir diese Bibliotheken angesehen habe, und das waren auch nicht Eigen und Blaze.

    In dem Fall gibts natürlich nichts daran auszusetzen, außer dass die Bibliothek je nach Anwendung eventuell etwas Overkill ist. Wichtig ist jedenfalls, dass nicht bei jeder kleinen Matrix eine zusätzliche Pointer-Indirektion stattfindet und man nicht die Algorithmen für die fetten Matrizen auf den Kleinen laufen lässt. Das sind schon andere Optimierungen die man hier braucht.



  • Danke noch einmal für die Hinweise.
    @wob : Du hast Recht was Python angeht. Ich hatte vergessen, dass die oft verwendete numpy-Bibliothek eben eine Bibliothek ist und nicht intrinsisch mitgeliefert wird.

    Eigentlich dachte ich, dass ich mein Programm jetzt fertig habe. Leider klappt der (nun hoffentlich) letzte Schritt nicht... war ja auch nicht anders zu erwarten.
    Ich möchte nämlich ein Objekt rve vom Typ RVE<2> an eine Funktion übergeben, die dann prüft ob Punkte innerhalb oder außerhalb der in rve liegen. Diese Punkte sind nur in dieser test_function verfügbar. Mein Versuch lautet dann wie folgt:

    #include <iostream>
    
    #include <numeric>
    #include <vector>
    #include <array>
    #include <memory>
    
    #include <math.h>
    // HEADER
    template<unsigned int spacedim>
    class AbstractShape{
        public:
            std::array<double,spacedim> m;
            AbstractShape(std::array<double,spacedim> m); 
            // use virtual to make this function overloadable for every derived class/object
            // use keyword const to declare the return value not to be altered
            // use &-sign to give back a reference (avoid copying)
            // use keyword const at the end to indicate that this function cannot change a member variable of the class
            //     and makes it a compiler error if it would do so
            virtual const bool inside(const std::array<double,spacedim>& x) const = 0; 
            virtual const std::string& getType() const = 0;
            // use deconstructor to avoid problems connected to destroyed classes with pointers to the base class
            virtual ~AbstractShape() = default;
    };
    
    template<unsigned int spacedim>
    class Circle : public AbstractShape<spacedim>{
        public:
            double r;
            Circle(std::array<double,spacedim> m,double r);
            // use keyword override to tell the compiler that we excpect to override a virtual method 
            // (this is just a safety feature that throws a compiler error if we are not overriding a virtual method at that stage)
            const std::string& getType() const override;
            const bool inside(const std::array<double,spacedim>& x) const override;
    };
    
    template<unsigned int spacedim>
    class RVE{ // representative volume element with shapes
        public:
            std::vector<std::unique_ptr<AbstractShape<spacedim>>> shapes;
            void add_shape( std::unique_ptr<AbstractShape<spacedim>> shape );
            // const std::vector<unsigned int> indicator_arr( const std::array<double,spacedim>&  x ) const;
            const bool indicator_bool( const std::array<double,spacedim>&  x) const;
        private:
            
    };
    
    // DEFINITIONS
    template<unsigned int spacedim>
    AbstractShape<spacedim>::AbstractShape(std::array<double,spacedim> m){
        for(unsigned int i=0;i<spacedim;i++){
            this->m[i] = m[i];
        }
    };
    
    template<unsigned int spacedim>
    Circle<spacedim>::Circle(std::array<double,spacedim> m,double r):AbstractShape<spacedim>(m){
        this->r=r;
    };
    
    template<unsigned int spacedim>
    const std::string& Circle<spacedim>::getType() const{
        // use the keyword static to maintain this variable throughout the entire life of the objects life
        // Der wichtigere Punkt war, dass nicht jede Instanz diesen String hält, der eh immer gleich ist und nie geändert werden darf.
        static std::string s = "Circle";
        return s;
    };
    
    template<unsigned int spacedim>
    const bool Circle<spacedim>::inside(const std::array<double,spacedim>& x) const{
        bool inside_flag;
        inside_flag = (this->m[0]-x[0])*(this->m[0]-x[0]) 
                     +(this->m[1]-x[1])*(this->m[1]-x[1]) - this->r*this->r <0.;
        return inside_flag;
    };
    
    template <unsigned int spacedim>
    void RVE<spacedim>::add_shape( std::unique_ptr<AbstractShape<spacedim>> shape ){
        this->shapes.push_back( std::move(shape) );
    }
    
    template <unsigned int spacedim>
    const bool RVE<spacedim>::indicator_bool(const std::array<double, spacedim>& x) const
    {
        for (unsigned int i=0;i<this->shapes.size();i++){
            if (this->shapes[i]->inside(x)){
                return true;
            }
        }
        return false;
    };
    
    // MAIN-PROGRAMM
    template<int spacedim>
    void test_function( RVE<spacedim> rve ){
        std::cout << rve.shapes.size() << "\n";
    }
    
    int main(){
        const unsigned int dim=2;
        double r1 = 0.25;
        std::array<double,dim> m1{0.0,0.0};
        std::vector<std::vector<double>> points{ {-0.03,0.06}, 
                                                 { 0.5,0.45 } };
        RVE<dim> rve;
        rve.add_shape( std::make_unique<Circle<dim>>( std::array<double,dim>{0.0,0.0} ,r1) );
        rve.add_shape( std::make_unique<Circle<dim>>( std::array<double,dim>{0.1,0.1} ,r1) );
        test_function( rve );
    };
    

    Zeile 108 macht hier Probleme, wobei ich denke, dass das Problem in der ursprünglichen Funktionsdefinition liegt. Habt ihr Vorschläge?



  • Verwende unsigned int spacedim als Template-Parameter.
    Außerdem verwende const RVE<spacedim> &rve als Parameter der Funktion (damit keine Kopie erforderlich ist).



  • @ Th69 : danke! das mit dem unsigned int spacedim war ein unnötiger Fehler😩 Aber warum zur Hölle wird das & benötigt? Das ein Programm bei Übergabe von lediglich der Referenz und nicht einer Kopie effizienter läuft leuchtet mir ein. Aber warum ist es hier an dieser Stelle notwendig?



  • @mawashi sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

    @ Th69 : danke! das mit dem unsigned int spacedim war ein unnötiger Fehler😩 Aber warum zur Hölle wird das & benötigt? Das ein Programm bei Übergabe von lediglich der Referenz und nicht einer Kopie effizienter läuft leuchtet mir ein. Aber warum ist es hier an dieser Stelle notwendig?

    Streng "notwendig" ist es nicht, aber RVE hat doch den Member std::vector<std::unique_ptr<AbstractShape<spacedim>>> shapes. Der wird bei einer By Value-Übergabe komplett mitkopiert: n mal Speicher reservieren für die std::unique_ptr, dann für jedes AbstractShape je einmal Speicher reservieren für die Objekte, plus Objekte konstruieren... und am Ende alles nochmal rückwärts - n Destruktoren aufrufen, n mal Speicher freigeben und schliesslich den Speicher für die std::unique_ptr freigeben. Das würde ich aus dem Bauch schon als schwergewichtig genug einschätzen, um eine Referenz zu rechtfertigen 😉

    Bei den std::array<double, spacedim>-Parametern hast du schliesslich auch eine Referenz verwendet... und da wäre es nicht unbedingt nötig, die paar doubles machen da keinen Unterschied. Die werden je nach Compiler-Optimierungen wahrscheinlich sogar alle in einem (SIMD-) Register an die Funktion übergeben.

    Natürlich kann man argumentieren, dass es "nur ne blöde Testfunktion" ist, aber es ist vielleicht nicht verkehrt, wenn man weiss, welches "Gewicht" die verschiedenen Typen haben und man bei Objekten einer gewissen Größe intuitiv zur Referenz greift.



  • @Finnegan sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

    Der wird bei einer By Value-Übergabe komplett mitkopiert: n mal Speicher reservieren für die std::unique_ptr (...) Das würde ich aus dem Bauch schon als schwergewichtig genug einschätzen, um eine Referenz zu rechtfertigen

    Ich würde es vor allem deshalb als notwendig einschätzen, weil unique_ptr NICHT kopierbar sind. Ein unique_ptr hat schlicht keinen copy-Konstruktor. Dazu brauche ich keinen Bauch 😉



  • Danke für die Erklärung. Das bringt mir noch einmal einiges an Verständnis.
    Tatsächlich ist das & nötig, da der Code sonst nicht kompiliert.

    Ansonsten danke noch an Alle. Vorerst läuft mein Program, hauptsächlich getrieben durch eure Hilfe. Ohne euch hätte ich die Kniffe so wohl nicht herausgefunden.👍🏻



  • @wob sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

    Ich würde es vor allem deshalb als notwendig einschätzen, weil unique_ptr NICHT kopierbar sind. Ein unique_ptr hat schlicht keinen copy-Konstruktor. Dazu brauche ich keinen Bauch 😉

    Hah! Stimmt ja 😁 ... ist aber vielleicht angebracht irgendwann mal Kopieroperationen für RVE zu implementieren, je nachdem wie man die Klasse verwenden will. "Geometrie kopieren" kann ja durchaus nützlich sein. Und dann kann man sich wieder an meine Argumentation erinnern 😉 .



  • @Finnegan sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

    Hah! Stimmt ja ... ist aber vielleicht angebracht irgendwann mal Kopieroperationen für RVE zu implementieren, je nachdem wie man die Klasse verwenden will. "Geometrie kopieren" kann ja durchaus nützlich sein.

    Stimmt, aber ob das immer tiefe Kopien sein müssen? Gerade wenn man viele Objekte hat, kann das schnell zu viel Speicherbedarf führen. Es kann durchaus eine gute Idee sein, die Objekte unveränderbar zu machen und bei Änderungen einfach neue Objekte zu erzeugen. Dann wird das Kopieren eine einefache Operation, weil man nur noch die Referenz / den Pointer kopieren muss.

    Aber hängt sicher vom Problem und der Datenmenge ab.


Anmelden zum Antworten