Probleme mit der Speicherung von Arrays auf dem Heap



  • Hallo,
    ich probiere gerade (eigentlich seit Tagen) eine hexagonale Map redblobgames in einem zweidimensionalen Array zu speichern. Leider ist das Programm buggy und ich habe keine Ahnung woher und wieso dieses komische Verhalten kommt (eine dreieckige Map, erzeugt nach dem selben Muster funktioniert nämlich).

    #include <iostream>
    
    using namespace std;
    
    struct Point {
        const int q_, r_;
        Point(int q, int r) : q_{q}, r_{r} {}
        inline void print() {
            cout << "q:" << q_ << ", r:" << r_ << endl;
        }
    };
    
    class PointMap {
    public:
        const int RADIUS;
    
        PointMap(int radius) : RADIUS{radius} {
            points = new Point**[2 * RADIUS + 1];
            for (int q = -RADIUS; q <= RADIUS; ++q) {
                int r1 = max(-RADIUS, -q - RADIUS);
                int r2 = min(RADIUS, -q + RADIUS);
                points[RADIUS + q] = new Point*[r2 - r1 + 1];
                for (int r = r1; r <= r2; ++r) {
                    points[RADIUS + q][RADIUS + r] = new Point(q, r);
                    points[RADIUS + q][RADIUS + r]->print();
                }
            }
            cout << "*** Ready constuctor ***\n\n";
        }
    
        ~PointMap() {
            cout << "*** Delete Map ***\n\n";
            for (int q = -RADIUS; q <= RADIUS; ++q) {
                int r1 = max(-RADIUS, -q - RADIUS);
                int r2 = min(RADIUS, -q + RADIUS);
                for (int r = r1; r <= r2; ++r) {
                    delete points[RADIUS + q][RADIUS + r];
                }
                delete[] points[RADIUS + q];
            }
            delete[] points;
        }
    
        void print(int row, int col) {
            points[RADIUS + row][RADIUS + col]->print();
        }
    
    private:
        Point*** points;
    };
    
    // class PointMap {
    // public:
    //     const int DIMENSION;
    
    //     PointMap(int d) : DIMENSION{d} {
    //         points = new Point**[DIMENSION];
    //         for (int i = 0; i < DIMENSION; ++i) {
    //             points[i] = new Point*[i + 1];
    //             for (int j = 0; j < i + 1; ++j) {
    //                 points[i][j] = new Point(i, j);
    //                 points[i][j]->print();
    //             }
    //         }
    //         cout << "*** Ready constuctor ***\n\n";
    //     }
    
    //     ~PointMap() {
    //         cout << "*** Delete Map ***\n\n";
    //         for (int i = 0; i < DIMENSION; ++i) {
    //             for (int j = 0; j < i + 1; ++j) {
    //                 delete points[i][j];
    //             }
    //             delete[] points[i];
    //         }
    //         delete[] points;
    //     }
    
    //     void print(int row, int col) {
    //         points[row][col]->print();
    //     }
    
    // private:
    //     Point*** points;
    // };
    
    int main() {
        ios::iostate status;
        while (true) {
            int DIMENSION;
            cout << "Radius (STR+D = Ende):";
            cin >> DIMENSION;
            status = cin.rdstate();
            if (cin.eof()) break;
            if (status) {
                cin.clear();
                cin.get();
            }
            else {
                PointMap* map = new PointMap(DIMENSION);
                // Hexagonale Map
                for (int q = -DIMENSION; q <= DIMENSION; ++q) {
                    int r1 = max(-DIMENSION, -q - DIMENSION);
                    int r2 = min(DIMENSION, -q + DIMENSION);
                    for (int r = r1; r <= r2; ++r) map->print(q, r);
                }
    
                // Dreieck Map
                // for (int i = 0; i < DIMENSION; ++i) {
                //     for (int j = 0; j < i + 1; ++j) map->print(i, j);
                // }
                cout << "*** main function ***\n\n";
            }
        }
    }
    

    Der 'Fehler' tritt nur bei Maps mit einem Radius > 1 auf. Dann sind die Werte der ersten Point-Struktur in den Zeilen des Array unsinn (im Konstruktor werden aber die richtigen Werte gespeichert - zumindest sieht es so aus). Je größer der Radius der Map umso mehr unsinnige Werte befinden sich in der Map. Das Programm ist ausführbar und demonstriert noch viel besser was genau schief läuft.
    Da ich noch unerfahren mit C++ bin, ist in dem Code wahrscheinlich einiges im argen, aber was mich zu aller erst interessiert woher diese komischen Daten in der Map kommen.


  • Mod

    Da sind erst einmal gleich zwei ganz fundamentale Dinge falsch, die höchstwahrscheinlich zu deinem Problem führen:

    1. Programmiertechnik: new/delete in Anwendungscode ist immer falsch. Nutz std::vector oder std::array (oder andere Container) und dann ist deine ganze Speicherverwaltung mit einem Schlag automatisch korrekt.
    2. Programmlogik: Ein Array ist kein Zeiger, ein Zeiger ist kein Array. Daraus folgt, dass ein Zeiger auf einen Zeiger erst recht etwas ganz anderes ist als ein Array von Arrays. Und ein Array von Zeigern wäre noch einmal etwas ganz anderes. Die passendste Abbildung für einen zusammenhängenden Speicherbereich mit mehrdimensionalen, voll dynamischen Abmessungen ist normalerweise ein passend großer eindimensionaler Speicherbereich mit darauf gesetzter Logik zur Umrechnung der Indizes. Zum Thema 2D-Arrays gibt es hier im Forum hunderte Threads, die man auch auf mehr Dimensionen übertragen kann.

    Da dies zwei gravierende Fehlerquellen sind, die ein fast vollständiges Umschreiben deines Programms erfordern, gucke ich mir den Rest nicht genauer an.



  • @rolber sagte in Probleme mit der Speicherung von Arrays auf dem Heap:

    Das Programm ist ausführbar und demonstriert noch viel besser was genau schief läuft.

    Ja? Woher weiß ich, was "Unsinn" ist?



  • @manni66 Wenn man das Programm ausführt erhält man die korrekte Ausgabe im Konstruktor und in der main-Funktion teilweise Unsinn. Man könnte sich auch den Artikel auf redblobgames durchlesen, da wäre neben map-strorage auch noch Koordinatensysteme von Bedeutung.



  • @SeppJ Viele Dank für Dein schnelles Feedback.

    @SeppJ sagte in Probleme mit der Speicherung von Arrays auf dem Heap:

    Programmiertechnik: new/delete in Anwendungscode ist immer falsch. Nutz std::vector oder std::array (oder andere Container) und dann ist deine ganze Speicherverwaltung mit einem Schlag automatisch korrekt.

    Als Anfänger stelle ich mir als erstes die Frage was das Gegenstück zu Anwendungscode ist. Wenn ich jetzt std::array verwende, muss ich dann nicht new/delete verwenden um etwas auf dem Heap zu speichern?

    Viele Grüße


  • Mod

    @rolber sagte in Probleme mit der Speicherung von Arrays auf dem Heap:

    @SeppJ Viele Dank für Dein schnelles Feedback.

    @SeppJ sagte in Probleme mit der Speicherung von Arrays auf dem Heap:

    Programmiertechnik: new/delete in Anwendungscode ist immer falsch. Nutz std::vector oder std::array (oder andere Container) und dann ist deine ganze Speicherverwaltung mit einem Schlag automatisch korrekt.

    Als Anfänger stelle ich mir als erstes die Frage was das Gegenstück zu Anwendungscode ist. Wenn ich jetzt std::array verwende, muss ich dann nicht new/delete verwenden um etwas auf dem Heap zu speichern?

    Als Anfänger solltest du dich eher fragen, wer dir new/delete beigebracht hat, und wie du von Heaps, etc. wissen kannst, ohne je von essentiellen Dingen wie vector oder array gehört zu haben. Vielleicht solltest du die Wahl deines Lehrmaterials überdenken?

    Zu deiner Frage: Die dynamische Variante von std::array ist std::vector. Das macht genau das, was du willst. Technisch gesehen macht das irgendwo ganz tief in seinen Internas auch new/delete, aber das schöne ist halt, dass dich solche technischen Details gar nicht mehr zu interessieren brauchen. Du solltest in Datenstrukturen und Logik denken, nicht in Stacks und Heaps.



  • @SeppJ Hi, Du bist aber flott😊

    ok, kann mir die letzte Frage selbst beantworten (Der C++-Programmierer, Ulrich Breymann Kap. 9.10.2): Im Unterschied zur Klasse vector steht die Anzahl der Elemente des Arrays schon zur Compilationszeit fest und kann nicht während der Laufzeit verändert werden.

    Bleibt also nur noch ein std::vector oder das flache Array.
    Im Breymann steht irgend wo auch, dass man grosse Datenmengen als Array auf dem Heap speichern sollte. Das würde auf jeden Fall meine Dreiecks-Map betreffen (die soll irgendwann mal eine kachelbare Heighmap werden - natürlich erst wenn sie groß ist ;-).

    Da ich CPP lernen will, stelle ich mir trotzdem noch die Frage warum der Code für eine Dreiecks-Map scheinbar funktioniert, während die Hexagon-Map unter anderem diese seltsamen Sachen speichert.



  • @rolber sagte in Probleme mit der Speicherung von Arrays auf dem Heap:

    Im Breymann steht irgend wo auch, dass man grosse Datenmengen als Array auf dem Heap speichern sollte.

    Ein std::vector *ist* ein "Array" auf dem Heap (free-store).

    @rolber sagte in Probleme mit der Speicherung von Arrays auf dem Heap:

    Bleibt also nur noch ein std::vector oder das flache Array.

    Vector bitte auch "flach".



  • @rolber sagte in Probleme mit der Speicherung von Arrays auf dem Heap:

    Man könnte sich auch den Artikel auf redblobgames durchlesen

    Nein!



  • @manni66 könnte == Konjunktiv



  • @Swordfish
    wieso nicht einen std::vector<std::vector<Point>>
    Die Indizes für eine flache Hex-Map sind ein bischen blöd zu berechnen, deshalb wollte ich mit Zeilen und Spalten arbeiten.
    Viele Grüße




  • Mod

    @rolber sagte in Probleme mit der Speicherung von Arrays auf dem Heap:

    @Swordfish
    wieso nicht einen std::vector<std::vector<Point>>
    Die Indizes für eine flache Hex-Map sind ein bischen blöd zu berechnen, deshalb wollte ich mit Zeilen und Spalten arbeiten.
    Viele Grüße

    Was Swordfish sagte. Aber als Ergänzung dazu: Das ist das gleiche Phänomen, das ich ansprach, als ich davon sprach, dass ein Zeiger auf einen Zeiger erst recht kein 2D-Array wäre. Dementsprechend ist ein Vector von Vectoren halt auch kein 2D-Array und auch kein 2D-Vector, sondern halt eben nur das: Ein Vector von Vectoren. Datenstrukturmäßig so etwas wie eine Liste von Listen, aber halt nicht die schachbrettartige Struktur, die du dir wünscht.

    Man kann solch eine Liste von Listen durch etwas Feintuning zwar auch schachbrettartig ansprechen (man muss halt sicher gehen, dass alle Unterlisten immer genau gleich lang sind), aber man zahlt dafür gleich doppelt: Zum einen zahlt man durchaus Laufzeitkosten für die Dynamik, die man aber gar nicht nutzt. Und zum anderen ist das ein unnötiger Logiklayer im Programm, um die Erhaltung der Schachbrettanforderungen sicher zu stellen, der dann Fehler enthalten kann.

    Daher: Nimm einen 1D-Vector der Größe X*Y (oder wie viele Dimensionen du brauchst) und darauf dann die relativ triviale Logik, 2D-Indexzugriffe auf (x, y) in den entsprechenden 1D-Index umzurechnen (der 1D-Index zu (x,y) ist x * Y + y, wenn Y die Länge der Y-Dimension ist). Das kostet auch keine Laufzeit, denn letztlich ist das genau das, was ein statisches 2D-Array intern selber auch macht. Das findest du, wie schon erwähnt, mindestens 100-fach hier im Forum vorgemacht.



  • Oder die von @DocShoe erstellte (finale) Klasse aus Array2D: Evolution von manueller Speicherverwaltung zur STL benutzen.



  • Erst einmal Vielen Dank für Eure Hilfe.

    Schon beim formulieren meiner Frage hatte ich Bedenken ob es so richtig ist. Ich bin CPP-Anfänger, kann aber ganz gut Java, also habe ich erst einmal so programmiert wie man es in Java machen würde. So sieht dann halt auch mein Code aus. Ein Grund warum ich CPP oder C lernen will, besteht in der Pflicht, sich um den Speicher selbst zu kümmern. Garbage collection ist eine feine Sache aber die meisten Roboter (und vor allem auch Spiele) werden wohl mit C bzw. CPP programmiert. Durch die objektorientierte Programmierung mit CPP habe ich mir eingebildet es könnte mehr wie einfaches C. Ohne es bisher umgesetzt zu haben, hätte ich C für meine Anwendung verwendet liefe es ganz sicher auf ein flaches Array hinaus.

    Würde ich meine Frage nochmals formulieren, dann so: Wieso ist dieser Code falsch obwohl er offensichtlich funktioniert?
    Und dann hätte ich nur den auskommentierten Teil (die dreieckige Geschichte) gepostet.

    Viele Grüße



  • @rolber sagte in Probleme mit der Speicherung von Arrays auf dem Heap:

    Ein Grund warum ich CPP oder C lernen will, besteht in der Pflicht, sich um den Speicher selbst zu kümmern.

    Das tut man in C++ seltenst. Siehe RAII/RDID und Rule of Zero



  • @Swordfish Vielen Dank für den Link, der scheint genau das richtige für mich zu sein:-)



  • @rolber: Du hast einen Speicherreservierungsfehler im Konstruktor

    points[RADIUS + q] = new Point*[2 * RADIUS + 1]; // [r2 - r1 + 1];
    

    Dadurch, daß du immer per RADIUS + col auf den 2. Index zugreifst (in print) , paßten deine Speicherzugriffe nicht, s.a. Ideone-Code.

    Alternativ in print jeweils r1 berechnen und damit indizieren.



  • @Th69 Hallo,
    wollte es erst nicht glauben, aber Du hast absolut recht, ich habe den Spalten-Index falsch berechnet.
    So klappt es:
    points[RADIUS + q][min(RADIUS, RADIUS + q) + r] = new Point(q, r);
    Im Destruktor und print dasselbe, und die Schleifen können bleiben wie sie sind.

    Das ich eine falsche Logik eingebaut habe, ist mir richtig peinlich.

    Vielen Dank, vielen Dank das Du dir die Mühe gemacht hast.


Anmelden zum Antworten