dynamisches, zweidimensionales Array

[Glocke]

Hi,

bisher habe ich mit std::map gearbeitet, um eine zweidimensionale Map darzustellen. Da ich jedoch ausschließlich unsigned integers für beide Schlüssel verwende, liegt die Benutzung eines "klassischen" Arrays nahe. Allerdings möchte ich mich nicht unbedingt bezüglich der Grid-Größe festlegen.

Gibt es eine fertige Template-basierte Implementierung für ein zweidimensionales Array? (Template-Parameter für den eigentlichen Inhalt einer Zelle). Oder darf/muss/sollte/kann ich mir selber eine Implementierung im Stile

Code: Alles auswählen

template <typename T>
class Grid2i {
    private:
        T** cells;
        int w, h;
    public:
        T get(int x, int y);
        void set(int x, int y, T data);
        void clear();
        // usw.
}

bauen? D.h. mit malloc, realloc und free arbeiten - und die Daten effektiv mittels T** cell verwalten (w und h als Breite/Höhe des Grids). Das wäre prinzipiell kein Problem - allerdings schreit das ganze irgendwie nach "das hat schon jemand gelöst, erfinde das Rad nicht neu!"

LG Glocke

[Xin]

Mir würde spontan etwas wie std::vector< std::vector< T > > in den Kopf kommen.
Davon kann man ja ableiten und ggfs. Zugriffsfunktionen überschreiben.
Wenn Du die Größen vorher fix weißt, würde ich das flott selbst implementieren.

[Glocke]

Mir würde spontan etwas wie std::vector< std::vector< T > > in den Kopf kommen.
Davon kann man ja ableiten und ggfs. Zugriffsfunktionen überschreiben.
Wenn Du die Größen vorher fix weißt, würde ich das flott selbst implementieren.

Afaik arbeitet std::vector mit graphentheoretischen Knoten. Imho müsste eine Implementierung - die direkt mit einem auf T** basierenden Array arbeitet - schneller sein. Dafür ist der Knoten-Ansatz universeller, d.h. nicht nur für ganzzahlige Schlüssel (weil ja Schlüssel bei traditionellen Arrays ganzzahlig und vorzeichenlos sein sollten).

[Xin]

Mir würde spontan etwas wie std::vector< std::vector< T > > in den Kopf kommen.
Davon kann man ja ableiten und ggfs. Zugriffsfunktionen überschreiben.
Wenn Du die Größen vorher fix weißt, würde ich das flott selbst implementieren.

Afaik arbeitet std::vector mit graphentheoretischen Knoten. Imho müsste eine Implementierung - die direkt mit einem auf T** basierenden Array arbeitet - schneller sein.

Der T** Ansatz ist immer der schnellste - schneller geht nicht, weil er quasi ohne Organisation auskommt.

Dafür muss man ihn selbst schreiben. std::vector ist eine Organisationsstruktur. In dem Moment legst Du die Frage, wie schnell vector ist in die Hände des Entwicklers. vector löst nur Dein Problem ein eindimensionales Array zu realisieren. Und soweit ich weiß, macht Vector da auch keine große Anstrengungen für.

Dafür ist der Knoten-Ansatz universeller, d.h. nicht nur für ganzzahlige Schlüssel (weil ja Schlüssel bei traditionellen Arrays ganzzahlig und vorzeichenlos sein sollten).

Du sprichst von der Map, hm?

[Glocke]

Der T** Ansatz ist immer der schnellste - schneller geht nicht, weil er quasi ohne Organisation auskommt.

Meine Frage ist eben, ob es da etwas vorgefertigtes mit Typparameter T gibt - oder ob ich das wirklich selber bauen müsste. Prinzipiell sollte das ja nichts exotisches sein, daher müsste ich das Rad ja nicht unbedingt neu erfinden - oder?

In dem Moment legst Du die Frage, wie schnell vector ist in die Hände des Entwicklers. vector löst nur Dein Problem ein eindimensionales Array zu realisieren.

Mein "Problem" ist, dass das Vector-Template für alle Typen funktioniert. Das - und die Tatsache, dass myVector.begin() einen Iterator liefert - legt nahe, dass es intern nicht mit T** arbeitet. Aber genau so etwas suche ich. Für mein Spielprojekt will ich die Grid-Implementierung von std::map auf genau so etwas modifizieren. Das Grid ist sehr sehr essentiell für mein Projekt - daher möchte ich da eine möglichst performante Lösung.

Du sprichst von der Map, hm?

Ich rede von so etwas wie

Code: Alles auswählen

float feld[5];

Da sind die Indizes immer vorzeichenlose Ganzzahlen.

[Glocke]

Ich hab' mal ne einfache Implementierung gebaut (

array2d.cpp

) die einmal ein 1D- und einmal ein 2D-Array (mit Typparameter) bereitstellt. Habt ihr eine Idee für mich was ich noch verbessern könnte oder wo eine mögliche Fehlerquelle liegt? Rein vom groben Testen her scheint sie erstmal nicht grob falsch zu sein

[Yoghurt]

Hallo Glocke,

habe nur kurz drübergeschaut und bin auch kein C++-Experte, aber warum verwendest du malloc und std::free anstatt new T[] und delete[]?

Ich denke, wenn man C++ programmiert, sollte man eher die C++ Funktionen/Libs nutzen und nicht die von C. => #include <cstdlib>

Vom Design her hätte ich versucht in der Array2D Klasse die Array1D Klasse zu verwenden, um Redundanzen zu vermeiden. Und logisch betrachtet, ist das Array2D<T> ja quasi ein Array1D<Array1D<T>>, oder?

[Xin]

habe nur kurz drübergeschaut und bin auch kein C++-Experte, aber warum verwendest du malloc und std::free anstatt new T[] und delete[]?

Ich hätte auch new und delete[] benutzt, aber faktisch ist das das gleiche. Der einzige Unterschied ist, dass die Programmiersprache Dir das Casting abnimmt.

Ich denke, wenn man C++ programmiert, sollte man eher die C++ Funktionen/Libs nutzen und nicht die von C. => #include <cstdlib>

Hätte er C benutzt, so hätte er #include <stdio.h> geschrieben. Die cstdlib gehört zu Standard-C++.

Vom Design her hätte ich versucht in der Array2D Klasse die Array1D Klasse zu verwenden, um Redundanzen zu vermeiden. Und logisch betrachtet, ist das Array2D<T> ja quasi ein Array1D<Array1D<T>>, oder?

Man hätte auch gleich std::vector< std::vector< T > > als Member nehmen können. ^^

Programmierung ist Handwerk. Es gibt nie nur eine richtige Lösung.
Man darf zum Beispiel gerne mal antesten, ob ich
t * values;
nicht reicht, wenn man get(x,y) so implementiert, dass man auf values[ y * width + x ] zugreift. Das könnte bei modernen CPUs schneller sein, als zweimal zu dereferenzieren.

[Yoghurt]

Ich hätte auch new und delete[] benutzt, aber faktisch ist das das gleiche. Der einzige Unterschied ist, dass die Programmiersprache Dir das Casting abnimmt.

Ich würde halt schauen, dass ich in meinem Code immer einheitlich bleibe, außer es gibt einen Grund vom "Standard" abzuweichen.

Hätte er C benutzt, so hätte er #include <stdio.h> geschrieben. Die cstdlib gehört zu Standard-C++.

Ja schon, ich habe eigentlich das gleiche gemeint wie im vorherigen Punkt. Warum soll ich eine C-Funktion verwenden in C++, wenn es dafür eine geeignetere (in meinen Augen, da typsicherere) C++ Funktion gibt?

Man hätte auch gleich std::vector< std::vector< T > > als Member nehmen können. ^^

Soweit ich das verstanden habe, will Glocke einen lightweight Wrapper um ein Array, das ihm etwas Verwaltungsaufwand abnimmt.
In meinen Augen spricht jedoch nichts dagegen in einer lightweight Array2D Klasse eine lightweight Array1D Klasse zu verwenden.

Programmierung ist Handwerk. Es gibt nie nur eine richtige Lösung.

Ich wollte auch gar nicht sagen, dass meine Vorschläge besser sind, Glockes Variante ist sehr wahrscheinlich performanter. Sollte nur ein Gedankenanstoß sein.

Man darf zum Beispiel gerne mal antesten, ob ich
t * values;
nicht reicht, wenn man get(x,y) so implementiert, dass man auf values[ y * width + x ] zugreift. Das könnte bei modernen CPUs schneller sein, als zweimal zu dereferenzieren.

Die Lösung find ich persönlich fast noch besser, vorallem weil man für die Verwaltung sowieso einen Wrapper drumrum hat. Und im Prinzip ist ein int[x][y] auch nichts anderes als ein int[x*y].

Außerdem könnte man dann vermutlich leichter die Array2D von der Array1D Klasse ableiten bzw. ein gemeinsames Interface schaffen, wenn man denn sowas machen will.

[Glocke]

Ich hätte auch new und delete[] benutzt, aber faktisch ist das das gleiche. Der einzige Unterschied ist, dass die Programmiersprache Dir das Casting abnimmt.

Bis auf das Abnehmen des Castings konnte ich auch keinen Unterschied herausfinden. Und da die Pointer komplett intern bleiben, laufe ich nicht Gefahr, dass irgendwer (der das Array verwendet) versucht die Pointer mit delete zu löschen.

Man darf zum Beispiel gerne mal antesten, ob ich
t * values;
nicht reicht, wenn man get(x,y) so implementiert, dass man auf values[ y * width + x ] zugreift. Das könnte bei modernen CPUs schneller sein, als zweimal zu dereferenzieren.

Außerdem könnte man dann vermutlich leichter die Array2D von der Array1D Klasse ableiten bzw. ein gemeinsames Interface schaffen, wenn man denn sowas machen will.

Der Ansatz mit T* würde afaik zusätzlichen Organisationsaufwand bedeuten. Hauptsächlich müsste ich beim resize die Daten (bzw. die Pointer darauf) "verschieben", um die Daten dann (wie du geschrieben hast) zu erreichen. Wenn ich allerdings selten resize, sollte der Ansatz etwas bringen

Soweit ich das verstanden habe, will Glocke einen lightweight Wrapper um ein Array, das ihm etwas Verwaltungsaufwand abnimmt.
In meinen Augen spricht jedoch nichts dagegen in einer lightweight Array2D Klasse eine lightweight Array1D Klasse zu verwenden.

Prinzipiell erzeugt das ja erstmal (wenn auch relativ minimalen) Overhead. Wenn ich die Methoden inline sollte der Overhead aber wieder sinken ... spannend...

"Allerdings" ist die 1D-Implementierung nur aus Gründen des "Herleitens" (der 2D-Implementierung) drinne. Effektiv brauche ich nur die 2D-Implementierung. Habt ihr noch Ideen wie ich sie noch leichtfüßiger machen könnte, ohne auf die Kapselung zur Klasse zu verzichten?